CHAPTER 4 MULTITHREADED PROGRAMMING

➢ Threads
✓ A thread is a basic unit of CPU utilization.
✓ It comprises a thread ID, a program counter, a register set, and a stack. It shares its
code section, data section, and other operating-system resources, such as open files
and signals with other threads belonging to the same process.
✓ A traditional (or heavyweight) process has a single thread of control. If a process has
multiple threads of control, it can perform more than one task at a time.
✓ The below figure 4.1 illustrates the difference between a traditional single threaded
process and a multithreaded process.

• Motivation

✓ Many software packages that run on modern desktop PCs are multithreaded.
✓ An application is implemented as a separate process with several threads of control.
Eg: A Web browser might have one thread to display images or text while another
thread retrieves data from the network.
✓ Process creation takes more time than thread creation. It is more efficient to use
process that contains multiple threads, so that the amount of time that a client have to
wait for its request to be serviced from the web server will be less.
✓ Threads also play an important role in remote procedure call.
• Benefits
✓ The benefits of multithreaded programming
1. Responsiveness: Multithreading allows program to continue running even if part
of it is blocked or is performing a lengthy operation, thereby increasing
responsiveness to the user.
2. Resource Sharing: Threads share the memory and resources of the process to
which they belong. The benefit of sharing code and data is that it allows an
application to have several different threads of activity within the same address
space.
3. Economy: Because of resource sharing context switching and thread creation are
fast when working with threads.
4. Utilization of multiprocessor architectures: Threads can run in parallel on
different processors. Multithreading on multi-CPU machine increases
concurrency.

➢ Multithreading Models
✓ Support for threads may be provided either at user level for user threads or by the
kernel for kernel threads.
✓ There must be a relationship between user threads and kernel threads. Three common
ways of establishing this relationship are,

• Many-to-One

✓ Many user-level threads are mapped to single kernel thread as shown in below
figure below.
✓ This model is efficient as the thread management is done by the thread library in
user space, but the entire process will block if a thread makes a blocking system call.
✓ As only one thread can access the kernel thread at a time, multiple threads are unable
to run in parallel on multiprocessors.
✓ Examples: Solaris Green Threads, GNU Portable Threads

• One-to-One

✓ Each user-level thread maps to kernel thread as shown in figure 4.3

✓ It provides more concurrency than Many-to-One model by allowing thread to run
when a thread makes a blocking system call.
✓ It allows multiple threads to run in parallel on multiprocessors.
✓ The only drawback is, creating a user thread requires creating the corresponding
kernel thread and it burdens performance of an application.
✓ Examples: Windows NT/XP/2000, Linux

✓x

• Many-to-Many Model

✓ One-to-One model restricts creating more user threads and Many-to-One model
allows creating more user threads but kernel can schedule only one thread at a time.
 These drawbacks can be overcome by Many-to-Many model as shown in below
figure. (Left side)
✓ Many-to-Many model allows many user level threads to be mapped to many kernel
threads.
✓ It allows the operating system to create a sufficient number of kernel threads.
✓ When thread performs a blocking system call, the kernel can schedule another thread
for execution.
✓ It allows user-level thread to be bound to a kernel thread and this is referred as two-
level model as shown in below figure. (Right side)
✓ Examples: IRIX, HP-UX, Solaris OS.

➢ Thread Libraries

✓ A thread library provides the programmer an API for creating and managing threads.
✓ There are two primary ways of implementing a thread library.
o The first approach is to provide a library entirely in user space with no kernel
support. All code and data structures for the library exist in user space.
o The second approach is to implement a kernel-level library supported directly by
the operating system.
✓ Three primary thread libraries are
o POSIX Pthreads: extension of posix standard, they may be provided as either a
user bor kernel library.
o Win32 threads: is a kernel level library available on windows systems.
o Java threads: API allows creation and management directly in Java programs.
However, on windows java threads are implemented using win32 and on UNIX
and Linux using Pthreads

• Pthreads

✓ Pthreads, the threads extension of the POSIX standard, may be provided as either a user
or kernel-level library.
✓ Pthreads refers to the POSIX standard (IEEE 1003.1c) defining an API for thread
creation and synchronization.
✓ This is a specification for thread behavior, not an implementation.
✓ Operating system designers may implement the specification in any way they wish.
Numerous systems implement the Pthreads specification, including Solaris, Linux, Mac
OS X, and Tru64 UNIX.
✓ Shareware implementations are available in the public domain for the various Windows
operating systems as well.
 Ex: Multithreaded C program using the Pthreads API

#include <pthread.h>
#include <stdio.h>
int sum; /* this data is shared by the thread(s) */
void *runner(void *param); /* the thread */
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: [Link] <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) /* The 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) ;
}

• Win32 Threads

✓ The Win32 thread library is a kernel-level library available on Windows systems.

✓ The technique for creating threads using the Win32 thread library is similar to the
Pthreads technique in several ways. We must include the windows.h header file when
using the Win32 API.
✓ Threads are created in the Win32 API using the CreateThread() function and a set of
attributes for the thread is passed to this function.
✓ These attributes include security information, the size of the stack, and a flag that can be
set to indicate if the thread is to start in a suspended state.
✓ The parent thread waits for the child thread using the WaitForSingleObject() function,
which causes the creating thread to block until the summation thread has exited.

Ex: Multithreaded C program using the Win32 API

#include <Windows.h>
#include <stdio.h>
 DWORD Sum; /* data is shared by the thread(s) */
/* the thread runs in this separate function */
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) /* perform some basic error checking */

{
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;
}
/*create the thread*/
ThreadHandle = CreateThread(NULL, 0, Summation, &Param, 0, &ThreadId);

// 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)
{
WaitForSingleObject(ThreadHandle,INFINITE); // now wait for the thread to finish
CloseHandle(ThreadHandle); // close the thread handle
printf("surn = %d\n" ,Sum);
}
}

• Java Threads

