Memory Management

Question 1

The IBM 360 had a scheme of locking 2-KB blocks by assigning each one a 4-bit key and
having the CPU compare the key on every memory reference to the 4-bit key in the PSW.
Name two drawbacks of this scheme not mentioned in the text.

Answer 1

First, special hardware is needed to do the comparisons, and it must be fast, since it is used on
every memory reference. Second, with 4-bit keys, only 16 programs can be in memory at once
(one of which is the operating system).

Question 2

In Fig. 3-3 (https://imgur.com/a/DbYhqga) the base and limit registers contain the same value, 16,384. Is this just an
accident, or are they always the same? It is just an accident, why are they the same in this
example?

Answer 2

It is an accident. The base register is 16,384 because the program happened to be loaded at
address 16,384. It could have been loaded anywhere. The limit register is 16,384 because the
program contains 16,384 bytes. It could have been any length. That the load address happens to
exactly match the program length is pure coincidence.

Question 3

A swapping system eliminates holes by compaction. Assuming a random distribution of
many holes and many data segments and a time to read or write a 32-bit memory word of 4 nsec, about how long does it take to compact 4 GB? For simplicity, assume that word 0 is part
of a hole and that the highest word in memory contains valid data.

Answer 3

Almost the entire memory has to be copied, which requires each word to be read and then
rewritten at a different location. Reading 4 bytes takes 4 nsec, so reading 1 byte takes 1 nsec
and writing it takes another 1 nsec, for a total of 2 nsec per byte compacted. This is a rate of
500,000,000 bytes/sec. To copy 4 GB (2³² bytes, which is about 4.295 × 10⁹ bytes), the computer
needs 2³²/500,000,000 sec, which is about 8.599 msec. This number is slightly pessimistic
because if the initial hole at the bottom of memory is k bytes, those k bytes do not need to be
copied. However, if there are many holes and many data segments, the holes will be small, so k
will be small and the error in the calculation will also be small.

Question 4

Consider a swapping system in which memory consists of the following hole sizes in
memory order: 10 MB, 4 MB, 20 MB, 18 MB, 7 MB, 9 MB, 12 MB, and 15 MB. Which hole is
taken for successive segment requests of (a) 12 MB, (b) 10 MB, and (c) 9 MB for first fit? Now
repeat the question for best fit, worst fit, and next fit.

Answer 4

● First fit takes 20 MB, 10 MB, 18 MB.
● Best fit takes 12 MB, 10 MB, and 9 MB.
● Worst fit takes 20 MB, 18 MB, and 15 MB.
● Next fit takes 20 MB, 18 MB, and 9 MB.

Question 5

What is the difference between a physical address and a virtual address?

Answer 5

https://imgur.com/a/Ru5zoEy

Question 6

For each of the following decimal virtual addresses, compute the virtual page number and
offset for a 4-KB page and for an 8 KB page: 20000, 32768, 60000.

Answer 6

(TUT7)
For the page size of 4 KB, page offset is 12 bits and for the page size 8 KB, page offset is 13 bits.
The page offset for 20000 is 3616 for both the pages of 4 KB and 8 KB size. The virtual page
number for 4 KB page will be 4 (that is 1000) and for 8 KB page is 2, the virtual page number will
be 1010.
The page offset for 32768 is 0 for both the pages of 4 KB and 8 KB size. The virtual page number
for 4 KB page will be 8 (that is 1000) and for 8 KB page is 4, the virtual page number will be
1050.
The page offset for 60000 is 2656 for both the pages of 4 KB and 8 KB size. The virtual page
number for 4 KB page will be 14 (that is 2025) and for 8 KB page is 7, the virtual page number
will be 1250.
For a 4-KB page size the (page, offset) pairs are (4, 3616), (8, 0), and (14, 2656). For an 8-KB page
size they are (2, 3616), (4, 0), and (7, 2656).

Question 7

Using the page table of Fig. 3-9 (https://imgur.com/a/GIeyIaH), give the physical address corresponding to each of the
following virtual addresses: 20, 4100, and 8300.

Answer 7

a) 8212
b) 4100
c) 24684

