OPERATING SYSTEMS II

CSC3002F
 Processes
• Program: static piece of compiled code
o By itself, does nothing
o Only becomes process when run by OS
• Process: program in execution
• OS provides environment for program execution and services to those executing programs
• OS distinguishes between two different kinds of processes:
o OS processes – run at more privileged level, provides services that OS exposes to
other kind of process
o User based process – the kind of process that we run
▪ This process may need to access kernel services which are themselves
processes
• OS has (OS processes + user processes) executing concurrently
• Have large number of processes running in system, all doing work, in various stages
o Need to ensure that they’re executing correctly
o Want to avoid inappropriately access shared memory etc
• Three main phases for processes:
o (1) Creation – initialisation, what code they run, etc
o (2) Scheduling – which process should run next
▪ Needed because have limited # of processing cores
▪ OS creates illusion of infinite # of processers – and all processes can run
concurrently (impossible)
• This happens when have worst case of one core
▪ OS scheduler deals with all this
o (3) Termination
• OS also enables inter-process communication (ipc)
• Process: unit of work in a time-sharing/multi-tasking OS
o Also called a job
o All modern OSes are time-sharing/multitasking OSes – appear to be running multiple
tasks at the same time
▪ Need to use time-sharing mechanism to create this illusion
• A user creates a process by double-clicking or running a program from the command line
o Two copies of a program running are two separate processes – OS is smart enough
to not duplicate program code, and other shared states between them
• A program is a static entity (the code)
o The specification, compiled code that process has to run
• A process is a dynamic entity – a program in memory executing or ready to execute
o Need to consider memory implications i.to usage

Process vs Program
• OS provides this process to run program – has lower access lvl than kernel
o Kernel is core of OS – provides services to user programs
o Distinguish between things running in kernel vs user mode

2|Page
 ▪ User can only run processes in user mode – lower access processes which
can’t modify certain things e.g. an area of disk/memory
• Such services would be provided by kernel through a kernel API
• User process would use that to get access to protected services
• A process is the execution of an application program with restricted rights
o The process is the abstraction for protected execution provided by the operating
system kernel
o Kernel provides restricted environment for program to run in
• A process needs permission from the operating system kernel before accessing the memory
of any other process, before reading or writing to the disk, before changing hardware
settings, and so forth
• Linux – use ps -A cmd
o Many options for ps
o PID is process ID – unique
o Child process can be spawned by parent process – thus have PID
o Processes can also be execution environment for other code

Process Tree

• Parent process creates children processes, which, in turn create other processes, forming a
tree of processes
o Every process has a parent – exception is process created by kernel when the PC first
boots
▪ In diagram, given name init
• Identified and managed via a process identifier (PID)

Linux Parent Process

• Linux cmds:
o ps -A - -forest OR pstree
• The init or systemd or launchd process (depending on distro) is the parent of all processes
on the system
o First program that is executed on boot
o Manages all other processes on the system

3|Page
 o Started by the kernel itself, so in principle it does not have a parent process
o Always has process ID of 1

Aside: Multiprocess Architecture: Web Browsers

• Web browsers such as Chrome, Internet Explorer, Firefox, and Safari, play a role similar to an
OS
• Browsers load and display web pages, but many pages embed scripting programs that the
browser must execute
o These scripts can be buggy or malicious; hackers have used them to take over vast
numbers of home computers

Process Creation
Process Context

• Surrounding info that’s required to ensure process can execute correctly

o This context includes necessary data to manage the orderly transfer of processes
between different states – can be waiting, sleeping etc.

4|Page
 • A process is a program together with its execution context which encompasses:
o The state of the processor (processor context), which is the value of its program
counter and all of its registers
▪ Recall that program counter is where next instruction is stored in memory
▪ This part of execution context is necessary for a process to be stopped and
then restarted at a later point
o Process’ memory map, which identifies the various regions of memory that have
been allocated to the process
▪ Can involve paging, etc
• A process in memory comprises:
o Text (compiled code) – static program; has no meaning unless executing (then
considered a process)
o Current state (incl. program counter and registers)
o Have memory regions that process stores info as it executes
▪ Static region contains global data – fixed over process’ lifetime
• Corresponds to static keyword in languages
o Stack (function parameters, return addresses, temporary data/local data)
▪ The stack holds the state of local variables during procedure calls.
▪ Limited resource – stores function call mechanism in memory
▪ When call function – essentially push series of parameters onto stack that
represent arguments to that function and return address (so function can
return to correct place and continue executing code)
▪ Function can call another function – creates another stack frame, which
does the same
▪ When create local variable inside a function – that variable is created on
stack as well
▪ Stack can run out with deep recursion
▪ On diagram – arrows pointing towards each other should never converge
• If they do, have crit failure of memory resource and will have some
kind of error e.g. segmentation fault / other kernel lvl signal to show
there’s an issue with memory usage
o Data (initialized static and global variables)
o Heap (memory dynamically added during runtime – e.g. using malloc or new)
▪ The heap holds any dynamically allocated data structures the program might
need
▪ Dynamic store – e.g. all calls to new in Java, c++ ex require space from heap
▪ Used, then freed up and returned to the system
▪ Happens automatically in java

Process Lists/Table
• To keep track of processes, the operating system maintains a process table (or list)
o List/ double linked list data structure
• Each entry pertains to each process which is running/ can run in that system
o Process isn’t always running – can be sleeping, waiting for i/o
o Need to record these states so OS can operate appropriately e.g schedule next
available thread/process onto the next core

5|Page
 • Large, complete data strc – stores all info that kernel requires to manage processes
effectively
o Scheduler makes heavy use of PCB
• Each entry in the process table is a Process Control Block (PCB)
o Corresponds to a particular process
o Contains fields with information that the kernel needs to know about the process
• A process is identified by a unique process ID (PID)
• Some OSes (UNIX-derived systems) have a notion of a process group
o A way to group processes together so that related processes can be signalled
▪ E.g. send terminal signal to process group – all processes in that group will
be terminated
o Collection of processes are doing some common task
o Every process is a member of some process group

Process Control Block

• Info associated with each process (also task control block)

o Process state – running, waiting, etc
▪ Knowing process state is critical to ensuring that it’s managed correctly
o Program counter – location of instruction to next execute
▪ Necessary manage how processes resume once they’ve stopped and when
they’re running, prog counter points to next instruction to be executed
o CPU registers – contents of all process centric registers, number and type is
architecture dependent
▪ Contains necessary info from CPU when a process is halted
▪ Crit to correct running of sys
o CPU scheduling information – priorities, scheduling queue pointers
▪ E.g. a certain process must run frequently because it’s important
o Memory-management info - memory allocated to the process
▪ Mapping, paging, etc
o Accounting information – CPU used, clock time elapsed since start, time limits
▪ How process is allowed to operate

6|Page
 ▪ For well-managed processes – need to place limits on them (can’t hog core)
o I/O status information – I/O devices allocated to process, list of open files
▪ Series of queues attached to each IO device
▪ Info that pertains to files that the process is manipulating
• Aside – modern OSes operate at finer granularity and use threads (essentially lightweight
processes)

Process Representation
• Linux:
o In Linux, the PCB is implemented as the data structure task_struct
▪ Contain info about a process, such as process id, process state, file
information, and so on
• OSes are written in C – lower lvl language
o C is well-suited to resource management at a low lvl
• The process block is the most complicated data structure in the operating system
o E.g. task_struct contains 83 field variables; 60 are primitive types, 3 are composite
data structures, and 20 are pointers to composite data structures

7|Page
Process Creation Unix

• UNIX has a system call to allow a process to spawn another process

o fork() system call creates new (child) process
o Executes independently of parent (but parent can wait())
▪ E.g. can force the parent to wait for child to terminate
o Execution continues in BOTH processes after fork() statement
o fork() can be dangerous in the wrong hands
• Once process uses a fork to create a child – for those processes, there are a series of options
that need to be set – determines how they run past that point
o Essentially, they then execute concurrently – leads to all the concurrency issues
• C code (above)
o Call fork cmd – creates a child process with identifier stored in pid
▪ Now have parent process and child – both execute at the instruction
immediately after fork cmd
o Both print out statement with process id
o Put parent into wait state – then stops operating
▪ Scheduler removes it from core and it goes onto wait queue
o Once child is terminated, the parent process is woken up and continues

Process Creation
• When creating a child process – need to determine how resources will be allocated to that
child
• Resource sharing options for processes
o Parent and children share all resources
o Children share subset of parent’s resources (e.g. Linux)
o Parent and child share no resources (e.g. Windows)
• Also have different options for how child and parent will execute after the fork() cmd – i.e.
child process creation
• Execution options
o Parent and children execute concurrently – as two independent processes that can
terminate separately or parent can wait for child

8|Page
 ▪ Also can overlay an additional program in child process and have it execute
that instead – child executes its own program
o Parent waits until children terminate
• Address space
o Child duplicate of parent - behaviour of fork system call in UNIX
▪ Have the same window in the address space – allows for easy sharing of info
between processes
▪ But often also want child to do something else
o Child has a program loaded into it - behaviour of exec system call in UNIX
▪ Replaces parent program with a new program – creates a new address space
and destroys whatever was there before and now operate completely
independently
• Running different programs
▪ A common use case

UNIX Example

• If process ID is negative => fork has failed

o If 0, know we’re in the child process, can then write logic for that
• Write execlp – variant of exec cmd
o Allows for input of cmd line parameters passed into a given executable
• Run directory listing program
• Program then terminates
• Inside parent, further down
o Execute wait cmd – waits until child terminates
o Since there’s only one child – unambiguous
• Issue exit cmd – signal to OS to terminate process and recoup all its resources
o Can either explicitly ask process to exit or can simply return
▪ With return, have return code and exit called on your behalf – use return #
as exit code

9|Page
Fork Example

• Fork is always used to create a child process from another process – can cascade these
• Execution continues IN BOTH process, after the fork() command
o Running the same code in parallel (unless exec used)
• Can check process ID
o If zero, we know we’re in a child process with some parent that used fork() to create
it
• Q: How may processes will be created by the small program below?
• A: 8!
o Doubling each time we fork() – why?
o At first lvl – program executes, hits first fork cmd, creates a new child process
▪ Now have parent and child
o One fork cmd has occurred – so crossed out
o Execution resumes in both processes after that
▪ Another fork – both go ahead and execute
▪ Now have two separate processes, executing fork
o Each of these now create another process
▪ Parent spawns a new child – 3rd column
▪ Another fork crossed out
▪ Now have parent and child, and then original child and its child
o All four of these have fork cmd to execute
▪ That happens – creates new subchild for each of those
• Now have 8 processes running

