JKU

CNCS
Department of CS

Course Title: Operating Systems

Chapter Two
Processes & Process Management

By: Mamaru E. (MSc. in IT)

@ 2018
JKU, Jinka, Ethiopia 1
Content
Process and Thread
Multi-threading
Inter-process communication (IPC)
Process Scheduling (Preemptive & non-
preemptive)
Deadlock (prevention, detection, avoidance)

2
 Processes
 A process is a program in execution.
 All modern computers do many things at the same time.
 In a Uniprocessor system, at any instant, the CPU is running only one process.
But,
 In a multiprogramming system, the CPU switches from processes quickly,
running each for tens or hundreds of processes.
 It is sometimes called pseudo-parallelism since one can imagine a parallel
processor.

3
Process Creation
 Events that can cause creation
 System initialization.
 A user requests to create a new process.
 Execution of a process creation system call by a running
process.
Process Termination
 Events that cause process termination:
 Normal exit (voluntary).
 Error exit (voluntary).
 Fatal error (involuntary).
 Killed by another process (involuntary).

4
 Processes State
 The process, from its creation to completion, passes through various states.
 The state defines the true behavior of the program in a processor.

Figure 2.1: Diagram of process state. 5

[Link]: The process is being created.
[Link]: The process is waiting to be assigned to a processor.
 Many processes are in the ready stage in a multiprogramming
environment.
3. Running: a process passes from the ready to the run state.
 Instructions are being executed
4. Waiting/Blocking: The process is waiting for some event to occur
(such as an I/O completion or reception of a signal).
5. Terminated: The process has finished execution.

6
Process/Task Control Block (PCB)
 Each process is represented in the OS by a PCB.
 PCB contains Information Associated with each Process.
 It's a data structure holding:
 PC,
 CPU registers,
 Memory management information,
 Accounting (time used, ID, ...)
 I/O status (such as file resources),
 Scheduling data (relative priority, etc.)
 Process State

7
 Pointer: The pointer points to another process control block.
 A pointer is used for maintaining the scheduling list.
 Process state: The state may be new, ready, running, waiting,
or halted.
Program counter: The counter indicates the address of the
next instruction to be executed for this process.
CPU registers: The registers vary in number and type,
depending on the computer architecture.
 They include accumulators, index registers, stack pointers, &
general-purpose registers, plus any condition-code information.
8
 CPU scheduling information: includes a process priority, pointers to scheduling
queues, and any other parameters.
Memory-management information: includes the value of the base and limit
registers, the page tables, or the segment tables, depending on the memory.
Accounting information: includes the amount of CPU and real-time used, time
limits, account numbers, and job or process numbers.
I/O Status information: The information includes the list of I/O devices
allocated to the processes and a list of open files.
 The PCB simply serves as the repository for any information that may vary from
process to process.
9
 Implementation of Processes
 The OS organizes the data about each process in a table,
naturally called the process table.
 Each entry in this table is called a process table entry (PTE)
or process control block.
 One entry per process.
 The central data structure for process management.
 A process state transition is reflected by a change in the
value of one or more fields in the PTE.

10
 Thread
 A thread is a single sequential flow of execution of tasks of a process.
 It is also known as the thread of execution or thread of control.
 A thread is a lightweight, independent unit of execution within a process.
 Think of a process as a container holding resources (memory, files, etc.), and
threads as the workers inside that container, sharing those resources to perform
specific tasks.
 Lightweight: Threads are "lighter" than processes.
 Creating, switching between, and terminating threads typically involves less
above than doing the same with processes.
 This is because threads share the same memory space and resources of their
parent process.
11
 Concurrency: Threads enable concurrency within a process.
 Multiple threads within a process can execute concurrently, either by truly
running in parallel on a multi-core processor or by rapidly switching between
each other, giving the illusion of parallelism.
 Shared Resources: Threads within the same process share resources such as:
 Memory space (global variables, heap)
 Open files
 I/O devices
 Code (instructions)
 Independent Execution: Each thread has its own:
 Program counter (instruction pointer)
 Stack (for local variables and function calls)
 Set of registers
