NATIONAL ECONOMICS UNIVERSITY

SCHOOL OF INFORMATION TECHNOLOGY AND DIGITAL ECONOMICS

CHAPTER 2
PROCESS MANAGEMENT
OVERVIEW

 Process Concept
 Process Scheduling
 Interprocess Communication
 Process Synchronization

2
PROCESS CONCEPT

 An operating system executes a variety of programs:

 Batch system – jobs
 Time-shared systems – user programs or tasks
 The terms job and process almost interchangeably.
 Process – a program in execution; process execution must progress in sequential
fashion.
 A process includes:
 program counter
 stack
 data section

3
PROGRAM VS PROCESS

4
PROGRAM VS PROCESS

 Program is a passive entity, a process is an active one.

 A program becomes a process when an executable file is loaded into
memory.
 Two processes may be associated with the same program.
 Process itself can be an execution environment for other code.

5
PROCESS STATE

 As a process executes, it changes state

 new: The process is being created.
 ready: The process is waiting to be assigned to a process.
 running: Instructions are being executed.
 waiting: The process is waiting for some event to occur.
 terminated: The process has finished execution.

6
DIAGRAM OF PROCESS STATE

7
PROCESS CONTROL BLOCK (PCB)

Information associated with each process:

 Process state
 Program counter
 CPU registers
 CPU scheduling information
 Memory-management information
 Accounting information
 I/O status information

8
PROCESS CONTROL BLOCK (PCB)

9
CPU SWITCH FROM PROCESS TO PROCESS

10
PROCESS SCHEDULING QUEUES

 Job queue – set of all processes in the system.

 Ready queue – set of all processes residing in main memory, ready
and waiting to execute.
 Device queues – set of processes waiting for an I/O device.
 Process migration between the various queues.

11
READY QUEUE AND VARIOUS I/O DEVICE QUEUES

12
PROCESS SCHEDULING QUEUES

 A new process is initially put in the ready queue. It waits there until it
is selected for execution. Once the process is allocated the CPU and
is executing, one of several events could occur:
 The process could issue an I/O request and then be placed in an I/O queue.
 The process could create a new child process and wait for the child’s
termination.
 The process could be removed forcibly from the CPU, as a result of an interrupt,
and be put back in the ready queue.

13
REPRESENTATION OF PROCESS SCHEDULING

14
SCHEDULERS

 Long-term scheduler (or job scheduler) – selects which processes

should be brought into the ready queue.
 Short-term scheduler (or CPU scheduler) – selects which process
should be executed next and allocates CPU.

15
SCHEDULERS

 The primary distinction between these two schedulers lies in

frequency of execution
 Short-term scheduler is invoked very frequently (milliseconds) 
(must be fast).
 Long-term scheduler is invoked very infrequently (seconds, minutes)
 (may be slow).
 The long-term scheduler controls the degree of multiprogramming.

16
SCHEDULERS

 In general, most processes can be described as either I/O bound or

CPU bound:
 An I/O-bound process is one that spends more of its time doing I/O than it
spends doing computations.
 A CPU-bound process, in contrast, generates I/O requests infrequently, using
more of its time doing computations.
 It is important that the long-term scheduler select a good process
mix of I/O-bound and CPU-bound processes

17
ADDITION OF MEDIUM TERM SCHEDULING

18
CONTEXT SWITCH

 The context is represented in the PCB of the process.

 It includes the value of the CPU registers, the process state, and
memory-management information.
 Generically, we perform a state save of the current state of the
CPU, and then a state restore to resume operations.

19
PROCESS CREATION

 Parent process creates children processes, which, in turn create other

processes, forming a tree of processes.
 Resource sharing
 Parent and children share all resources.
 Children share subset of parent’s resources.
 Parent and child share no resources.
 Execution
 Parent and children execute concurrently.
 Parent waits until children terminate.

20
PROCESS CREATION (CONT.)

 Address space
 Child duplicate of parent.
 Child has a program loaded into it.

 UNIX examples:
 fork system call creates new process
 execve system call used after a fork to replace the process’ memory space
with a new program.

21
A TREE OF PROCESSES ON A TYPICAL UNIX SYSTEM

22
PROCESS CREATION (CONT.)

 On UNIX systems, we can obtain a listing of processes by using the

ps command. For example, the command ps –el will list complete
information for all processes currently active in the system
 pstree is a UNIX command that shows the running processes

