Resource request alg

1. If request <= need, goto step 2

2. If request <= Available goto step3
3. Allocation= Allocation + Request
4. Available= Available-request
5. Need= Need- request.
Apply bankers algorithm

process Allocation request Avalable

P1 010 753 230 743
P2 302 322 020
P3 302 902 600
P4 211 222 011
P5 002 433 431

P2 --- requesting for resource—os will decide allocation of

resource is possible or not
P2--- request – 102
1. 102<=122(T)
2. 102<=332(t)
3. Allocation= 200+102=302
4. Available=332-102=230
 5. Need=122-102=020
1. Work=230
f f f f f

2. A)finish[1]= false (T)

b) 743<=230(F)
p1-has to wait
p2
a)finish[2]=false(t)
b)020<=230(t)
3. work=230+302=532
4. finish[2]=true
f T f f F
P3:
a) finish[3]=false(t)
b) 600<=532(f)
P3 has to wait.
P4:
a) finish[4]=false(t)
b) 011<=532(t)
 3. Allocation=211+532=743
4. Finish[4]=true
f t f t F

P5:
a)finish[5]=false(t)
b) 431<=743(t)
3. allocation=002+743=745
Finish[5]=true
f t f t t

P1:
a)finish[1]=false(t)
b) 743<=745(t)
3. allocation = 010+745=755
4. finish[1]=true;
t t f t T
P2:
a) Finish[2]=false{f}
P3
 a) Finish[3]=false(t)
b) 600<=755(t)
3. allocation=302+755=1057
Finish[3]=true
t t t t T
P4:
a) Finish[4]= false(f)
P5:
a) Finish[5]=false(f)

P1 request = 102
1 0 2<= 1 2 2(T)

1 0 2 <= 3 3 2(T)
Allocation= 200+102 = 302
Avalable= 332-102= 230
Need= 122-102= 020
P1 --- 2 R
P2 ---- 3 R

Tuesday(18-1-22)

Absenties: B1,B3,C4,C8,D1,D6,E3,E4,F0,32,35,37,40

Tuesday(18-1-22) Archana, Mohan

process Allocation request Avalable

P1 010 000 000
P2 302 200
P3 303 000
P4 211 100
P5 002 002

A = 8, b=2, c=6
Avalable(A) = Total instancs- Allocated
 7-7=0
Avalable(B)= 2-2=0
Avalable(C) = 6-6=0

1. Work= 0 0 0
F F F F F

2. P1: a) True
b)0 0 0 <= 0 0 0(t)
3. work= 0 0 0 + 0 1 0=0 1 0
T F F F F

P2: a)True
b)2 0 2 <=0 1 0 (f)
p2 to wait

p3: a)True
b)0 0 0<= 0 1 0(T)
work= 0 1 0 + 3 0 3 = 3 1 3
T F T F F

P4: a) true
b)1 0 0 <= 3 13(t)
work= 313+211 = 5 2 4
 T F T T F

P5: a)true
b)002<=524{T}
work= 524+002= 526
T F T T T

P1 a)false
P2 a) true
b) 202<=526(t)
work = 526+200= 726 – stop the process
T T F T T

a) 10 process – 3 process deadlock – abort all 3 processes

b) P1-deadlock-- Abort
c) P2- deadlock--Abort
d) P3- deadlock –Abort
P2, p3 deadlock detection alg

Deadlock Recovery
 Once deadlock occurred then how to come from
deadlock
1. Process Termination
2. Resource preemption

Process Termination
a) Abort all processes suffering from deadlock
Ex 10 processes --- 3 process – deadlock--- abort all
the 3 processes.
b)Abort 1 process one by one

Ex 10 processes --- 3 process – deadlock

P1 --- Abort
P2
P3
Apply deadlock detection alg--- identify process
suffering from deadlock.
P2,p3 – deadlock
P2 ---Abort
Apply deadlock detection alg--- identify process
suffering from deadlock.
 P3,p4
P3—Abort
Apply deadlock detection alg--- identify process
suffering from deadlock.

Resource preemption
Release the resource and allocate to another process
who needsit.
3 issues
1. Select the victm
2. Rollback
3. Starvation

Select the victm : select- process- release its resources.

A) Low priority prcess is made to release resources
B)Process which has executed for less amount of time
A)Ex P1—3 ---90%
P2—4 --- 88%
P3—1--- 70%
Roll Back: if any deadlock occurred, the process has
to execute again from starting.

Starvation: process waiting for longer time abort it.

CRITICAL SECTION
Room
Process who are sharing their memory.(data,
variables, code…)
Producer – consumer problem:
Share one common variable :: count
Producer –count++
Consumer—count—
Producer –count+ at same time consumer – count
—

Lead to wrong results