10 | P a g e
 Process State

• Only one process can be running on any processor at any instant

• A process changes state as it executes:
o New/created - the process is being created
▪ Takes time for process to be created, then admitted to ready state
o Running - instructions are being executed
▪ Process has been scheduled by dispatcher
▪ Can exit and move into terminated state
o Waiting - the process is waiting for some event to occur
▪ Process transitions when system event is raised (that it can’t deal with itself)
or it’s waiting on i/o transaction
▪ Typically order of magnitudes slower than CPU work – thus makes no sense
to have process sitting on core, doing nothing
• Thus, why process is moved from running to waiting state – kernel
moves process off core
▪ Lingers in waiting state until event is serviced or i/o is complete, then moves
back into ready state (where it can be dispatched again by scheduler to run
on some core)
o Ready - the process is waiting to be assigned to a processor
▪ Available for scheduling by dispatcher
▪ Interrupt changes process from running state to ready – process is put onto
the ready queue (can be rescheduled back onto the core it came from, or
another core)
o Terminated - the process has finished execution
• Process state diagram represents all stages a process can be in – represented as nodes
o Link/edges linking various states together – shows under which conditions they
transition from one state to another
• OS has to manage process through its entire lifetime – has to be aware of transitions and
have methods in place to recoup resources, manage prioritising of processes, generate
interrupts, service interrupts, etc

11 | P a g e
 • Process can be moved off core by an interrupt – most common interrupt type is when
process exceeds its execution quantum
o To give illusion of large array of processes running concurrently, need to time-slice
the amount of time that they can be run
o Only allow process to run from start to finish if it’s short – otherwise after a certain
amount of time, we interrupt its running on the core

Context Switching
• Entire execution environment – all the state it needs to run
• When a process is running, the system is said to be in the context of that process.
• Context switching can also be used for interrupts and system calls
• When the kernel decides to execute another process, it performs a context switch, causing
the system to execute in a different process’ context
o For a context switch, the kernel has to save enough information so that it can switch
back to the earlier process and continue executing exactly where it left off
o When a process executes a system call and has to change from user to kernel
mode, the kernel also has to save enough information so that it can later return to
user mode and continue executing the program
▪ System calls run in kernel mode because they have a privileged level –
they’re accessing low lvl resources
▪ Existing state has to be saved while system call is managed
▪ Need to restore process to its state prior to save occurring
• 75,000-100,000 context switches per second not uncommon!
o Context switching needs to happen very fast

CPU Context Switching

• Diagram shows process that has been interrupted – another process will be switched in by
scheduler
o Need to keep cores occupied at all times otherwise sys degrades
• Context switch steps:
o Save current process to PCB – save current state
o Decide which process to run next

12 | P a g e
 oLoad of new process from PCB – load pcb of new process that has been swapped in,
and continue executing
• Context switch should be fast, because it is overhead- the system does no useful work
while switching processes
• Diagram – process P0 on lhs, busy executing
o Sold line indicates where process is doing nothing because a sys call has happened
o E.g. i/o operation
o Save pcb for process – takes an amount of time
▪ Other process P1 is idle – thus its wasted time
▪ Want to minimise this time – context switch needs to be fast
o Reload state of process that want to swop in – P1
▪ Executes and will service interrupt / manage sys call
▪ Once complete, gives up control of call that its been running on
▪ Loads/saves its state so that it can be resumed later on if necessary
o Reload original process P0
• Have a lot of idle time – want to minimise this
• The more complex the OS and the PCB ➔ the longer the context switch
o Speed at which it happens depends on OS complexity, peculiarities of pcb (how info
rich it is)
• Time taken is dependent on hardware support (helps manage context switches):
o Hw designers try to support routine context -switch actions like saving/restoring all
CPU registers by one pair of machine instructions
o Some hw provides multiple sets of registers per CPU ➔ multiple contexts loaded at
once

Process Scheduling Queues

• Scheduling is used to determine which process next gets access to CPU – OS uses collection
of queues to manage this (non-exhaustive list below)
o Job queue – set of all processes in the system
▪ Can have thousands of entries – each need to be “scheduleable” and able to
run
▪ All processes that can run but may not be able to because they don’t reside
in main memory
o Ready queue – set of all processes residing in main memory, ready and waiting to
execute
▪ Just need to be context-switched onto core – can then execute
o Device queues – set of processes waiting for a particular I/O device
o Can attach different priorities to these queues, etc
• A process scheduler selects among available processes for next execution on CPU
• Processes migrate among the various queues – OS can move processes between these
queues, depending on sys constraints
• Queues generally implemented as a doubly-linked list of PCBs

13 | P a g e
Queue Examples

• Ready queue has pcbs which are ready to be executed

• Can have queues attached to i/o devices
o Have jobs waiting for slow service from these devices
• Have disk queue – have various processes waiting to read data from disk
• Also, terminal queue waiting for keyboard i/o
• Above are subset of possible queues
o Queues available depends on OS config

Process Scheduling

• Queueing diagram represents queues, resources and flow between them

• Circles are resources, arrows indicate flow
• New processes start in ready queue until dispatched
• Ready queue – sent here when process enters the sys
o Available to be dispatched onto CPU
• Once process runs on CPU i.e. moves from ready queue down to CPU

14 | P a g e
 o Exits to the right when terminating
o Or can experience a number of different conditions – moves it off the CPU and onto
a different queue
• IO request comes in – process migrates (because of that request) onto io wait queue
o Sits on queue until io resource available – once it is, and can service io
request/transaction, process moves onto ready queue
• Timeslice expires, process has to move off CPU so something else can run
o Moves directly back into ready queue
• Process could also create child – has to wait until child terminates (depending on nature of
parent-child relationship)
o Goes onto child-termination wait queue
o Once child terminates, can move onto ready queue again and be rescheduled
• If interrupt occurs when process running (last condition)
o Moves into interrupt wait queue
o Once interrupt is serviced, moves onto ready queue

Scheduler
• Short-term scheduler (or CPU scheduler) – selects process to be executed next and allocates
CPU
o Sometimes the only scheduler in a system
o Invoked frequently (milliseconds) – must be fast (cores needs to have something
running on it at all times)
o Needs to made decisions rapidly – algos used to make these decisions need to be
simple and sophisticated enough that they can be executed quickly
• Long-term scheduler (or job scheduler) – selects processes to be brought into the ready
queue
o Invoked infrequently (seconds, minutes) – may be slow
o Controls the degree of multitasking – i.e. the number of concurrent processes in
memory (can run, but aren’t necessarily running at a particular point in time)
o Brings in processes with lower priority – these processes often aren’t in main
memory
▪ Moves them into memory – now available for short term scheduler
• Processes can be described as either:
o I/O-bound – spend more time doing I/O than computations, many short CPU bursts
▪ Slow, ends up waiting a lot
▪ Long-term scheduler concerned with this
o CPU-bound – spends more time doing computations; few very long CPU bursts
• Problem is striking a balance between how much CPU time these processes get – where
the scheduler comes in
o Long-term scheduler strives for good process mix – collection of CPU-bound
processes doesn’t hog all the computational cores (otherwise io won’t happen)
o But also, don’t want io processes lingering on CPU – they’ll just need to be swoped
off again
▪ IO-bound thus need a fair chance at CPU, but must not be unnecessarily
swopped in – will need to do a context swop

15 | P a g e
Aside: Multitasking in Mobile Systems

16 | P a g e
 Inter-process Communication

• Processes within a system may be independent or cooperating

o Fork cmd is an independent way of creating a process
• Want processes to co-op – can achieve more
o These processes need a way to co-op – exchange info, control each other via synch
primitives
o Affected through inter-process communication
• Cooperating process can affect, or be affected by, other processes, including sharing data
• Reasons for supporting cooperating processes:
o Info sharing – typically shared memory
o Computation speedup (parallelization)
▪ Take computation and divide up into parallel tasks – want tasks to be able to
talk to one another and exchange info
▪ Decomposition of a problem into many smaller, sub problems
o Modularity – break up large pieces of functionality and wrap them in a process
▪ Need those processes to communicate
• Cooperating processes need interprocess communication (IPC)
• Two models of IPC
o Shared memory – can be faster (fewer system calls)
▪ Processes share a part of memory, where they can exchange info – leads to
many issues
o Message passing – better for distributed systems generally
▪ Processes send msgs to each other – end up with collection of queues
▪ One process will sent to queue – another will read from that queue

IPC Models: Shared Memory

• OS usually tries to prevent one processes from accessing another process’ memory
• With shared memory, two or more processes agree to remove this restriction and
exchange information by reading and writing data in shared areas
o Now we have to manage synch and ensuring correct computation happens
• e.g. POSIX shared memory In UNIX

17 | P a g e
IPC Models: Message Passing
• Message system – processes communicate with each other without resorting to shared
variables, using mechanisms for processes to communicate and to synchronize their
actions
o Have send and receive msg facility which all processes can access
o One process will send msg – arrives in msg queue
o Receiving process will basically receive a msg from a queue (i.e. pull a msg off)
• IPC facility provides two operations:
o send(message)
o receive(message)
o Msg size fixed or variable
• Examples:
o Windows advanced local procedure call (ALPC) facility
▪ Allows methods on a local system to behave akin to RPCs
o Pipes (named or unnamed) – UNIX (also Windows)
▪ Ordinary pipes – io device that child and parent use to communicate
(without using shared memory)
▪ Create a child with fork, then create pipe which allows parent and child to
write info back and forth
▪ Named pipes – persistent data structures that exist on disk
• Processes can read to/write from – requires more setup

o Client-server communication
▪ Sockets
▪ Remote Procedure Calls (RPCs) – have processes on different machine that
communicate with each other (using RPCS, pass msgs)

Process Termination
• Process terminates when it executes last statement
o Once process has finished all its work – can either put explicit call to exit, or use
return
▪ Generates call to exit with appropriate return code
o Asks the OS to delete it using the exit() system call
• On exit, process may return a status value (typically an integer) to a waiting parent process
o Parents wait for children with a wait() system call – moves onto ready queue until
that call is serviced
• On exit, all process resources are deallocated and reclaimed by the OS
o Including physical and virtual memory, open files, and I/O buffer, pcb and process ID
• Termination can occur in other circumstances
• A process can terminate another process via a system call