Question 8

The Intel 8086 processor did not have an MMU or support virtual memory. Nevertheless,
some companies sold systems that contained an unmodified 8086 CPU and did paging. Make
an educated guess as to how they did it. (Hint: Think about the logical location of the MMU.)

Answer 8

They built an MMU and inserted it between the 8086 and the bus. Thus all 8086 physical
addresses went into the MMU as virtual addresses. The MMU then mapped them onto physical
addresses, which went to the bus.

Question 9

What kind of hardware support is needed for a paged virtual memory to work?

Answer 9

There needs to be an MMU that can remap virtual pages to physical pages. Also, when a page
not currently mapped is referenced, there needs to be a trap to the operating system so it can
fetch the page.

Question 10

Copy on write is an interesting idea used on server systems. Does it make any sense on a
smartphone?

Answer 10

If the smartphone supports multiprogramming, which the iPhone, Android, and Windows
phones all do, then multiple processes are supported. If a process forks and pages are shared
between parent and child, copy on write definitely makes sense. A smartphone is smaller than a
server, but logically it is not so different.

Question 11

Consider the following C program:
int X[N];
int step = M; /* M is some predefined constant */
for (int i = 0; i < N; i += step) X[i] = X[i] + 1;

a) If this program is run on a machine with a 4-KB page size and 64-entry TLB, what values
of M and N will cause a TLB miss for every execution of the inner loop?
b) Would your answer in part (a) be different if the loop were repeated many times?
Explain.

Answer 11

(TUT7)
Minimum int size is 4 bytes which gives us 1024 integers per 4-KB memory page.
a) It means that after X[0] is accessed, accessing any of the succeeding elements up to
X[1023] would not generate TLB fault. However, if we try to access X[0], X[1024], X[2048]
and so on, each time a TLB miss will occur which means that M should be at least 1024.
b) M should still be at least 1024 to cause a TLB miss for every execution of the inner loop.
Assuming that such page replacement algorithm as FIFO is used, we need to fill the
whole TLB and make one more reference to an absent page to make sure that the page 0
is not in the TLB at the beginning of each outer cycle. It means that we need to have at
least 65 pages. In this case N should be at least 64 * 1024 + 1.

Question 12

The amount of disk space that must be available for page storage is related to the
maximum number of processes, n, the number of bytes in the virtual address space, v, and the
number of bytes of RAM, r. Give an expression for the worst-case disk-space requirements.
How realistic is this amount?

Answer 12

(TUT7)
The total virtual address space for all the processes combined is n · v, so this much storage is
needed for pages. However, an amount r can be in RAM, so the amount of disk storage required
is only n · v – r. This amount is far more than is ever needed in practice because rarely will there
be n processes actually running and even more rarely will all of them need the maximum
allowed virtual memory.

Question 13

13. If an instruction takes 1 nsec and a page fault takes an additional n nsec, give a formula for
    the effective instruction time if page faults occur every k instructions.

Answer 13

Given that each instruction takes 1 nsec to execute. To execute k instructions it takes k nsec.
After k instructions a page fault occurs, to handle a page fault it requires n nsec. Therefore, to
execute k instruction with a page fault it requires (k + n) nsec. Therefore, when it takes (k + n)
nsec to execute k instructions then it requires (k + n) / k nsec for each instruction. The formula
for effective instruction time is (k + n) / k.

Question 14

A machine has a 32-bit address space and an 8-KB page. The page table is entirely in
hardware, with one 32-bit word per entry. When a process starts, the page table is copied to
the hardware from memory, at one word every 100 nsec. If each process runs for 100 msec
(including the time to load the page table), what fraction of the CPU time is devoted to
loading the page tables?

Answer 14