12
 … Thread

 The first column lists some items shared by all threads in

a process.
 The second one lists some items private to each thread.
13
 The Thread Model
 A process contains several resources such as address space, open files,
accounting information, etc.
 In addition to these resources, a process has a thread of control.
 The idea of threads is to permit multiple threads of control to execute within
one process.
 This is often called multithreading, and threads are often called lightweight
processes.

14
The Classical Thread Model

(a) Three processes, each with one thread.

(b) One process with three threads.
15
 Reasons to use threads
 Enables parallelism (web server) with blocking
system calls
 Threads are faster to create and destroy than
processes
 Natural for multiple cores
 Easy programming model

16
 Situations to use threads
 Doing lengthy processing: When a Windows application is calculating, it
cannot process any more messages.
 As a result, the display cannot be updated.
 Doing background processing: Some tasks may not be time-critical, but need
to execute continuously.
 Doing I/O work: I/O to disk or to the network can have unpredictable delays.
 Threads allow you to ensure that I/O latency does not delay unrelated parts
of your application.

17
Threads: Benefits
• User responsiveness
– When one thread blocks, another may handle user I/O.
– But it depends on the threading implementation
• Resource sharing: economy
– Memory is shared (i.e., address space shared)
– Open files, sockets shared
• Speed
– E.g., Solaris: thread creation about 30x faster than heavyweight process
creation; context switch about 5x faster with thread
• Utilizing hardware parallelism
– Like heavyweight processes, they can make use of multiprocessor
architectures
18
 Threads: Drawbacks
 Synchronization Overhead: Managing shared resources requires synchronization.
 which can introduce overhead and complexity, potentially slowing down execution.
 Race Conditions: Without proper synchronization, multiple threads accessing shared data
concurrently can lead to unpredictable and incorrect results (race conditions).
 Deadlock: Threads can become blocked indefinitely, waiting for each other to release
resources, resulting in a standstill (deadlock).
 Increased Complexity: Designing and implementing multi-threaded applications requires
careful consideration of thread safety, synchronization, and potential concurrency issues.
 Security Risks: If not handled carefully, shared memory spaces in multithreaded
programs can become a security vulnerability.
19
 Inter-process Communication (IPC)
 IPC enables processes to exchange data and synchronize execution.
 Common IPC mechanisms include pipes, message queues, shared memory, and
sockets, facilitating cooperation between independent programs.
1. Race condition
 When two processes can interact, the outcome depends on the order in which the
processes execute.
2. Mutual exclusion
 Prohibit/Disallow more than one process from reading and writing the shared data
at the same time.
3. Critical region
 Part of the program where the shared memory is accessed.
20
Process Scheduling (context switch (process switch))

 The part of the OS that makes this decision is called the scheduler.
 The algorithm it uses is called the scheduling algorithm.
 Scheduling may involve both processes and threads.
 Scheduling a process means changing the active PCB pointed to by the CPU.
 Process switch: - It means that the memory, as seen by one process, is
changed to the memory seen by another process.
Scheduling Queues:
 Process is driven by events that are triggered/activated by needs and availability.
 Ready queue = contains those processes that are ready to run.
 I/O queue (waiting state ) = holds those processes waiting for I/O service.
21
 Scheduling Criteria
 Fairness – each process must get its fair share of the CPU.
 Throughput – number of jobs that are completed per unit
time.
 Turnaround Time: the time between the submission of a job
and the time of completion.
 Waiting Time – time spent to get into memory and time spent
waiting in the ready queue.
 Response Time – the time from submission of the job until the
first response is produced.

Objective:
- Maximize: CPU Utilization and Throughput
- Minimize: Turnaround Time, Waiting Time, and Response Time 22
Algorithm Concepts
• Preemptive algorithm
– If a process is still running at the end of its time
interval, it is suspended and another process is
picked up
• Non-preemptive
– Picks a process to run and then lets it run till it
blocks or it voluntarily releases the CPU
23
Common Types of Scheduling Algorithms
 CPU scheduling deals with the problem of deciding which of the processes
