uocis  CIS 415 Operating Systems - Spring 2003
 Navigate

Discussion: Week 5

Back to problems

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
r1r2r3 r1r2r3 r1r2r3
P1020121 101
P2100130 030
P3100101 001
P4000020 020

Determine which resources are still available and fill in the Still Needs matrix.
Available resources: 0×r1, 1×r2, 1×r3

What state (safe/unsafe/deadlocked) would the system be in if it were to immediately grant these resource requests?

  1. P3 requests 1×r3
    Safe: P3 can now run to completion, freeing up the resources that P1 requires. After P1 runs, both P2 or P4 can run to completion one after the other.
  2. P1 requests 1×r3
    Unsafe and possibly deadlocked: No process can safely run to completion because there are not enough resources available to fill the maximum request of any process. The system is deadlocked if no process will terminate before requesting its maximum allocation.
  3. P4 requests 1×r2
    Safe: This has the same safe sequence of execution as problem 1, except that P4 must run before P2.

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.
In this particular example, E is placed after A, and F is placed after B, no matter what scheme is used.

  1. Draw the final state of the system if the following sequence of requests is made under:
    1. dynamic partitioning first-fit
      After A and B are freed, G is allocated in the first hole, which eliminates the only large enough hole for H. In order to accomodate H, compaction is required.
      G: 3K (2K free) E: 3K (3K free) F: 3K (1K free) C: 4K (4K free) D
      1K

    2. dynamic partitioning next-fit
      After A and B are freed, G is allocated in the first > 3K hole after F, and H is placed in the first hole.
      H: 5K E: 3K (3K free) F: 3K (1K free) C: 4K G: 3K (1K free) D
      1K

    3. dynamic partitioning best-fit
      After A and B are freed, G is allocated in the only 3K hole, and H is placed in the first hole.
      H: 5K E: 3K G: 3K F: 3K (1K free) C: 4K (4K free) D
      1K

    4. simple paging with 1 frame = 1K using a first-fit placement algorithm
      The processes are placed in the same places as in (a.), but process H (shown in dark gray) can fit without compaction by being split up.
      G G G H H E E E H H H F F F   C C C C  
                    		      D

    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?
      A: base = 0000000000000000 (0000h=00K), bounds = 0001010000000000 (1400h=05K)
      B: base = 0010000000000000 (2000h=08K), bounds = 0010110000000000 (2C00h=11K)
      C: base = 0011110000000000 (3C00h=15K), bounds = 0100110000000000 (4C00h=19K)
      D: base = 0101110000000000 (5C00h=23K), bounds = 0110000000000000 (6000h=24K)

    2. Translate the following logical addresses into physical addresses and check for validity:
      1. Process A, address 85Ah (0000100001011010)
        physical = A.base + logical = 0000h + 085Ah = 085Ah
        Check against A.bounds: 085Ah < 1400h.
        Check against A.base: 085A > 0000h. Valid.

      2. Process B, address BFFh (0000101111111111)
        physical = B.base + logical = 2000h + 0BFFh = 2BFFh
        Check against B.bounds: 2BFFh < 2C00h.
        Check against B.base: 2BFF > 2C00h. Valid.

      3. Process D, address 400h (0000010000000000)
        physical = D.base + logical = 5C00h + 0400h = 6000h
        Check against D.bounds: 6000h > 6000h. Not valid.

      4. Process C, address FFFFh (1111111111111111) - use 16-bit math
        physical = C.base + logical = 3C00h + FFFFh = 3BFFh (overflow)
        Check against C.bounds: 3BFFh < 4C00h. However:
        Check against C.base: 3BFFh < 3C00h. Not valid.

  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.
      EFGH
      0
      1
      2
      5
      6
      7
      		 
      0
      1
      2
      11
      12
      13
      		 
      0
      1
      2
      0
      1
      2
      		 
      0
      1
      2
      3
      4
      3
      4
      8
      9
      10
      		 
    2. Translate the following logical addresses into physical addresses and check for validity:
      1. Process E, address C12h (0000110000010010)
        Page = 000011 (3), Offset = 0000010010 (18)
        Page 3 doesn't exist for E. Not valid.

      2. Process H, address 7FFh (0000011111111111)
        Page = 000001 (1), Offset = 1111111111 (1023)
        Page 1 = frame 4 (000100). Address = frame:offset = 0001001111111111. Valid.

      3. Process H, address 800h (0000100000000000)
        Page = 000010 (2), Offset = 0000000000 (0)
        Page 2 = frame 001000 (8). Address = frame:offset = 0010000000000000. Valid.

      Notice that though the logical addresses in parts ii. and iii. are consecutive, the physical addresses are not.


Created by: Tim Singer May 5, 2003