23
UNISTD C LIBRARY

 getpid()
 getppid()
 fork()
 wait()

24
UNIX PROCESS CREATION

#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
int main() {
pid_t pid;
pid = fork(); /* fork a child process */
if (pid < 0) { /* error occurred */
fprintf(stderr, "Fork Failed");
return 1;
}
else if (pid == 0) { /* child process */
execlp("/bin/ls","ls",NULL);
}
else { /* parent process */
/* parent will wait for the child to complete */
wait(NULL);
printf("Child Complete");
}
return 0;
}

25
PROCESS CREATION USING THE FORK() SYSTEM CALL

26
PROCESS TERMINATION

 Process executes last statement and asks the operating

system to decide it (exit).
 Output data from child to parent (via wait).
 Process’ resources are deallocated by operating system.
 Parent may terminate execution of children processes (abort).
 Child has exceeded allocated resources.
 Task assigned to child is no longer required.
 Parent is exiting.
 Operating system does not allow child to continue if its parent terminates.
 Cascading termination.
27
WINDOWS PROCESS CREATION

28
OUTLINE

 Scheduling Algorithms
 Interprocess Communication
 Thread
 Process Synchonization
 Deadlocks

29
SCHEDULING ALGORITHMS

 Whenever the CPU becomes idle, the operating system must select
one of the processes in the ready queue to be executed.
 The selection process is carried out by the short-term scheduler,
or CPU scheduler

30
PREEMPTIVE VS NON-PREEMPTIVE SCHEDULING

 Non-preemptive
 The running process keeps the CPU until it voluntarily gives up the CPU
 process exits
 switches to blocked state

 Preemptive:
 The running process can be interrupted and must release the CPU (can be forced to give
up CPU)

31
SCHEDULING CRITERIA

 CPU utilization:In a real system, it should range from 40 percent (for a lightly
loaded system) to 90 percent (for a heavily loaded system).
 Throughput: the number of processes that are completed per time unit
 Turnaround time: The interval from the time of submission of a process to the time
of completion. = waiting to get into memory + waiting in the ready queue +
executing on the CPU + doing I/O.
 Waiting time. is the sum of the periods spent waiting in the ready queue.
 Response time. the time from the submission of a request until the first response is
produced

It is desirable to maximize CPU utilization and throughput and to minimize turnaround

time, waiting time, and response time.
32
SCHEDULING ALGORITHMS

1. First-Come, First-Served Scheduling

Average wating time: (0+24+27)/3 = 17s

33
SCHEDULING ALGORITHMS (CONT)

1. First-Come, First-Served Scheduling (FCFS)

 If the processes arrive in the order P2, P3, P1, however, the results will be as
shown in the following Gantt chart:

Average wating time: (0+3+6)/3 = 3s

34
SCHEDULING ALGORITHMS (CONT)

1. First-Come, First-Served Scheduling (FCFS)

 Non-preemptive
 There is a convoy effect as all the other processes wait for the one big process
to get off the CPU

35
SCHEDULING ALGORITHMS (CONT)

2. Shortest-Job-First Scheduling (SJF)

 Waiting time = (3+16+9+0)/4 = 7

36
SCHEDULING ALGORITHMS (CONT)

2. Shortest-Job-First Scheduling (SJF):

 Non-preemptive scheduling
 The real difficulty with the SJF algorithm is knowing the length of the next CPU
request.
 For long-term (job) scheduling in a batch system, we can use the process time
limit that a user specifies when he submits the job
 SJF scheduling is used frequently in long-term scheduling.
 One approach to this problem is to try to approximate SJF scheduling. We may
not know the length of the next CPU burst, but we may be able to predict its
value.

37
SCHEDULING ALGORITHMS (CONT)

2. Shortest-Job-First Scheduling (SJF):

38
SCHEDULING ALGORITHMS (CONT)

3. Shortest Remaining Time First (SRTF) (SJF

preemptive)

Waiting time: [(10 − 1) + (1 − 1) + (17 − 2) + (5 − 3)]/4 = 26/4 = 6.5 39

SCHEDULING ALGORITHMS (CONT)

4. Priority Scheduling:
 Priorities are generally indicated by some fixed range of numbers, such as 0 to 7
or 0 to 4,095.
 Some systems use low numbers to represent low priority; others use low
numbers for high priority
 In this text, we assume that low numbers represent high priority