in the ready queue is to be allocated the CPU.
1. First-come-first-served (FCFS/FIFO)
2. Shortest job first (SJF) or Shortest Remaining Time Next
3. Priority Scheduling
4. Round Robin Scheduling
1. First-come-first-served (FCFS/FIFO)
 Non-preemptive
 The CPU is assigned in the order of the processes required
 When the running process blocks, the following one in the queue is
selected
 When a blocked process becomes ready, it is put at the end of the
queue.
 Not optimal, but it is simple to write and understand.
 Process priority is executed based on its arrival time. If they arrive at the same time, their order is
determined by alphabetical order.
Consider the following set of processes that arrive at time 0, with the
length of the CPU-burst time (execution time) given in milliseconds:
 If the processes arrive in the order P1, P2, & P3, and are served in FCFS order,
we get the result shown in the following Gantt chart:

 The following table shows the Arrival Time, Start Time, Waiting Time, Finish Time, and
Turnaround Time of the given Processes:

 The waiting time is 0 milliseconds for process P1, 24 milliseconds for process
P2, and 27 milliseconds for process P3. Thus,
 The average waiting time= (0 + 24 + 27)/3 = 17 milliseconds.
 The average turnaround time= (24 + 27 + 30)/3 = 27 milliseconds.
 If the processes arrive in the order P2, P3, and P1, however, the results will be as
shown in the following Gantt chart:

 The following table shows the Arrival Time, Start Time, Waiting Time, Finish Time, and
Turnaround Time of the given Processes:

 The average waiting time= (6 + 0 + 3)/3 = 9/3 = 3 milliseconds.

 The average turnaround time= (3 + 6 + 30)/3 = 39/3 = 13 milliseconds.
 This reduction is substantial. Thus, the average waiting time under an FCFS policy
is generally not minimal and may vary substantially if the process CPU-burst times
vary greatly.
27
2. Shortest job first (SJF)
 Be preemptive (shortest-remaining-time-first scheduling) or non-
preemptive
 Suppose we know the run-time in advance
 The CPU is assigned to the shortest job in the queue
 Optimal if all the jobs are available simultaneously.
 Process priority is executed based on its execution (burst) time. If they have the same
execution
e.g., considertime, their order
processes, withisthe
determined
length ofby
theFCFS.
CPU burst time given in milliseconds:

 N.B.: A process that has a shorter

execution time executes first.

 Using SJF scheduling, we would schedule these processes according to the f/f
Gantt chart:
 non-preemptive 28
 The following table shows the Arrival Time, Start Time, Waiting Time, Finish
Time, and Turnaround Time of the given Processes:

 The waiting time is 3 milliseconds for process P1, 16 milliseconds for process
P2, 9 milliseconds for process P3, and 0 milliseconds for process P4. Thus
 The average waiting time= (3 + 16 + 9 + 0)/4 = 28/4 = 7 milliseconds.
 The average turnaround time= (9 + 24 + 16 + 3)/4 = 52/4 = 13 milliseconds.

29
Preemptive SJF scheduling called shortest-remaining-time-first scheduling.
 As an example, consider the following four processes, with the length of the CPU-
burst time given in milliseconds:

If the processes arrive at the ready queue at the times shown and need the indicated
burst times, then the resulting preemptive SJF schedule is as depicted in the
following Gantt chart:

30
 Process Pl is started at time 0 since it is the only process in the queue.
 Process P2 arrives at time 1.
 The remaining time for process P1 (7 milliseconds) is larger than the time
required by process P2 (4 milliseconds), so process P1 is preempted, and process
P2 is scheduled.
 The average waiting time= (9 + 0 + 15 + 2)/4 = 26/4 = 6.5 milliseconds.
 The average turnaround time= (17 + 4 + 24 + 7)/4 = 52/4 = 13 milliseconds.
 A non-preemptive SJF scheduling would result in an average waiting time of
7.75 milliseconds. 31
 3. Priority Scheduling
 A priority is associated with each process, and the CPU is allocated to the process
with the highest priority.
 Equal-priority processes are scheduled in FCFS order.
 An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse
of the (predicted) next CPU burst.
 The larger the CPU burst, the lower the priority, and vice versa.
 Priorities are generally some fixed ranges of numbers, such as 0 to 7 or 0 to 4095.
 However, there is no general agreement on whether 0 is the highest or lowest
priority.
 Some systems use low numbers to represent low priority; others use low numbers
for high priority.
 This difference can lead to confusion.
 In this, we assume that low numbers represent high priority.
32
 As an example, consider the following set of processes, assumed to have arrived
at time 0, in the order P1, P2, P3, P4, P5, with the length of the CPU-burst time
given in milliseconds:

Gantt chart representation:

33
The following table shows the Arrival Time, Start Time, Waiting Time, Finish Time,
and Turnaround Time of the given Processes:

The average waiting time= (6 + 0 + 16 + 18 + 1)/5 = 41/5 = 8.2 milliseconds.

The average turnaround time= (16 + 1 + 18 + 19 + 6)/5 = 60/5 = 12 milliseconds.

34
 Priority scheduling can be either preemptive or non-
preemptive.
 When a process arrives at the ready queue, its priority is
compared with the priority of the currently running process.
 A preemptive priority scheduling algorithm will preempt the
CPU if the priority of the newly arrived process is higher than
the priority of the currently running process.
 A non-preemptive priority scheduling algorithm will simply put
the new process at the head of the ready queue.
 A major problem with priority scheduling algorithms is
indefinite blocking or starvation.
 A process that is ready to run but lacking the CPU can be
considered blocked, waiting for the CPU.
35
 A priority scheduling algorithm can leave some low-priority processes waiting
indefinitely for the CPU.
 In a heavily loaded computer system, a steady stream of higher-priority processes
can prevent a low-priority process from ever getting the CPU.
 A solution to the problem of indefinite blockage of low-priority processes is aging.
 Aging is a technique of gradually increasing the priority of processes that wait in
the system for a long time.
 For example, if priorities range from 0 (low) to 127 (high), we could increment
the priority of a waiting process by 1 every 15 minutes.
 Eventually, even a process with an initial priority of 0 would have the highest
priority in the system and would be executed.
 It would take no more than 32 hours for a priority 0 process to age to a priority 127
process.
36
 e
pl
am
Ex

Non-Preemptive Priority Scheduling:

1. At time 0, P1 arrives and starts running (no other processes yet).
2. P1 completes at time 5.
3. At time 5, P2 (priority 1) is in the ready queue and starts running.
4. P2 completes at time 8.
5. At time 8, P3 starts running.
6. P3 completes at time 10.
Completion Times: P1 = 5, P2 = 8, P3 = 10
Turnaround Times:
P1 = 5 - 0 = 5
P2 = 8 - 1 = 7
P3 = 10 - 2 = 8 37
Preemptive Priority Scheduling:
1. At time 0, P1 arrives and starts running.
2. At time 1, P2 arrives (priority 1). Since P2 has a higher priority, P1 is preempted,
and P2 starts running.
3. P2 completes at time 4.
4. At time 4, P1 resumes running (it has a remaining burst time of 4).
5. At time 5, P3 arrives. Since P1 has a higher priority than P3, P1 continues running.
6. P1 completes at time 8.
7. P3 starts running.
8. P3 completes at time 10.
Completion Times: P1 = 8, P2 = 4, P3 = 10
Turnaround Times:
P1 = 8 - 0 = 8
P2 = 4 - 1 = 3
P3 = 10 - 2 = 8
38
 4. Round-Robin Scheduling
 The RR is designed especially for timesharing systems.
 It is similar to FCFS, but preemption is added to switch between processes.
 A small unit of time, called a time quantum, or time slice, is defined.
 A time quantum is mostly between 10 and 100 milliseconds.
 The ready queue is treated as a circular queue.
 The CPU scheduler traverses the ready queue, allocating the CPU to each
process for a time interval of up to one time quantum.
 To implement RR, we keep the ready queue as a FIFO queue of processes.
 New processes are added to the tail of the ready queue.