18 | P a g e
 o e.g TerminateProcess() in Windows, abort() in Unix/Linux (abort exits without doing
proper resource management)
• Usually, a terminate system call can be invoked only by a parent process
o Otherwise, a user, or a misbehaving app could arbitrarily kill another user’s
processes
o Because a parent needs to know the identities of its children to terminate them, the
identity of the newly created process is passed to the parent on creation
• A parent may terminate the children processes because:
o Child has exceeded allocated resources
o Task assigned to child is no longer required
o The parent is exiting and the OS does not allow a child to continue if its parent
terminates
• Once a child process exits and lets OS know by issuing its exit cmd – OS recoups all resources
for that process
o However, at that point it hasn’t completely recovered the pcb – so there’s info in the
pcb that lingers until parent calls wait, or otherwise acks that process has completed
• After exiting, a child process still has an entry in a process list, so waiting parent can check
that is it complete and read its status code
o If no parent waiting (did not yet invoke wait()) process is a zombie – resources
freed up but entry still in pcb (parent needs to query that status)
▪ Once parent calls wait, process unravels
o If parent terminated without invoking wait(), process is an orphan – pcb is still
active, process lingers on system
▪ On UNIX systems, orphaned processes are generally inherited by process
with id 1, which then proceeds to kill them
o Parents need to check status of child process – wait() return child’s status (i.e. what
was the termination code for the child)
▪ That info is stored in pcb for the process – all other info can be recovered,
but some needs to stay there so that the correct behaviour occurs when
wait cmd is serviced
• Once process exits and resources recovered, parent issues wait cmd and allows it to be
serviced, and then returns status code to parent
o Parent can then go on and issue its own exit and terminate

19 | P a g e
 Multithreading
Threads

• Most modern applications have multiple “threads of control”, or threads, in order to process
more than one task at a time
• Thread is a basic unit of CPU utilization
• Thread comprises thread id, program counter, register set and a stack
• Threads within a process share code, data and files + signals etc, with creating parent
process
o Other things are unique to each thread e.g. registers, stack
• Can only have one thread running on any one time on a core – hence why multiple
cores/CPUS is advantageous
o With multiple cores, can have multiple threads running concurrently

On Processors

20 | P a g e
 • It is the job of the OS to provide the illusion of a nearly infinite number of virtual processors
o Achieved by timeslicing, moving threads off the cores, etc

Multithreading Benefits
• Responsiveness – may allow continued execution if part of process is blocked (e.g. an io
operation gets serviced), especially important for user interfaces and servers
o If only have one thread of execution, for io, entire process halts
o With multiple threads, these “subprograms” can continue running on different cores
while io request is serviced
• Resource sharing – threads share resources of process, easier than shared memory or
message passing
• Economy – cheaper than process creation, thread switching has a lower overhead than
context switching
o Process is a heavyweight thread – need to create a process to act as container for
the threads
• Scalability – process can take advantage of multiprocessor/ multicore architectures: more
concurrency

Kernel threads
• The OS kernel is multithreaded
• In Unix/Linux ps –ef will display the kernel threads
• The kernel thread kthreadd (pid = 2) is the parent of all other kernel threads

User and Kernel Threads

• Support for threads provided at two different levels:

o User threads – supported above the kernel and managed without kernel support,
primarily by user-level threads library
▪ Exist in user space – collection of processes that user has spawned
▪ Regular threads, created with no additional privilege
o Kernel threads – supported and managed directly by the OS
▪ Supported by nearly all modern OS (Windows, Linux, and Mac OS X)
▪ Threads are doing low lvl, kernel operations e.g. monitoring ports, managing
disk io requests, etc

21 | P a g e
 ▪ This is what is scheduled by scheduler to the various cores
▪ Have escalated level of privilege
o Need mapping between user and kernel threads
• Mapping between user and kernel threads can be:
o Many-to-One – all user threads (created by a user level thread library) are mapped
onto a single thread
▪ Create illusion that system is multithreaded
▪ Pure user-level thread implementation
▪ If one thread blocks, all block
▪ Few systems currently use this model, because multiple threads do not run
in parallel on multicore systems
• No collection of threads running in the kernel, so can’t have true
parallel support for threads (thus can’t run concurrently)

o One-to-One – every user thread is mapped onto corresponding kernel thread and is
dispatched onto different cores
▪ Creating a user-level thread creates a kernel thread
▪ # threads per process typically restricted
▪ Users can create a large number of threads – have to decide how to
schedule those
• OS can impose constraints as to how many threads one can create to
ensure system doesn’t get overwhelmed

o Many-to-Many – take large collection of user threads and map them to a smaller
collection of kernel threads
▪ E.g. Windows, Linux
▪ Many user-level threads to be mapped to as smaller or equal number of
kernel threads
▪ Allows the OS to create a sufficient number of kernel threads
▪ Mapping chosen to optimise various criteria around resource utilisation
• OS tries to ensure that it services as many threads as possible using
resource optimally
• E.g. threading waiting on io will be swooped out

22 | P a g e
Thread Libraries
• A thread library provides programmer with API for creating and managing threads
• May be:
o Entirely in user space, no kernel support OR
▪ E.g. many-to-one, don’t use kernel directly at all – create and manage
threads as lightweight user processes
• Mapping needs to then happen
o Kernel-level library supported by the OS
▪ Directly support creation of kernel threads – different levels of privilege
• Three primary thread libraries:
o POSIX Pthreads – user-level, kernel-level
o Windows threads – kernel lvl
▪ Operate with elevated access
o Java threads – JWM uses thread library on host system,
▪ e.g. Windows threads on Windows and Pthreads on Unix/Linux

23 | P a g e
Pthreads

• A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization
o May be provided either as user-level or kernel level
o Specification, not implementation
▪ API specifies behaviour of the thread library, implementation is up to
development of the library
• Common in UNIX operating systems
• Diagram:
o Top function is method run by thread
▪ Takes variable as an arg, and increments it
▪ Passing reference to variable – change persists to parent code
o Begin in main process (thread of execution)
▪ Print out their values
o Create reference to new thread
▪ Then in pthread_create, thread creation happens
o Thread now active
o Main program does the same operation – increments y
o Thread rejoins with parent before terminating

24 | P a g e
Java Threads

• Managed by the JVM, specification does not say how threads are mapped onto kernel
threads
o Provides consistent API for the user to create threads
o Typically implemented using the threads model provided by underlying OS
o Two techniques for creating threads in a Java program:
▪ (1) Create a new class that is derived from the Thread class and to override
its run() method
▪ (2) Define a class that implements the Runnable interface
o When a class implements Runnable, it must define a run() method
▪ The code implementing the run() method then runs as a separate thread

Implicit Threading

• In this model, creation and management of threads is done by compiler and threading
library, to take burden off programmer
o Rather than directly creating threads, create tasks
o These tasks are taken by a framework, mapped onto threads and then distributed to
different cores
• E.g. Java fork join, OpenMP (high lvl programming construct)
o OpenMP is embedded in C, c++ - use hash pragmas (instructions to pre-processor,
compiler to parallelise the code given sum constraints)

25 | P a g e
Threading Issues
Semantics

• Semantics of fork() and exec() system calls – fork() system call is used to create a separate,
duplicate process
o Does fork()duplicate only the calling thread (thread that fork was issued in), or all
threads (in the process)?
▪ Some UNIX systems have two versions of fork which operates at two
different levels
▪ Duplicating all is resource intensive
▪ When issued in process, fork() duplicates entire process – those processes
then carry on executing
o exec() usually works as normal – replace the running process including all threads
▪ Takes new process and overlays a new memory space and some executable
to run in

Signal Handling
• Signals are used in UNIX systems to notify a process that a particular event has occurred
o Process has to respond
o E.g. kill signal to terminate process
• May be synchronous (e.g. division by 0) or asynchronous (e.g. terminating a process or
expiration of a timer)
o Synchronous need to be operated on immediately/asap – managed by thread which
triggered that signal
▪ E.g. thread has division by zero or illegal memory access
▪ Thread receives signal and must act on it

26 | P a g e
 oAsynchronous – emerge from outside a thread
▪ Instruction to terminate a process, an interrupt to stop a particular thread
from executing (so another can be swopped in)
• For single-threaded, signal delivered to process
• Where should a signal be delivered for a multi-threaded program?
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 (and execute specific
responses to that signal)
• The choice of which paradigm to use depends on program and what support is available in
the OS
• Most versions of Unix allow threads to specify which signals it will accept and which not
o However, if there’s a particular signal they can all respond to, signals delivered only
to first accepting thread only
▪ Signal then considered to be processed

Thread Cancellation
• Terminating a thread before it has finished – thread to be cancelled is target thread
• Two general approaches:
o Asynchronous cancellation terminates the target thread immediately
o Deferred cancellation allows the target thread to periodically check if it should be
cancelled, allows the thread to terminate in an orderly fashion
• Deferred cancellation is generally preferred to asynchronous termination
• Asynchronous cancellation is problematic where resources allocated to a cancelled thread
are either not released or are in an unsafe state

27 | P a g e
 Synchronisation
• Sync – ensuring that certain set of relationships hold over a sequence of events
o Want to ensure, by using the correct sync primitives, that the correct order of
events always plays out and ordering of events is guaranteed and consistent
• Here, synchronization refers to relationships among events—
o any number of events and
o any kind of relationship (before, during, after)
• Synchronization constraints are requirements pertaining to the order of events
• In OSes, often need to satisfy synchronization constraints without the benefit of a clock,
either because there is no universal clock, or because we do not know to a fine enough
resolution when events occur
• Sync primitives don’t depend on time

Basic Sync Patterns

• Signalling – requirement that if have multiple threads, one particular statement executes
in one thread before another
▪ E.g. Thread A, statement a1 must execute before statement b1, thread B

28 | P a g e
 • Rendezvous – requirement is that a certain order of execution is maintained for
statements in different threads
o E.g. Thread A, statement a1 executes before statement b2, thread B AND that b1,
thread B must execute before statement a2, thread A

Concurrency and Sync Problems

• Biggest issue: concurrent access to shared data is prone to data races and other issues of
data integrity
o Concurrent access to shared data may result in data inconsistency
• Maintaining data consistency requires the correct sync mechanisms to ensure the orderly
execution of cooperating processes
• The synchronization mechanism is usually provided by both hardware and the OS
o The ability to execute an instruction, or a number of instructions, atomically is
crucial for being able to solve many of the synchronization problems
o Need primitives themselves to be atomic

29 | P a g e
 Synchronisation Mechanisms
• Solutions to sync problems
o Techniques range from hardware to software-based API’s
• All based on protecting critical regions through use of locks
o Two processes cannot have a lock simultaneously

