Department of Computer Engineering

Subject Name & code: Operating Systems(2160711)

A.Y. & semester: 2017-18, EVEN

Processes and Threads

By: Prof. Bhagirath Prajapati,
Computer Engineering Dept.

1
 Processes
The Process Model

a) Multiprogramming of four programs

b) Conceptual model of 4 independent, sequential processes
Only one physical program counter is there. When each process runs,
its logical program counter is loaded into physical program counter.
c) Only one program active at any instant
At any instant of time, CPU is running only one program.
But in the course of 1 second, it may work on several programs, thus giving
the users illusion of parallelism. It is also known as pseudoparallelism. 2
 Process Creation
Principal events that cause process creation
1. System initialization.
2. Execution of a process creation system call by running process.
3. User request to create a new process.
4. Initiation of a batch job.

System Initialization:
• When OS is booted, several processes are created.
• There may be foreground processes and background processes.
• Foreground processes interact with user and work for them.
• Background processes are not associated with particular users, but
have some specific function. e.g. process to accept incoming mail,
to accept incoming request for web pages etc.
• Processes that stay in the background to handle some activity such
as email, web pages, news, printing etc. are called daemons.

3
Execution of a process creation system:
• a running process issue system calls to create one or more new
processes to help it to do its job.

User request to create a new process:

• User can start a program by typing a command or clicking an icon.
• In both case, it will starts a new process and runs the selected
program in it.

Initiation of a batch job:

• It is applicable only to the batch systems found on large
mainframes.
• User submit batch jobs to the system. When OS decides that it has
the resources to run another job, it creates a new process and runs
the next job from the input queue in it.
• In both UNIX and Windows, after a process is created, both the
parent and child have their own address spaces. If either process
changes a word in its address space, the change is not visible to the
other process.
• In UNIX, the child’s initial address space is a copy of the parent’s,
but there are two distinct address space involved. Hence, it is
possible for a newly created process to share some of its parent’s
other resources such as open files.
• In Windows, the parent’s and child’s address space are different
from the start.
 Process Termination
Due to following conditions process terminates:
1. Normal exit (voluntary)
2. Error exit (voluntary)
3. Fatal error (involuntary)
4. Killed by another process (involuntary)

Normal exit:
• Process terminates when they have done their work.
• After compilation gets over, compiler executes system call to tell
OS that it is finished. This call is exit in UNIX.

Error exit:
• Process terminates when it finds a fatal error.
• For ex., trying to compile a program which does not exists.

6
Fatal error:
• Process terminates because of an error caused by itself, often due to
program bug.
• For ex, executing illegal instruction, referencing non existent memory,
divide by zero etc.
• In UNIX, it is possible to handle certain errors, where process is
signaled instead of termination.

Killed by another process:

• Process executes a system call telling the OS to kill some other
process.
• In UNIX, this call is kill.
• Only super user can use this system call.
 Process Hierarchies
• Parent creates a child process, child processes can create its own process
• Forms a hierarchy
– UNIX calls this a "process group“
– When a user sends a signal from keyboard, it is delivered to all members
of the process group currently associated with keyboard.
– Individually, each process can catch the signal, ignore the signal, or take
default action, which is to be killed by the signal.
– In UNIX, a special process called init, is present in the boot image. When
it starts running, it reads a file telling how many terminals there are. Then
it forks off one new process per terminal. These processes wait for
someone to log in. If a login is successful, login process executes a shell
to accept commands. These commands may start up more processes and
so forth.
• Windows has no concept of process hierarchy
– all processes are created equal

8
 Process States

• A process may be in one of the following states:

– Running (actually using CPU at that instant).
– Ready ( runnable; temporarily stopped to let another process run).
– Blocked ( unable to run until some external event happens).
• When a process blocks, it does so because logically it cannot continue,
typically because it is waiting for input that is not yet available. Here, the
suspension is inherent in the problem ( you cannot process the user’s
command line until it has been typed).
• It is also possible for a process that is conceptually ready and able to run to be
stopped because the OS has decided to allocate the CPU to another process for
a while. Here, it is the technicality of the system (not enough CPUs to give
each process its own private processor).

9
• Four transitions are possible among these three states:
1. Transition 1 occurs when a process discovers that it can not
continue. It happens when some input is required which is not
available.
2. Transition 2 occurs when the scheduler decides that the running
process has run long enough, and it is time to let another process
have some CPU time.
3. Transition 3 occurs when all other processes have had their fair
share and it is time for the first process to get the CPU to run again.
4. Transition 4 occurs when the external event for which a process was
waiting ( such as the arrival of some input) happens. If no other
process is running at that instant, transition 3 will be triggered and
the process will start running. Otherwise, it may have to wait in
ready state for a little while until the CPU is available and its turn
comes.
 Implementation of Processes
• OS maintains a table called process table, with one entry per process.
• These entries are also known as Process Control Blocks.
• Each entry contains information about
– Process’ state
– Program counter
– Stack pointer
– Memory allocation
– Status of its open files
– Accounting and scheduling information
– Everything else which must be saved when process is switched form one
state to other so that it can be restarted later as if it had never been
stopped.
Fields of a process table entry