40
SCHEDULING ALGORITHMS (CONT)

4. Priority Scheduling:

The average waiting time is 8.2 milliseconds.

41
SCHEDULING ALGORITHMS (CONT)

4. Priority Scheduling:
 Priorities can be defined either internally or externally.
 Internally defined priorities use some measurable quantity or quantities to compute the priority
of a process.
 time limits
 memory requirements
 the number of open files
 ratio of average I/O burst to average CPU burst

 External priorities are set by criteria outside the operating system

 the importance of the process
 the type and amount of funds being paid for computer use
 the department sponsoring the work
 often political, factors
42
SCHEDULING ALGORITHMS (CONT)

4. Priority Scheduling:
 A major problem with priority scheduling algorithms is indefinite blocking, or
starvation.
 Asolution to the problem of indefinite blockage of low-priority processes is aging
 For example, if priorities range from 127 (low) to 0 (high), we could increase the
priority of a waiting process by 1 every 15 minutes.
 Priority scheduling can be either preemptive (4a) or nonpreemptive. (4b)

43
SCHEDULING ALGORITHMS (CONT)

5. Round-Robin Scheduling
 Preemption scheduling
 The round-robin (RR) scheduling algorithm is designed especially for timesharing
systems.
 A small unit of time, called a time quantum or time slice, is defined. A time
quantum is generally from 10 to 100 milliseconds in length.
 The ready queue is treated as a circular queue.

44
SCHEDULING ALGORITHMS (CONT)

5. Round-Robin Scheduling

average waiting time is 17/3 = 5.66.

45
SCHEDULING ALGORITHMS (CONT)

5. Round-Robin Scheduling
 In the RR scheduling algorithm, no process is allocated the CPU for more than 1
time quantum in a row (unless it is the only runnable process)
 The performance of the RR algorithm depends heavily on the size of the time
quantum.
 At one extreme, if the time quantum is extremely large, the RR policy
 if the time quantum is extremely small, the RR approach can result in a large number
of context switches

46
SCHEDULING ALGORITHMS (CONT)

5. Round-Robin Scheduling

47
SCHEDULING ALGORITHMS (CONT)

6. Multilevel Queue Scheduling

 partitions the ready queue into several separate queues

48
SCHEDULING ALGORITHMS (CONT)

7. Multilevel Feedback Queue Scheduling

 allows a process to move between queues

49
SCHEDULING ALGORITHMS (CONT)

7. Multilevel Feedback Queue Scheduling

 A multilevel feedback queue scheduler is defined by the following parameters:
 Number of queues
 Scheduling algorithm for each queue
 Method used to determine when to upgrade a process to a higher priority queue
 Method used to determine when to demote a process to a lower priority queue
 Method used to determine which queue a process will enter when that process needs
service

50
SCHEDULING ALGORITHMS

8. Lottery scheduling works

 Scheduling works by assigning processes lottery tickets
 Whenever a scheduling decision has to be made, a lottery ticket is chosen at
random.
 More tickets – higher probaility of winning
 Solves starvation

51
COOPERATING PROCESSES

 Independent process cannot affect or be affected by the execution of

another process.
 Cooperating process can affect or be affected by the execution of
another process
 Reasons of process cooperation
 Information sharing
 Computation speed-up
 Modularity
 Convenience

52
COOPERATING PROCESSES

 There are two fundamental models of interprocess

communication:
 shared memory
 message passing

53
THREADS

 A thread (or lightweight process) is a basic unit of CPU utilization; it consists of:
 program counter
 register set
 stack space
 A thread shares with its peer threads its:
 code section
 data section
 operating-system resources
collectively know as a task.
 A traditional or heavyweight process is equal to a task with one thread

54
THREADS (CONT.)

 Most software applications that run on modern computers are

multithreaded
 A web browser might have one thread display images or text while another thread
retrieves data from the network, for example.
 A word processor may have a thread for displaying graphics, another thread for
responding to keystrokes from the user, and a third thread for performing spelling
and grammar checking in the background
 Benefits:
 Responsiveness
 Resource Sharing
 Economy
 Scalability

55
PROCESS VS THREAD

56
THREADS (CONT.)

57
MULTITHREADING MODELS

 Many-to-one model

58
MULTITHREADING MODELS

 One-to-one model.

59
MULTITHREADING MODELS

 Many-to-many model.