Classic Synchronisation Problems #1: Critical Section

Problem (mutual exclusion)

• Each process has critical section segment of code

o Process may be changing common variables, updating table, writing file, etc
o Part of code that involves updating some shared state or using some shared
resource
▪ E.g. writing to shared memory
o Need mechanism to control access to this section
• Simplest solution is using a mutex – i.e. a mutual exclusive
o Need to ensure there’s mutually exclusive access to that section of code
• Critical section is mutually exclusive – when one process in critical section, no other may be
in its critical section
o Guarantees there won’t be data races and other conditions occurring
• Critical section problem is how to design a protocol to solve this
o Want to design a consistent protocol that allows for peak performance
• Theoretical perspective:
o Diagram shows loop – process iteratively going through a computation
o Part of the computation involves critical section (want to protect)
o Part that doesn’t need to be protected is the remainder section
o Also have the entry and exit section – entry is where acquire means to control
access to critical section
▪ Exit section is where you give up control

Requirements for Solutions to Critical Section problem

• Solution must satisfy:

30 | P a g e
 o Mutual Exclusion – if process Pi is in its critical section, no other processes can be in
their critical sections
o Progress – if no process is executing in its critical section and some processes wish
to enter their critical sections, then only those processes that are not executing in
their remainder sections can participate in deciding which will enter its critical
section next, and this selection cannot be postponed indefinitely
▪ Basically, any process that wishes to enter its crit section should be allowed
to compete and should be allowed to make that decision in a reasonable
amount of time
o Bounded Waiting – there exists a bound, or limit, 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
▪ Once process requests access to crit section – should receive access within a
reasonable amount of time

Solving Critical Section Problem with Locks

• Only one process can acquire the lock at a time

• When the process has the lock, it can enter its crit section and perform its computation
o No other process can enter its critical section at that time because they don’t have
the lock
o Have to wait until other process releases the lock
• Once the lock is released, one of the other processes that was forced to wait can acquire the
lock and execute its crit section

Hardware Solutions to Synchronisation

31 | P a g e
test-and-set()

• Hw provides special atomic hw instructions to implement locks

• test-and-set(): combines the actions of testing variable and setting it to a specific value
into a single machine instruction which cannot be interrupted
• Example with lock implementation:

o test-and-set on LHS
o RHS shows critical section is executed – once finished, the lock is released

compare-and-swap()

• Hw provides special atomic hw instructions to implement locks

• compare-and-swap(): swaps the value of a variable only if it is equal to a given expected
value
• Example with lock implementation:

o Lock initially set to 0/false – if value matches expected value, can grab the lock

32 | P a g e
 ▪ Lock assumes values 1 in that case
▪ Return original value of lock, which is 0
o Once lock grabbed, can execute crit section
▪ Any other process trying to grab lock will fail
o Once crit section completed, set lock to zero – allows other program waiting to
enter its critical section
• Note: these approaches do not satisfy “bounded waiting” – a solution in terms of CAS is
provided in textbook
o Guarantees at most n-1 waiting turns for n threads

Atomic Variables

• The compare-and-swap() hardware not usually used directly to provide mutual exclusion
o Used to construct synchronization primitives such as atomic variables
• Updates to atomic variables are guaranteed to be atomic – no data races on a single variable
• E.g. might have variable x and want to atomically increment/decrement it some languages
have direct support for this through hw
o Guarantee with atomic increment on variable, that nothing can interrupt it
• Operation sequence for increment involves several registers – those can be interrupted by
interleaving of instructions from different processes
o Making an operation atomic allows a variable to be safely incremented without
having to worry about operations being interleaved or inconsistent data (due to
data races)
• Diagram shows example of atomic increment
• Hardware solutions are complicated and generally inaccessible to application programmers,
so OS designers build software tools to solve critical section problem

Software Solutions to Synchronisation

Mutex Lock

• Simplest is the mutex lock, which has an associated Boolean variable “available” to
indicate if the lock is available or not
o Two operations to access - acquire() and release()

33 | P a g e
 • Calls to acquire() and release() are atomic- usually implemented via hardware atomic
instructions
o Can’t be interrupted
• Solution requires busy waiting – lock is therefore called a spinlock
o Wasteful – CPU core runs tight while loop, constantly checking the state of this
variable
▪ Not doing any productive work
o Busy waiting seen as bad (from performance pov) – BUT if crit sections are short,
then amount of time spent in crit section will be small
▪ Thus, amount of time spent waiting for lock to be freed up is small
o With multiple CPUs with multiple cores, could have process spinning on spinlock on
one core, other cores occupied by other process
o But issues can occur when only have single core
• Diagram – while in crit section, available is false
o Once done, set available to true
o These operations are atomic

Semaphores

• More robust and sophisticated synchronization tool (than mutex locks)

o Generalisation of mutex locks – but allow for more sophisticated processing
• Semaphores are way of signalling what’s going on to system
• Semaphore S – integer variable accessed only via two atomic operations:
o wait() and signal()
▪ Originally called P() and V()
▪ In Java, called acquire( ) and release()
• Diagram
o Wait(s) – while s <0, spin around and do nothing
▪ If S positive, exit loop and decrement semaphore value
o Signal(s) – takes semaphore value and decrements it by 1
o Implementing mutex lock with semaphores?
▪ Create semaphore with int value 1, and call wait() on it
o When initialised, process comes in, executes wait method
▪ Decrements semaphore value – becomes 0, is able to enter its crit section
o Will raise signal afterwards to increase semaphore value to 1
▪ While it’s in its crit section, S = 0, so no other process can enter its critical
section
• If they call wait, they will be kept in busy waiting state – looping
around

34 | P a g e
 ▪ Once original process signals that its finished, only one other process is then
able to grab the semaphore, decrement the value and enter its crit section
(blocking other processes)
• When you create the semaphore, you can initialize its value to any integer, but after that the
only operations you are allowed to perform are value test, increment and decrement
o Decrement – a thread can only decrement the semaphore if it is > 0
▪ Otherwise the thread blocks itself and cannot continue until another thread
increments the semaphore
o Increment – when a thread increments the semaphore, if there are other threads
waiting, one of the waiting threads gets unblocked
• In the original definition you cannot read the current value of the semaphore
o BUT Java will let you do this

Types of Semaphores
• Binary semaphore – integer value can range only between 0 and 1
o Same as a mutex lock
o Generally initialised to 1
• Counting semaphore – integer value can range over an unrestricted domain
o Used to control access to a restricted number of processes
o Some value n > 1
o Place resource limit on the # of processes that can simultaneously enter their critical
section
o Multiplex

Example

• If the value of the semaphore is positive, then it represents the number of threads that can
decrement without blocking
• If the value is zero, it means there are no threads waiting, but if a thread tries to decrement,
it will block
• NOTE – if it is negative (permitted under the non-busy-waiting implementation) then the
value represents the number of threads that have blocked and are waiting

Semaphore Implementation

• Must guarantee that no two processes can execute the wait() and signal() on the same
semaphore at the same time (atomic) – usually done with hardware locks

35 | P a g e
 • Also, want to avoid busy waiting - although this is not a problem if critical section, and hence
waiting time, is short, also busy waiting avoids a context switch
o Modify wait() so that process blocks (suspends) and is put in waiting queue
▪ CPU scheduler chooses another process to execute
o Each semaphore now has two data items:
▪ Semaphore value (of type integer)
▪ List of processes in waiting queue
• Requires two additional operations:
o sleep()
▪ Require by wait() – suspend invoking process (the processes must also be
added to waiting queue)
o wakeup(P)
▪ Required by signal() – remove a process P from the waiting queue, call
wakeup(P)
• Scheduler can then dispatch it again (it is now ‘runnable’)

Basic Sync Patterns with Semaphores

• Signalling:
o Thread B – have semaphore initialised e.g. to 0
o Statement a1 has to execute first since semaphore can only be passed once it’s
value is >1, so its value can be decremented down to zero
▪ Can only happen once signal() increments sem to 1
o Once incremented, b1 can execute
• Rendezvous:

36 | P a g e
 o aArrived and bArrived initialised to 0
o a1 and b1 has no constraints – can execute in interleaved fashion
o a1 executes, then b1 (or other way around)
o Then one of these will run its signal first on a particular semaphore
o E.g. aArrived does it first – semaphore goes up to 1
▪ Then tries to execute wait – has to wait because value of bArrived is still 0
▪ Assume bArrived executes at some point – semaphore value increases to
one
▪ bArrived wait() can execute now
▪ Then a2 will be executed
▪ Similarly, correct sequence of operations ensure that thread B’s statements
will execute correctly

Monitors

• Alternative to semaphores
• High-level abstraction that provides a convenient and effective mechanism for process
synchronization
o Using semaphores is prone to error – can put wait() and signal() in incorrect place or
swop them around, refer to wrong semaphore with wait() or signal() etc
▪ Leads to hard-to-detect semaphore bugs
o Can alternatively wrap sync behaviour in abstract data type – monitor

37 | P a g e
 • Abstract data type – internal variables only accessible by code within the procedure
• Monitor is collection of data and series of methods that are guaranteed exclusive access to
that data
o Guarantee that only one of those methods can access those methods at any one
time
o Java has monitor data type
• Only one process may be active within the monitor at a time
• But not powerful enough to model some synchronization schemes
o Need some way to signal between different methods that some condition has
changed and now another method is allowed to start operating on monitor
o Achieved via condition variables

Condition Variables

• Have condition x
• Two operations are allowed on a condition variable:
o (1) x.wait()
▪ A process that invokes the operation is suspended until x.signal()
o (2) x.signal()
▪ Resumes one of processes (if any) that invoked x.wait()
▪ If nothing waiting on the variable, then it has no effect on the variable

38 | P a g e
39 | P a g e
 Classic Problems of
Synchronisation
Producer-Consumer Problem
• In multithreaded programs there is often a division of labour between threads
• In one common pattern, some threads are producers and some are consumers
o Producers create items of some kind and add them to a data structure;
o Consumers remove the items and process them
• E.g. Event-driven programs
o Whenever an event occurs, a producer thread creates an event object and adds it to
the event buffer
o Concurrently, consumer threads (“event handlers”) take events out of the buffer
and process them
▪ Event handlers
• Constraints to be enforced by synchronization:
o While an item is being added to or removed from the buffer, the buffer is in an
inconsistent state. Therefore, threads must have exclusive access to the buffer
o If a consumer thread arrives while the buffer is empty, it blocks until a producer
adds a new item
o In bounded buffer variant: producer cannot produce if buffer of BUFFER_SIZE is full