12
 What OS does when interrupt occurs
• Associated with each I/O device class is a location called interrupt vector.
• It contains the address of interrupt service procedure.
• When any interrupt occurs, user process’ PC, PSW and possibly one or more
registers are pushed onto the stack by interrupt hardware.
• The computer then jumps to the address specified in the interrupt vector. That
is all hardware does.
• Now it is the task of interrupt service procedure.
• It starts working by saving registers, often in process table entry for the
current process.
• Then the information pushed onto the stack by the interrupt is removed and
the stack pointer is set to point to a temporary stack used by the process
handler.
• When this routine is finished, it calls a C procedure to do the rest of the work
for this specific interrupt type.
• When it has done its job, possibly making some process now ready, the
scheduler is called to see who to run next.
• After that, control is passed back to the assembly language code to load up the
registers and memory map for now-current process and start it running.

13
Skeleton of what lowest level of OS does when an
interrupt occurs

14
 Threads
• In traditional OS, each process has an address space and a single
thread of control.
• There are frequently situations in which it is desirable to have multiple
threads of control in the same address space running in quasi-parallel,
as though they were separate processes.
Thread Model:
• The process model is based on two independent concepts: resource
grouping and execution.
• Resource grouping: Process is a way to group related resources
together. A process has an address space containing program text, data,
open files, child processes, pending alarms, signal handlers,
accounting information etc.
• Execution: Other concept a process has is a thread of execution,
usually shortened to thread.

15
• The thread has
– A program counter that keeps track of which instruction to execute
next.
– Registers which hold its current working variables.
– Stack which contains the execution history, with one frame for
each procedure called but not yet returned from.
• Processes are used to group resources together, threads are the entities
scheduled for execution on the CPU.
• Having multiple threads running in parallel in one process is
analogous to having multiple processes running in parallel in one
computer. In the former case, the threads share an address space, open
files and other resources. In the latter case, processes share physical
memory, disks, printers and other resources.
• As threads are having some of the properties of processes, they are
sometimes called lightweight processes.

16
 Threads
The Thread Model

(a) Three processes each with one thread

– Each process has its own address space and a single thread of control.
– Each of them operates in a different address space.
(b) One process with three threads
– Single process with three threads of control.
– All three of them share same address space.
17
• When a multithreaded process is run on a single-CPU system, the
threads take turns running, just like a multiprogramming of processes.
• The CPU switches rapidly back and for the among the threads
providing illusion that the threads are running in parallel.
• Different threads in a process are not quite as independent as different
processes.
• All threads have exactly same address space, which means that they
also share same global variables. Since every thread can access every
memory address within the process’ address space, one thread can
read, write or even completely wipe out another threads’ stack.
• There is no protection between threads because
– It is impossible
– It should not be necessary.
– Unlike different processes, which may be from different users and
which may be hostile to one another, a process is always owned by
a single user, who has presumably created multiple threads so that
they can cooperate, not fight.

18
• Like a traditional process ( a process with only one thread), a thread can
be in any one of several states: running, blocked, ready or terminated.
• A running thread currently has CPU and is active.
• A blocked thread is waiting for some event to unblock it.
• A ready thread is scheduled to run and will as soon as its turn comes up.
• The transitions between thread states are same as those between process
states.

19
 Why thread needs its own stack?

• Each thread’s stack contains one frame for each procedure called but
not yet returned from. This frame contains the procedure’s local
variables and the return address to use when procedure call has
finished.
• Each thread will generally call different procedures and thus a
different execution history. This is why is thread needs its own stack.
20
• When multithreading is present, processes normally start with a single
thread present.
• This thread has the ability to create new threads by calling a library
procedure called thread_create.
– New thread automatically runs in the address space of the creating thread.
• When a thread has finished its work, it can exit by calling a library
procedure called thread_exit.
• In some systems, one thread can wait for a specific thread to exit by
calling a procedure thread_wait.
• Another thread call is thread_yield, which allows a thread to
voluntarily give up the CPU to let another thread run.
– This call is important because there is no clock interrupt to actually
enforce timesharing like process. Thus it is important for threads to be
polite and voluntarily surrender CPU from time to time to give other
threads a chance to run.
Questions imposed by multithreaded system
• If the parent process has multiple threads, should the child also have
them? If not, the process may not function properly, since all of them
may be essential.
• If the child process gets as many threads as parent, what happens if a
thread in parent was blocked on a read call, say, from keyboard? Are
two threads now blocked on keyboard, one in parent and one in child?
When a line is typed, do both threads get a copy of it? Only parent?
Only child?
• Thread shares many data structures. What happens if one thread closes
a file while another one is still reading from it?
• Suppose that one thread notices that there is too little memory and
starts allocating more memory. Part way through, thread switch occurs
and new thread also notices that there is too little memory and starts
allocating more memory. Memory will probably be allocated twice.
 Thread Usage