60
THREAD LIBRARIES

 A thread library provides the programmer with an API for creating

and managing threads.
 Three main thread libraries are in use today:
 POSIX Pthreads
 Windows
 Java.

61
THREAD LIBRARIES

 For example, a multithreaded program that performs the summation

of a non-negative integer in a separate thread:

 Two strategies for creating multiple threads:

 Asynchronous threading
 Synchronous threading.

62
PTHREADS

 Pthreads refers to the POSIX standard (IEEE 1003.1c) defining an API

for thread creation and synchronization.

63
#include <pthread.h>
#include <stdio.h>
int sum; /* this data is shared by the thread(s) */
void *runner(void *param); /* threads call this function */

int main(int argc, char *argv[]){

pthread_t tid; /* the thread identifier */
pthread_attr_t attr; /* set of thread attributes */
if (argc != 2) {
fprintf(stderr,"usage: a.out <integer value>\n"); return -1;
}
if (atoi(argv[1]) < 0) {
fprintf(stderr,"%d must be >= 0\n",atoi(argv[1])); return -1;
}
pthread_attr_init(&attr); /* get the default attributes */
pthread_create(&tid,&attr,runner,argv[1]); /* create the thread */
pthread_join(tid,NULL); /* wait for the thread to exit */
printf("sum = %d\n",sum);
}
void *runner(void *param) { /* Thread will begin control in this function */
int i, upper = atoi(param);
sum = 0;
for (i = 1; i <= upper; i++)
sum += i;
pthread_exit(0);
}
#include <pthread.h>
#include <stdio.h>
int sum=0; /* this data is shared by the thread(s) */
void *runner(void *param); /* threads call this function */
int main(int argc, char *argv[]) {
pthread_t tid1; /* the thread identifier */
pthread_t tid2; /* the thread identifier */
pthread_attr_t attr; /* set of thread attributes */
pthread_attr_init(&attr); /* get the default attributes */
pthread_create(&tid1,&attr,runner,5); /* create the thread */
pthread_create(&tid2,&attr,runner,6); /* create the thread */
pthread_join(tid1,NULL); /* wait for the thread to exit */
pthread_join(tid2,NULL); /* wait for the thread to exit */
printf("sum = %d\n",sum);
}
void *runner(void *param) { /* Thread will begin control in this function */
for (int i = 1; i <= param; i++)
sum += i;
pthread_exit(0);
}
WINDOWS THREADS

 The technique for creating threads using theWindows thread library is similar to
the Pthreads technique in several ways.
 Threads are created in the Windows API using the CreateThread() function, and -
just as in Pthreads a set of attributes for the thread is passed to this function
 Once the summation thread is created, the parent must wait for it to complete
before outputting the value of Sum, as the value is set by the summation thread
 Windows API using the WaitForSingleObject() function to wait for the summation
thread

66
#include <windows.h>
#include <stdio.h>
DWORD Sum; /* data is shared by the thread(s) */
DWORD WINAPI Summation(LPVOID Param){
DWORD Upper = *(DWORD*)Param;
for (DWORD i = 0; i <= Upper; i++)
Sum += i;
return 0;
}
int main(int argc, char *argv[]){
DWORD ThreadId;
HANDLE ThreadHandle;
int Param;
if (argc != 2) {
fprintf(stderr,"An integer parameter is required\n"); return -1;
}
Param = atoi(argv[1]);
if (Param < 0) {
fprintf(stderr,"An integer >= 0 is required\n");
return -1;
}
ThreadHandle = CreateThread(/* create the thread */
NULL, /* default security attributes */
0, /* default stack size */
Summation, /* thread function */
&Param, /* parameter to thread function */
0, /* default creation flags */
&ThreadId); /* returns the thread identifier */
if (ThreadHandle != NULL) { /* now wait for the thread to finish */
WaitForSingleObject(ThreadHandle,INFINITE); /* close the thread handle */
CloseHandle(ThreadHandle);
printf("sum = %d\n",Sum);
}
}
JAVA THREADS

 Threads are the fundamental model of program execution in a Java

program, and the Java language and its API provide a rich set of
features for the creation and management of thread
 All Java programs comprise at least a single thread of control—even
a simple Java program consisting of only a main() method runs as a
single thread in the JVM