Pseudocode

40 | P a g e
Producer-Consumer
• Pseudocode shows there’s nothing to provide mutex access to parts where buffer needs to
be updated, as well as updating the counter
o These parts need to be protected to prevent inappropriate access which would lead
to data inconsistencies

With Semaphores
• Shared variables:
o int n ;
▪ Size of the buffer
o Semaphore mutex = 1 – binary semaphore
▪ Ensures mutex access to crit section
o Semaphore full = 0
▪ Counting semaphore
▪ Provides the # fully occupied buffer slots that consumer can pull data from
o Semaphore empty = n
▪ Counting semaphores
▪ Provides # of empty slots for producer to write into

Semaphores Pseudocode

• Only one process can have mutex at a time – once mutex grabbed, either p or c has it
o Can then do updates
• Producer waits(empty)
o Number of slots available for it to write on
o Can immediately pass through because all buffer slots are available
o Waits until it can grab mutex, once it has
▪ It updates, puts item in buffer
o Then signals an increase in full
• Consumer waits(full) i.e. there is something there for it to consume
o If item in the buffer, it can then pass by wait and decrement full to 0
o Grabs mutex to do its update
o Signals that there’s one more slot available to write info into

41 | P a g e
 • Producer now has more space to insert things in

Diagram

• Producer waits until buffer isn’t full – tries to get mutex lock
o Once it grabs it, it can safely add to buffer and do its updates
o Can then release the mutex

Aside: Producer Consumer with Monitors

• Force each method in monitor class to be synced

o So only one method can be in the monitor at any one time

Reader-Writers Problem
42 | P a g e
 • Any situation where a data structure, database, or file system is read and modified by
concurrent threads, some of which read and others write
o Can’t be reading when records are being modified
o When writing into, no other thread should be writing at the same time
• As with Producer-Consumer, asymmetric solution (different code for readers and writers)
• Synchronization constraints:
o Any number of readers can be in the critical section simultaneously
▪ Use counting semaphore
o Writers must have exclusive access to the critical section
• “Categorical mutual exclusion” – have two different categories of thread and we treat them
differently
• Several variants of how readers and writers are considered – all involve priority
o First variation – no reader kept waiting unless writer has permission to use shared
object
▪ Favours readers – unless writer in crit section, should get readers in asap
▪ Once in, all readers can pile in – writer has to wait until all readers are
finished
o Second variation – once writer is ready, it performs the write ASAP

Solution with Semaphores

• Read_count refers to # of readings reading crit section

• Rw_mutex – can be grabbed by writer/reader
o Allows for exclusive access to that crit section
• Both are binary mutexes
• Reader mutex
o Protects crit section for reader only – once read_count ==1, grabs rw mutex
▪ Then releases reader mutex (NOT rw mutex)
▪ Another thread can come in, grab mutex and put read_count up further, etc
▪ Waiting process can be starved i.e. producer
o Once reader acquires rw mutex, can commence reading, then update state data
o Once crit section exited, frees up the mutex

43 | P a g e
 • Not the best solution

Issues with Synchronisation

• Liveness – processes must make progress, not wait indefinitely
o Must guarantee this when using sync primitives
• Starvation – indefinite blocking
o e.g. process may never be removed from the semaphore queue in which it is
suspended
• Deadlock – two or more processes are waiting infinitely long for an event that can never
occur because can only be caused by one of the waiting processes

Dining Philosophers

• Create an array of 5 binary semaphores – once chopstick grabbed can’t be grabbed by

another philosopher
o Once finished, the philosopher releases it again

44 | P a g e
With Semaphores

• Have semaphores – call wait until we get the left and right chopstick
o Then eat – once done, call signal() to release system resources
▪ Put down left then right chopstick
o Mod operation is because the table is circular (last philosopher grabs the first
chopstick) – using circular buffer

Deadlock

• Standard solutions prone to deadlock

o Can make a dining-philosophers specific solution – then won’t be generalisable
o Instead want to develop set of methodologies/ tools that can work with any
deadlocking system – to avoid or recover from them if necessary
• Several solutions:
o Allow at most 4 philosophers to be sitting simultaneously at the table (with same
number of chopsticks)
▪ (deadlock then impossible)
o Allow a philosopher to pick up the chopsticks only if both are available (picking up
must be done in a critical section)
▪ Makes acquiring atomic
o Use an asymmetric solution -- an odd-numbered philosopher picks up first the left
chopstick and then the right chopstick

45 | P a g e
 ▪ Even-numbered philosopher picks up first the right chopstick and then the
left chopstick
▪ Preferred solution
o Also issue of starvation…

46 | P a g e
 Deadlock

• Can occur in Java code – locks/semaphores acquired in opposite order, ‘accidentally'

• Deadlock is possible, but may not occur
• Diagram - example illustrates a problem with handling deadlocks:
o Difficult to identify and test for deadlocks that may occur only under certain
scheduling circumstances

System Model
• Represents OS
• System comprises:
o A finite number of resources
▪ CPU cycles, files, and I/O devices
▪ Also sync tools such as mutex locks and semaphores
o Distributed among a number of competing threads
▪ Want threads to have fair access to these resources
• Under this simplified system model, a thread may use a resource in only the following
sequence:
o Request – if request can’t be immediately honoured, thread must wait
o Use – once acquired, often use exclusively
o Release – so that other threads competing for resource can access it
• A set of threads is in deadlock when every thread in the set is waiting for an event that can
be caused only by another thread in the set
o OS system kernel – have many threads that are potentially “scheduleable” and are
competing for resources
• Sync tools are the most common sources of deadlock

Safety vs Liveness
• There are two types of correctness properties for concurrent programs:
o Safety properties – the property must always be true
▪ E.g. acquiring a semaphore to get mutex access to crit section; using
mutexs/semaphores to ensure specific order of operation
o Liveness properties – the property must eventually become true
▪ Weaker constraint
▪ Liveness failure – most exemplified by deadlock
▪ Livelock – have set of processes unable to make progress at all

47 | P a g e
 • Spin around doing no useful work
• E.g. acquire and release lock – doing something, but it’s not
productive
• Solutions to safety issues often raise the possibility of liveness issues

Deadlock Characterisation
• Four necessary conditions must be satisfied simultaneously for deadlock to occur:
o Mutual exclusion- only one process at a time can use a resource
o Hold and wait: a process holding at least one resource is waiting to acquire
additional resources held by other processes
o No pre-emption – a resource can be released only voluntarily by the process holding
it, after that process has completed its task
o Circular wait – there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is
waiting for a resource that is held by P1, P1 is waiting for a resource that is held by
P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a
resource that is held by P0

Resource Allocation Graph

• A set of vertices V and a set of edges E

• V is partitioned into two types:
o P = {P1, P2, …, Pn}, the set consisting of all the processes in the system
▪ i.e. all threads
o R = {R1, R2, …, Rm}, the set consisting of all resource types in the system
▪ Resource nodes – different # of resource nodes vs number of
threads/process in system
• Edge of two types:
o Request edge – directed edge Pi → R
▪ Have process Pi making a request from the resource node i.e. a resource
held by the node
▪ Have different resource categories – could be requesting mutex lock or
semaphore, file system handle, etc

o Assignment edge – directed edge Rj → Pi

48 | P a g e
 ▪ Edges from resource to process

• Diagram:
o Have P1 requesting resource from resource pool R1, but R1 is allocated to P2
o Similarly, for P2, R3 and P3
o P1 and P2 requesting from R2
o Snapshot of resource request and allocation in a system
• If graph contains no cycles => no deadlock
• If graph contains a cycle:
o If only one instance per resource type, then deadlock exists
o If several instances per resource type, then possibility of deadlock
▪ This is the case with the diagram above
▪ Possible to break cycle and work out process of sequence execution such
that process can finish its task, free up its resources and honour resource
request edges from other processes

Checkpoint

• No, there is no cycle with a closed loop

49 | P a g e
 • Yes – P1 to R3 to P3 to R1 to P1
o All nodes participating in cycle and only one resource available for each resource
node in that cycle

• (a) Deadlock possible – but have more than one resource per node
o Deadlock potential but not guaranteed
o If P4 executed first, frees up resource to go back to resource pool R2
▪ P3 can then acquire resource – becomes resource assignment edge from R3
to P3
▪ Could then free up resource in R1 and R2 – P4 and P3 now finished, P1 can
grab resource
o Multiple solutions to avoid deadlock
• (b) Multiple cycles – all involve resource nodes with more than one resource element
o Deadlock – no way to satisfy resource requests to break deadlock condition
• If have cycle and resource nodes have single resource, definitely deadlock

50 | P a g e
 o But with multiple resource elements per resource node/vertex, then need to look at
problem more carefully and see if there’s a sequence of operations which can be
performed which will allow for resources to be gradually freed up

• Some cycles – P1 and P3

o Potential deadlock cycle – but there is not deadlock
o Can find execution path which can break the cycle by flipping an edge
▪ Allow P4 to execute and will return resource to R3 and R2
▪ Because R2 available, can then use resource in P1- becomes assignment
edge (cycle broken)
▪ P1 has resource from R1 and now R2, so it can complete – frees up
resources back to R2 and R1

Handling Deadlock
• Pretend that deadlocks never occur in the system (ignore the problem)
o E.g. most OS’s, including Windows and Linux
o Up to kernel and application developers to write programs that handle deadlocks
• Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a
deadlocked state
o Deadlock prevention – ensure that at least one of the necessary conditions cannot
hold
▪ All 4 conditions have to hold for deadlock to occur – if can get around one of
them, then can prevent deadlock
o Deadlock avoidance – OS requires advance information on which resources a thread
will request
▪ Additional info given to system when trying to acquire resources
▪ System runs some algos, does some computations to detect if honouring
that resource request is going to lead to deadlock in future
• Could then deny request, put process on wait queue and try again
later
o Deadlock recovery – allow the system to enter a deadlocked state, detect it, and
recover
▪ E.g. dtbs – commit, rollback if there’s a problem and then rollback to
previous state

51 | P a g e
 ▪ Can roll-back to prior non-deadlocked state

OSes and Deadlock

• Why do OSes not handle deadlock?
o Undetected deadlock is bad
o Will cause the system’s performance to deteriorate, because resources are held by
threads that cannot run…. and more and more threads, as they make requests for
resources, will enter a deadlocked state.
o Eventually, the system will stop functioning and will need to be restarted manually
• So, why don’t OS’s handle deadlock?
o Needs to much resources and has performance implications for a conventional OS
▪ i.e, resource intensive
o Rather assume it’s a rare event and leaves it up to the programmers