(FE17) (FFE18)
The page table contains 2³²/2¹³ = 2¹⁹ entries, which is 524,288.
To copy one entry into the hardware, 100 nsec are required. Therefore, to load 2¹⁹ entries, the
time required is 2¹⁹ × 100 nsec = 52,428,800 nsec = 52 msec.
Loading the page table takes 52,43 msec. If a process gets 100 msec, this consists of 52 msec for
loading the page table and 48 msec for running. Thus 52,43% of the time is spent loading page
tables.

Question 15

Suppose that a machine has 48-bit virtual addresses and 32-bit physical addresses.
a) If pages are 4 KB, how many entries are in the page table if it has only a single level?
Explain.
b) Suppose this same system has a TLB (Translation Lookaside Buffer) with 32 entries.
Furthermore, suppose that a program contains instructions that fit into one page and
it sequentially reads long integer elements from an array that spans thousands of
pages. How effective will the TLB be for this case?

Answer 15

(FE17)
Answer:
a) Given that the virtual address space is 48-bit and the pages are 4KB (2² × 2¹⁰ = 2¹²), the
number of entries in the page table is given by: 2⁴⁸ / 2¹² = 2³⁶ = 68,719,476,736.
b) TLB (Transaction look-aside buffer) will be very effective in this case. The instruction
addresses would achieve 100% hits in the TLB. Data pages would also achieve a hit rate
of 100% unless the program moves to the next page for data. A 4 KB page has the
capability to store 1024 long integer values. Thus single misses in the TLB will be
observed and an extra memory access will be observed for every 1024 references to
data.

Question 16

You are given the following data about a virtual memory system:
a) The TLB can hold 1024 entries and can be accessed in 1 clock cycle (1 nsec).
b) A page table entry can be found in 100 clock cycles or 100 nsec.
c) The average page replacement time is 6 msec.
If page references are handled by the TLB 99% of the time, and only 0.01% lead to a page
fault, what is the effective address-translation time?

Answer 16

The chance of a hit is 0.99 for the TLB, 0.0099 for the page table, and 0.0001 for a page fault.
The effective address translation time in nsec is then: 0. 99 × 1 + 0.0099 × 100 + 0.0001 × 6 × 10⁶
≈ 602 nsec.
Note that the effective address translation time is quite high because it is dominated by the
page replacement time even when page faults only occur once in 10,000 references.

Question 17

Suppose that a machine has 38-bit virtual addresses and 32-bit physical addresses.
a) What is the main advantage of a multilevel page table over a single-level one?
b) With a two-level page table, 16-KB pages, and 4-byte entries, how many bits should be
allocated for the top-level page table field and how many for the next level page table
field? Explain.

Answer 17

Consider:
a) A multilevel page table reduces the number of actual pages of the page table that need
to be in memory because of its hierarchic structure. In fact, in a program with lots of
instruction and data locality, we only need the top level page table (one page), one
instruction page, and one data page.
b) Allocate 12 bits for each of the three page fields. The offset field requires 14 bits to
address 16 KB. That leaves 24 bits for the page fields. Since each entry is 4 bytes, one
page can hold 2¹² page table entries and therefore requires 12 bits to index one page. So
allocating 12 bits for each of the page fields will address all 2³⁸ bytes.

Question 18

Section 3.3.4 states that the Pentium Pro extended each entry in the page table hierarchy
to 64 bits but still could only address only 4 GB of memory. Explain how this statement can be
true when page table entries have 64 bits.

Answer 18

The virtual address was changed from (PT1, PT2, Offset) to (PT1, PT2, PT3, Offset). But the
virtual address still used only 32 bits. The bit configuration of a virtual address changed from
(10, 10, 12) to (2, 9, 9, 12).

Question 19

A computer with a 32-bit address uses a two-level page table. Virtual addresses are split
into a 9-bit top-level page table field, an 11-bit second-level page table field, and an offset.
How large are the pages and how many are there in the address space?