✓ The Java thread API allows thread creation and management directly in Java programs.
✓ 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 threads.
✓ All Java programs comprise at least a single thread of control and even a simple Java
program consisting of only a main() method runs as a single thread in the JVM.
✓ There are two techniques for creating threads in a Java program. One approach is to
create a new class that is derived from the Thread class and to override its run()
method. An alternative and more commonly used technique is to define a class that
implements the Runnable interface. The Runnable interface is defined as follows:

public interface Runnable

{
public abstract void run () ;
}

✓ When a class implements Runnable, it must define a run() method. The code
implementing the run() method runs as a separate thread.
✓ Creating a Thread object does not specifically create the new thread but it is the start()
method that actually creates the new thread. Calling the start() method for the new
object does two things:
o It allocates memory and initializes a new thread in the JVM.
o It calls the run() method, making the thread eligible to be run by the JVM.
✓ As Java is a pure object-oriented language, it has no notion of global data. If two or
more threads have to share data means then the sharing occurs by passing reference to
the shared object to the appropriate threads.
✓ This shared object is referenced through the appropriate getSum() and setSum()
methods.
✓ As the Integer class is immutable, that is, once its value is set it cannot change, a new
sum class is designed.
✓ The parent threads in Java uses join() method to wait for the child threads to finish
before proceeding.

Ex: Java program for the summation of a non-negative integer.

class Sum
{
private int sum;
public int getSum()
{
return sum;
}

public void setSum(int sum)

{
[Link] = sum;
}
}

class Summation implements Runnable

{
private int upper;
private Sum sumValue;
 public Summation(int upper, Sum sumValue)
{
[Link] = upper;
[Link] = sumValue;
}

public void run()

{
int sum = 0;
for (int i = 0; i <= upper; i++)
sum += i;
[Link](sum);
}
}

public class Driver