Deadlock Prevention
• Four necessary conditions must be satisfied simultaneously for deadlock to occur
o Which of these can we remove?
▪ To prevent deadlock from occurring
• (1) Mutual exclusion – only one process at a time can use a resource
o Safety is an absolute requirement – removal cannot be used for prevention
• (2) Hold and wait – a process holding at least one resource is waiting to acquire additional
resources held by other processes
o Have beginnings of a circular dependency – have resource, but trying to grab
another one
▪ In grabbing another, doesn’t necessarily free the one you’re holding
o Could say – can only request a resource, it’s not allowed to hold any other resources
▪ Or it needs to request all resources before it begins execution
▪ Or allow it to request resources only when no other is allocated to it
▪ All of these are impractical, bad solutions with performance hits
o Removal impractical – low resource utilization
o Starvation possible
• (3) No pre-emption – a resource can be released only voluntarily by the process holding it,
after that process has completed its task
o Removal impractical for most systems – performance implication for constantly
interrupting threads in order to release their resources
o Sync primitives used to avoid/control deadlock can’t be interrupted
▪ i.e. atomic operations protecting crit sections
• (4) Circular wait – there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is
waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …,
Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held
by P0
o Create total ordering of resource types i.e. sequential ordering of resources
o Processes request resources – walk through sequence from start to end, can find a
way of avoiding it
o Use resource graphs

52 | P a g e
Deadlock Avoidance
• Ensure that the system will never enter a deadlock state
o Essentially force all threads in system to declare their resource requests upfront
• Requires additional a priori information available on possible resource requests
o Simplest and most useful model requires that each process declare the maximum
number of resources of each type that it may need
o The deadlock-avoidance algorithm dynamically examines the resource-allocation
state to ensure that there can never be a circular-wait condition
o Resource-allocation state is defined by the number of available and allocated
resources, and the maximum demands of the processes

Safe State Concept

• System is in safe state if there exists a sequence of ALL the processes in the system, such
that for each Pi the resources that Pi can still request can be satisfied by currently available
resources + resources held by all the Pj, with j < i
o Sequence that is determined must allow us, for any particular entry in the sequence,
must be able to satisfy the requests of that thread using only the free, available
resources at that time AND the resources held at that time by a lower index
o E.g. have 5 threads in system, and we’re working with thread 3 T3
▪ When looking at T3s request to see if it can be honoured, we must look at all
available resources, as well as those held by T1 and T2
o If this property holds for all of the Pi in the sequence that was determined, then
can’t enter circular wait state and thus can’t deadlock
• That is:
o If Pi resource needs cannot be met now, then Pi can wait until all processes Pj ( j < i )
have finished executing
▪ When they have finished executing, they release all their resources and then
Pi can obtain the needed resources, execute, return allocated resources, and
terminate
▪ When Pi terminates, Pi+1 can obtain its required resources, and so on
• When predecessor threads finish – they return allocated resources
to pool and thus allows next process in sequence to grab those and
execute
o Execution may be deferred for a short period BUT still be able to execute –
preferable to deadlock (have no control over resource requests)

53 | P a g e
 ▪ There are some performance hits – but can workout sequence of thread
execution (such that conditions hold), then can guarantee circular wait can’t
occur
• If a system is in safe state => no deadlocks
o i.e. obeys above properties -
• If a system is in unsafe state => possibility of deadlock
o i.e. can’t find sequence of thread execution (and resource deallocation when thread
terminates)
o Deadlock not guaranteed but possible under certain conditions

Example

• Have system consisting of 12 resources divided up amongst 3 threads T0,T1,T2

• Taking snapshots at two different times – want to determine if that config of threads is in a
safe state/not
• At time 0:
o T0 – 5 resources
o T1 – 2
o T2 – 2
o 9 resources out of 12 – 3 resources free
o In a safe state
▪ T0 – can still grab 5 resources (only 3 avail)
• Can’t safely execute T0 first
• Can execute after T1 – T0 grabs 2, now have 5 resources free
• Grabs 5 resources so it can execute
▪ T1 – has 2, can grab 2
• Can execute T1
▪ T2 – has 2 but could claim 7 more
▪ Executes after T0 – have 8 resources in system
▪ 7<8 so can execute
• At time 1 – shows that i.t.o total # of allocated resources, have 10 (out of 12)
o Only 2 free
o Unsafe state
o Can’t honour T0 or T2 – have to execute T1

54 | P a g e
 ▪If T1 executes and returns 2 resources, now only have 4 resources in
resource pool
▪ Can’t do anything else – T2 needs 6 and T0 needs 5
• Ensure that a system will never enter an unsafe state

• Whenever a thread requests a resource that is currently available, the system decides
whether the resource can be allocated immediately or the thread must wait
o The request is granted only if the allocation leaves the system in a safe state
o If a thread requests a resource currently available, may have to wait
o Resource utilization may be lower than it would otherwise be

Deadlock Avoidance Algorithms

• For:
o Single instance of a resource type – use a variant of the resource-allocation graph
o Multiple instances of a resource type – use the Banker’s Algorithm

Resource-Allocation-Graph Algorithm

• For single instance of a resource type

• Each process must a priori claim maximum resource use

55 | P a g e
 • Use a variant of the resource -allocation graph with claim edges
o Claim edge Pi → Rj indicates that process Pj may request resource Rj
▪ Represented by a dashed line
o Claim edge converts to request edge when a process requests a resource
o Request edge converted to an assignment edge when the resource is allocated to
the process
o When a resource is released by a process, assignment edge reconverts to a claim
edge
▪ May want to claim that resource again at a later point in execution
o A cycle in the graph implies that the system is in unsafe state
• Suppose that process Pi requests a resource Rj
o The request can be granted only if converting the request edge to an assignment
edge does not result in the formation of a cycle in the resource allocation graph
o Otherwise, the process must wait
o Check for safety with a cycle-detection algorithm
▪ Order of n^2 operations, where n is the number of threads in the system
▪ Expensive

• (a) No cycle in this state – look at thread requesting resource

o Only grant resource if converting request edge to assignment edge doesn’t form a
cycle
o No deadlock
• (b) P2 granted the resource on R2 – now have a cycle
o Unsafe state
o No deadlock because P1 has not yet requested R2 – P2 could complete, free up R2
(no longer a request edge – becomes claim edge)
o P1 could then release R1 and then P2 could then claim and complete its execution
o Deadlock potential – but not guaranteed
• By forcing things to avoid unsafe states, impose performance penalties because threads end
up waiting more because can’t grant certain resource requests
o Preferable to allowing deadlock

56 | P a g e
Bankers Algorithm

• Multiple instances of a resource type