39
 The CPU scheduler picks the first process from the ready queue, sets a timer to
interrupt after a 1-time quantum, and dispatches the process.
 One of two things will then happen.
 The process may have a CPU burst of less than 1-time quantum.
 In this case, the process itself will release the CPU voluntarily.
 The scheduler will then proceed to the next process in the ready queue.
 Otherwise, if the CPU burst of the currently running process exceeds the 1-time
quantum, the timer will go off, causing an interruption to the OS.
 A context switch will be executed, and the process will be put at the tail of the
ready queue.
 The CPU scheduler will then select the next process in the ready queue.
 The average waiting time under the RR policy, however, is often quite long.
40
 Consider the following set of processes that arrive at time 0, with the length of the
CPU-burst time given in milliseconds:

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

The following table shows the Arrival Time, Start Time, Waiting Time, Finish Time, and
Turnaround Time of the given Processes:

 The average waiting time= (6 + 4 + 7)/7 = 17/3 = 5.66 milliseconds.

 The average turnaround time= (30 + 7 + 10)/3 = 47/3 = 15.66 milliseconds.
 In the RR, no process is allocated the CPU for more than 1 time quantum in a row.
 If a process’ CPU burst exceeds 1 time quantum, that process is preempted and is
put back in the ready queue.
42
 Deadlocks
 A deadlock is a set of processes that is deadlocked if each process in the set
is waiting for an event that only another process in the set can cause.

Conditions for Resource Deadlocks

 All the following four conditions must hold for a deadlock to occur.
1. Mutual exclusion: only one process at a time can use a resource.
2. Hold and wait: a process holding at least one resource is waiting to acquire
additional resources held by other processes.
3. No preemption: a resource can be released only voluntarily by the process
holding it after that process has completed its task.
4. Circular wait: there exists a set of waiting processes.
 Deadlock Modeling

Strategies for dealing with deadlocks:

[Link] ignore the problem.

[Link] and recovery. Let deadlocks occur, detect them, take

action.

[Link] avoidance by careful resource allocation.

[Link], by structurally negating one of the four required

conditions.
 Deadlock Detection
 If a system does not employ a deadlock prevention algorithm or a deadlock
avoidance algorithm, then a deadlock situation may occur.
 Therefore, the system must provide:
 Detection: an algorithm that examines the state of the system to determine
whether a deadlock has occurred.
 Recovery: an algorithm to recover from the deadlock.
 A detection and recovery scheme requires overhead that includes:
– Run-time costs of maintaining the necessary information.
– Executing the detection algorithm.
– The potential losses inherent in recovering from a deadlock.
 Deadlock Avoidance
 The simplest and most useful model requires that each process
declare the maximum number of resources of each type that it
may need.
• The deadlock-avoidance algorithm dynamically examines the
resource-allocation state to ensure that there can never be a
circular wait condition.
• Resource-allocation state is defined by the number of available and
allocated resources, and the maximum demands of the processes.
 Deadlock Prevention
• Attacking the mutual exclusion condition
– resource assigned exclusively to a single process, e.g., memory
– Not possible for all types of resources.
• Attacking the hold and wait condition
– require all processes to request all their resources before starting execution
– processes do not know how many resources they will need until they have
started running
• Attacking the no preemption condition
– Forcibly take away the resource.
– Problem, e.g., forcibly taking away the printer while it is printing.
• Attacking the circular wait condition
 Recovery from Deadlock: Process Termination

• Abort all deadlocked processes.

• Abort one process at a time until the deadlock cycle is eliminated.
• In which order should we choose to abort?
– Priority of the process.
– How long process computed, and how much longer to complete
– Resources the process has used.
– The resources process needs to be completed.
– How many processes will need to be terminated?
– Is the process interactive or batch?

49
 Recovery from Deadlock: Resource Preemption

 Selecting a victim – minimize cost.

 Rollback – return to some safe state, restart the process for that state.
 Starvation – the same process may always be picked as the victim,
including the number of rollbacks in the cost factor.

50
 u !
y o
k
a n
n?
Th
tio
e s
Q u

51