Answer 19

Total bits = Virtual page numbers (VPN) + offset bits
Number of bytes per page = 2^offset bits
Number of pages in the address space = 2^number of virtual page numbers
Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. This yields a 4-
KB page. Twenty bits for the virtual page implies 2²⁰ pages.

Question 20

A computer has 32-bit virtual addresses and 4-KB pages. The program and data together
fit in the lowest page (0–4095). The stack fits in the highest page. How many entries are
needed in the page table if traditional (one-level) paging is used? How many page table
entries are needed for two-level paging, with 10 bits in each part?

Answer 20

For a one-level page table, there are 2³²/2¹² or 2M pages needed. Thus the page table must have
2M entries. For two-level paging, the main page table has 1K entries, each of which points to a
second page table. Only two of these are used. Thus, in total only three page table entries are
needed, one in the top-level table and one in each of the lower-level tables.

Question 21

Below is an execution trace of a program fragment for a computer with 512-byte pages.
The program is located at address 1020, and its stack pointer is at 8192 (the stack grows
toward 0). Give the page reference string generated by this program. Each instruction
occupies 4 bytes (1 word) including immediate constants. Both instruction and data
references count in the reference string.
Load word 6144 into register 0
Push register 0 onto the stack
Call a procedure at 5120, stacking the return address
Subtract the immediate constant 16 from the stack pointer
Compare the actual parameter to the immediate constant 4
Jump if equal to 5152

Answer 21

The code and reference string are as follows:
LOAD 6144, R0 1(I), 12(D)
PUSH R0 2(I), 15(D)
CALL 5120 2(I), 15(D)
JEQ 5152 10(I)
The code (I) indicates an instruction reference, whereas (D) indicates a data reference.

Question 22

A computer whose processes have 1024 pages in their address spaces keeps its page
tables in memory. The overhead required for reading a word from the page table is 5 nsec. To
reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page
frame) pairs, and can do a lookup in 1 nsec. What hit rate is needed to reduce the mean
overhead to 2 nsec?

Answer 22

The effective instruction time is 1h + 5(1 − h), where h is the hit rate. If we equate this formula
with 2 and solve for h, we find that h must be at least 0.75.

Question 23

How can the associative memory device needed for a TLB be implemented in hardware,
and what are the implications of such a design for expandability?

Answer 23

An associative memory essentially compares a key to the contents of multiple registers
simultaneously. For each register there must be a set of comparators that compare each bit in
the register contents to the key being searched for. The number of gates (or transistors) needed
to implement such a device is a linear function of the number of registers, so expanding the
design gets expensive linearly.

Question 24

A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8 KB. How
many entries are needed for a single-level linear page table?

Answer 24

Page size = 8KB = 2¹³ bits (Page offset is 13 bits)
Actual virtual address bits = Virtual address size – Page offset = 48 – 13 = 35.
Number of page entries is 2³⁵ = 34359738368.

Question 25

A computer with an 8KB page, a 256KB main memory, and a 64GB virtual address space
uses an inverted page table to implement its virtual memory. How big should the hash table
be to ensure a mean hash chain length of less than 1? Assume that the hashtable size is a
power of two.

Answer 25

Page size = 8KB = 2¹³ bytes
The 256MB RAM would have 2⁸ × 2¹⁰× 2¹⁰ = 2²⁸ entries.
Number of pages required is 2²⁸/2¹³ = 2¹⁵ = 32768.

If the hash table is 32K, the mean chain length would be 1. In order to achieve a mean chain
length less than one, the next possible size or 32768 + 32768 = 65536 slots in table are needed over which the 32768 entries can be spread. This would give a mean chain length less than 1 i.e.
0.5.

Question 26

A student in a compiler design course proposes to the professor a project of writing a
compiler that will produce a list of page references that can be used to implement the optimal
page replacement algorithm. Is this possible? Why or why not? Is there anything that could be
done to improve paging efficiency at run time?