{
public static void main(String[] args)
{
if ([Link] > 0)
{
if ([Link](args[O]) < 0)
[Link](args[O] + "must be>= 0.");
else
{
Sum sumObject = new Sum(); //create the object to be shared
int upper= [Link](args[O]);
Thread thrd =new Thread(new Summation(upper, sumObject));
[Link]();
try
{
thrd. join () ;
[Link]("The sum of "+upper+" is "+[Link]());
}
catch (InterruptedException ie) { }
}
}
else
[Link]("Usage: Summation <integer value>");
}

➢ Threading Issues

• The fork() and exec() System Calls

✓ The semantics of the fork() and exec() system calls change in a multithreaded
program. Some UNIX systems have chosen to have two versions of fork(), one
that duplicates all threads and another that duplicates only the thread that
invoked the fork() system call.
 ✓ If a thread invokes the exec() system call, the program specified in the parameter
to exec() will replace the entire process including all threads.
✓ Which of the two versions of fork() to use depends on the application. If exec()
is called immediately after forking, then duplicating all threads is unnecessary, as
the program specified in the parameters to exec() will replace the process. In this
instance, duplicating only the calling thread is appropriate.

• Thread Cancellation

✓ Thread cancellation is the task of terminating a thread before it has completed. For
example, if multiple threads are concurrently searching through a database and one
thread returns the result, the remaining threads might be cancelled.
✓ A thread that is to be cancelled is often referred to as the target thread. Cancellation
of a target thread may occur in two different scenarios:
o Asynchronous cancellation: One thread immediately terminates the target
thread.
o Deferred cancellation: The target thread periodically checks whether it should
terminate, allowing it an opportunity to terminate itself in an orderly fashion.

✓ The difficulty with asynchronous cancellation occurs in situations where resources

have been allocated to a cancelled thread or where a thread is cancelled while in the
midst of updating data it is sharing with other threads. This becomes especially
troublesome with asynchronous cancellation. Often, the operating system will
reclaim system resources from a cancelled thread but will not reclaim all resources.
Therefore, cancelling a thread asynchronously may not free a necessary system-wide
resource.
✓ With deferred cancellation, one thread indicates that a target thread is to be
cancelled, but cancellation occurs only after the target thread has checked a flag to
determine if it should be cancelled or not. This allows a thread to check whether it
should be cancelled at a point when it can be cancelled safely. Pthreads refers to
such points as cancellation points.
• Signal Handling

✓ A signal is used in UNIX systems to notify a process that a particular event has
occurred.
✓ A signal may be received either synchronously or asynchronously, depending on the
source of and the reason for the event being signaled.
✓ All signals, whether synchronous or asynchronous, follow the same pattern:
o A signal is generated by the occurrence of a particular event.
o A generated signal is delivered to a process.
o Once delivered, the signal must be handled.
✓ Examples of synchronous signals include illegal memory access and division by 0.
If a running program performs either of these actions, a signal is generated.
Synchronous signals are delivered to the same process that performed the operation
that caused the signal.
✓ When a signal is generated by an event external to a running process, that process
receives the signal asynchronously. Examples of such signals include terminating a
process with specific keystrokes (such as <control><C>) and having a timer
expires. An asynchronous signal is sent to another process.
✓ Every signal may be handled by one of two possible handlers,
o A default signal handler
o A user-defined signal handler
 ✓ Every signal has a default signal handler that is run by the kernel when handling
that signal.
✓ This default action can be overridden by a user-defined signal handler that is called
to handle the signal.
✓ Signals may be handled in different ways. Some signals (such as changing the size
of a window) may simply be ignored; others (such as an illegal memory access) may
be handled by terminating the program.
✓ Delivering signals is more complicated in multithreaded programs. The following
options exist to deliver a signal:

o Deliver the signal to the thread to which the signal applies.

o Deliver the signal to every thread in the process.
o Deliver the signal to certain threads in the process.
o Assign a specific thread to receive all signals for the process.

• Thread Pools

✓ The 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.
✓ When a server receives a request, it awakens a thread from this pool and passes the
request to it to service.
✓ Once the thread completes its service, it returns to the pool and waits for more work.
✓ If the pool contains no available thread, the server waits until one becomes free.
✓ The benefits of Thread pools are,
o Servicing a request with an existing thread is usually faster than waiting to
create a thread.
o 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.
✓ The number of threads in the pool can be set based on factors such as the number of
CPUs in the system, the amount of physical memory, and the expected number of
concurrent client requests.

• Thread-Specific Data

✓ Threads belonging to a process share the data of the process. This sharing of data
provides one of the benefits of multithreaded programming. But, in some circumstances,
each thread might need its own copy of certain data. Such data is called as thread-
specific data. For example, in a transaction-processing system, we might service each
transaction in a separate thread. Furthermore, each transaction may be assigned a unique
identifier.
✓ Most thread libraries including Win32 and Pthreads provide support for thread-specific
data.

• Scheduler Activations

✓ Many systems implementing either the many-to-many or two-level model place an

intermediate data structure between the user and kernel threads. This data structure is
 known as a lightweight process, or LWP as shown in the following figure

✓ An application may require any number of LWPs to run efficiently.

✓ In a CPU-bound application running on a single processor only one thread can run at
once, so one LWP is sufficient. An application that is I/O- intensive may require
multiple LWPs to execute.
✓ One scheme for communication between the user-thread library and the kernel is known
as scheduler activation. It works as follows: The kernel provides an application with a
set of virtual processors (LWPs), and the application can schedule user threads onto an
available virtual processor. The kernel must inform an application about certain events.
This procedure is known as an upcall.
✓ Upcalls are handled by the thread library with an upcall handler, and upcall handlers
must run on a virtual processor.
✓ One event that triggers an upcall occurs when an application thread is about to block. In
this situation, the kernel makes an upcall to the application informing it that a thread is
about to block and identifying the specific thread. The kernel then allocates a new
virtual processor to the application.
✓ The application runs an upcall handler on this new virtual processor, which saves the
state of the blocking thread and gives up the virtual processor on which the blocking
thread is running. The upcall handler then schedules another thread that is eligible to run
on the new virtual processor.
✓ When the event that the blocking thread was waiting for occurs, the kernel makes
another upcall to the thread library informing it that the previously blocked thread is
now eligible to run.
✓ The upcall handler for this event also requires a virtual processor, and the kernel may
allocate a new virtual processor or preempt one of the user threads and run the upcall
handler on its virtual processor.
✓ After marking the unblocked thread as eligible to run, the application schedules an
eligible thread to run on an available virtual processor.

➢ Differences

✓ The differences between process and thread are,

Process Thread
1. It is called heavyweight process. It is called lightweight process.
Process switching needs interface with Thread switching does not need interface
2.
OS. with OS.
Multiple processes use more resources Multiple threaded processes use fewer
3.
than multiple threads. resources than multiple processes.
 In multiple process implementations
each process executes same code but All threads can share same set of open
4.
has its own memory and file files.
resources.
If one server process is blocked no While one server thread is blocked and
5. other server process can execute until waiting, second thread in the same task
the first process unblocked. could run.
One thread can read, write or even
In multiple processes each process
6. completely wipeout another threads
operates independently of others.
stack.

CHAPTER 5

PROCESS SHEDULING

➢ Basic Concepts

✓ In a single-processor system, only one process can run at a time and others must wait
until the CPU is free and can be rescheduled.
✓ The objective of multiprogramming is to have some process running at all times, to
maximize CPU utilization.
✓ With multiprogramming, several processes are kept in memory at one time. When one
process has to wait, the operating system takes the CPU away from that process and
gives the CPU to another process.
✓ The CPU is one of the primary computer resources. Thus, its scheduling is central to
✓ operating-system design.

• CPU–I/O Burst Cycle

✓ Process execution consists of a cycle of CPU execution and I/O wait

✓ Process execution starts with CPU burst and this is followed by I/O burst as shown
in below figure.
✓ The final CPU burst ends with a system request to terminate execution.
 ✓ The duration of CPU bursts vary from process to process and from computer to
computer.

✓ The frequency curve is as shown below figure.

• CPU Scheduler

✓ Whenever the CPU becomes idle, the operating system must select one of the
processes in the ready queue to be executed. This selection is carried out by the
short-term scheduler (or CPU scheduler).
✓ The scheduler selects a process from the processes in memory that are ready to
execute and allocates the CPU to that process.
✓ A ready queue can be implemented as a FIFO queue, a priority queue, a tree, or
simply an unordered linked list. But all the processes in the ready queue are lined up
 waiting for a chance to run on the CPU. The records in the queues are Process
Control Blocks (PCBs) of the processes.

• Preemptive scheduling
✓ CPU-scheduling decisions may take place under the following four circumstances.
1. When a process switches from the running state to the waiting state (for example,
as the result of an I/O request or an invocation of wait for the termination of one
of the child processes)
2. When a process switches from the running state to the ready state (for example,
when an interrupt occurs)
3. When a process switches from the waiting state to the ready state (for example,
at completion of I/O)
4. When a process terminates

✓ When scheduling takes place only under circumstances 1 and 4, we say that the
scheduling scheme is nonpreemptive or cooperative; otherwise, it is preemptive.
✓ Under nonpreemptive scheduling, once the CPU has been allocated to a process, the
process keeps the CPU until it releases the CPU either by terminating or by
switching to the waiting state. A scheduling algorithm is preemptive if, once a
process has been given the CPU and it can be taken away.

• Dispatcher

✓ Another component involved in the CPU-scheduling function is the dispatcher.

✓ The dispatcher is the module that gives control of the CPU to the process selected by
the short-term scheduler.
✓ This function involves the following:
o Switching context
o Switching to user mode
o Jumping to the proper location in the user program to restart that program

✓ The dispatcher should be as fast as possible, since it is invoked during every process
switch.
✓ The time it takes for the dispatcher to stop one process and start another running is
known as the dispatch latency.

➢ Scheduling Criteria
✓ Many criteria have been suggested for comparing CPU scheduling algorithms. The
criteria include the following:

o CPU utilization: CPU must be kept as busy as [Link] utilization can range
from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly
loaded system) to 90 percent (for a heavily used system).
o Throughput: If the CPU is busy executing processes, then work is being done. One
measure of work is the number of processes that are completed per time unit, called
throughput. For long processes, this rate may be one process per hour; for short
transactions, it may be 10 processes per second.
o Turnaround time: The interval from the time of submission of a process to the time
of completion is the turnaround time. Turnaround time is the sum of the periods
 spent waiting to get into memory, waiting in the ready queue, executing on the CPU,
