INTRODUCTION Early computers allowed only one program to be executed at a time.

This
program had complete control of the system and had access to all the system’s resources. In
contrast, contemporary computer systems allow multiple programs to be loaded into memory
and executed concurrently. This evolution required firmer control and more
compartmentalization of the various programs; and these resulted in the notion of a process,
which is a program in execution. A process is the unit of work in a modern time-sharing system.
The more complex the operating system is, the more it is expected to do on behalf of its users.
Although its main concern is the execution of user programs, it also needs to take care of
various system tasks that are better left outside the kernel itself. A system therefore consists of
a collection of processes: operating-system processes executing system code and user
processes executing user code. Potentially, all these processes can execute concurrently, with
the CPU (or CPUs) multiplexed among them. By switching the CPU between processes, the
operating system can make the counter more productive. In this module, you will read about
what processes are and how they work. LEARNING OBJECTIVES At the end of this module,
the student can be able to: 1. Introduce the notion of a process – a program in execution, which
forms the basis of all computation. 2. Describe the various features of processes, including
scheduling, creation, and termination. 3. Explore interprocess communication using shared
memory and message passing. 4. Describe communication in client-server systems. UNIT 3 47
LECTURE DISCUSSION What Is a Process? A process is a program in execution. For
example, when we write a program in C or C++ and compile it, the compiler creates binary
code. The original code and binary code are both programs. When we actually run the binary
code, it becomes a process. A process is an active entity, as opposed to a program, which is
considered to be a passive entity. A single program can create many processes when run
multiple times; for example, when we open a .exe or binary file multiple times, multiple
processes are being created. Figure 3.6: Process in memory What does a Process Look Like in
Memory? • Text Section – A process, sometimes known as the Text Section, also includes the
current activity represented by the value of the program counter. • Stack – Contains the
temporary data, such as function parameters, returns addresses, and local variables. • Data
Section – Contains the global variable. • Heap Section – Dynamically allocated memory to
process during its run time. 48 Lesson 2: Process States As process executes, it changes state.
The state of a process is defined in part by the current activity of that process. A process may
be in one of the following states: • New – Newly created process or the process being created. •
Ready – After creation process moves to Ready state, in other words, the process is ready for
execution. • Run – Currently running process in CPU (only one process at a time can be under
execution in a single processor). • Wait (or Block) – When a process request I/O access. •
Complete (or Terminated) – The process that completed its execution. • Suspended Ready –
When the ready queue becomes full, some processes are moved to this state. • Suspended
Block – When waiting queue becomes full. Context Switching The process of saving the context
of one process and loading the context of another process is known as context switching. In
simple terms, it is like loading and unloading the process from running state to ready state.
Context switching happens when: Figure 3.7: Process states 49 • When a high-priority process
comes to ready state (i.e. with higher priority than the running process) • An interrupt occurs. •
User and kernel mode switch (though, this is not necessary) • Preemptive CPU scheduling is
used. Context Switch versus Mode Switch A mode switch occurs when CPU privilege level is
changed, for example when a system call is made or a fault occurs. The kernel works in a more
privileged mode than a standard user task. If a user process wants to access things which are
only accessible to the kernel, a mode switch must occur. The currently executing process need
not to be changed during a mode switch. A mode switch typically occurs for a process context
switch to occur. Only the kernel can cause a context switch. CPU-Bound versus I/O-Bound
Processes A CPU-bound process requires more CPU time or spends more time in the running
state, while an I/O-bound process requires more I/O time and less CPU time. An I/O bound
process spends more time in the waiting state. 50 Lesson 3: Process Creation and Termination
There are two basic operations that can be performed on a process: Creation and Termination.
Process Creation A process may be created in the system for different operations. Some of the
events that lead to process creation are: • User request for process creation • System
initialization • Batch job initialization • Execution of a process creation system call by a running
process. Here are the steps in process creation: 1. When a new process is created, the
operating system assigns a unique Process Identifier (PID) to it and inserts a new entry in
primary process table. 2. Then the required memory space for all the elements of process such
as program, data, and stack is allocated including space for its Process Control Block (PCB). 3.
Next, the various values in PCB are initialized such as: a. Process identification part is filled with
PID assigned to it in step 1 and also its parent’s PID. b. The processor register values are
mostly filled with zeroes, except for the stack pointer and program counter. Stack pointer is filled
with the address of stack allocated to it in step 2 and program counter is filled with the address
of its program entry point. c. The process state information would be set to “New”. d. Priority
would be lowest by default, but user can specify any priority during creation. In the beginning,
process is not allocated to any I/O devices or files. The user has to request them or if this is a
child process it may inherit some resources from its parent. 51 4. Then, the operating system
will link this process to scheduling queue and the process state would be changed from “New”
to “Ready”. Now, process is competing for the CPU. 5. Additionally, operating system will create
some other date structures such as log files or accounting files to keep track of processes
activity. A process may be created by another process using fork(). The creating process is
called the parent process and the created process is called the child process. A child process
can have only one parent but a parent process may have many children. Both the parent and
child processes have the same memory image, open files and environment strings. However,
they have distinct address spaces. A diagram that demonstrates process creation using fork() is
as follows: Figure 3.8: Process creation using fork() Process Termination Process termination
occurs when the exit system is called. A process usually exits after its completion but
sometimes there are cases where the process aborts execution and terminates. When a
process exits, resources, memory, and I/O devices are all deallocated. Some of the causes of
process termination are as follows: • When a parent process is terminated, its child process is
also terminated. This happens when a child process cannot exist without its parent process. • If
a process needs additional memory more than what the system allocated, termination happens
because of memory scarcity. • A process tries to access a resource that is not allowed to use. •
If the process fails to allocate a resource within the allotted time. • When a parent process
requests the termination of its child process. 52 • The task is no longer required or needed.
Lesson 4: Process Threads A thread is a path of execution within a process code, with its own
program counter that keeps track of which instruction to execute next, system registers which
hold its current working variables, and a stack which contains the execution history. Each thread
belongs to exactly one process and no thread can exist outside a process. Each thread
represents a separate flow of control. Threads have been successfully used in implementing
network servers and web server. They also provide a suitable foundation for parallel execution
of applications on shared memory multiprocessors. The following shows the working of a single-
threaded and a multithreaded process. Figure 3.9: Single-threaded (left) and multithreaded
process (right). Multithreading A thread is also known as lightweight process. The idea is to
achieve parallelism by dividing a process into multiple threads. For example, in a browser,
multiple tabs can be different threads. Microsoft Word uses multiple threads: one thread to
format the text, another thread to process the inputs, etc. 53 Thread versus Process The
primary difference is that threads within the same process run in a shared memory space, while
processes run is separate memory spaces. Threads are not independent of one another like
processes are, and as a result, threads share with other threads their code section, data
section, and OS resources (like open files and signals). But, like processes, a thread has its
own program counter (PC), register set, and stack space. Below are some of the differences
between the thread and process: Table 3.1 – Differences between Thread and Process Process
Thread Process is heavy weight or resource intensive. Thread is light weight, taking lesser
resources than a process. Process switching needs interaction with operating system. Thread
switching does not need to interact with operating system. In multiple processing environments,
each process executes the same code but has its own memory and file resources. All threads
can share same set of open files, child processes. If one process is blocked, then no other
processes can execute until the first process is unblocked. While one thread is blocked and
waiting, a second thread in the same task can run. Multiple processes without using threads use
more resources. Multiple threaded processes use fewer resources. In multiple processes, each
process operates independently of the others. One thread can read, write or change another
thread’s data. Advantages of Thread over Process 1. Responsiveness – If the process is
divided into multiple threads, if one thread completes its execution, then its output can be
immediately returned. 2. Faster context switch – Context switch time between threads is lower
compared to process context switch. Process context switching requires more overhead from
the CPU. 3. Effective utilization of multiprocessor system – If we have multiple threads in a
single process, then we can schedule threads on multiple processor. This will make process
execution faster. 54 4. Resource sharing – Resources like code, data, and files can be shares
among all threads within a process (Note: Stack and registers can’t be shared among the
threads. Each thread has its own stack and registers.) 5. Communication – Communication
between multiple threads is easier, as the thread shares common address space. While in
process we have to follow some specific communication technique for communication between
two processes. 6. Enhanced throughput of the system – If a process is divided into multiple
threads, and each thread function is considered as one job, then the number of jobs completed
per unit of time is increased, thus increasing the throughput of the system. 55 Lesson 5:
Process Schedulers Process scheduling is an activity of the process manager that controls and
manages the removing of processes and choosing another process using a certain strategy in
the CPU. Let’s put it in this way. It’s like a student attending subjects on a single room. When a
time allotted for a certain subject goes up, another professor will come in, teaching a different
subject, depending on the schedule assigned by the school. It can be also be compared to a
queue in a grocery store. The same goes for the scheduling of processes. If a process is
finished, another one will take its place, or simply be just removed from the queue, depending
on the chosen strategy. Process Scheduling Queues The operating system maintains all PCBs
(Process Control Blocks) in scheduling queues. PCB is a structure of data which contains the
information related to the process. The system maintains a different queue for each of the
process states and PCBs of all processes at the same execution state are placed in the same
queue. The system maintains the three important scheduling queues for processes: • Job
Queue – This keeps all the processes in the system. • Ready Queue – This keeps all processes
wait in the main memory, ready and waiting to be executed. A new process is always put in this
queue. Device Queue – The processes which are blocked due to unavailability of an I/O device
make up this queue. This can be compared to baking batches of cookies. Let’s say that you only
have two trays and a single oven. When you have prepared two full trays of cookies, and if
you’re going to make another batch, you have to put it somewhere else first, for example, on a
plate (Job Queue), because the trays (Ready Queue) are still unavailable. Meanwhile, a tray of
unbaked cookies must be set aside first while another tray is still being baked inside the oven
(CPU) since one cannot bake more than a tray, which then will stay on the ready queue. Figure
3.10: Process scheduling queues. 56 The operating system can use various strategies or
policies to manage each queue (such as First Come First Serve, Shortest Job First, etc. which
will be discussed on the next part of this module). The scheduler determines how to move
processes between read and run queues which can only have one entry per processor core on
the CPU as shown in the diagram above. Schedulers There are three types of schedulers that
chooses the jobs to be submitted to the system to decide which process is to be run. These are
the long-term, short-term, and medium-term schedulers which will be discussed below. Long-
term scheduler (also known as job scheduler) is the one responsible for determining which
programs should be admitted to the system. It selects processes from the queue and puts them
in the memory for it to be executed. Short-term scheduler’s (also known as CPU scheduler)
main task is to improve system performance while following a certain set of criteria. It is where
the change happens from ready state to running state of the process. These are also known as
dispatchers, because the manage processes that are ready to execute and allocates CPU to
one of them. Medium-term scheduler is where the swapping part of the process occurs.
Swapping takes place whenever a process becomes suspended. When processes are
suspended, it cannot be completed anymore. Thus, removing it from the memory and placing it
on the secondary storage. This reduces the degree of multiprogramming and is necessary to
improve the process mix. For example, if a person on a line for payment forgets his/her money,
he is forced to leave the queue and come at the back again. 57 Lesson 6: Process Scheduling
Concepts Process scheduling is the process manager’s ability to remove running process from
the CPU and selecting another process through a particular strategy. It is the cycle by which the
CPU determines which processes are ready to be moved to the running state. The main goal of
this is to keep the CPU occupied all the time and to provide the least amount of response time
for every program. To do this, the scheduler should apply the appropriate rules to swap
processes in and out of the CPU. There are two scheduling categories, namely the non-
preemptive scheduling and the preemptive scheduling. Non-preemptive scheduling is a where
process will not be interrupted and will be executed until it is finished, while preemptive
scheduling is where a process can be interrupted to give way for another process that has a
higher priority of shorter job than the current ongoing one. Scheduling of processes is also done
to finish the work/process on time. Below are different time with respect to a process: • Arrival
Time (AT) – Time at which the process arrives in the ready queue. • Completion Time – Time at
which process completes its execution. • Burst Time (BT) – Time required by a process for CPU
execution. • Turn Around Time (TaT) – Time difference between completion time and arrival
time. Formula: Turn Around Time = Completion Time – Arrival Time • Waiting Time (WT) – Time
difference between TaT and BT. Formula: Waiting Time = Turn Around Time – Burst Time 58
Lesson 7: Process Scheduling Algorithms A process scheduler uses various algorithms to
execute processes on the CPU. These scheduling algorithms are divided into two categories
mentioned above. These algorithms are as follows: Table 3.2 Scheduling Algorithms Non-
Preemptive Preemptive First Come First Serve (FCFS) Round Robin Shortest Job First (SJF)
Shortest Remaining Time First (SRTF) Non-Preemptive Priority Preemptive Priority Additional
two algorithms are Multi-Level Queue (MLQ) and Multi-Level Feedback Queue (MLFQ) which
contain two or more algorithms. Objectives of Process Scheduling Algorithms The following are
the objectives of these scheduling algorithms: • Maximize CPU utilization [Keep CPU as busy as
possible] • Fair allocation of CPU • Maximize throughput [Number of processes that complete
their execution per time unit] • Minimize turnaround time, waiting time, and response time.
Scheduling Algorithms 1. First Come First Serve (FCFS) – Simplest scheduling algorithm that
schedules according to arrival times of processes. First come first serve scheduling algorithm
states that the process that requests the CPU first is allocated the CPU first. It is implemented
by using the First In First Out (FIFO) queue. When a process enters the ready queue, its PCB is
linked onto the tall of the queue. When the CPU is free, it is allocated to the process at the head
of the queue. The running process is then removed from the queue. To put it in this way,
imagine that you are in a fast food chain, when you order a food at the cashier, you must fall in
line. Whoever comes first in line will be served first by the cashier. Consider the following table:
59 Job Arrival Time Burst Time J1 0 5 J2 1 4 J3 3 3 J4 5 6 Step 1: Draw a timeline for you to
know the arrangement of jobs in chronological order. J1 J2 J3 J4 0 1 3 5 Step 2: Create a Gantt
chart by following the arrangement of the jobs and taking their respective burst times. The first
job to come is J1 that arrived in time 0 and with a burst time of 5. Therefore the Gantt chart will
be J1 5 Next job to come is J2 with a burst time of 4. J1 J2 0 5 9 Next job to come is J3 with a
burst time of 3. J1 J2 J3 0 5 9 12 Then, the last job to come is J4 with a burst time of 6. J1 J2 J3
J4 0 5 9 12 18 Now, let’s check the CPU Utilization, turnaround time, and waiting time. To
compute for the CPU Utilization, use this formula: ����� ����� ���� ���
���� � 100 Take note that the End Time that we are talking here is the end time of the
Gantt char. Therefore, 18 18 � 100 = 100% ��� ����������� 60 Next, we will
get the turnaround and waiting time of each job as well as the average turnaround and waiting
times. Use the formula given on the previous lesson. Job Turnaround Time Waiting Time J1 5 –
0 = 5 5 – 5 = 0 J2 9 – 1 = 8 8 – 4 = 4 J3 12 – 3 = 9 9 – 3 = 6 J4 18 – 5 = 13 13 – 6 = 7 Average
8.75 4.25 One of the problems that the FCFS suffers is the convoy effect. Convoy effect is a
phenomenon associated with the FCFS algorithm, in which the whole operating system slows
down due to few slow processes. 2. Shortest Job First (SJF) – Process which have the shortest
burst time are scheduled first. If two processes have the same burst time then FCFS is used to
break the tie. Given the same example in FCFS, The Gantt chart using SJF will be: J1 J3 J2 J4
0 5 8 12 18 Same formula will be used for the CPU utilization, turnaround time and waiting time.
3. Non-Preemptive Priority (NPP) – The job with the highest priority is processed first. In case of
jobs having the same priority, the job’s arrival time will be considered, therefore processing first
the job who arrived first. Using the example in the FCFS, we will adding a priority to each job.
The highest priority will be 0, and so on. Job Arrival Time Burst Time Priority J1 0 5 3 J2 1 4 0
J3 3 3 2 J4 5 6 1 The Gantt chart of these jobs using the NPP will be: 61 J1 J2 J4 J3 0 5 9 15
18 4. Preemptive Priority – This is the preemptive version of the NPP. Both prioritizes the job
with higher priority but it preempts every time a process enters the ready state, it then compares
the priority of the new job to the current job and to all of the process inside the ready queue and
will execute the process with higher priority. Let’s still use the given in NPP and to create a
Gantt chart using the Preemptive Priority. However, we will change the priority to be able to
simulate the latter algorithm. Job Arrival Time Burst Time Priority J1 0 5 1 J2 1 4 0 J3 3 3 2 J4 5
6 1 The Gantt chart will be: J1 J2 J2 J1 J4 J3 0 1 3 5 9 15 18 1. Shortest Remaining Time First
(SRTF) – This is the preemptive version of SJF but similar process to Preemptive Priority in
which the job will preempt every time a new job enters the ready state. In this algorithm, the job
with shortest burst time or remaining time will be processed first. Using the given in the previous
algorithm, the Gantt chart for this algorithm will be: J1 J2 J2 J3 J1 J4 0 1 3 5 8 12 18 2. Round
Robin (RR) – This is the preemptive version of the FCFS. Each process is assigned a fixed time
(Time Quantum / Time Slice) in cyclic way. It is designed especially for the time sharing system.
The ready queue is treated as a circular queue. The CPU scheduler goes around the ready
queue, allocating the CPU to each process for a time interval of up to 1-time quantum. To
implement Round Robin scheduling, we keep the 62 ready queue as FIFO queue of processes.
New processes are added to the tail of the ready queue. The CPU scheduler pick the first
process from the ready queue, sets a timer ton interrupt after 1-time quantum, and dispatches
the process. One of the two things will then happen. The process may have a CPU burst of less
than 1-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 is longer than 1-time quantum, the timer will go off and will cause an
interrupt to the operating system. A context switch will be executed, and the process will be put
at the tail of the ready queue. The CPU scheduler will then select the next process in the ready
queue. To have a better understanding of this algorithm, consider yourself queueing at the ATM
station where there maximum transactions allowed is 2. If you have more than 2 transactions,
after your second transaction, you must go to the back of the line to give way to the person next
to you. Using again the given in the previous algorithm, let’s create a Gantt chart using the
Round Robin with a Time Slice of 2. J1 J2 J1 J3 J2 J4 J1 J3 J4 J4 0 2 4 6 8 10 12 13 14 16 18
3. Multilevel Queue (MLQ) – According to the priority of process, processes are places in
different queues. Generally high priority processes are placed in the top level queue. Online
after completion of processes from top level queue, lower level queued processes are
scheduled. Example: Consider the given table: Job Arrival Time Burst Time Priority Queue No.
J1 0 5 1 0 J2 0 4 1 1 J3 0 3 2 0 J4 5 6 0 1 63 As you can see, the Level column is added to the
table. That column is connected to this table below in which each level is assigned to a single
algorithm and a priority. Queue No. Algorithm Priority 0 Shortest Job First High Level Queue 1
Non-Preemptive Priority Low Level Queue Therefore, since Queue No. 0 has the highest level
queue, all jobs under the said queue will be executed first, then followed by the queue number
with the next to the highest level queue and so on. The Gantt chart using MLQ will be: J3 J5 J4
J2 0 3 8 14 18 Following the algorithm on the Queue No. 0, J3 was executed first followed by
J5. Since, there no jobs left for Queue No. 1, the next queue number will be executed then.
Hence, having J4 to be executed first followed by J2, following the algorithm on the Queue No.
1. 5. Multi-Level Feedback Queue (MLFQ) – It allows the process to move between queues.
The idea is to separate processes according to the characteristics of their CPU bursts. If a
process uses too much CPU time, it is moved to a lower-priority queue. This is similar to MLQ
however, this process can move between the queues. MLFQ keep analyzing the behavior (time
of execution) of processes and according to which it changes its priority. The diagram and the
explanation below will make you understand how MLFQ works. Figure 3.12 MLFQ process flow
64 Let us suppose that Queue 1 and 2 follow Round Robin with a time slice of 4 and 8,
respectively, and Queue 3 follows FCFS. The implementation of MLFQ will be: 1. When a
process starts executing then it enters Queue 1. 2. In Queue 1, process executes for 4 unit and
if it completes its Burst time, then the CPU will be ready for the next process. 3. If a process
completes the 4 unit and still has remaining burst time, then its priority gets reduced and will be
shifted to Queue 2. 4. Above steps 2 and 3 are true for Queue 2, however, must use a time slice
of 8 instead of 4. If a process has still remaining burst time after executing for 8 unit, it will be
shifted to Queue 3. 5. In the last queue, processes are scheduled in FCFS. 6. A process in
lower priority can be only executed when higher priority queues are empty. 7. A process running
in the lower priority queue is interrupted by a process arriving in the higher priority queue.