Answer 26

The list containing page references cannot be used for the implementation of the page
replacement algorithm. Since the execution of the program is predicted at the compilation time.
When any information is collected by the compiler, then, the information should be used during
the link time for the rearrangement of the code objects. Then the procedure, which is located
near the code object, can make a call to them. It is also possible that calling code and procedure
may be lie on same page. By doing so, the page efficiency can be improved.

Question 27

Suppose that the virtual page reference stream contains repetitions of long sequences of
page references followed occasionally by a random page reference. For example, the
sequence: 0, 1, … , 511, 431, 0, 1, … , 511, 332, 0, 1, … consists of repetitions of the sequence
0, 1, … , 511 followed by a random reference to pages 431 and 332.
a) Why will the standard replacement algorithms (LRU, FIFO, clock) not be effective in
handling this workload for a page allocation that is less than the sequence length?
b) If this program were allocated 500 page frames, describe a page replacement approach
that would perform much better than the LRU, FIFO, or clock algorithms.

Answer 27

(TUT8)
Under these circumstances:
a) Consider, for example, a page allocation scheme with 510 frames. First 510 references
will generate page faults because none of the pages are in memory. The next reference
will generate page fault too and also will push page 1 out of memory. Therefore, every
reference will page fault unless the number of page frames is 512, the length of the
entire sequence.
b) If there are 500 frames, map pages 0–498 to fixed frames and vary only one frame.

Question 28

If FIFO page replacement is used with four page frames and eight pages, how many page
faults will occur with the reference string 0172327103 if the four frames are initially empty?
Now repeat this problem for LRU.

Answer 28

(TUT8)
The page frames for FIFO are as follows:
x0172333300
xx017222233
xxx01777722
xxxx0111177
The page frames for LRU are as follows:
x0172327103
xx017232710
xxx01773271
xxxx0111327

Question 29

Consider the page sequence of Fig. 3-15(b) (https://imgur.com/a/7peaZtk). Suppose that the R bits for the pages B
through A are 11011011, respectively. Which page will second chance remove?

Answer 29

The first page with a 0 bit will be chosen, in this case D.

Question 30

A small computer on a smart card has four page frames. At the first clock tick, the R bits
are 0111 (page 0 is 0, the rest are 1). At subsequent clock ticks, the values are 1011, 1010,
1101, 0010, 1010, 1100, and 0001. If the aging algorithm is used with an 8-bit counter, give the
values of the four counters after the last tick.

Answer 30

(TUT8)
The counters are:
● Page 0: 01101110 = 110₁₀
● Page 1: 01001001 = 73₁₀
● Page 2: 00110111 = 55₁₀
● Page 3: 10001011 = 139₁₀

Question 31

Give a simple example of a page reference sequence where the first page selected for
replacement will be different for the clock and LRU page replacement algorithms. Assume
that a process is allocated 3 frames, and the reference string contains page numbers from the
set 0, 1, 2, 3.

Answer 31

(TUT8)
The sequence: 0, 1, 2, 1, 0, 2, 1, 2, 0, 3. In LRU, page 1 will be replaced by page 3. In clock, page
1 will be replaced, since all pages will be marked and the cursor is at page 0.

Question 32

In the WSClock algorithm of Fig. 3-20(c) (https://imgur.com/a/EipGl66), the hand points to a page with R = 0. If τ = 400,
will this page be removed? What about if τ = 1000?

Answer 32

(TUT8)
The age of the page is 2204 − 1213 = 991. If τ = 400, it is definitely out of the working set and
was not recently referenced so it will be evicted. The τ = 1000 situation is different. Now the
page falls within the working set (barely), so it is not removed.

Question 33

Suppose that the WSClock page replacement algorithm uses a τ of two ticks, and the
system state is the following (https://imgur.com/a/cebm6Pe) where the three flag bits V, R, and M stand for Valid, Referenced, and Modified, respectively.
a) If a clock interrupt occurs at tick 10, show the contents of the new table entries.
Explain. (You can omit entries that are unchanged.)
b) Suppose that instead of a clock interrupt, a page fault occurs at tick 10 due to a read
request to page 4. Show the contents of the new table entries. Explain. (You can omit
entries that are unchanged.)

Answer 33

Consider:
a) For every R bit that is set, set the time-stamp value to 10 and clear all R bits. You could
also change the (0, 1) R-M entries to (0, 0*). So the entries for pages 1 and 2 will change
to: (https://imgur.com/a/MCiuQJS, first)

b) Evict page 3 (R = 0 and M = 0) and load page 4: (https://imgur.com/a/MCiuQJS, second)

Question 34

A student has claimed that “in the abstract, the basic page replacement algorithms (FIFO,
LRU, optimal) are identical except for the attribute used for selecting the page to be
replaced.”
c) What is that attribute for the FIFO algorithm? LRU algorithm? Optimal algorithm?
d) Give the generic algorithm for these page replacement algorithms.

