1. Compare the main memory organization schemes of contiguous-memory allocation,
ID: 3824610 • Letter: 1
Question
1. Compare the main memory organization schemes of contiguous-memory allocation, pure segmentation, and pure pagingwith respect to the following issues (HINT: use a table)
a. external fragmentation, b. internal fragmentation, c. ability to share code across processes
2. Consider a paging system with the page table stored in memory.
a. If a memory reference takes 110 nanoseconds, how long does a paged memory reference take?
b. If we add associative registers, and 80 percent of all page-table references are found in the associative registers(TLB), what is the effective memory reference time? (Assume that finding a page-table entry in the associativeregisters takes 15 ns, if the entry is there.)
3. Consider the following reference string:
a. How many page faults would this string produce under the FIFO page replacement strategy with three frames?
b. How many page faults would this string produce under the OPT replacement strategy with three frames?
c. How many page faults would this string produce under the LRU replacement strategy with three frames?
4. Briefly discuss the reason systems do not implement the Optimal page replacement algorithm
5. Briefly describe the enhanced second chance algorithm and compare it to FIFO and LRU.
6. What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system
do to eliminate this problem?
7. The CPU has a logical address format with 4 bits for the page number and 2 bits for the offset. The page table for aprocess is:Page frame
15 6 I
Map the following logical addresses to physical addresses: (8 frames – 3 bits for frame #)
Logical Address Physical Address
1000 11
0011 11
1111 01
0110 10
0100 11
0010 10
1110 11
8. Consider a demand paging virtual memory system with 24 bit virtual address space, page size is (8KB or 2^13) andthe system has 8 MB of main memory. Assume the page table is single level and stored in memory.
a. When we split a logical address into page number and offset within the page, how many bits are used for the
page number, and how many bits are used for the offset?
b. Assuming page table entries are 4 bytes each and a single level page table is used, how many bytes are requiredto store a page table?
c. If the OS reserves 1 MB (128 frames) of physical memory for kernel code, buffers, etc., how many physicalframes are left for demand paging?
d. Suppose at some point in time our TLB contains the entries:
The user attempts to access the logical address 0000 0000 1000 1011 0011 0100. Is this a TLB miss? Briefly explain.
e. What is the physical address?
9. Suppose that a disk drive has 2000 cylinders, numbered 0 to 1999. The drive is currently serving a request at cylinder130, and the previous request was at cylinder 124. The queue of pending requests, in order, is
84, 1110, 30, 825, 200, 120, 980, 515, 33, 300
Starting from the current head position, what is the access sequence and the total distance (in cylinders) that the diskarm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?
a. FCFS
b. SSTF
c. SCAN
d. LOOK
e. C-SCAN
f. C-LOOK
3 1 4 3 1 5 2 3 4 5 2 1 3 2 1Explanation / Answer
1)
a). External fragmentation is
Contiguous allocation with the fixed size
partions are not suffer from the external fragmentation, but
contiguous allocation with variable sized partitions. Pure
paging does not suffer from external fragmentation, since
partitions and pages are fixed in size. Segmentation does suffer
from external fragmentation.
b)Internal fragmentation
internal fragmentation does not suffers segmentation and variable-sized
partitions, since by definition, a segment/partition is exactly as large as it needs to
be. However, the contiguous allocation with fixed size partitions and
paging both may suffering from internal fragmentation when
partitions and pages are not completely filled.
c.) Ability to share code across processes
Contiguous allocation
provides no support for the code sharing.
In segmentation, as long as the segments of a process do not mix
text and data, we can easily share code between processes.
We adjust the segment tables of the each process point to the
same segment of code in memory. For security reasons, however,
it would probably be desirable to have some method of
preventing processes from modifying the code, since doing so would
allow one process to change the code executed by another.
In pure paging, code can be shared across processes simply by
sharing page frames. To do this, adjust the page tables of the
two processes so that their different logical pages map to the
same physical page frame. However, we do need to make certain
that no page frame contains the data, which should not be
shared. We could accomplish this by, for example, padding the
last page of the text segment of the process with
no-op
machine
language instructions
contiguous memory allocation:
the size of the partition
in which a process resides was fixed, the compiler (or loader, if
sophisticated enough must determine at compile time/load time the
maximum distance between the both of stack and the heap in order to
calculate the size of the process address space. If this space is
made too large, memory will be wasted. If the space is too small,
the stack and the heap will collide and corrupt the data or crash the
program.
In addition, the space between the top of the (downward
growing) stack and the (upward growing) heap was unused, leading
to wasted memory or dumped memory.
pure segmentation:
If the stack and heap are the placed in the same
segment the memory will either be wasted, or we risk the possibility
of a stack/heap collision. If the stack and heap are placed in
different segments, we may be able to expand the heap, but the
maximum stack size is fixed at load time, since the stack grows
downward. One solution on a system that uses pure
segmentation is to redefine the stack to grow upwards from the
bottom of its segment.
pure paging:
Pure paging suffers from the same problem as
contiguous memory allocation. since we need to allocate the frame
for each page of the process, even if the page is unused. We can
solve this problem by combining pure paging with a scheme
called “virtual memory”.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.