1. Terminologies

aInternal Fragmentation

A small chunk of “unused” memory internal to a partition

bExternal Fragmentation

It occurs as small chunks of memory accumulate as a by-product of partitioning due to imperfect fits.

cAbsolute Code

Code that have address binding at the compile time.

dDeadlock

Processes are in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set.

eOverlays

Keep in memory only those instructions and data needed at any given time. When other instructions and data are needed. They are loaded into space occupied previously by those that are no longer needed.

fInverted page Table

Each entry in an inverted page table (shared by all processes) corresponds to a physical frame: Virtual Address: <Process ID, Page Number, Offset>

gDeadlock Prevention Method

Fail at least one of the necessary conditions!

hPure Demand Paging

Never bring in a page into the memory until it is required.

  1. Given the following snapshot of the system: Please determine whether there exists any safe sequence. If there is any one, shows me one.

Allocation
A B C / Max
A B C / Available
A B C
P0 / 0 0 0 / 7 5 3 / 3 3 0
P1 / 2 1 2 / 3 2 2
P2 / 3 0 2 / 9 0 2
P3 / 2 1 1 / 2 2 2
P4 / 0 0 2 / 4 3 3

Sol: a. Yes

b. P1--> P3 P0  P2 P4

  1. Given a computer system with a 32-bit virtual address, 1KB pages, and 4 bytes per page entry, suppose that the maximum physical memory size is 16GB and the system is byte-addressable. Let paging be implemented for the system. Please answer the following questions:

aWhat is the number of bits for physical addresses? What is the maximum number of frames for the system?

bSuppose that TLB is adopted, and a single-level paging is adopted. Let the memory access time and TLB access be 100ns and 20ns, respectively. Suppose that the TLB hit ratio is 98%. What is the effective memory access time?

cSuppose that multi-level paging is adopted! How many levels do we have? Let the memory access time and TLB access time be 98%. What is the effective memory access time?

dSuppose that the virtual memory of the computer system adopts demand paging. Suppose that the effective memory access time of the computer system without any page fault be 100ns, and the service time for a page fault be 15ms. What should be the page fault rate such that the effective memory access time under demand paging is no more than 120ns?

Sol: a. 34 bits, 224 frames

b. EMAT = 0.98*(20+100)+0.02*(20+100+100) ns

c. Levels = 3, EMAT = 0.98 * (20+100)+0.02*(20+100+100+100+100) ns

d. 120>=(1-pfr)*100+pfr*15000000 ns

  1. There are three possible binding times considered for address bindings: compiler time, load time, and run time. Under which binding times, each logical address is equal to its corresponding physical address? Could we run compacting for contiguous memory allocation (multiple users) when address binding time is at load time? Why?

Sol: a. compile time and load time.

b. No, It is because each logical address must be equal to its corresponding physical address. No moving of code or data segments is possible.

  1. There are 4 necessary conditions for a deadlock. What are they? What are the differences on the concepts between deadlock prevention protocols and deadlock avoidance protocols.

Sol: a. mutual exclusion, hold and wait, no preemption, circular wait.

b. Deadlock prevention: a set of methods to ensure that a least one of the necessary deadlock conditions can not hold. Deadlock avoidance requires that the OS be given in advance addition information concerning which resources a process will request. With that knowledge, the system makes sure that the system always stays at a safe state.

  1. Please answer the following questions on memory management.

aAddress binding could be done at the compile time, load time, or execution time. Please list any of them that results in the collapsing of logical and physical address space.

bIt is necessary that a physical memory space in demand paging is always larger than a logical memory space? Please explain.

cWhat is the major difference between the swapper and the page?

dWhat is major problem for static partitions in contiguous allocation and multi-user support?

Sol: a. Compile time & load time binding schemes results in the collapsing of logical and physical address spaces.

b. No! It depends on their numbers of address bits!

c. The swapper swaps in/out an entire process, while the pager works on the swapping of pages.

d. Internal fragmentation gives poor memory utilization!

  1. Please compare paging and segmentation in terms of fragmentation, sharing of code/data, and translation of logical/physical address. What is “paged segments”

Sol:

paging / segmentation
Fragmentation / Internal / External
Sharing of code/data / Pages do not reflect the units in sharing / Segment is a logical unit
Address translation / Offset must be checked against segment size

Paged segment – divide segment further into pages. Segment need not be in contiguous memory.

  1. Deadlocks could be handled in many ways. Please illustrate one deadlock prevention method based on condition “Hold - and -Wait”. What two problems does it often have?

Sol: Hold - and –Wait

  1. Acquire all needed resources before its execution.
  2. Release allocated resources before request additional resources!

Problem: Low Resource Utilization, Starvation.

  1. Dynamic partitioning provides better utilization for multiple users in contiguous memory allocation. External fragmentation seems being a major problem. Please define “external fragmentation”. There could also exist some internal fragmentation problem. Why? Compacting seems being a way to resolve the external fragmentation problem. What is “compacting”? Is there any requirement on compacting in terms of address binding?

Sol: a. External fragmentation: External fragmentation occurs as small chunks of memory accumulate as a by-product of partitioning due to imperfect fits.

b. Reason for internal fragmentation: Reduce free space maintenance cost.

c. Compact all free areas into one contiguous region.

d. Requires user processes to be relocatable.