• Four reasons for having threads in system:
1. In many applications, multiple activities are going on at once. Some
of these may block from time to time. By decomposing such an
application into multiple sequential threads that run in quasi-
parallel, the programming model becomes simpler.
2. Threads do not have any resources attached to them, they are easier
to create and destroy than processes.
3. Threads yield no performance gain when all of them are CPU
bound, but when there is substantial computing and also substantial
I/O, having threads allows these activities to overlap, thus speeding
up the application.
4. Threads are useful on systems with multiple CPUs, where read
parallelism is possible.
 Thread Usage Example

A word processor with three threads

24
Thread Usage Example

A multithreaded Web server

Implementing Threads in User Space

A user-level threads package

26
• When thread package is entirely in user space, kernel knows nothing
about them. As far as the kernel is concerned, it is managing ordinary,
single-threaded processes.
• The threads run on top of a runtime system, which is a collection of
procedures that manage threads. (i.e. threqad_create, thread_exit,
thread_wait, thread_yield etc.)
• When threads are managed in user space, each process needs its own
private thread table to keep track of the thread in that process. This
table is analogous to the kernel’s process table, except that it keeps
track only of the per thread properties.
• The thread table is managed by run time system.
• When a thread is moved to ready state or blocked state, the
information needed to restart it is stored in the thread table, exactly the
same way as the kernel stores information about processes in the
process table.
 Advantages of thread implementation in user space
1. A user level thread package can be implemented on an OS that does
not support threads.
2. If the machine has an instruction to store all the registers and
another one to load them all, the entire thread switch can be done in
a handful of instructions, hence it is faster compare to trapping to
kernel.
3. The procedure that saves the thread’s state ( when a thread is
finished running for moment, thread_yield is called to save thread’s
information in the thread table) and the scheduler are just local
procedures, so invoking them is much more efficient than making a
kernel call. It makes thread scheduling fast.
4. User level threads allow each process to have its own customized
scheduling algorithm.
Disadvantages/problems of thread implementation in user space
1. Because of the blocking system call, when one thread executes
system call, it will trap to kernel and hence all threads of that
process will be stopped. i.e. one blocked thread will affect the other
threads.
2. Somewhat analogous to the problem of blocking system call is the
problem of page fault. If the program calls or jumps to an
instruction that is not in memory, a page fault occurs and OS will go
and get that instruction from disk. The process is blocked while the
necessary instruction is being located and read in. If a thread causes
a page fault, kernel, not even knowing about the existence of
threads, blocks the entire process until disk I/O is complete, even
though other threads might be runnable.
3. If a thread starts running, no other thread in that process will ever
run unless the first thread voluntarily gives up the CPU. Unless a
thread enters the runtime system of its own free will, the scheduler
will never get a chance.
Disadvantages/problems of thread implementation in user space

Solutions for problem of blocking system call.

• The system calls could all be changed to be non blocking,
but requiring changes to OS is unattractive. Besides, one of
the arguments for user level thread was precisely that they
could run with existing OS. In addition, changing the
semantics of system call will require changes to many user
programs.
• If it is possible to tell in advance if a call will block. In some
versions of UNIX, system call select exists which allows
caller to tell whether a prospective read will block. When
this call is present, the library procedure read can be
replaced with a new one that first does a select call and then
only does read call if it is safe. The code placed around the
system call to do the checking is called a jacket or wrapper.
Implementing Threads in the Kernel

A threads package managed by the kernel

31
• Kernel has a thread table that keeps track of all the threads in the system. It
holds each thread’s registers, state and other info.
• When a thread wants to create a new thread or destroy an existing thread, it
makes a kernel call, which then does the creation or destruction by updating
the kernel thread table.
• Kernel also maintains the traditional process table to keep track of processes.
• Cost is more compared to user level thread because of the system call required
to be used instead of run time system.
• When a thread blocks, kernel can run
– Another thread from the same process (if one is ready)
– A thread from different process
• Due to relatively greater cost of creating and destroying threads in kernel,
threads recycling is done by some system. When a thread is destroyed, it is
marked as not runnable, but its kernel data structures are not affected. Later,
when a new thread must be created, an old thread is reactivated, saving some
overhead.
• Kernel threads don’t require new non blocking system calls.
 Hybrid Implementations

Multiplexing user-level threads onto kernel- level threads

33
 Scheduler Activations
• Goal – mimic functionality of kernel threads
– gain performance and flexibility of user space threads
• Avoids unnecessary user/kernel transitions
• Kernel assigns virtual processors to each process
– lets runtime system allocate threads to processors
• Problem:
Fundamental reliance on kernel (lower layer)
calling procedures in user space (higher layer)

34
 Pop-Up Threads

• Creation of a new thread when message arrives

(a) before message arrives
(b) after message arrives
35
 Making Single-Threaded Code Multithreaded (1)

Conflicts between threads over the use of a global variable

36
Making Single-Threaded Code Multithreaded (2)

Threads can have private global variables

37
 Interprocess Communication
• Three issues related to interprocess communication:
1. How one process can pass information to another.
2. It has to be make sure that two or more processes do not get into
each other’s way when engaging in critical activities.
3. Proper sequencing is required when dependencies are present.