68
class Summation implements Runnable{
private int upper;
public Summation(int upper) {
this.upper = upper;
}
public void run() {
int sum = 0;
for (int i = 0; i <= upper; i++)
a.sumObject += i;
}
}
public class a {
static int sumObject = 0;
public static void main(String[] args) {
int upper = Integer.parseInt(args[0]);
Thread thread = new Thread(new Summation(upper));
thread.start();
try {
thread.join();
System.out.println("The sum of "+upper+" is " + a.sumObject);
} catch (InterruptedException ie) { }
}
}
IMPLICIT THREADING

 Implicit Threading: strategy for designing multithreaded programs

that can take advantage of multicore processors
 Thread Pools
 OpenMP (Open Multiple Processing)
 GDC (Grand Central Dispatch)

70
THREAD POOLS

 The general idea behind a thread pool is to create a number of threads at process
startup and place them into a pool, where they sit and wait for work

71
THREAD POOLS

 Thread pools offer these benefits:

 Servicing a request with an existing thread is faster than waiting to create a
thread.
 A thread pool limits the number of threads that exist at any one point. This is
particularly important on systems that cannot support a large number of
concurrent threads.
 Separating the task to be performed from the mechanics of creating the task
allows us to use different strategies for running the task. For example, the
task could be scheduled to execute after a time delay or to execute periodically

72
import java.util.concurrent.ArrayBlockingQueue;

Java
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class Study {

public static void main(String[] args) {
ArrayBlockingQueue<Runnable> queue = new ArrayBlockingQueue<Runnable>(100);
~20s ~4s
ThreadPoolExecutor pool = new ThreadPoolExecutor(5,10,1,TimeUnit.SECONDS,queue);
for(int i=0;i<20;i++) {
final int threadNo= i;
pool.execute(new Runnable() {
@Override
public void run() {
System.out.println("Thread " + threadNo + ": Start");
try {
Thread.sleep(1000);
} catch (InterruptedException e) {}
System.out.println("Thread " + threadNo + ": End");
}
});
}
}
}
THEAD POOLS

 The Windows API provides several functions related to thread pools:

 QueueUserWorkItem(&poolFunction, context, flags):

 &poolFunction: A pointer to the defined callback function
 Context: A single parameter value to be passed to the thread function.
 The flags that control execution. This parameter can be one or more of the following
values.

74
OPENMP

 OpenMP is a set of compiler directives as well as an API for programs written in C, C++,
or FORTRAN that provides support for parallel programming in shared-memory environments
 OpenMP identifies parallel regions as blocks of code that may run in parallel

75
#include <omp.h>
#include <stdio.h>
int main(int argc, char *argv[]){
/* sequential code */
#pragma omp parallel
{
printf("I am a parallel region.");
}
/* sequential code */
return 0;
}
#pragma omp parallel for
for (i = 0; i < N; i++) {
c[i] = a[i] + b[i];
}
MULTIPLE THREADS WITHIN A TASK

77
THREADS SUPPORT IN SOLARIS 2

 Solaris 2 is a version of UNIX with support for threads at the kernel and user levels,
symmetric multiprocessing, and
real-time scheduling.
 LWP – intermediate level between user-level threads and kernel-level threads.
 Resource needs of thread types:
 Kernel thread: small data structure and a stack; thread switching does not require changing memory
access information – relatively fast.
 LWP: PCB with register data, accounting and memory information,; switching between LWPs is
relatively slow.
 User-level thread: only ned stack and program counter; no kernel involvement means fast switching.
Kernel only sees the LWPs that support user-level threads.

78
SOLARIS 2 THREADS

79
INTERPROCESS COMMUNICATION (IPC)

 Mechanism for processes to communicate and to synchronize their actions.

 Message system – processes communicate with each other without resorting to shared variables.
 IPC facility provides two operations:
 send(message) – message size fixed or variable
 receive(message)
 If P and Q wish to communicate, they need to:
 establish a communication link between them
 exchange messages via send/receive
 Implementation of communication link
 physical (e.g., shared memory, hardware bus)
 logical (e.g., logical properties)

80
IMPLEMENTATION QUESTIONS

 How are links established?

 Can a link be associated with more than two processes?
 How many links can there be between every pair of communicating
processes?
 What is the capacity of a link?
 Is the size of a message that the link can accommodate fixed or
variable?
 Is a link unidirectional or bi-directional?