and doing I/O.
o Waiting time: The CPU scheduling algorithm does not affect the amount of time
during which a process executes or does I/O; it affects only the amount of time that a
process spends waiting in the ready queue. Waiting time is the sum of the periods
spent waiting in the ready queue.
o Response time: The measure of the time from the submission of a request until the
first response is produced. This measure, called response time, is the time it takes to
start responding, not the time it takes to output the response.

➢ Scheduling Algorithms

CPU Scheduling deals with the problem of deciding which of the processes in the ready
queue is to be allocated the CPU. Following are some scheduling algorithms,

o FCFS Scheduling.
o Round Robin Scheduling.
o SJF Scheduling.
o Priority Scheduling.
o Multilevel Queue Scheduling.
o Multilevel Feedback Queue Scheduling.

• First-Come-First-Served (FCFS) Scheduling

✓ The simplest CPU-scheduling algorithm is the first-come, first-served (FCFS)

scheduling algorithm.
✓ With this scheme, the process that requests the CPU first is allocated the CPU first.
✓ The implementation of the FCFS policy is easily managed with a FIFO queue.
✓ When a process enters the ready queue, its PCB is linked onto the tail of the queue.
✓ When the CPU is free, it is allocated to the process at the head of the queue. The
running process is then removed from the queue.
✓ The average waiting time under the FCFS policy is often quite long. Consider the
following set of processes that arrive at time 0, with the length of the CPU burst
given in milliseconds:

✓ If the processes arrive in the order P1, P2, P3, and are served in FCFS order, we get
the result shown in the following Gantt chart:

✓ The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2, and 27
milliseconds for process P3. Thus, the average waiting time is (0 + 24 + 27)/3 = 17
milliseconds.
 ✓ The FCFS scheduling algorithm is nonpreemptive. Once the CPU has been allocated to
a process, that process keeps the CPU until it releases the CPU, either by terminating or
by requesting I/O. The FCFS algorithm is thus particularly troublesome for time-sharing
systems, where it is important that each user get a share of the CPU at regular intervals.

• Shortest-Job-First Scheduling

✓ This algorithm associates with each process the length of the process's next CPU burst.
✓ When the CPU is available, it is assigned to the process that has the smallest next CPU
burst.
✓ If the next CPU bursts of two processes are the same, FCFS scheduling is used to break
the tie.
✓ As an example of SJF scheduling, consider the following set of processes, with the
length of the CPU burst given in milliseconds:

✓ Using SJF scheduling, we would schedule these processes according to the following
Gantt chart:

✓ The waiting time is 3 milliseconds for process P1, 16 milliseconds for process P2, 9
milliseconds for process P3, and 0 milliseconds for process P4. Thus, the average waiting
time is (3 + 16 + 9 + 0)/4 = 7 milliseconds.
✓ The SJF scheduling algorithm is optimal, it gives the minimum average waiting time for
a given set of processes. Moving a short process before a long one, decreases the waiting
time of the short process more than it increases the waiting time of the long process.
Consequently, the average waiting time decreases.
✓ The SJF algorithm can be either preemptive or nonpreemptive. The choice arises
when a new process arrives at the ready queue while a previous process is still
executing. The next CPU burst of the newly arrived process may be shorter than what is
left of the currently executing process. A preemptive SJF algorithm will preempt the
currently executing process, whereas a nonpreemptive SJF algorithm will allow the
currently running process to finish its CPU burst. Preemptive SJF scheduling is
sometimes called shortest-remaining-time-first scheduling.
✓ As an example, consider the following four processes, with the length of the CPU burst
given in milliseconds:
 ✓ If the processes arrive at the ready queue at the times shown and need the indicated burst
times, then the resulting preemptive SJF schedule is as depicted in the following Gantt
chart:

✓ Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives
at time 1.
✓ The remaining time for process P1 (7 milliseconds) is larger than the time required by
process P2 (4 milliseconds), so process P1 is preempted, and process P2 is scheduled. The
average waiting time for this example is ((10 -1) + (1-1) + (17 -2) + (5- 3))/4 = 26/4 =
6.5 milliseconds. Nonpreemptive SJF scheduling would result in an average waiting
time of 7.75 milliseconds.

• Priority Scheduling

✓ The SJF algorithm is a special case of the general priority scheduling algorithm.
✓ A priority is associated with each process, and the CPU is allocated to the process with
the highest priority.
✓ Equal-priority processes are scheduled in FCFS order.
✓ An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of
the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and
vice versa.
✓ As an example, consider the following set of processes, assumed to have arrived at time
0, in the order P1, P2, … , P5, with the length of the CPU burst given in milliseconds:

✓ Using priority scheduling, we would schedule these processes according to the following
Gantt chart:

✓ The average waiting time is 8.2 milliseconds.

✓ Priority scheduling can be either preemptive or nonpreemptive. When a process
arrives at the ready queue, its priority is compared with the priority of the currently
running process. A preemptive priority scheduling algorithm will preempt the CPU if
the priority of the newly arrived process is higher than the priority of the currently
running process. A nonpreemptive priority scheduling algorithm will simply put the new
process at the head of the ready queue.
✓ A major problem with priority scheduling algorithms is indefinite blocking, or
starvation. A process that is ready to run but waiting for the CPU can be considered
blocked. A priority scheduling algorithm can leave some low- priority processes waiting
 indefinitely. In a heavily loaded computer system, a steady stream of higher-priority
