Problem 9.2
Explain the difference between internal and
external fragmentation.
Answer Internal Fragmentation is the area in a region or a page that is not used by the job occupying that region or page. This space is unavailable for use by the system until that job is finished and the page or region is released.
Problem 9.3
Describe the following allocation algorithms:
Answer
Problem 9.5
Given memory partitions of 100K, 500K, 200K, 300K,
and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit
algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which
algorithm makes the most efficient use of memory?
Answer
Problem 9.7
Why are page sizes always powers of 2?
Answer Recall that paging is implemented by breaking up an address into a page and offset number. It is most efficient to break the address into X page bits and Y offset bits, rather than perform arithmetic on the address to calculate the page number and offset. Because each bit position represents a power of 2, splitting an address between bits results in a page size that is a power of 2.
Problem 9.8
Consider a logical address space of eight pages of
1024 words each, mapped onto a physical memory of 32 frames.
Answer
Problem 9.9
On a system with paging, a process cannot access
memory that it does not own; why? How could the operating system allow access to
other memory? Why should it or should it not?
Answer
An address on a paging system is a logical page number and
an offset. The physical page is found by searching a table based on the logical
page number to produce a physical page number. Because the operating system
controls the contents of this table, it can limit a process to accessing only
those physical pages allocated to the process. There is no way for a process to
refer to a page it does not own because the page will not be in the page table.
To allow such access, an operating system simply needs to allow entries for
non-process memory to be added to the process s page table. This is useful when
two or more processes need to exchange data they just read and write to the same
physical addresses (which may be at varying logical addresses). This makes for
very efficient interprocess communication.
Problem 9.10
Consider a paging system with the page table stored
in memory.
Problem 9.11
What is the effect of allowing two entries in a page
table to point to the same page frame in memory? Explain how this effect could
be used to decrease the amount of time needed to copy a large amount of memory
from one place to another. What effect would updating some byte on the one page
have on the other page
Answer: By allowing two entries in a page table to point to the same
page frame in memory, users can share code and data. If the code is reentrant,
much memory space can be saved through the shared use of large programs such as
text editors, compilers,and database systems. "Copying" large amounts of memory
could be effected by having dif- ferent page tables point to the same memory
location.
However, sharing of nonreentrant code or data means that any user
having access to the code can modify it and these modifications would be
reflected in the other user's "copy."
Problem 9.12
Why segmentation and paging sometimes combined into
one scheme?
Answer:
Segmentation and paging are often combined in order to
improve upon each other. Segmented paging is helpful when the page table becomes
very large. A large contiguous section of the page table that is unused can be
collapsed into a single segment table entry with a page table address of zero.
Pages segmentation handles the case of having very long segments that require a
lot of time for allocation. By paging the segments, we reduce wasted memory due
to external fragmentation as well as simplify the allocation.
Problem 9.13
Describe a mechanism by which one segment could
belong to the address space of two different processes.
Answer:
Since segment tables are a collection of base-limit
registers, segments can be shared when entries in the segment table of two
different jobs point to the same physical location. The two segment tables must
have identical base pointers and the shared segment number must be the same in
the two processes.
Problem 9.14
Explain why it is easier to share a reentrant module
using segmentation than it is to do so when pure paging is used.
Answer:
Since segmentation is based on a logical division of
memory rather that a physical one, segments of any size can be shared with only
one entry in the segment tables of each user. With paging there must be a common
entry in the page tables for each page that is shared.
Problem 9.16
Consider the following segment table:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
What are the physical addresses for the following logical addresses?
a. 0,430
b. 1,10
c. 2,500
d. 3,400
e. 4,112
Answer:
a. 219 + 430 = 649
b. 2300 + 10 = 2310
d. illegal reference, trap to operating system
d. 1327 + 400
= 1727
e. illegal reference, trap to operating system
Problem 9.17
Consider the Intel address translation scheme shown
in Figure 9.20 in OSC (page 292).
Answer:
a. The selector is an index into the segment
descriptor table. The segment descriptor result plus the original offset is used
to produce a linear address with a dir, page, and offset. The dir is an index
into a page directory. The entry from the page directory selects the page table,
and de page field is an index into the page table. The entry from the page
table, plus the offset, is the physical address.
b. Such a page
translation mechanism offers the flexibility to allow most operating system to
implement their memory scheme in hardware, instead of having to implement some
parts in hardware and some in software. Because it can be done in hardware it is
more efficient (and the kernel is simpler).
c. Address
translation can take longer due to the multiple table lookups it can invoke.
Caches help, but there will still be cache misses.
-->