81
DIRECT COMMUNICATION

 Processes must name each other explicitly:

 send (P, message) – send a message to process P
 receive(Q, message) – receive a message from process Q
 Properties of communication link
 Links are established automatically.
 A link is associated with exactly one pair of communicating processes.
 Between each pair there exists exactly one link.
 The link may be unidirectional, but is usually bi-directional.

82
INDIRECT COMMUNICATION

 Messages are directed and received from mailboxes (also referred to as ports).
 Each mailbox has a unique id.
 Processes can communicate only if they share a mailbox.
 Properties of communication link
 Link established only if processes share a common mailbox
 A link may be associated with many processes.
 Each pair of processes may share several communication links.
 Link may be unidirectional or bi-directional.
 Operations
 create a new mailbox
 send and receive messages through mailbox
 destroy a mailbox

83
INDIRECT COMMUNICATION (CONTINUED)

 Mailbox sharing
 P1, P2, and P3 share mailbox A.
 P1, sends; P2 and P3 receive.
 Who gets the message?
 Solutions
 Allow a link to be associated with at most two processes.
 Allow only one process at a time to execute a receive operation.
 Allow the system to select arbitrarily the receiver. Sender is notified
who the receiver was.
84
BUFFERING

 Queue of messages attached to the link; implemented in one of three

ways.
1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous).
2. Bounded capacity – finite length of n messages
Sender must wait if link full.
3. Unbounded capacity – infinite length
Sender never waits.

85
EXCEPTION CONDITIONS – ERROR RECOVERY

 Process terminates
 Lost messages
 Scrambled Messages

86
PROCESS SYNCHRONIZATION

 Concurrent access to shared data may result in data inconsistency.

 Maintaining data consistency requires mechanisms to ensure the orderly execution
of cooperating processes.
 Shared-memory solution to bounded-butter problem (Chapter 4) allows at most n –
1 items in buffer at the same time. A solution, where all N buffers are used is not
simple.
 Suppose that we modify the producer-consumer code by adding a variable counter,
initialized to 0 and incremented each time a new item is added to the buffer

87
BOUNDED-BUFFER

 Shared data type item = … ;

var buffer array [0..n-1] of item;
in, out: 0..n-1;
counter: 0..n;
in, out, counter := 0;
 Producer process
repeat
…
produce an item in nextp
…
while counter = n do no-op;
buffer [in] := nextp;
in := in + 1 mod n;
counter := counter +1;
until false;
88
BOUNDED-BUFFER (CONT.)

 Consumer process
repeat
while counter = 0 do no-op;
nextc := buffer [out];
out := out + 1 mod n;
counter := counter – 1;
…
consume the item in nextc
…
until false;
 The statements:
 counter := counter + 1;
 counter := counter - 1;
must be executed atomically.
89
THE CRITICAL-SECTION PROBLEM

 n processes all competing to use some shared data

 Each process has a code segment, called critical section, in which the
shared data is accessed.
 Problem – ensure that when one process is executing in its critical
section, no other process is allowed to execute in its critical section.
 Structure of process Pi
repeat
entry section
critical section
exit section
reminder section
until false;

90
SOLUTION TO CRITICAL-SECTION PROBLEM

1. Mutual Exclusion. If process Pi is executing in its critical section,

then no other processes can be executing in their critical sections.
2.Progress. If no process is executing in its critical section and there exist
some processes that wish to enter their critical section, then the selection
of the processes that will enter the critical section next cannot be
postponed indefinitely.
3.Bounded Waiting. A bound must exist on the number of times that
other processes are allowed to enter their critical sections after a process
has made a request to enter its critical section and before that request is
granted.
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes.
91
INITIAL ATTEMPTS TO SOLVE PROBLEM

 Only 2 processes, P0 and P1

 General structure of process Pi (other process Pj)

repeat
entry section
critical section
exit section
reminder section
until false;
 Processes may share some common variables to synchronize their actions.

92
ALGORITHM 1

 Shared variables:
 var turn: (0..1);
initially turn = 0
 turn - i  P can enter its critical section
i

 Process P
i

repeat
while turn  i do no-op;
critical section
turn := j;
reminder section
until false;
 Satisfies mutual exclusion, but not progress

93
ALGORITHM 2

 Shared variables
 var flag: array [0..1] of boolean;
initially flag [0] = flag [1] = false.
 flag [i] = true  Pi ready to enter its critical section
 Process P
i

repeat
flag[i] := true;
while flag[j] do no-op;
critical section
flag [i] := false;
remainder section
until false;
 Satisfies mutual exclusion, but not progress requirement.

