Winter 2000

Homework assignment 4 solutions

8.9

A process can only use virtual addresses to talk about memory, and all those addresses are translated by the operating systems into physical pages it owns. It has no vocabulary to talk about other address spaces.

The operating system could provide system calls to access other address spaces, which would take both an address and an address space identifier. An operating system might provide such a capability to allow debugging, in which a debugger can read memory of another process, or in client-server computing, where a trusted server can copy memory from the client process. Another possibility is to allow entries for other address spaces to be put in the page table for a process, which allows it to look at that memory.

8.11

The effect of having two page table entries point to the same physical page is that both addresses refer to the same data. This might be useful to provide a quick way to copy large pieces of data that will only be written infrequently, by simply updating the PTE of the destination to point to the PTE of the source. If the data is then written, either the change will be seen at both addresses, or if the OS has marked the destination PTEs as copy-on-write, the OS can then perform the copy operation.

8.14

A reentrant module is one that is executed by multiple processes simultaneously. The advantage of segments for sharing is that independent of the size of the memory shared, only one entry, that for the segment, is needed. In addition, if addresses can be made segment-relative, it is easier to have pointers within that segment because they can all be relative to the segment base rather than to an arbitrary virtual address.

8.17

1. The processor takes an address, and pulls out the segment descriptor. The segment descriptor plus the remaining portion of the original address forms a linear virtual address, which can be looked up in the directory, page table, and page.
2. The advantages are that the page translation can be done more quickly because it is in hardware. In addition, it relieves the burden of having the complexity in the operating system. Finally, the complex mechanism allows fancier forms of sharing and protection at hardware than does a simple software scheme.
3. The drawback is that the complexity of the hardware, while fast relative to software, is slower than other addressing schemes.

9.3

The virtual address, in binary, is "0001 0001 0001 0010 0011 0100 0101 0110". (Supposedly it should have been hex…but that wasn’t obvious in the problem.) Since the page size is 2^12, the page offset is the last twelve bits. The other 20 bits are the virtual page number, which are used to lookup the corresponding physical page in the page table. Most of the lookup will be done in hardware. We look in the TLB with the 20 bits of VPN (hardware). If there is a miss, we go to the OS to refill the TLB using the page table (software). In the meantime, it’s likely that the lower 12 bits looked up the cache in parallel (hardware) and if the tag in the TLB matched the tag in the cache, we have a hit. If not, we go out to main memory with the TLB tag and the 12 bit offset. (This probably left out some details…if you have any questions, e-mail Mike or Tim).

9.7

Benefits:

• Increased memory available to programs
• Simplified code because it can assume a standard memory layout
• More uniform address space available to programs

Costs:

• Cost of memory access must involve virtual to physical translation
• Virtual-to-physical mapping uses up physical memory, leaving less for programs

For systems where there are only a small number of programs, and their memory requirements are well defined, virtual memory may not add many benefits and may slow down the programs.

9.9

1. Install a faster CPU — no, as it is already under-utilized
2. Install a bigger paging disk — no, because there is no indication that there isn’t enough paging space
3. Increase the degree of multi-programming — Assuming that the new programs are similar to the old ones, then no, as there are already too many programs for the memory available However, if the new programs were different, in that the used little memory but lots of CPU, then yes.
4. Decrease the degree of multi-programming — yes, because that would decrease the amount of memory needed, which would reduce the need for paging. But we could likewise say no if the programs being removed used little memory and lots of CPU.
5. Increase main memory — yes, because hopefully fewer pages would be needed to be swapped, allowing more computation between page faults.
6. Install a faster hard disk — yes, because the disk is currently the bottleneck, so the CPU will spend less time waiting for the disk.
7. Add prefetching — yes, as it will allow more data to be brought in on a request, allowing more computation before the next page fault if the program has predictable memory usage.
8. Increase page size — depending on the program type, it may increase utilization because more memory accesses can be handled on the larger page before needing another page fault. For very random accesses, the larger page size means that fewer pages are in memory, causing more page faults and lower CPU utilization.

9.17

Effective access time = 80 % * 1 microsoecond + // for entries in the TLB

20% * 2 microseconds + // for all TLB misses

2% * 20 milliseconds // for page faults

= 401.2 microseconds