跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年8月実施 専門科目I 問題2

Author​

kainoj

Description​

We consider a 32-bit machine with 32KB physical memory, upon which the operating system supports the paging functionality. The page size is 4KB, the virtual memory size is 4GB, and there is no cache memory. Answer the following questions. Note that 1KB is equivalent to 1024 bytes.

(1) Explain each of the following terms regarding the paging functionality, briefly:

  • Page
  • Page Table
  • Page Replacement
  • Page Fault
  • Translation Look-aside Buffer (TLB)

(2) Obtain the physical address in hexadecimal corresponding to the virtual address of 2A0F (hexadecimal) when the following page table is given.

Page number (decimal)Frame number (binary)Valid bit
01111
10000
21101
30000
41011
50000
60000
70000
80000
90011
101001
110001
120111
130000
140000
150101

(3) Obtain the number of page faults caused by executing each of the following two pieces of program code written in C language.

Program Code 1:
​

for (j = 0; j < 1024; j++)
    for (i = 0; i < 1024; i++)
        sum += A[i * 1024 + j];

Program Code 2:
​

for (i = 0; i < 1024; i++)
    for (j = 0; j < 1024; j++)
        sum += A[i * 1024 + j];

Note that each program code is executed under the following assumptions.

  • i, j, and sum are 32-bit integer variables. A is a 32-bit integer 1-dimensional array with 1024 × 1024 elements. The values of sum and each element of A are all set.
  • Program code optimization by a compiler is disabled.
  • In the initial state, all the pages that are allocated for A are not valid. Any data (including the program code and the page table) other than A are allocated to some valid page, and it is never paged out.
  • Page allocation for the start address of A is aligned with a page boundary.
  • Page replacement is based on the Least Recently Used (LRU) policy.

Kai​

(1)​

  • Page – instead of loading the whole program into the memory, we divide it into fixed-sized chunks called pages and we load some of them to fixed-size chunks of physical memory called frames We load to the memory only those pages that we currently need. Bonus: motivation: processes spend of their execution time accessing only of their space in the memory.
  • Page Table – stores mapping between virtual and physical addresses. It's a region in a memory where we can look-up actual page physical address.
  • Page Replacement - when we cannot allocate a page in a memory, we need to evict some page residing in the memory.
  • Page fault – access to the page which is not in the memory
  • TLB - fast, hardware supported cache memory speeding up address translation (accessing an address via page table requires two actual physical memory accesses).

(2)​

A page has . If we were to address every word (i.e. every ) within a page, then there are possible addresses. To address them all we need bits.

Thus, lower bits of the virtual address make an offset within a page, and the rest of bits make index in the page table:

Offset within a page: , Page number, PageTable[] = . Sanity check: this page is valid, yay. The physical address corresponding to virtual is:

(3)​

We can fit integers into one page. It is easier to look at as a 2-dimensional array, which elements are stored continuously in the memory, row-by-row. We can fit one whole row into a page. Since memory size is and page has then pages fit into the memory. However, one page is reserved, so we can store total of rows of in the memory.

Program 2 accesses row by row. Thus, first rows will be accessed with no page fault (PF). th and every following row row will cause PF. Hence, there will be:

page faults in total.

Program 1 accesses column by column. Every element of a column will land in a different page, thus only first accesses to won't cause PF. We got:

page faults in total.

This one was also solved in Silberschatz's Operating Systems Concepts, 9th ed., Chapter 9.9.5.