All these issues apply equally well to threads also.

 Race Conditions

Where two or more processes are reading or writing some shared data and the final
result depends on who runs precisely when are called race conditions.

39
 Critical Regions
• To avoid race conditions, we require mutual exclusion, that is, some way of
making sure that if one process is using a shared variable or file, the other
processes will be excluded from doing the same thing.
• The part of the program where the share memory is accessed is called the critical
region or critical section.
• If we could arrange matters such that no two processes were ever in their critical
regions at the same time, we could avoid races.

Four conditions to hold to have a good solution of race conditions:

1. No two processes simultaneously in critical region
2. No assumptions made about speeds or numbers of CPUs
3. No process running outside its critical region may block another process
4. No process must wait forever to enter its critical region
 Mutual Exclusion with Busy Waiting
• Disabling Interrupts
– Disable all interrupts just after entering into critical region and re-enable
them just before leaving it.
– No clock interrupts can occur.
– Unattractive because it is unwise to give user processes the power to turn
off interrupts.
– In multiprocessor system, disabling interrupts affects only the CPU that
executed disable instruction. The other ones will continue running and can
access the shared memory.
– Kernel can itself disable interrupts for a few instructions while it is
updating variables or lists.
– It is often useful technique within the OS itself but not appropriate as a
general mutual exclusion mechanism for user processes.
 Mutual Exclusion with Busy Waiting
• Lock Variables
– A single, shared (lock) variable is maintained, initially 0.
– 0 means no process is in its critical region, 1 means some process is in its
critical region.
– First tests the lock before entering into critical region.
– If the lock is 0, set it to 1 and enter into critical region.
– If the lock is already 1, wait until it becomes 0.
– Problem with Lock variable:
• One process reads the lock and sees that it is 0. Before it can set the
lock to 1, another process is scheduled, runs, and sets the lock to 1.
When first process runs again, it will also set lock to 1. Hence, two
processes will be in their critical region at a time.
 Mutual Exclusion with Busy Waiting
• Strict Alternation

– The integer variable turn, initially 0, keeps track of whose turn it is to

enter the critical region and examine or update the shared memory.
– Initially process 0 inspects turn, finds it to be 0, and enters its critical
region.
– Process 1 also finds it to be 0 and therefore sits in a tight loop continually
testing turn to see when it becomes 1.
– When process 0 leaves the critical region, it sets turn to 1, to allow
process 1 to enter its critical region.
– Continuously testing a variable until some value appears is called busy
waiting. (usually it should be avoided as it wastes CPU time)
– A lock that uses busy waiting is called a spin lock.
 Mutual Exclusion with Busy Waiting
• Problem with Strict Alternation
– Suppose that process 0 leaves the critical region, it sets turn to 1, to allow
process 1 to enter its critical region.
– Process 1 finishes its critical region quickly, so both processes are in their
non critical regions, with turn set to 0.
– Now process 0 executes whole loop quickly, exiting is critical region and
setting turn to 1. At this point, turn is 1 and both processes are executing
in their non critical regions.
– Suddenly, process 0 finishes its non critical region and goes back to the
top of its loop. But it is not permitted to enter its critical region now
because turn is 1 and process 1 is busy with its non critical region.
– Means, taking turns is not a good idea when one of the processes is much
slower than the other.
– This situation violates condition 3: process 0 is being blocked by a
process not in its critical region.
 Mutual Exclusion with Busy Waiting
• Peterson’s Solutions
– Before entering into critical region, each process calls enter_region with
its own process number, 0 or 1, as parameter.
– This call will cause it to wait, if need be, until it is safe to enter.
– After finishing with critical region, the process calls leave_region to
indicate that it is done and to allow the other process to enter, if it so
desires.
Working: Initially neither process is in its critical region.
– Process 0 calls enter_region. It indicate its interest by setting its array
element and sets turn to 0.
– Since prcoess 1 is not interested, enter_region returns immediately.
– If process 1 now calls enter_region, it will hang there until interested[0]
goes to false, which will only happen when process 0 calls leave_region to
exit the critical region.
– When both processes call enter_region almost simultaneously, both will
store their process no in turn. Whichever store is done last is the one that
counts; the first one is overwritten and lost. Suppose that process 1 stores
last, so turn is 1. When both processes come to while statement, process 0
executes it zero times and enters its critical region. Process 1 loops and
 Mutual Exclusion with Busy Waiting

Peterson's solution for achieving mutual exclusion

 Mutual Exclusion with Busy Waiting
The TSL instruction
TSL RX, LOCK
– It reads the contents of memory word lock into register RX and stores a nonzero
value at memory address lock.
– The operation of reading the word and storing into it are indivisible operation – no
other processor can access the memory word until the instruction is finished.
– CPU executing TSL instruction locks the memory bus to prohibit other CPUs from
accessing memory until it is done.

Mutual Exclusion using TSL instruction:

– A shared variable lock is used.
– When lock is 0, any process may set it to 1 using TSL instruction and then read or
write shared memory. When it is done, process sets lock back to 0 using ordinary
move instruction.
 Mutual Exclusion using TSL instruction

– Process wants to access critical region, calls enter_region, in which

• First instruction copies old value of lock to the register an then sets
lock to 1.
• Then old value is compared with 0.
• If it is nonzero, the lock was already set, so program goes back to
beginning and tests it again.
• Later when it becomes 0, returns from enter_region with lock set.

– When process finishes with critical region, calls leave_region and sets
lock to 0

• enter_region:
TSL REGISTER, LOCK
CMP REGISTER,#0
JNE enter_region
RET
• Leave_region:
MOVE LOCK,#0
RET
 Sleep and Wakeup
• Problems with peterson’s solution and TSL instruction:
– Require busy waiting – hence waste CPU time
– Priority Inversion Problem:
• Consider a computer with two processes, H with high priority and L
with low priority.
• The scheduling rules are such that H is run whenever it is in ready
state.
• At a certain moment, with L in its critical region, H becomes ready to
run.
• H now begins busy waiting but since L is never scheduled while H is
running, L never gets chance to leave its critical region, so H loops
foreever.

• Interprocess communication primitives: sleep and wakeup

– It blocks the process instead of wasting CPU time.
– Sleep is a system call that causes the caller to block, that is, be suspended
until another process wakes it up.
– The wakeup call has one parameter, the process to be awakened.
• Producer-Consumer Problem:
– Also known as Bounded-buffer problem.
– Two processes share a common, fixed-size buffer.
– One of them, producer, puts information into the buffer, the other one,
consumer, takes it out.
– Trouble arises when producer wants to put a new item in buffer, but is
already full. The solution is for the producer to go to sleep, to be
awakened when consumer has removed one or more items.
– Similarly, if consumer wants to remove an item from the buffer and sees
that the buffer is empty, it goes to sleep until produces puts something in
buffer and wakes it up.
Producer-consumer problem with Sleep and Wakeup
– Race condition:
• It can occur because access to count is unconstrained.
• Suppose buffer is empty and the consumer has just read count to see
if it is 0. At that instant, the scheduler decides to stop running the
consumer temporarily and start running the producer. The producer
inserts an item in buffer, increments count, and notices that it is now
1. Reasoning that count was just 0, and thus, the consumer must be
sleeping, the producer calls wakeup to wake the consumer up.
• Unfortunately, the consumer is not yet logically asleep, so the wakeup
signal is lost. When consumer next runs, it will test the value of count
it previously read, find it to be 0, and go to sleep. Sooner or later,
producer will fill up the buffer and also go to sleep. Both will sleep
forever.

– Solution:
• Wakeup waiting bit is to be added.
• When a wakeup is sent to a process that is still awake, this bit is set.
• Later, when process tries to go to sleep, if the wakeup waiting bit is
on, it will be turned off, but the process stay awake.
• The wakeup waiting bit is piggy bank for wakeup signals.
 Semaphores
• It is a variable to count the no of wakeups saved for future use.
• A semaphore could have the value 0, indicating that no wakeups were saved,
or some positive value if one or more wakeups were pending.
• Two operations : Down & Up
• Down operation on a semaphore checks to see if the value is greater than 0. If
so, it decrements the value (uses one stored wakeup) and just continues. If the
value is 0, the process is put to sleep without completing down for the
moment.
• Checking the value, changing it and possibly going to sleep is (indivisible)
atomic action.
– It is guaranteed that once a semaphore operation has started, no other
process can access the semaphore until the operation has completed.
• The up operation increments the value of the semaphore addressed.
– If one or more processes were sleeping on that semaphore, unable to
complete an earlier down operation, one of them is chosen by the system
and is allowed to complete its down.
– Thus, after an up on a semaphore with processes sleeping on it, the
semaphore will still be 0, but there will be one fewer process sleeping on
it.
The producer-consumer problem using semaphores
• Three semaphores are used:
– full: count the number of slots that are full, initially 0.
– empty: count the number of slots that are empty, initially equal to number
of slots in the buffer.
– mutex: take care the producer and consumer do not access the buffer at
the same time, initially 1.

• Semaphores that are initialized to 1 and used by two or more processes

to ensure that only one of them can enter its critical region at the same
time are called binary semaphores.

• full and empty semaphores are used for synchronization and mutex
semaphore is used for mutual exclusion.
 Mutexes