Solution for CS
1. software sol or App—Peterson solution
2.Hardware sol or app—Syncronization hardware.
 Achieve CS satisfy 3 conditions/issues
1. Mutual Exclusion
2. Progress
3. Bounded waiting.
Def: It isa part of the program where shared memory is
accessed.

count
p3

Critical section
Count – shared variable
P1,p2, p3
Afetr some time p3 – count
Issues
1. Mutual Exclusion: only one process can you critical section
at a time. If another process wants to use CR when any
process is inside , then that process has to wait.
P1—cr -- p2,p3 –wait
P2—cr—p1,p3 – wait
 P3—cr—p1,p2 –wait.

2. Progress: p1,p2,p3,p4,p5
Os –decide—which process should cr—finite amount of
time.
3. Bounded Wating:
P2

P2—waiting—request –cs--- starvation

P1—request –cs(3-1=2,2-1=1,1-1=0)
Limit -3

Put a limit that a process can enter into cs when another

process is waiting.
Structure of cs
Entry section:
a) collect the request of the process---use CS
ex: p1,p2,p3 ---cr –request
p1- entry section—wait
p2-entry section—wait
p3-entry section –wait.
b) P0—cr—entry section will lock the cs
2.Critical section: shared memory
3. Exit section : p0 will come out of CS.

4. Remainder section –optional section

1. Software app—Person solution

Requirements—2 process--- cs—p0,p1
Input
turn=1—process p1 can use cs
turn=0—process p0 can use cs
flag[2]=true/false
flag[0]=true—p0 is interested in using cs
flag[0]=false ---p0 is not interested in using cs
flag[1]= true—p1 is interested in using cs
flag[1]=false ---p1 is not interested in using cs
structure
while(true)--- p0,p1 i=0,j=1,p1=true,p0=false;
{
Flag[i]=true;---flag[0]=true;
Turn=j; -- turn=1;p1
While(flag[j]==true(t) && turn==j);--true—respective process
has to wait.
While(flag[j]==true(t) && turn==j);--false—respective process
can use CS.

Condition(t)—p1---p0 is already using CS and so p1 has to wait.

Condition(F)—p1--- p1 can you cs. cs is free
Critical section
Flag[0]=false;
}

P0

While condition for p1(t)---wait

P1
Process p1 – while condition(f)—p1 use cs---p0=false.

P1

While condition for p0(t)---wait

P0

Process p0 – while condition(f)—p0 use cs---p1=false.

3 isuues
1. Mutual exclusion---
P0(t)---p1(cs)—p0(wait)
P1(t)—p0(CS)—P1(wait)
2. Progress—satisfied.
3. Bounded Waiting.---2 process
P0-waiting then p1—cs
P1-waiting then p0-cs
Satisfied.
Hardware app—synchronization of hardware
Using machine instructuions.
1. swap()
2. Test and set()----automic instructions--- all instructions
will be executed at once.

Swap()

Void swap(boolen *a, boolen *b)

{
Boolean=temp;
Temp=*a;
*a=*b;
*b=temp;
}
Do
{
Key= true;
While(key== true)(f)
Swap(&lock,&key);
Critical section;--p0
Lock=false;
}while(true);

lock false
 p0: Key=false

3 issues
Satisfies on mutual exclusion
Not satisfy bounded waiting.

Test and set

Test and set – machine instruction

Boolean testandset(Boolean *target)

Boolen rv= *target;

*target=true;

Retuen rv;

Do

Waiting[i]=true;

Key=true;

While(waiting[i] && key)

Key= testandset(&lock);
//critical section

J=(i+1)%n

While((j!=i)&& !waiting[j])

J=(j+1)%n

If(j==i)

Lock=false;

Else

Waiting[j]=false;

}while(true);

Two shared variables

1. Waiting[n]= false;
2. Boolean lock;

f f f f f

5 process
P0,p1,p2,p3,p4,p5
P0:
T f f f f

true
 key
While(waiting[i] && key)---t && t(t)

Key=false;
true

Lock,target
rv= false
While(waiting[i] && key)t && false---false---respective process can
you cs

P0

P1:
t t f f F
true

While(waiting[i] && key)—t && t—true

Key= testandset(&lock);

Rv=true;
true
 Lock,target
Key=true;
While(waiting[i] && key)—t && t –T---p1 has to wait, because some
other process is in cs.

Bouded waiting

Case1. P1 is interested

Case 2 : p1 is not interested

Case 3: other process are not interested

Case1. P1 is interested

I=0—pointing to process p0

//J=1—pointing to process p1

N—number of process interested in using critical section--5

Exit section

t t f f F

J=(0+1)%5=1%5=1 j=1