processes can prevent a low-priority process from ever getting the CPU.
✓ A solution to the problem of indefinite blockage of low-priority processes is aging.
Aging is a technique of gradually increasing the priority of processes that wait in the
system for a long time.

• Round-Robin Scheduling

✓ The round-robin (RR) scheduling algorithm is designed especially for timesharing

systems.
✓ It is similar to FCFS scheduling, but preemption is added to switch between processes.
✓ A small unit of time, called a time quantum or time slice, is defined. A time quantum
is generally from 10 to 100 milliseconds.
✓ The ready queue is treated as a circular queue. The CPU scheduler goes around the
ready queue, allocating the CPU to each process for a time interval of up to 1 time
quantum.
✓ To implement RR scheduling, we keep the ready queue as a FIFO queue of processes.
New processes are added to the tail of the ready queue.
✓ The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt
after 1 time quantum, and dispatches the process. One of two things will then happen.
o The process may have a CPU burst of less than 1 time quantum. In this case, the
process itself will release the CPU voluntarily. The scheduler will then proceed to
the next process in the ready queue.
o Otherwise, if the CPU burst of the currently running process is longer than 1 time
quantum, the timer will go off and will cause an interrupt to the operating system. A
context switch will be executed, and the process will be put at the tail of the ready
queue. The CPU scheduler will then select the next process in the ready queue.
✓ The average waiting time under the RR policy is often long. Consider the following set
of processes that arrive at time 0, with the length of the CPU burst given in milliseconds:

✓ If we use a time quantum of 4 milliseconds, then process P1 gets the first 4 milliseconds.
Since it requires another 20 milliseconds, it is preempted after the first time quantum,
and the CPU is given to the next process in the queue ie. process P2. Since process P2
does not need 4 milliseconds, it quits before its time quantum expires.
✓ The CPU is then given to the next process P3. Once each process has received 1 time
quantum, the CPU is returned to process P1 for an additional time quantum. The
resulting RR schedule is

✓ The average waiting time is 17/3 = 5.66 milliseconds.

✓ The RR scheduling algorithm is thus preemptive.
 ✓ If there are n processes in the ready queue and the time quantum is q, then each process
gets 1/n of the CPU time in chunks of at most q time units. Each process must wait no
longer than (n-1) * q time units until its next time quantum. For example, with five
processes and a time quantum of 20 milliseconds, each process will get up to 20
milliseconds every 100 milliseconds.

• Multilevel Queue Scheduling

✓ Another class of scheduling algorithms has been created for situations in which
processes are easily classified into different groups. For example, a common division is
made between foreground (interactive) processes and background (batch)
processes.
✓ These two types of processes have different response-time requirements and may have
different scheduling needs.
✓ Foreground processes have priority over background processes.
✓ A multilevel queue scheduling algorithm partitions the ready queue into several separate
queues as shown in figure 5.3.
✓ The processes are permanently assigned to one queue based on some property of the
process, such as memory size, process priority, or process type.
✓ Each queue has its own scheduling algorithm. For example, separate queues might be
used for foreground and background processes.
✓ The foreground queue might be scheduled by an RR algorithm, while the background
queue is scheduled by an FCFS algorithm.

✓ There must be scheduling among the queues, which is commonly implemented as fixed-
priority preemptive scheduling. For example, the foreground queue may have absolute
priority over the background queue.
✓ An example of a multilevel queue scheduling algorithm with five queues, listed below
in order of priority:
1. System processes
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student processes
 ✓ Each queue has absolute priority over lower-priority queues. No process in the batch
queue could run unless the queues for system processes, interactive processes, and
interactive editing processes were all empty.
✓ If an interactive editing process entered the ready queue while a batch process was
running, the batch process would be preempted.
✓ Another possibility is to time-slice among the queues. So, each queue gets a certain
portion of the CPU time, which it can then schedule among its various processes. For
example, the foreground queue can be given 80 percent of the CPU time for RR
scheduling among its processes, whereas the background queue receives 20 percent of
the CPU to give to its processes on an FCFS basis.

• Multilevel Feedback-Queue Scheduling

✓ When the multilevel queue scheduling algorithm is used, processes are permanently
assigned to a queue when they enter the system.
✓ The multilevel feedback-queue scheduling algorithm allows a process to move between
queues. The idea is to separate processes according to the characteristics of their CPU
bursts.
✓ If a process uses too much CPU time, it will be moved to a lower-priority queue. This
scheme leaves I/O-bound and interactive processes in the higher-priority queues.
✓ A process that waits too long in a lower-priority queue may be moved to a higher-
priority queue. This form of aging prevents starvation.
✓ For example, consider a multilevel feedback-queue scheduler with three queues,
numbered from 0 to 2 as shown in below figure 5.4.
✓ The scheduler first executes all processes in queue 0. Only when queue 0 is empty it
will execute processes in queue 1.
✓ Similarly, processes in queue 2 will only be executed if queues 0 and 1 are empty. A
process that arrives for queue 1 will preempt a process in queue 2.
✓ A process in queue 1 will in turn be preempted by a process arriving for queue 0.

✓ A process entering the ready queue is put in queue 0. A process in queue 0 is given a
time quantum of 8 milliseconds. If it does not finish within this time, it is moved to the
tail of queue 1. If queue 0 is empty, the process at the head of queue 1 is given a
quantum of 16 milliseconds. If it does not complete, it is preempted and is put into
queue 2. Processes in queue 2 are scheduled on an FCFS basis but they run only when
queue 0 and 1 are empty.
 ✓ This scheduling algorithm gives highest priority to any process with a CPU burst of 8
milliseconds or less. Such a process will quickly get the CPU, finish its CPU burst, and
go off to its next I/O burst. Processes that need more than 8 but less than 24 milliseconds
are also served quickly, although with lower priority than shorter processes. Long
processes automatically sink to queue 2 and are served in FCFS order with any CPU
cycles left over from queues 0 and 1.
✓ A multilevel feedback-queue scheduler is defined by the following parameters:
o The number of queues.
o The scheduling algorithm for each queue.
o The method used to determine when to upgrade a process to a higher-priority
queue.
o The method used to determine when to demote a process to a lower-priority
queue.
o The method used to determine which queue a process will enter when that
process needs service.