• It is used when semaphore’s ability to count is not needed.
• Mutexes are good only for managing mutual exclusion to some shared
resource or piece of code.
• They are useful in thread packages that are implemented entirely in
user space.
• Mutex is a variable that can be in one of two states: unlocked or
locked. 0 means unlocked and all other values meaning locked.
• Two procedures are used with mutexes.
– When a thread (or process) needs access to a critical region, it calls
mutex_lock. If the mutex is current unlocked, the call succeeds and the
calling thread is free to enter the critical region.
– If mutex is already locked, the calling thread is blocked until the thread in
the critical region is finished and calls mutex_unlock.
• As mutexes are simple, they can easily be implemented in user space
if a TSL instruction is available.
Implementation of mutex_lock and mutex_unlock
• Difference between call to mutex_lock and enter_region:
– When enter_region fails to enter the critical region, it does busy waiting.
– Eventually clock interrupt switches cpu to other process, which may release
lock.
– With threads, as no clock interrupt is available, thread that tries to acquire a
lock by busy waiting will loop forever and never acquire the lock because it
never allows any other thread to run and release the lock.
– In mutex_lock, when thread fails to acquire a lock, it calls thread_yield to give
up CPU to another thread.
– No busy waiting. When thread runs next time, it tests the lock again.
– As thread_yield is just a call to thread scheduler in user space, it is very fast.
– Not required for kernel involvement.
• If processes have disjoint address spaces, how can they share turn variable in
peterson’s algorithm, or semaphores or a common buffer? Answer is:
– Some of the shared data structures, such as the semaphores, can be stored in
the kernel and only accessed via system calls.
– Most OS offer a way for processes to share some portion of their address space
with other processes.
– In nothing else is possible, a shared file can be used.
 Monitors
• Problem with semaphores:
– Suppose that two down’s in the producer’s code were reversed in order, so
mutex was decremented before empty instead of after it. If the buffer were
completely full, the producer would block, with mutex set to 0. consequently,
next time when consumer tried to access the buffer, it would do a down on
mutex, now 0, and block too. Both processes would stay blocked forever.
– Care must be taken while using semaphores.
• Monitor is a higher-level synchronization primitive.
• It is a collection of procedures, variables, and data structures that are all grouped
together in a special kind of module or package.
• Processes may call the procedures in a monitor whenever they want to, but they
cannot directly access the monitor’s internal data structures from procedures
declared outside the monitor.
• It have an important property that only one process can be active in a monitor at
any instant.
• It is a programming language construct, so compiler will handle it accordingly.
• As the compiler is arranging for mutual exclusion, it is much less likely that
something will go wrong.
• It is sufficient to know that by turning all the critical regions into monitor
procedures, no two processes will ever execute their critical region at the same
time.
Monitors

Example of a monitor
60
• Along with mutual exclusion, a way for processes to block is also needed when
they cannot proceed.
• We can have two condition variables full and empty along with two operations on
them, wait and signal.
• When a monitor procedure discovers that it cannot continue because of full buffer,
it does a wait on variable full. This action causes the calling process to block. It
also allows another process that had been previously prohibited from entering the
monitor to enter now.
• This other process, the consumer, can wake up its sleeping partner by doing a
signal on the condition variable that its partner is waiting on.
• A process doing a signal must exit the monitor immediately to allow another
process to get scheduled.
• Sleep and wakeup failed because while one process was trying to go to sleep, the
other one was trying to wake it up. With monitors, this cannot happen. The
automatic mutual exclusion on monitor procedures guarantees that processes will
be able to finish wait/signal before other process enters monitor.
• Problems with monitors:
– It is a programming language construct. The compiler must recognize them
and arrange for mutual exclusion somehow.
– Monitors and semaphores are designed for solving mutual exclusion problem
on one or more CPUs that all have access to a common memory. In a
distributed system consisting of multiple CPUs, each with its own private
memory, connected by a LAN, these primitives become inapplicable.

• Conclusion:
– Semaphores are too low level and monitors are not usable except in a few
programming languages. Also, none of the primitives provide for information
exchange between machines.
 Message Passing
• This method of inter process communication uses two primitives, send and receive.
• They are system calls and can be available as library procedures.
• Design issues for message passing systems:
– Acknowledgement message is to be sent back to sender to guard against lost
messages. If the sender does not receive acknowledgement message within a
time interval, it retransmit the message.
– If message itself it received correctly but acknowledgement is lost. It is
essential to distinguish a new message from retransmitted one. It can be solved
by putting consecutive sequence no in each original msg.
– Naming of processes
– Authentication
– performance
 Message Passing

The producer-consumer problem with N messages

64
 Barriers

• Use of a barrier
– processes approaching a barrier
– all processes but one blocked at barrier
– last process arrives, all are let through
65
 Scheduling
• The part of OS that makes the choice between processes which one should run next
is called Scheduler, and the algorithm it uses is called Scheduling Algorithm.
• Computer Bound processes are those who spend most of their time in computing,
using CPU.
– Have lond CPU bursts
– Infrequent I/O waits
• I/O Bound processes are those who spend most of their time waiting for I/O.
– Short CPU bursts
– Frequent I/O waits
• As CPUs are improved much faster than disks, If an I/O bound process wants to
run, it should get a chance quickly so it can issue its disk request and keep the disk
busy.
 Scheduling
• When to schedule?
1. When a new process is created:
– A decision needs to be made whether to run the parent process or the child
process.
2. When a process exits:
– As process can no longer run, some other process must be chosen from the
set of ready processes.
3. When a process blocks on I/O, on a semaphore or for some other reason.
4. When an I/O interrupt occurs:
– If interrupt comes from an I/O device that has now finished its work, some
process that was blocked waiting for I/O may now be ready to run.
– It is up to Scheduler to decide to run newly ready process, process that was
running when interrupt arrived should continue running, or some third
process should run.
 Scheduling