Answer 34

Consider:
a) The attributes are: (FIFO) load time; (LRU) latest reference time; and (Optimal) nearest
reference time in the future.
b) There is the labeling algorithm and the replacement algorithm. The labeling algorithm
labels each page with the attribute given in part (a). The replacement algorithm evicts
the page with the smallest label.

Question 35

How long does it take to load a 64-KB program from a disk whose average seek time is 5
msec, whose rotation time is 5 msec, and whose tracks hold 1 MB
a) for a 2-KB page size?
b) for a 4-KB page size?
The pages are spread randomly around the disk and the number of cylinders is so large that
the chance of two pages being on the same cylinder is negligible.

Answer 35

a) Number of pages = Program size / Page size = 64 KB / 2 KB = 32
Access time = Seek time + Rotation time = 10 msec
Time for loading 2 KB on 1 MB = (Page size / Track size) × Access time
= (2 / 1024) × 10 = 0.0195 msec
Loading time = (Access time + Time for loading 2 KB on 1 MB) × No. of pages =
= (5 + 5 + 0.0195) × 32 msec = 320.624 msec
b) 160.624 msec

Question 36

A computer has four page frames. The time of loading, time of last access, and the R and
M bits for each page are as shown below (the times are in clock ticks): https://imgur.com/a/gyrufq7

a) Which page will NRU replace?
b) Which page will FIFO replace?
c) Which page will LRU replace?
d) Which page will second chance replace?

Answer 36

NRU removes page 2. FIFO removes page 3. LRU removes page 1. Second chance removes page
2.

Question 37

37. Suppose that two processes A and B share a page that is not in memory. If process A faults
    on the shared page, the page table entry for process A must be updated once the page is read
    into memory.
    a) Under what conditions should the page table update for process B be delayed even
    though the handling of process A’s page fault will bring the shared page into memory?
    Explain.
    b) What is the potential cost of delaying the page table update?

Answer 37

Sharing pages brings up all kinds of complications and options:
a) The page table update should be delayed for process B if it will never access the shared
page or if it accesses it when the page has been swapped out again. Unfortunately, in
the general case, we do not know what process B will do in the future.
b) The cost is that this lazy page fault handling can incur more page faults. The overhead of
each page fault plays an important role in determining if this strategy is more efficient.
(Aside: This cost is similar to that faced by the copy-on-write strategy for supporting
some UNIX fork system call implementations.)

Question 38

38. Consider the following two-dimensional array:
    int X[64][64];
    Suppose that a system has four page frames and each frame is 128 words (an integer occupies
    one word). Programs that manipulate the X array fit into exactly one page and always occupy
    page 0. The data are swapped in and out of the other three frames. The X array is stored in
    row-major order (i.e., X[0][1] follows X[0][0] in memory). Which of the two code fragments
    shown below will generate the lowest number of page faults? Explain and compute the total
    number of page faults.