➢ Multiple-Processor Scheduling

• Approaches to Multiple-Processor Scheduling

✓ One approach to CPU scheduling in a multiprocessor system is where all scheduling

decisions, I/O processing, and other system activities are handled by a single
processor i.e., the master server. The other processors execute only user code. This
asymmetric multiprocessing is simple because only one processor accesses the
system data structures, reducing the need for data sharing.
✓ A second approach uses symmetric multiprocessing (SMP), where each processor
is self-scheduling. All processes may be in a common ready queue, or each
processor may have its own private queue of ready processes.

• Some of the issues related to SMP are,

a. Processor Affinity

✓ The data most recently accessed by the process is populated in the cache for the
processor and successive memory accesses by the process are often satisfied in
cache memory.
✓ If the process migrates to another processor, the contents of cache memory must be
invalidated for the processor being migrated from, and the cache for the processor
being migrated to must be re-populated. Because of the high cost of invalidating
and re-populating caches, most SMP systems try to avoid migration of processes
from one processor to another and instead tries to keep a process running on the
same processor. This is known as processor affinity, i.e., a process has an affinity
for the processor on which it is currently running.
✓ Processor affinity takes several forms. When an operating system has a policy of
attempting to keep a process running on the same processor but not guaranteeing
that it will do so, a situation is known as soft affinity. Here, it is possible for a
process to migrate between processors.
✓ Some systems such as Linux provide system calls that support hard affinity,
thereby allowing a process to specify that it must not migrate to other processors.

b. Load Balancing
 ✓ On SMP systems, it is important to keep the workload balanced among all
processors to utilize the benefits of having more than one processor. Otherwise, one
or more processors may sit idle while other processors have high workloads along
with lists of processes awaiting the CPU.
✓ Load balancing attempts to keep the workload evenly distributed across all
processors in an SMP system.
✓ There are two general approaches to load balancing: push migration and pull
migration.
✓ With push migration, a specific task periodically checks the load on each processor
and if it finds an imbalance it evenly distributes the load by moving (or pushing)
processes from overloaded to idle or less-busy processors.
✓ Pull migration occurs when an idle processor pulls a waiting task from a busy
processor.

c. Symmetric Multithreading

✓ SMP systems allow several threads to run concurrently by providing multiple

physical processors.
✓ An alternative strategy is to provide multiple logical processors rather than
physical processors. Such a strategy is known as symmetric multithreading (or
SMT).
✓ The idea behind SMT is to create multiple logical processors on the same physical
processor, presenting a view of several logical processors to the operating system,
even on a system with only a single physical processor.
✓ Each logical processor has its own architecture state, which includes general-
purpose and machine-state registers and is responsible for its own interrupt
handling, meaning that interrupts are delivered to and handled by logical processors
rather than physical ones. Otherwise, each logical processor shares the resources of
its physical processor, such as cache memory and buses.
✓ The following figure 5.5 illustrates a typical SMT architecture with two physical
processors, each housing two logical processors. From the operating system's
perspective, four processors are available for work on this system.

➢ Thread Scheduling

✓ On operating systems that support user-level and kernel-level threads, the kernel-level
threads are being scheduled by the operating system.
✓ User-level threads are managed by a thread library, and the kernel is unaware of them.
To run on a CPU, user-level threads must be mapped to an associated kernel-level
 thread, although this mapping may be indirect and may use a lightweight process
(LWP).
✓ One distinction between user-level and kernel-level threads lies in how they are
scheduled. On systems implementing the many-to-one and many-to-many models, the
thread library schedules user-level threads to run on an available LWP, a scheme known
as process-contention scope (PCS), since competition for the CPU takes place among
threads belonging to the same process.
✓ To decide which kernel thread to schedule onto a CPU, the kernel uses system-
contention scope (SCS). Competition for the CPU with SCS scheduling takes place
among all threads in the system.
✓ PCS is done according to priority. The scheduler selects the runnable thread with the
highest priority to run. User-level thread priorities are set by the programmer. PCS will
preempt the currently running thread in favour of a higher-priority thread.

• Pthread Scheduling

✓ Pthreads identifies the following contention scope values:

o PTHREAD_SCOPE_PROCESS schedules threads using PCS scheduling.

o PTHREAD_SCOPE_SYSTEM schedules threads using SCS scheduling.

✓ On systems implementing the many-to-many model, the

PTHREAD_SCOPE_PROCESS policy schedules user-level threads onto available
LWPs.
✓ The number of LWPs is maintained by the thread library using scheduler activations.
The PTHREAD_SCOPE_SYSTEM scheduling policy will create and bind an LWP
for each user-level thread on many-to-many systems, effectively mapping threads
using the one-to-one policy.
✓ The Pthread IPC provides the following two functions for getting and setting the
contention scope policy;

o pthread_attr_setscope (pthread_attr_t *attr, int scope)

o pthread_attr_getscope (pthread_attr_t *attr, int *scope)

✓ The first parameter for both functions contains a pointer to the attribute set for the
thread.
✓ The second parameter for the pthread_attr_setscope () function is passed either the
THREAD_SCOPE_SYSTEM or PTHREAD_SCOPE_PROCESS value, indicating
how the contention scope is to be set. In the case of pthread_attr_getscope(), this
second parameter contains a pointer to an int value that is set to the current value of
the contention scope. If an error occurs, each of these functions returns non-zero
values.

Process Synchronization
Process Synchronization
✓ To introduce the critical-section problem, whose solutions can be used to ensure the consistency
of shared data
✓ To present both software and hardware solutions of the critical-section problem
✓ To introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity
 ✓ Concurrent access to shared data may result in data inconsistency