94
ALGORITHM 3

 Combined shared variables of algorithms 1 and 2.

 Process P
i

repeat
flag [i] := true;
turn := j;
while (flag [j] and turn = j) do no-op;
critical section
flag [i] := false;
remainder section
until false;
 Meets all three requirements; solves the critical-section problem for two processes.

95
BAKERY ALGORITHM

 Before entering its critical section, process receives a number. Holder of the
smallest number enters the critical section.
 If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else
Pj is served first.
 The numbering scheme always generates numbers in increasing order of
enumeration; i.e., 1,2,3,3,3,3,4,5...

96
BAKERY ALGORITHM (CONT.)

 Notation < lexicographical order (ticket #, process id #)

 (a,b) < c,d) if a < c or if a = c and b < d
 max (a0,…, an-1) is a number, k, such that k  ai for i - 0,
…, n – 1
 Shared data

var choosing: array [0..n – 1] of boolean;

number: array [0..n – 1] of integer,
Data structures are initialized to false and 0 respectively

97
BAKERY ALGORITHM (CONT.)

repeat
choosing[i] := true;
number[i] := max(number[0], number[1], …, number [n – 1])+1;
choosing[i] := false;
for j := 0 to n – 1
do begin
while choosing[j] do no-op;
while number[j]  0
and (number[j],j) < (number[i], i) do no-op;
end;
critical section
number[i] := 0;
remainder section
until false;
98
SYNCHRONIZATION HARDWARE

 Test and modify the content of a word atomically.

function Test-and-Set (var target: boolean): boolean;
begin
Test-and-Set := target;
target := true;
end;

99
MUTUAL EXCLUSION WITH TEST-AND-SET

 Shared data: var lock: boolean (initially false)

 Process P
i

repeat
while Test-and-Set (lock) do no-op;
critical section
lock := false;
remainder section
until false;

10
SEMAPHORE

 Synchronization tool that does not require busy waiting.

 Semaphore S – integer variable
 can only be accessed via two indivisible (atomic) operations

wait (S): while S 0 do no-op;

S := S – 1;

signal (S): S := S + 1;

10
EXAMPLE: CRITICAL SECTION OF N PROCESSES

 Shared variables
 var mutex : semaphore
 initially mutex = 1

 Process Pi

repeat
wait(mutex);
critical section
signal(mutex);
remainder section
until false;
10
SEMAPHORE IMPLEMENTATION

 Define a semaphore as a record

type semaphore = record
value: integer
L: list of process;
end;
 Assume two simple operations:
 block suspends the process that invokes it.
 wakeup(P) resumes the execution of a blocked process P.

10
IMPLEMENTATION (CONT.)

 Semaphore operations now defined as

wait(S): S.value := S.value – 1;
if S.value < 0
then begin
add this process to S.L;
block;
end;
signal(S): S.value := S.value = 1;
if S.value  0
then begin
remove a process P from S.L;
wakeup(P);
end;
10
SEMAPHORE AS GENERAL SYNCHRONIZATION TOOL

 Execute B in Pj only after A executed in Pi

 Use semaphore flag initialized to 0
 Code:
Pi Pj
 
A wait(flag)
signal(flag) B

10
DEADLOCK AND STARVATION

 Deadlock – two or more processes are waiting indefinitely for an event that can be
caused by only one of the waiting processes.
 Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
 
signal(S); signal(Q);
signal(Q) signal(S);
 Starvation – indefinite blocking. A process may never be removed from the
semaphore queue in which it is suspended.
10
TWO TYPES OF SEMAPHORES

 Counting semaphore – integer value can range over an unrestricted

domain.
 Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement.
 Can implement a counting semaphore S as a binary semaphore.

10
IMPLEMENTING S AS A BINARY SEMAPHORE

 Data structures:
var S1: binary-semaphore;
S2: binary-semaphore;
S3: binary-semaphore;
C: integer;
 Initialization:
S1 = S3 = 1
S2 = 0
C = initial value of semaphore S
10
IMPLEMENTING S (CONT.)

 wait operation
wait(S3);
wait(S1);
C := C – 1;
if C < 0
then begin
signal(S1);
wait(S2);
end
else signal(S1);
signal(S3);
 signal operation
wait(S1);
C := C + 1;
if C  0 then signal(S2);
signal(S)1;

10