Basic
OS concepts
Process
A process is a basic unit of abstraction to build concurrent execution of
multiple programs. A process is a sequential program in
execution. A program is a "static" part whereas a process is a dynamic
part. One program can be executed by many processes. A process
consists of : code segment, data segment, stack segment. They
can be shared or separated. When they are shared, only a single
address space is needed hence the implementation is simple.
Threads and Objects are alternatives to Process in many OS.
To achieve concurrency using one processor, each process will be allocated a
slice of time for its execution. All processes will be scheduled to be
executed by time multiplexing. For example two processes A, B.
They will be executed like this:
A B
A B A B A B
A simple programming abstraction to achieve this is "co-routine" where A
call B, B call A by not starting A at the beginning but resume the execution
at the point where A has stopped.
To manage multiple programs, a scheduler keeps a list of all
processes. When starting an execution of a time slice, a process will
be selected to be run according to some policy. A process is run
until it is:
1 time-out using up its
allotted time
2 blocked the process requests a resource and has to
wait for it.
3 terminated the process runs to its completion.
We can model the behaviour of the process as follows:
state
event
next state
READY
task-switch
RUNNING
RUNNING
time-out
READY
RUNNING
terminate
DEAD
RUNNING
block
WAIT
WAIT
wakeup
READY
To execute a process on a processor, computation state, i.e. all
variables pertain to that process must be save/restore properly upon task
switching. These are pc, fp, sp, including separate stack segment for
each process. Code segment is naturally shared. Data segment can be
shared using single address space. These information is stored in a
process descriptor (or called process control block etc.). Task-switch
is defined as:
task-switch
save current state,
set it to READY
select next process
make it runnable, set
it to RUNNING
To understand how a process requests a resource we first study how a
resource is shared.
Semaphore
In sharing a resource, it is necessary to ensure "mutual exclusion".
That is, during a period of one process using that resource, other process
that also want that resource must wait. Dijkstra invented "semaphore"
(1965) to achieve this "mutex" behaviour. A semaphore is a
variable (can be binary, 0/1 or an integer) associated with a resource,
indicates availability of the resource to the process that requested
it. Two operations are defined on a semaphore: wait, signal
(originally Dijkstra called it P, V).
Associated with each semaphore is a waiting list of the process that wait on
this semaphore. They are defined as follows:
Wait
sem
value = value - 1
if value < 0
block this process, set it to WAIT
put
this process to the waiting list
Signal sem
value = value + 1
if value <= 0
remove a waiting process from the waiting list
wakeup that process
These two operations must be atomic, that is, they must run to completion
without interruption. (can not task switch in between)
How to use a semaphore
For resource sharing, we can let only one process to acquire it, all other
processes that request that resource will be waiting in the waiting
list. The code where this mutual exclusion is required is said
to be "critical section". A semaphore is used to protect this
section. Start with sem = 1
....
// critical section
wait sem
... code to access shared resource
signal sem
The first process that enters the critical section will "close the
door". After it exits this section, it "open the door" to let other
process in. A semaphore is the basis that other mechanism can be
built such as process synchronisation or process communication.
Process synchronisation
When two processes want to "synchronise" at some point, two semaphores
can be used to achieve it. Let two processes be A, B. Assume A
arrives to the synchronise point before B. Then A must wait for B and
vice versa if B arrives before A.
A
B
signal
sem1 wait sem1
wait
sem2 signal sem2
The sequence can be rearranged and the behaviour is still correct:
A
B
signal
sem1 signal sem2
wait
sem2 wait sem1
Example
Use semaphore to protect share resource and synchronise between two
concurrent processes: writer() and reader()
// empty, full, mutex -- semaphores
// shareVar
shareVar = 0
empty = initsem()
full = initsem()
mutex = initsem()
writer()
i = 0
while( i < 3 )
wait(empty)
wait(mutex)
shareVar = shareVar + 1
signal(mutex)
signal(full)
i = i + 1
reader()
i = 0
while( i < 3 )
wait(full)
wait(mutex)
print("+",shareVar)
signal(mutex)
signal(empty)
i = i + 1
Think how to do a synchronisation of more than two processes. For
n-processes, how many semaphores are needed?
last update 8 Apr 2016