Fragment A
for (int j = 0; j < 64; j++)
for (int i = 0; i < 64; i++) X[i][j] = 0;
Fragment B
for (int i = 0; i < 64; i++)
for (int j = 0; j < 64; j++) X[i][j] = 0;

Answer 38

Fragment B since the code has more spatial locality than Fragment A. The inner loop causes only
one page fault for every other iteration of the outer loop. (There will be only 32 page faults.)
[Aside (Fragment A): Since a frame is 128 words, one row of the X array occupies half of a page
(i.e., 64 words). The entire array fits into 64 × 32/128 = 16 frames. The inner loop of the code
steps through consecutive rows of X for a given column. Thus, every other reference to X[i][j]
will cause a page fault. The total number of page faults will be 64 × 64/2 = 2, 048].

Question 39

You have been hired by a cloud computing company that deploys thousands of servers at
each of its data centers. They have recently heard that it would be worthwhile to handle a
page fault at server A by reading the page from the RAM memory of some other server rather
than its local disk drive.
a) How could that be done?
b) Under what conditions would the approach be worthwhile? Be feasible?

Answer 39

It can certainly be done.
a) The approach has similarities to using flash memory as a paging device in smartphones
except now the virtual swap area is a RAM located on a remote server. All of the
software infrastructure for the virtual swap area would have to be developed.
b) The approach might be worthwhile by noting that the access time of disk drives is in the
millisecond range while the access time of RAM via a network connection is in the
microsecond range if the software overhead is not too high. But the approach might
make sense only if there is lots of idle RAM in the server farm. And then, there is also the
issue of reliability. Since RAM is volatile, the virtual swap area would be lost if the
remote server went down.

Question 40

One of the first timesharing machines, the DEC PDP-1, had a (core) memory of 4K 18-bit
words. It held one process at a time in its memory. When the scheduler decided to run
another process, the process in memory was written to a paging drum, with 4K 18-bit words
around the circumference of the drum. The drum could start writing (or reading) at any word,
rather than only at word 0. Why do you suppose this drum was chosen?

Answer 40

The PDP-1 paging drum had the advantage of no rotational latency. This saved half a rotation
each time memory was written to the drum.

Question 41

A computer provides each process with 65,536 bytes of address space divided into pages
of 4096 bytes each. A particular program has a text size of 32,768 bytes, a data size of 16,386
bytes, and a stack size of 15,870 bytes. Will this program fit in the machine’s address space?
Suppose that instead of 4096 bytes, the page size were 512 bytes, would it then fit? Each page
must contain either text, data, or stack, not a mixture of two or three of them.

Answer 41

(TUT9)
The text is eight pages, the data are five pages, and the stack is four pages. The program does
not fit because it needs 17 4096-byte pages. With a 512-byte page, the situation is different.
Here the text is 64 pages, the data are 33 pages, and the stack is 31 pages, for a total of 128
512-byte pages, which fits. With the small page size it is OK, but not with the large one.

Question 42

It has been observed that the number of instructions executed between page faults is
directly proportional to the number of page frames allocated to a program. If the available
memory is doubled, the mean interval between page faults is also doubled. Suppose that a
normal instruction takes 1 microsec, but if a page fault occurs, it takes 2001 μ sec (i.e., 2 msec)
to handle the fault. If a program takes 60 sec to run, during which time it gets 15,000 page
faults, how long would it take to run if twice as much memory were available?

Answer 42

The program is getting 15,000 page faults, each of which uses 2 msec of extra processing time.
Together, the page fault overhead is 30 sec. This means that of the 60 sec used, half was spent
on page fault overhead, and half on running the program. If we run the program with twice as
much memory, we get half as many memory page faults, and only 15 sec of page fault
overhead, so the total run time will be 45 sec.

Question 43

