CIS 415 Operating Systems - Spring 2003

Discussion: Week 5

Solutions

PART I: Deadlock Avoidance

Consider a system with three resources r1, r2 and r3. This particular system has 2 of r1, 3 of r2 and only 1 of r3. Four processes with the following maximum requests and current allocations are running on the system:

	Current Allocation			Maximum Requests			Still Needs
	r1	r2	r3	r1	r2	r3	r1	r2	r3
P1	0	2	0	1	2	1
P2	1	0	0	1	3	0
P3	1	0	0	1	0	1
P4	0	0	0	0	2	0

Determine which resources are still available and fill in the Still Needs matrix.
What state (safe/unsafe/deadlocked) would the system be in if it were to immediately grant these resource requests?

1. P₃ requests 1×r₃
2. P₁ requests 1×r₃
3. P₄ requests 1×r₂

PART II: Memory Management

Here is a representation of the memory contents of a system with 24K of main memory:

A: 5K

(3K free)

B: 3K

(4K free)

C: 4K

(4K free)

D 1K

Assume process D has the most recent allocation.

1. Draw the final state of the system if the following sequence of requests is made under:
   1. dynamic partitioning first-fit
   2. dynamic partitioning next-fit
   3. dynamic partitioning best-fit
   4. simple paging with 1 frame = 1K using a first-fit placement algorithm

   E requests 3K
   F requests 3K
   A completes and is released
   B completes and is released
   G requests 3K
   H requests 5K

2. Under a dynamic partitioning system with the allocations given for problem 1:
   1. What are the base and bounds registers for processes A, B, C and D?
   2. Translate the following logical addresses into physical addresses and check for validity:
      1. Process A, address 85Ah (0000100001011010)
      2. Process B, address BFFh (0000101111111111)
      3. Process D, address 400h (0000010000000000)
      4. Process C, address FFFFh (1111111111111111) - use 16-bit math
3. Given the final state of the system in your solution to problem 1d:
   1. Draw the page tables for processes E, F, G and H.
   2. Translate the following logical addresses into physical addresses and check for validity:
      1. Process E, address C12h (0000110000010010)
      2. Process H, address 7FFh (0000011111111111)
      3. Process H, address 800h (0000100000000000)