While((j!=i)&& !waiting[j])—while((1!=0) &&!(true)

while((1!=0)&&false)T && falsefalse

indicates that p1 is interested to enter into CS

If(j==i)-if(1==0)(false)
Waiting[1]=false;

t f f f F

Entery section

Waiting[0]=true;

Key= true;

While(waiting[i] && key)---t && tt

Key=testandset(&lock)—lock=true

Key=true

While(waiting[i] && key) t && tt—p0waiting or using CS

P1:

f t f f f
Waiting[1]=true

Key=true;

While(waiting[i] && key)t&&T->

Key =testandset(&lock)--
true

Key=false

While(waiting[i] && key)--false

Case 2 p1 is not interested and p2 is interested, p0 already using CS

t f t f F
I=0

J=(i+0)%n—(1+0)%5=1

While((j!=i)&& !waiting[j])

While((1!=0)&& !(false))

While((1!=0)&& true)—T && T – True

J=(j+1)%n—(1+1)%5---2%5=2—indicates that process p2 is interested

in using CS

If(j==i)—if(2==0)(false)

Waiting[2]=false;

t f f f F

Case 3 : no other process is interested—p0 is interested in using cs

n=1

J=(i+1)%n—(0+1)%1=1%1=0

J=0;

While((j!=i)&& !waiting[j])

While((0!=0)&& !true)—(while( 0!=0 && false)—false

true
If(0==0)(T)

Lock=false;

false

P0 is the only process to enter into CS again and again

From case 1 and case2 Bounded waiting is also satisfied.

\

Semaphores: shared integer variable

Intilialise and acces the semaphore--- 2 operations
1. Wait()
2. Signal()
Ex: p0,p1,mutex=1;
P0:
Wait(mutex);
Wait(mutex) s—semaphore variable;---- entry section

While(1<=0); true- process remains in the loop

False – process will go to the next step;

S--;=s=0

Critical section---p0 can use CS

Signal(mutex=0);

Signal(S) ---exit section of CS

S++; s=1;

Mutex=1.

P1: mutex=0;
Wait(mutex)
Wait(mutex) s—semaphore variable;---- entry section

While(0<=0); true- process remains in the loop

False – process will go to the next step;

S--;=

P1 has to wait or p0 is using CS

Monitors: replacement of semaphore

Semaphore is created by operating

Monitors are created by programming languages—java

C – doesnot support monitors.

Monitor:

Acitivate only one process at a time in the monitor

Prc1,prc2,prc3

Syntax of monitor:

Data members and functions

Monitor monitor name

Shared variable declaration;

Procedure p1(…)---here use Prc1

}
Procedure p2(..)

Procedure p3(..)

----

}
Procedure initialized(..)
{
Initialize code; -- shared variables which are accessed by the
processes;
}

Schematic view of monitor

3 parts
1. Shared data
2. Procedures
3. Initialization code
Conditional variable:
We can access wait and signal
X,Y
X.wait, X.signal
y.wait, y.signal
x.wait—the execution of process will stop and the process enters
the waiting state.
x.signal—the execution of process will resume

IPC: device where two process can share their information and
also communicate
1. Single system –shared memory
2.
3. Different Systems ---two process present in two different
systems

Communicate
1. Pipes
2. FIFO
3. MESSAGE QUEUE
PIPES:
CREATE A PIPE
PIPE(int fd[2])—fd = file descriptor
Success = 0;
Failure =-1;--- perror();
Fd[0]=read
Fd[1]=write
Write()-
Success= return the count of words which are written
Failure- -1
At a time is writng = 512 bytes
Read()-
Success= return the count of words which are read
Failure= -1
At a reading = 1 byte
Message Queue:
Linked list where group of messages will be flowing from one
process to another using kernel
Msgget()- new queue or open an existing queue
Msgnd()- write messages
Msgrcv()- read the messages
Msgctl() – control of operations on message queue
Assignment
Batch1—important questions
Batch2- graphical representation
Batch3-summary
Batch4-ppt
 Unit 4
Programs execution or storing of files
Types
1. Primary
2. Secondary
3. Registers
4. Cache

Memory management

How the memory is utilizesd.

P1,p2,p3—mm
P1 and p2 active

Address Binding
Mapping a program to memory –binding
3 different forms
1. Compile time address binding
2. Load time address binding
3. Execution or dynamic address binding

Compile time address binding

Program the memory how much is needed will be exactly
provided
prog 1 : 5 mb of mem
5mb memory provided by os.

2.Load time address binding

When program is loaded only the memory will be allocated.
3,Execution time address binding
When prog is under execution add can be relocated

Logical address Physical address space

space(virtual)
Generated by CPU Capacity of memory present
in the system—taken care
by memory unit
It is a set of all logical addres It is a set of all physical
generated by the program addres generated by the
program
Note: logical and physical address are same at compile and
load time
Prg1 – 5mb
Logical and physical address will be changing at execution