• Less efficient than resource-allocation graph
o Each process must a priori claim maximum use
o When a process requests a resource, it may have to wait
▪ At every step, there is two phases:
• (1) Check if we’re in a safe state
• (2) If there’s a new resource request – can we grant it without
moving into an unsafe state?
• If both there are guaranteed, then deadlock won’t occur
o When a process gets all its resources it must return them in a finite amount of time
• Have to define a series of data structures (vectors and matrices) that represent info about
the current state of the system and the future request state of the various threads
o Available – length m (# of resource types)
▪ How many resources are available to be grabbed by different threads to
use?
▪ Unallocated
o Max – rows n (per thread) x columns m (per resource type)
▪ Each row corresponds to a different thread
▪ Number of instances of a particular resource type that thread may request
▪ i.e. over all time, thread i can’t request more than k of resource j
o Allocation – n x m
▪ Thread i (row) is currently allocated k instances of Rj
▪ Each row will be for a particular thread
o Need – how much does a thread need of each resource to complete its task

57 | P a g e
Safety Calculation

• Determines if we’re in a safe state/not

• Work set to available set of resources i.e. amount of resources system has available
o Can add to/ remove from as the algo executes
o M elements per resource type
• Finish – Boolean vector; per thread
o Whether/not thread has completed its work i.e. has executed
o Set to false for every thread
• Just want to search through list of threads and find an ordering of threads such that they can
be executed in that order, whilst ensuring always being in a safe state
o Scan list of available threads, looking at their resource needs, based on amount of
resources available
o Find a thread that hasn’t completed, whose needs are less than the current
resources available in the system
▪ If can find that thread, then commit those resources to it
▪ Go to step 3 – add the amount of resources needed for that thread to
continue executing to current running total of all available system resources
(because it has executed and completed)
▪ Those resources are returned to the system and flag that thread as
completed
▪ Then search for additional threads to commit resources to
o If can’t find such a thread – know there’s a problem
▪ Go to step 4 and finish[i] will be false for some i – know system is in an
unsafe state
• Ideally want to find complete sequence that visits all threads in some order, such that when
step 4 is reached, finish is true for all threads in the sequence
o Thus, have executable sequence that guarantees no deadlock
• Computationally expensive
o May require on order m x n^2 operations to determine whether a state is safe

58 | P a g e
Example

• i.e. T0 allocated 0 As, 1 Bs and 0 Cs (and so forth)

• Sum across column for A, B and C
o Have 7 As allocated – with 10 max in system => 3 As available to be used by threads
in their resource allocation requests
▪ Calculate Bs = 3, Cs = 2
o So have work = 3 3 2
• Is there an ordering of threads such that can look at its current need and see if its less than
current available work
o Need matrix = Max – Allocation
o Examine each row as it corresponds to different thread
• T0 does not match criteria- move to T1
o T1 does match criteria as 1 2 2 < 3 3 2
o Assume T1 executed – free its resources back up
▪ So, 2 0 0 added onto running total of available system resources i.e. work
▪ Flag T1 to be true
• Available resources now 5 3 2
o Look at list – scan from top
o T0 = no, T1 processed, T2 = no – land at T3 which meets criteria
o 532+211=743
o Flag T3 true
• Available resources now 7 4 3
o Look at list – scan from top
o T0 now meets criteria
o Add 0 1 0 to 7 4 3 = 7 5 3
o Flag T0 true
• Available resources now 7 5 3
o T2 fits criteria
o Add 3 0 2 to 7 5 3 = 10 5 5
• Available resources now 10 5 5

59 | P a g e
 o Only have T4 left – can satisfy that
o 4 3 1 < 10 5 5
o Add 0 0 2 + 10 5 5 = 10 5 7 (all system resources)
• The system is in a safe state as the sequence < T1, T3, T0, T2, T4> satisfies safety criterion

Resource-Process Request for Process Pi

• Requesti[j] = k – particular thread/process wants k instances of resource type j

o E.g. 3 0 2 => 3 As, 0 Bs and 2 Cs
• Check if can meet that – if can, just apply request (i.e. mod data structures as if request
valid)
o Run safety detection algo to determine if we’re left in a safe state
• If safe – allocate resources to thread
• Otherwise make thread wait

Example

• Have previous state with resources available, max and needs

• T1 request (1,0,2)
o Is request < need i.e. 1 0 2 < 1 2 2? Yes!

60 | P a g e
 o Is request < available resources i.e. 1 0 2 < 3 3 2? Yes!
o Update structures to see if going to be in safe state
▪ Available = available – request i.e, 3 3 2 – 1 0 2 = 2 3 0
▪ Allocation = allocation + request i.e. 2 0 0 + 1 0 2 = 3 0 2
▪ Need = Need – request i.e. 1 2 2 – 1 0 2 = 0 2 0
▪ Run safety algo
▪ The system is in a safe state since the sequence < T1, T3, T4, T0, T2> satisfies
safety criteria.
▪ Request is therefore granted
o Request (3,3,0) by T4
▪ Need T4 is 3 3 0 < 4 3 1 so request < need
▪ BUT 3 3 0 > 2 30 so cannot grant this
o Request (0,2,0) by T0
▪ Need T0 is 0 2 0 < 7 4 3 so request < need
▪ 0 20 < 2 3 0 so request < available resources
▪ So mod vectors
• Available = 2 3 0 – 0 2 0 = 2 1 0
• Allocation = 0 1 0 + 0 2 0 = 0 3 0
• Need = 7 5 3 – 0 3 0 = 7 2 3
▪ Run safety check – result is unsafe state
▪ Restore old resource info – go back to previous request
▪ Force T0 to wait

Deadlock Recovery
• Allow system to enter deadlocked state and then recover
• Requires:
o Deadlock detection
▪ Detection algorithms for
• Single instance of a resource type
• Multiple instances of a resource type
▪ Recovery scheme – so system can recover and continue to do useful work

61 | P a g e
Deadlock detection
Single instance of each resource type

• Maintain a wait -for graph

o Nodes are processes
o Pi → Pj if Pi is waiting for Pj
• System needs to maintain the wait-for graph and periodically invoke an algorithm to search
for a cycle in the graph
o Cycle => deadlock
o n^2 operations – n is the number of vertices in the graph
• System might elect to run deadlock detection algo periodically e.g. when CPU utilisation
drops below a particular threshold
o Calling the algo too frequently is costly (because of cycle detection)
o Resource implication for detecting that deadlock has occurred

Multiple Instances of each resource type

• Use algorithm similar to Banker’s algorithm
• Requires an order of m x n^2 operations to detect whether the system is in a deadlocked
state
o M – resources
o N – threads

Aside: Java Thread Dumps

• Java does not provide explicit support for deadlock detection
• A thread dump can be used to analyse a running program to determine if there is a
deadlock
o Snapshot of the states of all threads in a Java application
o Show locking information, including which locks a blocked thread is waiting to
acquire
• To generate a thread dump of a running application, from the command line enter: jstack -l

Recovery from Deadlock

62 | P a g e
Process Termination
• Options:
o Abort all deadlocked processes – may leave process(es) in an inconsistent state
▪ E.g. stopping a file i/o before its done
▪ Will also need a mechanism to recover resources
▪ E.g. if you’ve acquired mutex and want to abort a process– need to ensure
that the lock is again made available to system
▪ Have to restart computations from scratch
• Lost productivity
o Abort one process at a time until the deadlock cycle is eliminated
▪ In which order should we choose to abort?
▪ Have to look at process priority, how many processes a thread is hanging
onto, etc

Resource Pre-emption
• Forcibly remove resources from threads that’re deadlocked, in order to break the deadlock
o Again, there are implications
• Selecting a victim – minimize cost
o Choose a thread to “steal resources from” which minimises impact on the rest of the
system
• Rollback – return to some safe state, restart process for that state
o Take process and remove its resources – in doing so, have interfered with its
computation
o Thus, need to backtrack to a point and restart thread where it can continue with
computations and try and reacquire that resource again
o Not a trivial task
• Starvation – same process may always be picked as victim, include number of rollback in cost
factor
o Due to victim selection criteria, could end up picking the same victim – thread will be
unable to acquire any resources
o May need to keep track of # of rollbacks – additional cost
▪ If rollback too many times, then won’t steal resource from it

Proceed without Resource

• E.g. Amazon web site – how it deals with web requests when its server is overloaded
o If inventory server not available for a specific length of time, front end web server
will give up, complete order and queue a background check, sending apology to
customer if item not available.
o This is preferable to hanging indefinitely

Transactions
• Transactions are used widely in file systems and databases
o Transaction either complete (and transaction commits) or do not happen at all
(aborts)
• Transactional systems are good for deadlock recovery:
o Thread roll back

63 | P a g e
 ▪ Roll back or undo threads actions to a clean state (picking one or more
victim threads)
o Thread restarting
▪ Victim thread is restarted
o Would have to be built on top of OS in practice – thus difficult to get working at user
thread level
▪ Would also need to maintain data strcs to maintain this transactional nature

64 | P a g e
 CPU Scheduling

• Crit OS function – underlies the OSes responsiveness

• Modern OS’s schedule kernel-level threads — not processes
o But terms "process scheduling” and "thread scheduling" used interchangeably
o Scheduling allows another process run on CPU when process waiting for I/O
• Scheduling allows OS to hide latency – latency arises because threads have to wait for
system operations
o E.g. thread calls sys function – has to wait until function resolved before it can
continue executing
o Bad for performance if CPU core sits idle whilst tasks are happening
• In multicore environment – want to ensure that whenever CPU released – there is a thread
that can be scheduled to use CPU core effectively (i.e. no slack)
• Processes typically have many short CPU bursts and few long CPU bursts
o I/O-bound - many short CPU bursts
▪ Intermittent CPU bursts
▪ Bulk of its type for a process-activity type is spent waiting for IO to be
completed
o CPU-bound - few long CPU bursts
▪ CPU burst is concentrated burst of CPU activity – e.g. performing
computations, updating registers, etc

65 | P a g e
 o This distribution (i.e. proportion of each of these cycles) is important when
implementing a CPU-scheduling algorithm
o Continual interleaving of the CPU and IO burst cycles
• A priori there is no global scheduling algo that works well for all possible scenarios – need to
look at characteristics of your sys, the computation and IO characteristics and choose
scheduler based on that
• Graph above shows a well-balanced system
o CPU bursts are quite short – then have a long tail (small number of long CPU bursts)

CPU Scheduler
• Selects one of the processes in the ready queue to be executed
• Ready queue can be implemented as:
o FIFO queue
o A priority queue
o A tree
o An unordered linked list
o Choose which can based on the complexity of underlying system or how entries
need to be inserted into queue
• The records in the queue are process control blocks (PCBs)
o PCB contains necessary info to execute processes – process state, peripheral data,
etc
• How does the operating system choose which thread to run next?

Pre-emptive and Non-Pre-emptive scheduling

• CPU scheduling decisions can take place when a process switches from:
o (1) Running state to waiting state
o (2) Running state to ready state
o (3) Waiting state to ready state
o (4) Running state to terminated
• Scheduler decides how to do these transitions and what process to swop in once something
has been swopped out
o Trying to max CPU utilisation – don’t want CPU to be idle

66 | P a g e
 o E.g. when going from running state to waiting state – want another thread to be
scheduled in
• Non-pre-emptive/cooperative scheduling if done in situations 1 and 4 only
o Once it has CPU, process keeps it until terminated or waiting
o If only use this kind of scheduling = huge performance hit
▪ Have processes that will hog CPU
• Otherwise pre-emptive scheduling
o Can result in race conditions
• Virtually all modern OS’s (e.g. Windows, Mac OS X, Linux, and UNIX) use pre-emptive
scheduling algorithms

Scheduling Criteria
• Criteria depends on specifics of underlying system
• Have a series of tradeoffs – want to ID way of picking certain metrics and comparing them
against each other for different utilisation patterns in OS
o Use that to try to decide which scheduler makes sense for a particular use case
• Range of different scheduling algorithms with different properties
• Many potential criteria for comparison, such as:
o Maximise CPU utilization – keep the CPU as busy as possible
▪ Looking at the single core case
▪ Obviously, the best utilisation depends on the device e.g. don’t want 90%
utilisation for a mobile device (drains battery too fast)
o Maximise throughput – number of processes that complete their execution per time
unit
o Minimise turnaround time = interval from the time of submission of a process to the
time of completion
▪ i.e. total amount of time a process has been waiting in the ready queue
o Minimise total amount of time a process has been waiting in the ready queue
o Minimise response time = time to start responding
▪ Amount of time it takes from when a request was submitted until the first
process response is produced, not output (for time-sharing environment)

Scheduling Algorithms
• Concerned with the problem of deciding which of the processes in the ready queue is
allocated the CPU’s core
• Focus first on uniprocessor/ single core systems
• Five algos:
o (1) First–come, First-serve (FCFS)
o (2) Shortest-Job-First Scheduling (SJF)
o (3) Round-Robin Scheduling (RR)
o (4) Priority Scheduling
o (5) Multilevel Queue Scheduling

First–come, First-serve Scheduling

• Managed with FIFO queue
o Arriving process PCB added to end of the queue

67 | P a g e
 o Process at head of queue scheduled next on CPU
• Advantages:
o Simple
o “Fair”
• Disadvantages – average waiting time/ average response time can be long
o E.g. a long job can be scheduled onto CPU and hog it
o Less equitable access to CPU

• Gantt Chart denotates how long process takes to execute and their order
• Series of process arrive at time 0 – each process has a burst time measured in a unit
(milliseconds for examples)
• P1, P2, P3 arrive at the same time – using FIFO scheduler, P1 first placed on CPU and
executes
o Runs for 24 ms – then P2 (goes to 27 ms), and then finally P3 at 30 ms
• Waiting times for processes can be computed and calculate the average
o Avg waiting time = 17 ms – an example of convoy effect
o Convoy effect: short process queued behind long process
▪
o NB this is a possible exam question

68 | P a g e
 • With a different ordering, as seen directly above, can see that have an avg waiting time of 3
ms
o Much lower than 17ms from previous example
• Is FIFO sensible? Yes! It can be!
o When all tasks that need to be accomplished will each take roughly the same
amount of time, then it doesn’t matter
• Aside:

Shortest-Job-First Scheduling
• Under this approach, next job to be chosen by scheduler is the one that has the least
remaining time
o Not concerned with length of the running process – only at burst time
• Actually shortest-next-CPU-burst algorithm
• Associate with each process the length of its next CPU burst – when a process arrives at the
queue
o Use these lengths to schedule the process with the shortest time from those
currently in the queue
• SJF is provably optimal for response time:
o Minimum average Waiting time for a given set of processes
o Consider a case where have a short burst-time process scheduled after a long one
▪ If computing avg waiting time as metric – if move the short one before the
long time, then avg waiting time decreases for the entire system
• Example:
o All processes arrive at time 0 – p4 waiting time = 0ms, p3 = 3ms, etc
▪ 7ms as avg waiting time
o FCFS is longer

69 | P a g e
 • Accurate implementation is impossible.
• Approximate implementation is difficult:
o Hard to predict the length of the next CPU burst
▪ Thus, have to model – need some prediction scheme to guess at the next
burst time and use that as burst length for incoming job
• Assume that the next CPU burst will be similar to previous
o Predict length of next CPU burst as exponential average of previous – moving avg
which exponentially waits closer samples
▪ Samples closer to current point in time will receive a heavier weight –
further away get a much lower weight
o Pick the process with the shortest predicted CPU burst – schedule on that basis,
apply SJF algo to that

• Formalised:
o α weight between 0-1 – weighting factor that determines relative importance of
contributing terms
▪ α will sum to 1
o t is system burst time – don’t know upfront, use hindsight (deducible once the burst
has happened)
o τ is predicted burst value at a particular time step
o τn+1 – value used in SJF algo at next time step

70 | P a g e
 ▪ Predicted next CPU burst length is linear weighted sum of the previous
actual burst length + some other weighted term that encapsulates entire
history up until that point
▪ Basically, a recurrence relation
▪ As one iterates, τn will accumulate more info about the past
▪ Need to set τ0 – e.g. a constant
• Example:

• Black line is the actual burst time, blue represents the value computed by exponential
averaging scheme – lags when updated with new values, until the sequence of burst times
become similar (then converges)
• Establish impact of weighting using recurrence relations τn+1 – expand it
o By plugging in values and iteratively expanding them out – get an equation
o Terms very far in past have a high exponential factor (e.g. τ0) – and these factors
are less than one
▪ If take value between 0-1 and multiply it by itself repeatedly, it gets smaller
and smaller quickly
▪ Thus, impact of very distant terms compared to current, is very very low
• Extreme of α value – setting α to 0 will make formula reduce to next predicted burst (ie
entire history), but ignores most recent burst info that you get from system
o Use if system is unstable and burst times are not converging
• If α set to 1 – next predicted burst is the same as previous actual burst
o Ignoring history completely
• So, with guess τj = 10 and cpu burst τi = 6, then 5+3=8 (diagram)
o And so on
o Eventually, guesses being made start converging on the actual burst time – once
system has settled down

71 | P a g e
Pre-emptive or Non-pre-emptive

• SJF is either pre-emptive or non-pre-emptive

• If the predicted CPU burst of a newly arrived process is shorter than what is left of the
currently executing process, a pre-emptive SJF algorithm will pre-empt the currently
executing process (boot off the running process and swop in the newly arrived process) ,
whereas a non-pre-emptive algorithm will allow the currently running process to finish its
CPU burst
• Pre-emptive example:
o Have process 1-4, each arriving at different times with different past times
o P1 arrives and immediately gets scheduled and runs – 1ms later, p2 arrives
▪ P2 has burst time of 4ms, and p1 has 7ms left to execute
▪ So, move p1 off CPU, put it back into queue and put p2 onto CPU
o P2 runs for 4ms
o P3 arrives – p2 has 3 ms left, while p3 has 9, so it continues
o P4 arrives – at time 3, p2 has 2ms left, and that is less than p4’s 5ms
o P2 then completes at 5ms
o Then take processes that remain i.t.o their burst length – schedule p4, p1 and p3
o Avg waiting time – have to account for when each process arrived and how long
they had to wait
• Non-pre-emptive example:

o P1 arrives and runs for 8ms – but all the other processes arrive during that 8ms
o Once p1 finishes, choose the one with the next shortest burst time – p2, then p3 and
finally p3
o Avg waiting time is thus 7.75ms (worse then pre-emptive but better than FCFS)

Potential Issues
• If have long task, it will be switched on and off the CPU quite frequently, especially if it’s
mixed in with a bunch of smaller tasks
o This requires a context switch each time – adds to the general system overhead
• Potential to have starvation if have a bunch of shorter jobs that pre-empt a longer job

72 | P a g e
 o Depending on job length, may never get to run, or very little time – will take much
longer to finish

Round-Robin Scheduling (RR)

• Each process gets a small slice of CPU time (time quantum, q) – q is generally 10 to 100 ms
o Ensures that starvation can’t occur – even long processes are guaranteed to run on
the CPU (even If its just for a short amount of time), without being pre-empted by
shorter tasks
▪ All tasks are pre-empted if they go behind the time quantum, but even
longer tasks will be able to run quite frequently
• After this, process is pre-empted and added to end of the ready queue
o Ready queue treated as a circular queue – processes enter the queue, process at the
front is taken off, allowed to run for 1 time quantum
▪ If it hasn’t finished, it’s pre-empted and pushed onto the back of the queue
▪ Next item then runs, and cycle repeats
o New processes are added to ‘end’ of queue
o Scheduling is repeated until all processes have been completed
• Timer interrupts every quantum to schedule next process
• Performance depends heavily on size of quantum – choice has a severe impact on
performance of round robin scheduling scheme
o large ⇒ FCFS (FIFO)
o q small ⇒ q must be large with respect to context switch, otherwise overhead is too
high
▪ Smaller queue has more characteristics of a SJF approach i.t.o how it
regularly schedules processes with shorter remaining burst times
▪ Must still be mindful of quantum choice – everytime there’s an interrupt,
need to handle a process/thread context switch
• These switches still have a cost
• A quantum that is too small will be context switching all the time –
adds considerably to amount of times process required to execute
▪ Context switch < 10 µs
• For N processes in the ready queue and time quantum q:
o Each process gets 1/N of the CPU time in chunks of at most q time units at once
o Waiting time for a process no more than (N-1)*q time units – guaranteed bound on
waiting time, so can’t have any process starving
• Example

73 | P a g e
 o Short processes have a burst time shorter than the time quantum – when scheduled,
they’ll be able to run to completion
o P1 will run for time quantum, pre-empted (placed on the back of the queue)
▪ Then p2 scheduled – and so on
o When only p1 left – can be scheduled to be exclusively run on the queue or it could
be interrupted every quantum, chosen to run on the queue (and so on)
▪ Depends on scheduler
• Waiting time for round-robin approach isn’t necessarily better than others – because for
longer programs, they have to wait a long time to achieve completion
• Better response time because only need to run a process until it gets to a point where it can
start returning data/producing a response that’s useful for the user
• A bigger quantum size can have unexpected results on turnaround time

• Average Turnaround time of a set of processes does not necessarily improve as the time-
quantum size increases
o Average turnaround time can usually be improved if most processes finish their next
CPU burst in a single time quantum.

74 | P a g e
 o A rule of thumb is that 80 percent of the CPU bursts should be shorter than the time
quantum
▪ Can use statistical data and then modify time quantum dynamically
depending on computational load

Priority Scheduling
• A priority number (integer) is associated with each process
• CPU allocated to the process with the highest priority
o Preemptive – higher priority process can pre-empt the CPU and start running
o Non-preemptive
• SJF is actually priority scheduling, where priority is the inverse of predicted next CPU burst
time.
• Usually smallest # ≡ highest priority
• Priorities can be assigned internally – e.g. . I/O burst or externally (importance of process
etc.)
o Problem: Starvation (indefinite blocking) – low priority processes may never
execute.
o Solution: Aging – as time progresses increase the priority of the process
• Can combine priority scheduling and RR
o System executes the highest priority process; processes with the same priority will
be run using round-robin
o

Multilevel Queue Scheduling

• For priority scheduling, O(n) search may be necessary to determine the highest-priority
process.
o Easier to have separate queues for each distinct priority, priority scheduling
schedules the process in the highest - priority queue.
o A process is then permanently in a given queue.
• Can also partition according to type of process, eg. background /foreground
o i.e. some queues associated to some kinds of processes
o Foreground – need more rapid response time
o Background – run more slowly, and less frequently (lower priority)
• Each queue has its own scheduling algorithm:
o Foreground – RR
o Background – FCFS

75 | P a g e
 • Biggest issue: need to be able to extract tasks across all the queues to run on the collection
of cores
o Can service the high priority queues, and then move down – i.e. only service the
next pq when the current one is empty
▪ Problem – those current queues may never empty, leads to starvation
o Could thus allocate a fraction of the CPU budget to each of the queues
• Scheduling must be done between the queues:
o Fixed priority scheduling; (i.e., serve all from foreground then from background).
Possibility of starvation.
o Time slice – each queue gets a certain amount of CPU time which it can schedule
amongst its processes;
▪ i.e., 80% to foreground in RR
▪ 20% to background in FCFS
• A process can move between the various queues – depending on various criteria
o Aging can be implemented this way
o Multilevel-feedback-queue scheduler defined by the following parameters:
▪ Number of queues
▪ Scheduling algorithms for each queue
▪ Method used to determine when to upgrade a process
▪ Method used to determine when to demote a process
▪ Method used to determine which queue a process will enter when that
process needs service

Scheduling Algorithm Evaluation

• Analytical modelling: deterministic evaluation.
o Can always get the same result based on a given result and series of input #s
o Give exact numbers for comparison – models are the algos, take a collection of data
that corresponds to burst time in the system, run the model and see what it predicts
over all the scheduling algos
o Simple and fast, but limited to fixed scenario
• Queueing Models: queueing-network analysis.
o distribution of CPU and I/O bursts measured and then approximated or estimated
(probabilistic).
o Knowing arrival rates and service rates, we can compute utilization, average queue
length, average wait time, and so on.
▪ E.g. Little’s formula
• Simulations: program a model of the computer system.
o Use random-number generator to generate processes, CPU burst times, arrivals,
departures, and so on, according to probability distributions.
o As simulation executes, generates statistics of algorithm performance.
• Actual implementation
• Terms:
o n = average queue length
o W = average waiting time in queue
o λ = average arrival rate into queue

76 | P a g e
 o Littles law – in steady state, processes leaving queue must equal processes arriving,
thus:
▪ n=λxW
▪ Valid for any scheduling algorithm and arrival distribution

77 | P a g e