Midterm 51-69

Question 1

What is the job of a “page table”?

Answer 1

It contains a translation (mapping) of virtual to physical addresses.

Question 2

Assume that the logical address is 24 bits and the physical memory is 1MB. Also, assume that each page or frame is 4KB.

a) Show how the logical and physical addresses are partitioned.
b) What is the size of the page table?
c) Assume the logical address is ABCDEF, the content of the page table in line DEF is AB, and in line ABC is F5. Where in the physical memory, this logical address is mapped?

Answer 2

a) physical: 20 bits, frame: 8 bits, offset: 12 bits
virtual: 24 bits, page: 12 bits, offset: 12 bits
b) Page table has 2^12 lines.
c) Virtual address ABCDEF is at address F5DEF.

Question 3

Imagine that we have fixed block sizes of size 2048 bytes. Also, imagine that the process size is P. Write a C code that, for 10000 times, randomly generates an integer P, between 1 and 20000. Then for each value of P, determine the amount of internal fragmentation and calculate the mean value of that. Copy/paste your code in your solution file. Also, report the average value of internal fragmentation.

Answer 3

See code on review Q53.

Fragmentation = block size - used bytes

Question 4

Accessing the page table may have considerable delays. What is a solution to reduce the average delay of the page address mapping?

Answer 4

Use of TLB.

Question 5

Practice Q55!!

Answer 5

On review!

Question 6

What is the purpose of using “valid bit” in the page memory table?

Answer 6

This bit is just for protection purposes. The “valid” bit indicates that the associated page is in the process’s logical address space and is thus a legal page. When the bit is set to invalid, the page is not in the process’s logical address space. Illegal addresses are trapped by the use of the valid-invalid bit. The operating system sets this bit for each page to allow or disallow access to the page.

Question 7

What is a “reentrant”page? Usually, reentrant pages belong to some specific processes. Name two examples of such processes.

Answer 7

The Reentrant code is non-self-modifying: it never changes during execution. Thus, two or more processes can execute the same code at the same time. Each process has its own copy of registers and data storage to hold the data for the process’s execution. The data for two different processes will, of course, be different. The reentrant page is a read-only copy of code shared among processes. Examples are text editors, compilers, C libraries, and windows systems.

Question 8

Name three strategies that are used to reduce the size of page tables when the logical address is large.

Answer 8

Hierarchical Paging, Hashed Page Tables, Inverted Page Tables

Question 9

Suppose that the logical address is 32 bits and the page offset is 12 bits. Show an example of a hierarchical page address.

Answer 9

Page number: p1 10 bits, p2 10 bits

Offset: 12 bits.

Question 10

Why a hierarchical page addressing is not possible for 64-bit logical addressing? What are the two alternative methods?

Answer 10

Even a three- level page table requires a 2^32 line third-level table. If we use more page table layers, for example, eight layers, then going through all layers to find the address of a page would be prohibitively long. Alternative approaches are using hash tables and TLBs.

Question 11

Explain the following diagram. What are p, q, s, r, and d? Suppose the 64-bit logical address of F1234567890ABCDE is mapped into the physical address of 4FFCDE. What are the values of p, d, and r? Also, give an example of the value of q.

Answer 11

Go to Q61 in review.

We see that pages are 4KB since the low significant 12 bits of the physical and logical addresses are the same. P is the page number which is 52 bits, and the first 13 Hex digits of the address. r is 4FF, and d is CDE. q is another 52-bit page number that is hashed into the same place as p is hashed to. Since we don’t know the hash function, we can throw in any 52-bit number as q. For example, CADF13571234F is q.

Question 12

a) What is an “inverted page table?”

b) How can we limit the search process?

Answer 12

a) The page table is as big as the number of physical pages. This method makes the page table size much smaller than using a table that has 2^(number of virtual pages).
b) hashing could be used to limit the search. For example, the virtual page number is hashed in three different methods to restrict the search to only three entries of the inverted table.

Question 13

The 64-bit Sparc Solaris uses two hash tables. What are these two tables? What is “page walk” in the memory mapping process of this system?

Answer 13

Two hash tables are used. One table is used for the user codes, and one table for the OS. Also, a TLB is used for fast search. Page walk: If the address is not in the TLB, the system “walks back” and searches the hash tables.

Question 14

Some operating systems occasionally deactivate “swapping.” What is the purpose, and what are the occasions?

Answer 14

Swapping requires the transfer of data and code from the main memory to the backing store. The data transfer is time-consuming. In UNIX, swapping is disabled until the number of allocated pages becomes higher than a threshold.

Question 15

Suppose that a process takes 200MB of the main memory. This process has to be swapped by sending it to the backing memory and bringing a new process, of the same size, into the main memory. The transfer rate is 150MB/sec. How long does this context switch will take?

Answer 15

200MB + 200MB = 400MB –> (400MB/150MB/sec) = 2.67 sec

Question 16

What is a “pending I/O” during process swapping? Explain “double buffering” that is used to remedy pending I/O.

Answer 16

Sometimes, a process has to be swapped into the backing store, and that process may have been transferring data from I/O. The swapped-out process would lose the data. OS could use its memory space to buffer the I/O data, and when the process is brought back into the main memory, OS should deliver the buffer data to the process. The data is moved twice, which is called double buffering.

Question 17

What is the maximum size of a segment in an IA-32 system? What are the differences between LDT and GDT? The logical addresses in IA-32 systems consist of two parts. What are these two parts called, and what are their purposes?

Answer 17

Addresses in IA-32 systems consist of a selector and an offset. A selector is a 16-bit number consisting of s(13 bits), g(1 bit), p(2 bits) The s part designates the segment number, g indicates whether the segment is in the global descriptor table (GDT) or the local descriptor table (LDT). Also, the 2 bits p is used for protection. An offset is a 32-bit number specifying the locationofthebytewithinthesegmentinquestion. Anoffsetof32bitmeans that each segment could be as large as 4GB.

Question 18

The following diagram shows the addressing system of the IA-32. What is the difference between addressing a 4KB page and a 4MB page?

Answer 18

See diagram in Q68 of review.

If the virtual address is 32 bits, then the physical address is usually less than 32 bits, for example, 28 bits. The high 10 bits of the virtual address are used to find a line in the page directory. There is a bit in the content of the page directory line that indicates if the page size is 4MB or 4KB. For 4MB pages, the page directory provides a 28-bit start address which we add our 4MB page offset of 22 bits to that. For 4KB pages, the page director offers a 28-bit address that points to the start of a page table. The page table has 2^10 lines and using the page table part of the virtual address, and we refer to the appropriate line of the table. The content of the page table is a 28-bit physical address which we add the 12 bit offset to it to get the physical address of the line of the 4KB page.

Question 19

The addressing method in the ARM architecture is shown below. Explain how this architecture works for 4KB, 16KB, 1MB, and 16MB pages.

Answer 19

See diagram in Q69 of review.

If the virtual page table is 32 bits, then the physical address is smaller, and it is, for example, 28 bits. The outer page table entries consist of two bits that indicate the page size. For example, 00 means the page size is 4KB, 01 means 16KB, 10 means 1MB, and 11 means that the referenced page is 16MB. Besides these two bits, the content of the outer page table has 28 bits, which points to either the inner page table or a 1MB or 16MB page. Hence, the offset part could be 12 bits, 14 bits, 20 bits, or 24 bits.