1

Request Current State Final State If Grant or Deny Reason for Final Edge Type
Before Request Request Denial
Request Performed

P4 -> R1 safe Safe Grant - Assignment Edge

P2 -> R1 safe safe Deny P4 holds R1 Request Edge
P2 -> R3 safe safe Grant - Assignment Edge
P1 -> R2 safe safe Grant - Assignment Edge
P5 -> R4 safe Unsafe Deny Cycle Request Edge
P3 -> R1 safe safe Deny P4 holds R1 Assignment Edge
P3 -> R2 safe safe Deny P1 holds R2 Request Edge
P1 -> R4 safe safe Grant - Assignment Edge
P5-> R2 safe safe Deny P1 holds R2 Request Edge

Final Resource Allocation Graph

P11 R2
P51

P21

R3

R1

R4

P31

P41

2
a)
P5 P3 P4 P1 P2

A B C A B C A B C A B C A B C
4 2 1 4 3 2 6 6 4 7 7 5 8 7 7

The system is in safe state.

b) There are two rules;

i. 1. P2 need (7,0,4) > (1,0,2) TRUE , 2. Available (2,0,1) > (1,0,2) FALSE ( then reject the request)

ii. 1. P3 need (3,0,1) > (2,0,1) TRUE , 2. Available (2,0,1) >= (2,0,1) TRUE

NEW SYSTEM

Allocation MAX NEED AVAILABLE

A B C A B C A B C
P1 1 1 1 3 2 5 A B C
2 1 4
P2 1 0 2 8 0 6 0 0 0
7 0 4
P3 2 1 2 3 1 2 1 0 0
P4 2 3 2 4 4 4 2 1 2
P5 2 2 0 3 2 0 1 0 0

iii. 1. P4 need (2,1,2) >(1,0,0) TRUE , 2. Available (2,0,1) > (1,0,0) TRUE

NEW SYSTEM

Allocation MAX NEED AVAILABLE

A B C A B C A B C
A B C
3 2 5 2 1 4 1 0 1
P1 1 1 1
P2 1 0 2 8 0 6 7 0 4
P3 0 1 1 3 1 2 3 0 1
P4 3 3 2 4 4 4 1 1 2
P5 2 2 0 3 2 0 1 0 0

S0, Availables->

P5 P3 P4 P1 P2

A B C A B C A B C A B C A B C
3 2 1 3 3 2 6 6 4 7 7 5 8 7 7

Finally, request is granted.

3
a) First-fit

15KB 10KB 15KB 20KB 5KB 35KB 15KB 25KB 30KB 15KB
P1 P4 P5 P2

NOT: P3 cannot be allocated because no hole large enough.

b) Best-fit

35KB 5KB 20KB 5KB 40KB 10KB 25KB 30KB 15KB

P2 P5 P3 P4 P1

c) Worst-fit

35KB 5KB 25KB 15KB 10KB 25KB 25KB 20KB 10KB 15KB
P2 P1 P4 P5

NOT: P3 cannot be allocated because no hole large enough.

4
a)
Hash = Page Number % 4

Here, Page Number is the first two bits of the logical address and is used to convert this page number
to a frame number in physical memory.

İs
Class
Page Frame İ 0
Number Number the
SEN
0 4
message 1
1 3 OS
exam
2 1

3 0 2

this
hope
2025 3
to
pass 4
welcome
secret
CEN

b)

Logical address Value at physical address

11 01 I
01 01 Hope
01 11 to
00 00 pass
11 11 the
11 01 class

Answer is “I hope to pass the class”

a) Number of pages = Size of the logical address space / Page size

 219 = 231 / 212

b)

Memory required= Number of entries / Size of each entry

219 x 4 KB = 2 MB(221)