Two main categories with respect to how they deal with clock interrupt:
• Nonpreemptive:
– Pick a process to run until it blocks or until it voluntarily releases the CPU.
– CPU will not be forcefully taken back.
– No scheduling decision are made during clock interrupts.
• Preemptive:
– Picks a process and let it run for a max of some fixed time.
– Currently running process is suspended at every clock interrupt.
Three categories with respect to environment in which they work:
• Batch:
– No users are waiting for a quick response.
– Non preemptive algorithms or preemptive algorithm with long time periods
can be used.
• Interactive:
– Preemption is essential to keep one process from hogging CPU and denying
service to the others.
• Real time:
– Preemption is sometimes not needed because processes know that they may
no turn for long periods of time.
Scheduling Algorithm Goals

69
 Scheduling in Batch Systems
• First Come First Served:
– It is non preemptive
– Processes are assigned the CPU in order they request it.
– A single queue of ready processes are maintained.
– When the running process blocks, the first process on the queue is run next. When a
blocked process becomes ready, like a newly arrived job, it is put on the end of the
queue.
• Advantages:
– Easy to understand
– Easy to program
– Giving fair chance to process. (one which is waiting since long, given first chance)
• Disadvantages:
– Non Preemption sometimes increase run time of process
• Shortest Job first:
– It assumes that run times of processes are known in advance.
– When several equally important jobs are sitting in the input queue waiting to be
started, the scheduler picks the shortest job first.
• Example:
– Four jobs A,B,C, and D with run times of 8,4,4 and 4 minutes.
– By running them in this order, turnaround time for A is 8 minutes, for B is 12
minutes, for C is 16 minutes and for D is 20 minutes, for an average of 14 minutes.
– Using shortest job first strategy, the turnaround times are now 4,8,12 and 20
minutes for an average of 11 minutes.

• Advantage:
– It is optimal. For example, consider four jobs with run times of a, b, c and d
respectively. First job finishes at time a, second finishes at time a+b, and so on.
– The mean turnaround time is (4a+3b+2c+d)/4.
– It is clear that a contributes more to average than other so it should be shrotest, with
b next, then c and finally d as the longest as it affects only its own turnaround time.
• Disadvantage:
– It is optimal only when all the jobs are available simultaneously.
• Shortest Remaining time Next:
– It is a preemptive version of shortest job first.
– It always chooses the process whose remaining run time is shortest.
– It also assumes that run times of processes are known in advance.
– When a new job arrives, its total time is compared to the current process’ remaining
time.
– If new job needs less time to finish than current process, the current process is
suspended and new job is started.

• Advantage:
– It allows new short jobs to get good service.
Three level scheduling
73
 Scheduling in Interactive Systems
• Round Robin Scheduling:
– It is oldest, simplest, fairest and most widely used algorithm.
– Each process is assigned a time interval, called quantum.
– If the process is still running at the end of the quantum, the CPU is preempted and given to
another process.
– List of runnable processes is maintained. When the process uses up its quantum, it is put on the
end of the list as show below.

• Length of quantum:
– Suppose that context switch takes 1 ms and quantum is 4 ms. With this parameters, after doing 4
ms of useful work, CPU will have to spend 1 ms on process switching. 20% of CPU time will be
wasted on administrative overhead.
– To improve CPU efficiency, if quantum is set to 100 ms, wasted time will be 1%. But for
interactive system, it is not good to wait for 100 ms for every response.
– Conclusion: Setting quantum too short causes too many process switches and lowers the CPU
efficiency, and setting it too long cause poor performance for short interactive request. Hence,
quantum around 20-50 ms is often a reasonable compromise.