A group of operating system designers for the Frugal Computer Company are thinking
about ways to reduce the amount of backing store needed in their new operating system. The
head guru has just suggested not bothering to save the program text in the swap area at all,
but just page it in directly from the binary file whenever it is needed. Under what conditions,
if any, does this idea work for the program text? Under what conditions, if any, does it work
for the data?

Answer 43

It works for the program if the program cannot be modified. It works for the data if the data
cannot be modified. However, it is common that the program cannot be modified and
extremely rare that the data cannot be modified. If the data area on the binary file were
overwritten with updated pages, the next time the program was started, it would not have the
original data.

Question 44

A machine-language instruction to load a 32-bit word into a register contains the 32-bit
address of the word to be loaded. What is the maximum number of page faults this
instruction can cause?

Answer 44

The instruction could lie astride a page boundary, causing two page faults just to fetch the
instruction. The word fetched could also span a page boundary, generating two more faults, for
a total of four. If words must be aligned in memory, the data word can cause only one fault, but
an instruction to load a 32-bit word at address 4094 on a machine with a 4-KB page is legal on
some machines (including the x86).

Question 45

Explain the difference between internal fragmentation and external fragmentation. Which
one occurs in paging systems? Which one occurs in systems using pure segmentation?

Answer 45

(TUT9)
Internal fragmentation occurs when the last allocation unit is not full. External fragmentation
occurs when space is wasted between two allocation units. In a paging system, the wasted
space in the last page is lost to internal fragmentation. In a pure segmentation system, some
space is invariably lost between the segments. This is due to external fragmentation.

Question 46

When segmentation and paging are both being used, as in MULTICS, first the segment
descriptor must be looked up, then the page descriptor. Does the TLB also work this way, with
two levels of lookup?

Answer 46

No. The search key uses both the segment number and the virtual page number, so the exact
page can be found in a single match.

Question 47

We consider a program which has the two segments shown below consisting of
instructions in segment 0, and read/write data in segment 1. Segment 0 has read/execute
protection, and segment 1 has just read/write protection. The memory system is a demand
paged virtual memory system with virtual addresses that have a 4-bit page number, and a 10-
bit offset. The page tables and protection are as follows (all numbers in the table are in
decimal): https://imgur.com/a/t030Vbp

For each of the following cases, either give the real (actual) memory address which results
from dynamic address translation or identify the type of fault which occurs (either page or
protection fault).
a) Fetch from segment 1, page 1, offset 3
b) Store into segment 0, page 0, offset 16
c) Fetch from segment 1, page 4, offset 28
d) Jump to location in segment 1, page 3, offset 32

Answer 47

https://imgur.com/a/XoUM0sG

Question 48

Can you think of any situations where supporting virtual memory would be a bad idea,
and what would be gained by not having to support virtual memory? Explain.

Answer 48

(TUT9)
General virtual memory support is not needed when the memory requirements of all
applications are well known and controlled. Some examples are smart cards, special-purpose
processors (e.g., network processors), and embedded processors. In these situations, we should
always consider the possibility of using more real memory. If the operating system did not have
to support virtual memory, the code would be much simpler and smaller. On the other hand,
some ideas from virtual memory may still be profitably exploited, although with different design
requirements. For example, program/thread isolation might be paging to flash memory.

Question 49

Virtual memory provides a mechanism for isolating one process from another. What
memory management difficulties would be involved in allowing two operating systems to run
concurrently? How might these difficulties be addressed?

Answer 49

This question addresses one aspect of virtual machine support. Recent attempts include Denali,
Xen, and VMware. The fundamental hurdle is how to achieve near-native performance, that is,
as if the executing operating system had memory to itself. The problem is how to quickly switch
to another operating system and therefore how to deal with the TLB. Typically, you want to give
some number of TLB entries to each kernel and ensure that each kernel operates within its
proper virtual memory context. But sometimes the hardware (e.g., some Intel architectures)
wants to handle TLB misses without knowledge of what you are trying to do. So, you need to
either handle the TLB miss in software or provide hardware support for tagging TLB entries with
a context ID.