protection for different segments. Sometimes segmentation and paging are com-
bined to provide a two-dimensional virtual memory. The MULTICS system and the
32-bit Intel x86 support segmentation and paging.
Still, it is clear that few operat-
ing system developers care deeply about segmentation (because they are married to
a different memory model).
Consequently, it seems to be going out of fashion fast.
Today, even the 64-bit version of the x86 no longer supports real segmentation.
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
Name two drawbacks of this scheme not mentioned in the text.
In Fig. 3-3 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
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.
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
(c) 9 MB
for first fit? Now repeat the question for best fit, worst fit, and next fit.
What is the difference between a physical address and a virtual address?
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.
Using the page table of Fig. 3-9, give the physical address corresponding to each of the
following virtual addresses:
The Intel 8086 processor did not have an MMU or support virtual memory. Neverthe-
less, some companies sold systems that contained an unmodified 8086 CPU and did
paging. Make an educated guess as to how they did it.
: Think about the logical
location of the MMU.)
What kind of hardware support is needed for a paged virtual memory to work?
Copy on write is an interesting idea used on server systems. Does it make any sense on
Consider the following C program:
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
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?
The amount of disk space that must be available for page storage is related to the maxi-
mum number of processes,
, the number of bytes in the virtual address space,
the number of bytes of RAM,
Give an expression for the worst-case disk-space re-
quirements. How realistic is this amount?
If an instruction takes 1 nsec and a page fault takes an additional
nsec, give a formula
for the effective instruction time if page faults occur every
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 cop-
ied 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?
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
(b) Suppose this same system has a TLB (Translation Lookaside Buffer) with 32 en-
tries. Furthermore, suppose that a program contains instructions that fit into one
page and it sequentially reads long integer elements from an array that spans thou-
sands of pages.
How effective will the TLB be for this case?
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?
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.