74
• Priority Scheduling:
– Each process is assigned a priority, and the runnable process with highest priority is
allowed to run.
– To prevent high-priority processes from running indefinitely, the scheduler may
decrease the priority of currently running process at each clock tick. If this action
causes its priority to drop below that of the next highest process, a process switch
occurs.
– Alternatively, each process may be assigned a maximum time quantum that it is
allowed to run. When this quantum is used up, the next highest priority process is
given a chance to run.
– Priorities can be assigned to processes statically or dynamically.
– A simple algorithm for giving good service to I/O bound processes is to set the
priority to 1/f, where f is the fraction of last quantum that a process used. A process
that used only 1 ms of its 50 ms quantum would get priority 50, while a process that
ran 25 ms before blocking would get priority 2, and a process that used the whole
quantum would get priority 1.
– Group processes into priority classes and use priority scheduling among the classes
but round-robin within each class.
– The scheduling algorithm is as follows: as long as there are runnable processes in
priority class 4, run each one for one quantum, round robin fashion. If priority class
4 is empty, then run class 3 processes round robin and so on.
– If priorities are not adjusted occasionally, lower priority classes may all starve to
death.
• Multiple Queues:
– Set up process in priority classes.
– Processes in the highest class run for one quantum. Processes in next highest class
run for two quantum and so on.
– Whenever a process used up all the quantum allocated to it, it was moved down one
class.
– Consider a process that needed to compute continuously for 100 quantum. It would
initially be given one quantum, then swapped out. Next time it would get two
quantum and swapped out. On succeeding runs it would get 4,8,16,32 and 64
quantum, although it would have used only 37 of the final 64 quantum to complete
it s work. Only 7 swaps are needed instead of 100 with a pure round-robin
algorithm.
• Shortest Process Next:
– As shortest job first always produce minimum average response time for batch
system, it would be nice if it could be used for interactive processes as well.
– Interactive processes generally follow the pattern of wait for command, execute
command, wait for command, and so on.
– The only problem is figuring out which of the currently runnable processes is the
shorter one.
– One approach is to make estimates based on past behavior and run the process with
the shortest estimated running time.
– Suppose that estimated time per command for some terminal is T0, Next run is
measured to be T1. Estimate can be updated by taking a weighted sum of these two
numbers, that is aT0 + (1-a)T1. with a = ½,
T0, T0/2 + T1/2, T0/4 + T1/4 + T2/2, T0/8 + T1/8 + T2/4 + T3/2
– The technique of estimating the next value in series by taking the weighted average
of the current measured value and the previous estimate is sometimes called aging.
• Guaranteed Scheduling:
– Make real promises to the users about performance and then live up to them.
– The promise is: if there are n users logged in while a process is working, it will
receive about 1/n of the CPU power.
– To make good on this promise, the system must keep track of how much CPU
each process has had since its creation. It then computes the amount of CPU
each one is entitled to, namely the time since creation divided by n.
– Since the amount of CPU time each process has actually had is also known, it
is straightforward to compute the ratio of actual CPU time consumed to CPU
time entitled.
– A ratio of 0.5 means that a process has only had half of what is should have
had and a ratio of 2 means that a process has had twice as much as it was
entitled to.
– The algorithm is then to run the process with the lowest ratio until its ratio has
moved above its closet competitor.

• Disadvantage:
– It is difficult to implement
• Lottery Scheduling:
– Idea is to give processes lottery tickets for various system resources, such as
CPU time.
– Whenever scheduling decision has to be made, a lottery ticket is chosen at
random and the process holding that ticket gets the resource.
– When applied to CPU scheduling, the system might hold a lottery 50 times a
second, with each winner getting 20 ms of CPU time as a prize.
– More important processes can be given extra tickets, to increase their chance
of winning.
– If there are 100 tickets outstanding, and one process holds 20 of them, it will
have a 20 percent chance of winning each lottery.
– In contrast to Priority scheduler, where it is very hard to state what having a
priority of 40 actually means, here the rule is clear: a process holding a
fraction f of the tickets will get about a fraction f of the resource in question.
• Important properties:
– If a new process show up and is granted some tickets, at the very next lottery it
will have a chance of winning in proportion to the no of tickets it holds. i.e.
lottery scheduling is highly responsive.
– Cooperating processes may exchange tickets if they wish. For example, when
a client process send a message to a server process and then blocks, it may
give all of its tickets to the server, to increase the chance of the server running
next. When the server is finished, it returns the tickets so that client can run
again.
• Fair Share Scheduling:
– So far it is assumed that each process is scheduled on its own, without regard
to who its owner is.
– As a result, if user 1 starts up 9 processes and user 2 starts up 1 process, with
round robin or equal priorities, user 1 will get 90% of the CPU and user 2 will
get only 10% of it.
– To prevent this situation, owner of process is taken into account.
– Each user is allocated some fraction of the CPU and the scheduler picks
processes in such a way as to enforce it.
– Thus if two users have each been promised 50% of the CPU, they will each
get that, no matter how many processes they have in existence.
 Scheduling in Real-Time Systems
• The events that a real time system may have to respond to is
categorized as
– Periodic events (occurring at regular intervals)
– Aperiodic (occurring unpredictably)
• A system may have to respond to multiple periodic events. Depending
on how much time each event requires for processing, it may not even
be possible to handle them all. For example, there are
– m periodic events
– event i occurs with period Pi and requires Ci seconds
– Then the load can only be handled if
m
Ci

i 1 Pi
1

• A real time system that meets this criteria is said to be schedulable.

81
 Policy versus Mechanism

• Separate what is allowed to be done with how it is done

– a process knows which of its children threads are important and need priority
– Take input from user processes about scheduling decisions.

• Scheduling algorithm parameterized

– mechanism in the kernel
– Parameters filled in by user processes
– policy set by user process
– For example, kernel uses priority scheduling algorithm but provides a system
call by which a process can set and change the priorities of its children.

82
 Thread Scheduling

Possible scheduling of user-level threads

• 50-msec process quantum
• threads run 5 msec/CPU burst

83
 Thread Scheduling

Possible scheduling of kernel-level threads

• 50-msec process quantum
• threads run 5 msec/CPU burst

84