✓ Maintaining data consistency requires mechanisms to ensure the orderly execution of
cooperating processes
✓ Suppose that we wanted to provide a solution to the consumer-producer problem that fills all the
buffers. We can do so by having an integer count that keeps track of the number of full buffers.
Initially, count is set to 0. It is incremented by the producer after it produces a new buffer and is
decremented by the consumer after it consumes a buffer.

Producer
while (true)
{
/* produce an item and put in nextProduced */
while (count == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
Consumer
while (true)
{
while (count == 0)
; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
/* consume the item in nextConsumed
}
Race condition: The situation where several processes access – and manipulate shared data
concurrently. The final value of the shared data depends upon which process finishes last. To
prevent race conditions, concurrent processes must be synchronized.
The Critical-Section Problem
Consider a system consisting of n processes {Po, P1 , ... , Pn-1}. Each process has a segment of
code, called a Critical Section, in which the process may be changing common variables, updating a
table, writing a file, and so on.
The important feature of the system is that, when one process is executing in its critical section,
no other process is to be allowed to execute in its critical section. That is, no two processes are
executing in their critical sections at the same time.

Problem – ensure that when one process is executing in its critical section, no other process is
allowed to execute in its critical section.

The general structure of a typical process Pi is shown in figure. The entry section and exit
section are enclosed in boxes to highlight these important segments of code.
A solution to the critical-section problem must satisfy the following three requirements:
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
Peterson's solution
A classic software-based solution to the critical-section problem known as Peterson's solution.
Peterson's solution is restricted to two processes that alternate execution between their critical
sections and remainder sections. The processes are numbered P0 and P1. For convenience, when
presenting Pi, we use Pj to denote the other process; that is, j equals 1- j.
• The two processes share two variables:
o int turn;
o Boolean flag[2]
• The variable turn indicates whose turn it is to enter the critical section.
• The flag array is used to indicate if a process is ready to enter the critical section. flag[i] =
true implies that process Pi is ready!
do {
flag[i] = TRUE;
turn = j;
while ( flag[j] && turn == j);
CRITICAL SECTION
flag[i] = FALSE;
REMAINDER SECTION
} while (TRUE);
To enter the critical section, process Pi first sets flag [i] to be true and then sets turn to the
value j, thereby asserting that if the other process wishes to enter the critical section, it can do so. If
both processes try to enter at the same time, turn will be set to both i and j at roughly the same time.
Only one of these assignments will last; the other will occur but will be overwritten
immediately.
We now prove that this solution is correct. We need to show that:
• Mutual exclusion is preserved.
• The progress requirement is satisfied.
• The bounded-waiting requirement is met.

Synchronization Hardware
Software-based solutions such as Peterson's are not guaranteed to work on modern computer
architectures. Instead, we can generally state that any solution to the critical-section problem
requires a simple tool-a lock.
 Race conditions are prevented by requiring that critical regions be protected by locks. That
is, a process must acquire a lock before entering a critical section; it releases the lock when it exits
the critical section.

• Many systems provide hardware support for critical section code

• Uniprocessors – could disable interrupts
o Currently running code would execute without preemption
o Generally too inefficient on multiprocessor systems
▪ Operating systems using this not broadly scalable
• Modern machines provide special atomic hardware instructions
▪ Atomic = non-interruptable
o Either test memory word and set value
o Or swap contents of two memory words
TestAndndSet Instruction

• Solution using TestAndSet Shared Boolean variable lock, initialized to false.

Swap Instruction
 Solution using Swap, Shared Boolean variable lock; Each process has a local Boolean variable
key.

Although these algorithms satisfy the mutual-exclusio n requirement, they do not satisfy the
bounded-waiting requirement. We present another algorithm using the TestAndSet() instruction that
satisfies all the critical-section requirements.

Semaphore:
The hardware-based solutions to the critical-section problem prese nted are complicated for
application programmers to use. To overcome this difficulty, we can us e a synchronization tool
called a Semaphor.
A semaphore S is an integer variable that, apart from initialization, is accessed only through
two standard atomic operations: wait () and signal () (Originally called P() a nd V())
Wait() function is as follows:
wait (S) {
while S <= 0
; // no-op
S--;
}
Signal() function is as follows:
signal (S) {
S++;
}
Semaphore as General Synchronization Tool

• 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
o Also known as mutex locks
• Can implement a counting semaphore S as a binary semaphore
• Provides mutual exclusion
Semaphore S; // initialized to 1
wait (S);
Critical Section
signal (S);
Semaphore implementation

• Must guarantee that no two processes can execute wait () and signal () on the same
semaphore at the same time
• Thus, implementation becomes the critical section problem where the wait and signal code
are placed in the critical section.
o Could now have busy waiting in critical section implementation
▪ But implementation code is short
▪ Little busy waiting if critical section rarely occupied
• Busy waiting wastes CPU cycles that some other process might be able to use productively.
This type of semaphore is also called spinlock a because the process "spins" while waiting
for the lock
• Note that applications may spend lots of time in critical sections and therefore this is not a
good solution.

Semaphore Implementation with no Busy waiting

• With each semaphore there is an associated waiting queue. Each entry in a waiting queue
has two data items:
o value (of type integer)
o pointer to next record in the list
• Two operations:
o block – place the process invoking the operation on the appropriate waiting queue.
o wakeup – remove one of processes in the waiting queue and place it in the ready
queue.
• Implementation of wait:
wait (S){
value--;
if (value < 0) {
 add this process to waiting queue
block(); }
}

• Implementation of signal:
Signal (S){
value++;
if (value <= 0) {
remove a process P from the waiting queue
wakeup(P); }
}
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.

Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem
Bounded-Buffer Problem
We assume that the pool consists of n buffers, each capable of holding one item. The mutex
semaphore provides mutual exclusion for accesses to the buffer pool and is initialized to the value
1. The empty and full semaphores comct the number of empty and full buffers. The semaphore
empty is initialized to the value n; the semaphore full is initialized to the value 0.
• The structure of the Producer process:
do {
// produce an item
wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
 signal (full);
} while (true);

• The structure of the Consumer process:

do {
wait (full);
wait (mutex);
// remove an item from buffer
signal (mutex);
signal (empty);

// consume the removed item

} while (true);
Readers-Writers Problem
• A data set is shared among a number of concurrent processes
o Readers – only read the data set; they do not perform any updates
o Writers – can both read and write.
• Problem – allow multiple readers to read at the same time. Only one single writer can
access the shared data at the same time.
• Shared Data
o Data set
semaphore mutex, wrt;
int readcount;
o Semaphore mutex initialized to 1.
o Semaphore wrt initialized to 1.
o Integer readcount initialized to 0.
• The structure of a writer process
do {
wait (wrt) ;

// writing is performed
signal (wrt) ;
} while (true)
• The structure of a reader process
do {
wait (mutex) ;
readcount ++ ;
if (readercount == 1) wait (wrt) ;
signal (mutex)
// reading is performed
 wait (mutex) ;
readcount - - ;
if redacount == 0) signal (wrt) ;
signal (mutex) ;
} while (true);
Dining-Philosophers Problem
Consider five philosophers who spend their lives thinking and eating.
The philosophers share a circular table surrounded by five chairs, each belonging to one
philosopher. In the center of the table is a bowl of rice, and the table is laid with five single
chopsticks. When a philosopher thinks, she does not interact with her colleagues. From time to
time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to her (the
chopsticks that are between her and her left and right neighbors). A philosopher may pick up only
one chopstick at a time. Obviously, she cam1ot pick up a chopstick that is already in the hand of a
neighbor. When a htmgry philosopher has both her chopsticks at the same time, she eats without
releasing her chopsticks. When she is finished eating, she puts down both of her chopsticks and
starts thinking again.

It is a simple representation of the need to allocate several resources among several

processes in a deadlock-free and starvation-free manner.

semaphore chopstick[5]; // initialized to 1

The structure of Philosopher i:

do {
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );

// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );

// think
} while (true) ;
Monitors
Problems with Semaphores
Although semaphores provide a convenient and effective mechanism for process
synchronization, using them incorrectly can result in timing errors that are difficult to detect.

• All processes share a semaphore variable mutex, which is initialized to 1. Each process
must execute wait (mutex) before entering the critical section and signal (mutex)
afterward. If this sequence is not observed, two processes may be in their critical
sections simultaneously.
• Suppose that a process interchanges the order in which the wait() and signal() operations
on the semaphore mutex are executed, resulting in the following execution:
signal(mutex);
…
critical section
…
wait(mutex);
In this situation, several processes may be executing in their critical sections
simultaneously, violating the mutual-exclusion requirement.
• Suppose that a process replaces signal (mutex) with wait (mutex). That is, it executes
wait(mutex);
…
critical section
…
wait(mutex);
In this case, a deadlock will occur.
• Suppose that a process omits the wait (mutex), or the signal (mutex), or both. In this
case, either mutual exclusion is violated or a deadlock will occur.

To deal with such errors, researchers have developed high-level language constructs. In this
section, we describe one fundamental high-level synchronization construct-the monitor type.

Monitor: A high-level abstraction that provides a convenient and effective mechanism for
process synchronization. Only one process may be active within the monitor at a time.

A abstract data type- or ADT- encapsulates private data with public methods to operate on
that data.
 A monitor type is an ADT which presents a set of programmer-defined operations that are
provided mutual exclusion within the monitor.

The monitor type also contains the declaration of variables whose values define the state of
an instance of that type, along with the bodies of procedures or functions that operate on those
variables. The syntax of a monitor type is shown below.

the programmer does not need to code this synchronization constraint explicitly. A
programmer who needs to write a tailor-made synchronization scheme can define one or more
variables of type condition:

• To allow a process to wait within the monitor, a condition variable must be declared, as
o condition x, y;
• Two operations on a condition variable:
o [Link] () – a process that invokes the operation is suspended.
o [Link] () – resumes one of processes (if any) that invoked [Link] ()
The [Link]() operation resumes exactly one suspended process. If no process is suspended,
then the signal() operation has no effect; that is, the state of x is the same as if the operation had
never been executed.
Dining Philosophers Solution using Monitos

We illustrate monitor concepts by presenting a deadlock-free solution to the dining-

philosophers problem. This solution imposes the restriction that a philosopher may pick up her
chopsticks only if both of them are available. To code this solution, we need to distinguish among
three states in which we may find a philosopher. For this purpose, we introduce the following data
structure:
enum{THINKING, HUNGRY, EATING}state[5];
Philosopher i can set the variable state [i] = EATING only if her two neighbors are not
eating: (state [ (i +4) % 5] ! = EATING) and (state [ (i +1) % 5] '= EATING). We also need to
declare condition
self[5];
In which philosopher i can delay herself when she is hungry but is unable to obtain the
chopsticks she needs.
usage:

Monitor Implementation Using Semaphores

• Variables
▪ semaphore mutex; // (initially = 1)
▪ semaphore next; // (initially = 0)
▪ int next_count = 0;
• Each external procedure F will be replaced by
 wait(mutex);
…
body of F;
…
if (next_count > 0)
signal(next)
else
signal(mutex);
• Mutual exclusion within a monitor is ensured.
• For each condition variable x, we have:
semaphore x_sem; // (initially = 0)
int x_count = 0;
• The operation [Link] can be implemented as:
x_count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x_count--;
• The operation [Link] can be implemented as:
if (x_count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count--;
}

• When we wake a process in the monitor, which process do we wake?

• Conditional-wait construct: [Link](c);
o c – integer expression evaluated when the wait operation is executed.
o value of c (a priority number) stored with the name of the process that is suspended.
o when [Link] is executed, process with smallest associated priority number is
resumed next.
• Check two conditions to establish correctness of system:
o User processes must always make their calls on the monitor in a correct sequence.
o Must ensure that an uncooperative process does not ignore the mutual-exclusion
gateway provided by the monitor, and try to access the shared resource directly,
without using the access protocols.