OS-UNIT-II

____________________________________________
(Process and CPU Scheduling - Process concepts and scheduling, Operations on processes,
Cooperating Processes, Threads, and Interposes Communication, Scheduling Criteria, Scheduling
Algorithms, Multiple -Processor Scheduling. System call interface for process management-fork, exit,
wait, waitpid, exec)

What is Process?
• A process can be thought of as a program in execution, a process will need certain resources—
such as CPU time, memory, files, and I/O devices —to accomplish its task.
• These resources are allocated to the process either when it is created or while it is executing.
• A process is the unit of work in most systems. Systems consist of a collection of processes:
Operating-system processes execute system code, and user processes execute user code. All
these processes may execute concurrently
• Process memory is divided into four sections
o The text section comprises the compiled program code, read in from non-volatile
storage when the program is launched.
o The data section stores global and static variables, allocated and initialized prior to
executing main.
o The heap is used for dynamic memory allocation, and is managed via calls to new,
delete, malloc, free, etc.
o The stack is used for local variables. Space on the stack is reserved for local variables
when they are declared, and the space is freed up when the variables go out of scope.
The stack is also used for function return values.

Fig: Process Memory

1
Process States
The state of a process is defined in part by the current activity of that process. As a process executes, it
changes state.Each process may be in one of the following states:
• New: The process is being created.
• Ready: The process is waiting to be assigned to a processor.
• Running: Instructions are being executed.
• Waiting: The process is waiting for some event to occur
• Terminated: The process has finished execution.

Fig: Process States

Process Control Block (PCB)

Each process is represented in the operating system by a process control block (PCB)—also called a
task control block(TCB). The PCB simply serves as the repository for any information related to a
process.

Fig: Process Control Block

PCB contains many pieces of information associated with a specific process, including these:
1. Process state
2. Program counter
3. CPU registers
4. CPU-scheduling information
5. Memory-management information
2
 6. Accounting information
7. I/O status information
o Process state. The state may be new, ready, running, waiting, halted, and so on.
o Program counter. The counter indicates the address of the next instruction to be executed for
this process.
o CPU registers. The registers vary in number and type, depending on the computer architecture.
They include accumulators, index registers, stack pointers, and general-purpose registers, plus
any condition-code information.
o CPU-scheduling information. This information includes a process priority, pointers to
scheduling queues, and any other scheduling parameters.
o Memory-management information. This information may include such information as the
value of the base and limit registers, the page tables, or the segment tables etc.,
o Accounting information. This information includes the amount of CPU and real time used,
time limits, account numbers, job or process numbers, and so on.
o I/O status information. This information includes the list of I/O devices allocated to the
process, a list of open files, and so on.

Difference between Process and Program

Scheduling Queues
• As processes enter the system, they are put into a “job queue”, which consists of all processes
in the system.
• The processes that are residing in main memory and are ready and waiting to execute are kept
on a list called the “ready queue”. This queue is generally stored as a linked list.
• The list of processes waiting for a particular I/O device is called a “device queue”.
• A ready-queue header contains pointers to the first and final PCBs in the list.
• Each PCB includes a pointer field that points to the next PCB in the ready queue.

3
 Fig: Snapshot of Ready Queue and Other Queues

• The system also includes other queues. When a process is allocated the CPU, it executes for a
while and eventually quits, is interrupted, or waits for the occurrence of a particular event,
such as the completion of an I/O request.

Queueing Diagram
• A common representation of process scheduling is a queueing diagram where, each
rectangular box represents a queue. Two types of queues are present: the ready queue and a set
of device queues.
• The circles represent the resources that serve the queues, and the arrows indicate the flow of
processes in the system.
• A new process is initially put in the ready queue. It waits there until it is selected for execution,
or is dispatched.
• Once the process is allocated the CPU and is executing, one of several events could occur:
 The process could issue an I/O request and then be placed in an I/O queue.
 The process could create a new sub-process and wait for the sub-process's termination.
 The process could be removed forcibly from the CPU, as a result of an interrupt, and be
put back in the ready queue.
• In the first two cases, the process eventually switches from the waiting state to the ready state
and is then put back in the ready queue.
• A process continues this cycle until it terminates, at which time it is removed from all queues
and has its PCB and resources deallocated

Fig: Queuing Diagram

4
Process Schedulers
A process migrates among the various scheduling queues throughout its lifetime. The operating
system must select processes from these queues in some fashion. The selection process is carried out
by the appropriate scheduler.
The Schedulers are:
1. The long-term scheduler, or job scheduler
2. The short-term scheduler, or CPU scheduler
3. The medium-term scheduling
The primary distinction between these schedulers lies in frequency of execution.
The Short-term scheduler:The short-term scheduler, or CPU scheduler, selects from among the
processes that are ready to execute and allocates the CPU to one of them.
 The short-term scheduler must select a new process for the CPU frequently.
 A process may execute for only a few milliseconds before waiting for an I/O request. Often,
the short-term scheduler executes at least once every 100 milliseconds. Because of the short
time between executions, the short-term scheduler must be fast. All CPU scheduling
algorithms are type of short-term scheduler.
The long-term scheduler: The long-term scheduler, or job scheduler, selects processes from this pool
and loads them into memory for execution.The long-term scheduler executes much less frequently;
minutes may separate the creation of one new process and the next.The long-term scheduler controls
the degree of multi-programming. If the degree of multiprogramming is stable, then the average rate
of process creation must be equal to the average departure rate of processes leaving the system.
• Thus, the long-term scheduler may need to be invoked only when a process leaves the system.
Because of the longer interval between executions, the long-term scheduler can afford to take
more time to decide which process should be selected for execution.
• It is important that the long-term scheduler make a careful selection.
• In general, most processes can be described as either L/O bound or CPU bound. An I/O-bound
process is one that spends more of its time doing I/O than it spends doing computations. A
CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time
doing computations.
• It is important that the long-term scheduler select a good process mix of I/O-bound and CPU-
bound processes. The system with the best performance will thus have a combination of CPU-
bound and I/O-bound processes.
This medium-term scheduler: The key idea behind a medium-term scheduler is that sometimes it
can be advantageous to remove processes from memory and thus reduce the degree of
multiprogramming. Later, the process can be reintroduced into memory, and its execution can be
continued where it left off. This scheme is called swapping.
• The process is swapped out, and is later swapped in, by the medium-term scheduler.
• Swapping may be necessary to improve the process mix or because a change in memory
requirements has overcommitted available memory, requiring memory to be freed up.

5
 Fig: Medium Term Scheduler

Context Switch
Interrupts cause the operating system to change a CPU from one process to another process. When an
interrupt occurs, the system needs to save the current context of the process on the CPU so that it can
restore that context when it resumingit.
• Switching the CPU to another process requires performing a state save of the current process
and a state restore of a different process. This task is known as a context switch.

Fig: Context Switch

• When a context switch occurs, the kernel saves the context of the old process in its PCB and
loads the saved context of the new process scheduled to run.
• Context-switch time is pure overhead, because the system does no useful work while
switching.
• Context time speed varies from machine to machine, depending on the hardware support they
are

Operations on Processes
The processes in most systems can execute concurrently, and they may be created and deleted
dynamically, and the mechanism provided for this dynamic creation and deletion are:
 Process creation and
 Process termination.

6
Process Creation:
• A process may create several new processes, via a create-process system call, during the
course of execution.
• The creating process is called a parent process, and the new processes are called the children
of that process.
• Each of these new processes may in turn create other processes, forming a tree of processes.
• Most operating systems identify processes according to a unique process identifier (or pid),
which is typically an integer number.
• In general, a process will need certain resources to accomplish its task. When a process creates
a sub-process, that sub-process may be able to obtain its resources directly from the operating
system, or it may be constrained to a subset of the resources of the parent process.
• The parent may have to partition its resources among its children, or it may be able to share
some resources among several of its children.
• Restricting a child process to a subset of the parent's resources prevents any process from
overloading the system by creating too many sub-processes.

Fig:Process Creation-A tree of processes on a typical Solaris system

When a process creates a new process, two possibilities exist in terms of execution:
1. The parent continues to execute concurrently with its children.
2. The parent waits until some or all of its children have terminated.
There are also two possibilities in terms of the address space of the new process:
1. The child process is a duplicate of the parent process (it has the same program and data as the
parent).

7
 2. The child process has a new program loaded into it.
Process Termination:
• A process terminates when it finishes executing its final statement and asks the operating
system to delete it by using the exit () system call.
• At that point, the process may return a status value (typically an integer) to its parent process
(via the wait() system call).
• All the resources of the process—including physical and virtual memory, open files, and I/O
buffers—are deallocated by the operating system.
• Termination can occur in other circumstances as well. A process can cause the termination of
another process via an appropriate system call .
• Usually, such a system call can be invoked only by the parent of the process that is to be
terminated. Otherwise, users could arbitrarily kill each other's jobs.
• A parent may terminate the execution of one of its children for a variety of reasons, such as
these:
 The child has exceeded its usage of some of the resources that it has been allocated.
 The task assigned to the child is no longer required.
 The parent is exiting, and the operating system does not allow a child to continue
• If its parent terminates. Some systems, including VMS, do not allow a child to exist if its
parent has terminated.
• In such systems, if a process terminates (either normally or abnormally), then all its children
must also be terminated. This phenomenon, referred to as “cascading termination”, is
normally initiated by the operating system.

Cooperating Processes vs Independent Process

A process is cooperating if it can affect or be affected by the other processes executing in the system.
Clearly, any process that shares data with other processes is a cooperating process.Cooperating
processes require an inter-process communication (IPC) mechanism that will allow them to exchange
data and information.
Independent Process: A process is independent if it cannot affect or be affected by the other
processes executing in the system. Any process that does not share data with any other process is
independent.
Inter-Process Communication
Inter-process communication (IPC) is a mechanism that allows processes to communicate with each
other and synchronize their actions. The communication between these processes can be seen as a
method of co-operation between them.
There are several reasons for providing IPC are.
• Information sharing. Since several users may be interested in the same piece of information, we
must provide an environment to allow concurrent access to such information.

8
• Computation speedup. If we want a particular task to run faster, we must break it into subtasks,
each of which will be executing in parallel with the others.
• Modularity. We may want to construct the system in a modular fashion, dividing the system
functions into separate processes or threads.
• Convenience. Even an individual user may work on many tasks at the same time. For instance, a
user may be editing, printing, and compiling in parallel.
Processes can communicate with each other through both:
1. Shared Memory and
2. Message passing.

Shared Memory
• Inter-process communication using shared memory requires communicating processes to
establish a region of shared memory. They can then exchange information by reading and
writing data in the shared areas.
• The form of the data and the location are determined by these processes, and are not under the
operating system's control. The processes are also responsible for ensuring that they are not
writing to the same location simultaneously.
• Producer-consumer problem, which is a common paradigm for cooperating processes. A
producer process produces information that is consumed by a consumer process.
• We generally think of a server as a producer and a client as a consumer a web server produces
HTML files and images, which are consumed by the client web browser requesting the
resource.
• One solution to the producer-consumer problem uses shared memory.
Producer Consumer Problem Using Shared Memory

9
 Fig: Producer Consumer Problem

• A buffer of items that can be filled by the producer and emptied by the consumer. This buffer
will reside in a region of memory that is shared by the producer and consumer processes.
• A producer can produce one item while the consumer is consuming another item. The
producer and consumer must be synchronized, so that the consumer does not try to consume an
item that has not yet been produced.
• Two types of buffers can be used. The unbounded buffer places no practical limit on the size
of the buffer. The consumer may have to wait for new items, but the producer can always
produce new items.
• The bounded buffer assumes a fixed buffer size. In this case, the consumer must wait if the
buffer is empty, and the producer must wait if the buffer is full. The following variables reside
in a region of memory shared by the producer and consumer processes:

• The shared buffer is implemented as a circular array with two logical pointers: in and out. The
variable in points to the next free position in the buffer; out points to the first full position in
the buffer. The buffer is empty when in == out; the buffer is full when ((in + 1) %
BUFFERSIZE) == out.
Message-Passing Systems
• Message passing provides a mechanism to allow processes to communicate and to synchronize
their actions without sharing the same address space and is particularly useful in a distributed
environment.
• A message-passing facility provides at least two operations: send (message) and receive
(message).
• Messages can be sent in fixed size or variable size.
o If only fixed-sized messages can be sent, the system-level implementation is
straightforward. This restriction, however, makes the task of programming more difficult.
o Conversely, variable-sized messages require a more complex system-level implementation,
but the programming task becomes simpler.
• If processes P and Q want to communicate, they must send messages to and receive messages
from each other; a communication link must exist between them.

10
 • This link can be implemented in a variety of ways. Here are several methods for logically
implementing a link and the send()/receive() operations:
 Direct or indirect communication
 Synchronous or asynchronous communication
 Automatic or explicit buffering
Issues with Logical Link Implementation
 Naming,
 Synchronization and

 Buffering
Naming: Processes that want to communicate must have a way to refer to each other. They can use
either direct or indirect communication.
• Under direct communication, each process that wants to communicate must explicitly name
the recipient or sender of the communication.
• In this scheme, the send() and receive() primitives are defined as:
send(P, message)—Send a message to process P.
receive (Q, message)—Receive a message from process Q.
A communication link in this scheme has the following properties:
• A link is established automatically between every pair of processes that want to communicate. The
processes need to know only each other's identity to communicate.
• A link is associated with exactly two processes.Between each pair of processes, there exists exactly
one link.
Direct Communication scheme exhibits
• Symmetry in addressing: both the sender process and the receiver process must name the
other to communicate.
• Asymmetry in addressing: Here, only the sender names the recipient; the recipient is not
required to name the sender. In this scheme, the send() and receive () primitives are defined as
follows:
 send(P, message)—Send a message to process P.
 receive(id, message)—Receive a message from any process;
• The disadvantage in both of these schemes are Changing the identifier of a process may
necessitate examining all other process definitions. All references to the old identifier must be
found, so that they can be modified to the new identifier.
• In general, any such hard-coding techniques, where identifiers must be explicitly stated, are
less desirable than techniques involving indirection.
Indirect communication
• With indirect communication, the messages are sent to and received from mailboxes, or ports.

11
 • A mailbox can be viewed abstractly as an object into which messages can be placed by
processes and from which messages can be removed.
• Each mailbox has a unique identification. In this scheme, a process can communicate with
some other process via a number of different mailboxes. Two processes can communicate only
if the processes have a shared mailbox.
The send() and receive () primitives are defined as follows:
 send(A, message)—Send a message to mailbox A.
 receive(A, message)—Receive a message from mailbox A.
Indirect Communication scheme, a communication link has the following properties:
• A link is established between a pair of processes only if both members of the pair have a shared
mailbox.
• A link may be associated with more than two processes.
• Between each pair of communicating processes, there may be a number of different links, with each
link corresponding to one mailbox.
• When we have common mail box for 3 processes and one process send message to the mailbox
then conflict occur in deciding the receiver , The Possible solutions are as follow:
 Allow a link to be associated with two processes at most.
 Allow at most one process at a time to execute a receive () operation.
 Allow the system to select arbitrarily which process will receive the message, the system also
may define an algorithm for selecting which process will receive the message
• A mailbox may be owned either by a process or by the operating system.
• If the mailbox is owned by a process, then we distinguish between the owner and the user. Owner
can receive the message and user could send the message.
• When a process that owns a mailbox terminates, the mailbox disappears. Any process that
subsequently sends a message to this mailbox must be notified that the mailbox no longer exists.
• If a mailbox that is owned by the operating system has an existence of its own. It is independent
and is not attached to any particular process.
• The operating system then must provide a mechanism that allows a process to do the following:
 Create a new mailbox.
 Send and receive messages through the mailbox.
 Delete a mailbox.
• The process that creates a new mailbox is that mailbox's owner by default. Initially, the owner is
the only process that can receive messages through this mailbox.
• However, the ownership and receiving privilege may be passed to other processes through
appropriate system calls.
Synchronization
Message passing may be either blocking or non-blocking— also known as synchronous and
asynchronous.

12
• Blocking send. The sending process is blocked until the message is received by the receiving
process or by the mailbox.
•Non-blocking send. The sending process sends the message and resumes operation.
• Blocking receive. The receiver blocks until a message is available.
• Non-blocking receive. The receiver retrieves either a valid message or a null.
Buffering
Whether communication is direct or indirect, messages exchanged by communicating processes reside
in a temporary queue. Basically, such queues can be implemented in three ways:
1. Zero capacity
2. Bounded capacity
3. Unbounded capacity
The zero-capacity case is sometimes referred to as a message system with no buffering; the other
cases are referred to as systems with automatic buffering.
• Zero capacity. The queue has a maximum length of zero; thus, the link cannot have any
messages waiting in it. In this case, the sender must block until the recipient receives the
message.
• Bounded capacity. The queue has finite length n; thus, at most n messages can reside in it. If
the queue is not full when a new message is sent, the message is placed in the queue, and the
sender can continue execution without waiting. The links capacity is finite, if the link is full,
the sender must block until space is available in the queue.
• Unbounded capacity. The queues length is potentially infinite; thus, any number of messages
can wait in it. The sender never blocks.
Examples of I PC Systems
• POSIX API uses shared memory
• Message passing technique was used in the Mach operating system
• Windows XP, uses shared memory as a mechanism for providing certain types of message
passing.

Threads
• A thread is a lightweight sub-process. It is a separate path of execution because each thread runs in
a different stack frame.
• A process may contain multiple threads. Threads share the process resources, but still, they execute
independently.

13
Why 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.
• MS Word uses multiple threads: one thread to format the text, another thread to process inputs,
etc.
Process ‘VS’ Thread

Benefits of multithreaded programming

The benefits of multithreaded programming can be broken down into four major categories:
1. Responsiveness. Multithreading an interactive application may allow a program to continue
running even if part of it is blocked or is performing a lengthy operation, thereby increasing
responsiveness to the user.
2. Resource sharing. By default, threads share the memory and the resources of the process to which
they belong. The benefit of sharing code and data is that it allows an application to have several
different threads of activity within the same address space.
3. Economy. Allocating memory and resources for process creation is costly. Because threads share
resources of the process to which they belong, it is more economical to create and context-switch
threads

14
4. Utilization of multiprocessor architectures. The benefits of multithreading can be greatly
increased in a multiprocessor architecture, where threads may be running in parallel on different
processors. A single threaded process can only run on one CPU, no matter how many are available.
Multithreading on a multi-CPU machine increases concurrency.

Types of Threads
There are two types of threads, which are:
1. User Level Thread: As the name suggests, the user-level threads are only managed by users, and
the kernel does not have its information. These are faster, easy to create and manage. The kernel
takes all these threads as a single process and handles them as one process only. The user-level
threads are implemented by user-level libraries, not by the system calls.
2. Kernel-Level Thread: The kernel-level threads are handled by the Operating system and managed
by its kernel. These threads are slower than user-level threads because context information is
managed by the kernel. To create and implement a kernel-level thread, we need to make a system
call.

Multithreading Models
Based on the relationship between user threads and kernel threads, we have Three
Multithreadingmodels:
• Many to many relationship.
• Many to one relationship.
• One to one relationship.

Many-to-One Model
• The many-to-one model maps many user-level threads to one kernel thread.
• Thread management is done by the thread library in user space, so it is efficient; but the entire
process will block if a thread makes a blocking system call.
• Also, because only one thread can access the kernel at a time, multiple threads are unable to
run in parallel on multiprocessors.
• Green threads—a thread library available for Solaris—uses this model, as does GNU Portable
Threads.

15
One-to-One Model
• The one-to-one model maps each user thread to a kernel thread.
• It provides more concurrency than the many-to-one model by allowing another thread to run
when a thread makes a blocking system call; it also allows multiple threads to run in parallel
on multiprocessors.
• The only drawback to this model is that creating a user thread requires creating the
corresponding kernel thread.

• Because the overhead of creating kernel threads can burden the performance of an application,
most implementations of this model restrict the number of threads supported by the system.
• Linux, along with the family of Windows operating systems—including Windows 95, 98, NT,
2000, and XP— implement the one-to-one model.

Many-to-Many Model
• The many-to-many model multiplexes many user-level threads to a smaller or equal number of
kernel threads.
• The number of kernel threads may be specific to either a particular application or a particular
machine.
• Whereas the many-to-one model allows the developer to create as many user threads as she
wishes, true concurrency is not gained because the kernel can schedule only one thread at a
time.
• The one-to-one model allows for greater concurrency, but the developer has to be careful not
to create too many threads within an application.

16
 • The many-to-many model suffers from neither of these shortcomings: Developers can create as
many user threads as necessary, and the corresponding kernel threads can run in parallel on a
multiprocessor. Also, when a thread performs a blocking system call, the kernel can schedule
another thread for execution.
• One popular variation on the many-to-many model still multiplexes many user-level threads to
a smaller or equal number of kernel threads but also allows a user-level thread to be bound to a
kernel thread.
• This variation, sometimes referred to as the two-level model , is supported by operating
systems such as IRIX, HP-UX, and Tru64 UNIX.
• The Solaris operating system supported the two-level model in versions older than Solaris 9.
However, beginning with Solaris 9, this system uses the one-to-one model.

CPU Scheduling
In multi-programming environment, multiple processes will be competing for the assignment of
CPU.Whenever the CPU becomes idle, the operating system must select one of the processes in the
ready queue to be executed. The selection process is carried out by the short-term scheduler (or CPU
scheduler). The scheduler selects a process from the processes in memory that are ready to execute
and allocates the CPU to that process.
Preemptive ‘VS’ Non-preemptive
Non-preemptive:Under nonpreemptive scheduling, once the CPU has been allocated to a process, the
process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting
state.
• This type of scheduling is rigid. Non-preemptive scheduling has no overheads of scheduling
the processes. There is no cost associated with non-preemptive scheduling.
• In non-preemptive scheduling, if the process which has long burst time is executing, then the
other method which has less burst time may starve.
• Example : FIFO, NON-Preemtive SJF
Preemtive Scheduling: In Preemtive Scheduling, we can interrupt the process in between of
execution. In preemptive scheduling, the processes are allocated for a short period.
• This type of schedule is flexible as each process in the ready queue gets some time to run
CPU.
• Preemptive scheduling has overheads of scheduling the processes. There is a cost associated
with the preemptive scheduling.
• In preemptive scheduling, if a process which has high priority arrives in the ready queue, then
the process which has low priority may starve.
• Example: Round Robin, Priority and SRTF etc.

Dispatcher
Here dispatcher is the module that gives control of the CPU to the process selected by the short-term
scheduler.This function involves the following:
17
  Switching context
 Switching to user mode
 Jumping to the proper location in the user program to restart that program
• The dispatcher should be as fast as possible, since it is invoked during every process switch.
• The time it takes for the dispatcher to stop one process and start another running is known as the
“dispatch latency”

Scheduling Criteria
Different CPU scheduling algorithms have different properties, in choosing which algorithm to use in
a particular situation, we must consider the properties of the various algorithms. Many criteria have
been suggested for comparing CPU scheduling algorithms.
The criteria include the following:
1. CPU utilization
2. Throughput
3. Turnaround time
4. Waiting time

5. Response time
• CPU utilization. CPU utilization refers to a computer's usage of processing resources, or the
amount of work handled by a CPU. Actual CPU utilization varies depending on the amount and
type of managed computing tasks. CPU utilization can range from 0 to 100 percent.

• Throughput. The number of processes that are completed per time unit, called throughput. For
long processes, this rate may be one process per hour; for short transactions, it may be 10
processes per second.

• Turnaround time. The interval from the time of submission of a process to the time of
completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to
get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.

• Waiting time. Waiting time is the sum of the periods spent waiting in the ready queue.

• Response time. It’s the Time at which process first gets the CPU. It’s also measured as the
time from the submission of a request until the first response is produced. This measure, called
response time.

Burst Time
• Burst Time- Burst time is the amount of time required by a process for executing on CPU. It
is also called as execution time or running time.
• Every process in a computer system requires some amount of time for its execution. This time
is both the CPU time and the I/O time.
• The CPU time is the time taken by CPU to execute the process. While the I/O time is the time
taken by the process to perform some I/O operation.

18
 • In general, we ignore the I/O time and we consider only the CPU time for a process. So, Burst
time is the total time taken by the process for its execution on the CPU.
Arrival time
• Arrival time is the time when a process enters into the ready state and is ready for its
execution. Here in the above example, the arrival time of all the 3 processes are 0 ms, 1 ms,
and 2 ms respectively.
Exit time
• Exit time is the time when a process completes its execution and exit from the system.

Fig: Burst time and Arrival Time

Gantt chart
A chart in which a series of horizontal lines shows the amount of work done . A Gantt chart is
a graphical depiction of a process schedule. It's is a type of bar chart that shows the start and finish
times of different Processes.Example Gantt Chart for the 3 Processes .

‘CPU’ Scheduling Algorithms

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be
allocated the CPU. There are many different CPU scheduling algorithms.
o First-Come, First-Served Scheduling
o Shortest-Job-First Scheduling
o Priority Scheduling
o Round-Robin Scheduling
o Multilevel Queue Scheduling
o Multilevel Feedback-Queue Scheduling

First-Come, First-Served Scheduling

19
 • The simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling
algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first.
The implementation of the FCFS policy is easily managed with a FIFO queue.
• When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the
CPU is free, it is allocated to the process at the head of the queue. The running process is then
removed from the queue.
• The code for FCFS scheduling is simple to write and understand. The average waiting time under
the FCFS policy, however, is often quite long.
• Consider the following set of processes that arrive at time 0, with the length of the CPU burst
given in milliseconds:

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

• The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2, and 27
milliseconds for process P3.
• Thus, the average waiting time is (0 + 24 + 27)/3 = 17 milliseconds.

Problems with FCFS Scheduling: Below we have a few shortcomings or problems with the FCFS
scheduling algorithm:

1. It is Non Pre-emptive algorithm, which means the process priority doesn't matter.

2. Not optimal Average Waiting Time.

3. Resources utilization in parallel is not possible, which leads to Convoy Effect, and hence poor
resource (CPU, I/O etc) utilization.

What is Convoy Effect?

Convoy Effect is a situation where many processes, who need to use a resource for short time are
blocked by one process holding that resource for a long time. This essentially leads to poort utilization
of resources and hence poor performance.

Shortest-Job-First Scheduling (SJF)

20
  Shortest-job-first (SJF) scheduling algorithm, associates with each process the length of the
process's next CPU burst. When the CPU is available, it is assigned to the process that has the
smallest next CPU burst.
 If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie.
 SJF can be Non-Pre-emptive or Pre-emptive. A non-pre-emptive SJF algorithm will allow the
currently running process to finish its CPU burst.
As an example of Non-Pre-emptive SJF scheduling, consider the following set of processes, with the
length of the CPU burst given in milliseconds:

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

PID AT BT CT TAT WT
P1 0 6 9 9 3
P2 0 8 24 24 16
P3 0 7 16 16 9
P4 0 3 3 3 0

The waiting time is 3 milliseconds for process P1, 16 milliseconds for process P2, 9 milliseconds for
process P3, and 0 milliseconds for process P4. Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7
milliseconds. By comparison, if we were using the FCFS scheduling scheme, the average waiting time
would be 10.25 milliseconds. The SJF scheduling algorithm is provably optimal, in that it gives the
minimum average waiting time for a given set of processes. The real difficulty with the SJF algorithm
is knowing the length of the next CPU request. Although the SJF algorithm is optimal, it cannot be
implemented at the level of short-term CPU scheduling. There is no way to know the length of the
next CPU burst.
Pre-emptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling. As an
example, consider the following four processes, with the length of the CPU burst given in
milliseconds:

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

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

Priority Scheduling
The SJF algorithm is a special case of the general priority scheduling algorithm. A priority is
associated with each process, and the CPU is allocated to the process with the highest priority. Equal-
priority processes are scheduled in FCFS order. An SJF algorithm is simply a priority algorithm where
the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower
the priority, and vice versa.
Priorities are generally indicated by some fixed range of numbers, such as 0 to 7 or 0 to 4,095.
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. In this text, we
assume that low numbers represent high priority. As an example, consider the following set of
processes, assumed to have arrived at time 0, in the order Pi, P2, • • -, P5, with the length of the CPU
burst given in milliseconds

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

The average waiting time is 8.2 milliseconds. Priorities can be defined either internally or externally.
Internally defined priorities use some measurable quantity or quantities to compute the priority of a
process. For example, time limits, memory requirements, the number of open files, and the ratio of
average I/O burst to average CPU burst have been used in computing priorities. External priorities are
set by criteria outside the operating system, such as the importance of the process, the type and
amount of funds being paid for computer use, the department sponsoring the work, and other, often
political, factors.

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

Round-Robin Scheduling
The round-robin (RR) scheduling algorithm is designed especially for timesharing systems. It is
similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of
time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100
milliseconds. The ready queue is treated as a circular queue. The CPU scheduler goes around the
ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

To implement RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes
are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready
queue, sets a timer to interrupt after 1 time quantum, and dispatches the process. One of two things
will then happen. 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 is longer than 1 time
quantum, the timer will go off and will cause an interrupt to the operating system. A context switch
will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will
then select the next process in the ready queue. The average waiting time under the RR policy is often
long. Consider the following set of processes that arrive at time 0, with the length of the CPU burst
given in milliseconds:

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

The average waiting time is 17/3 = 5.66 milliseconds. In the RR scheduling algorithm, no process is
allocated the CPU for more than 1 time quantum in a row. If a process's CPU burst exceeds 1 time
quantum, that process is preempted and is put back in the ready queue. The RR scheduling algorithm
is thus preemptive. The performance of the RR algorithm depends heavily on the size of the time
quantum. At one extreme, if the time quantum is extremely large, the RR policy is the same as the
FCFS policy If the time quantum is extremely small (say, 1 millisecond), the RR approach is called
processor sharing and, in software, we need also to consider the effect of context switching on the
performance of RR scheduling.

Multilevel Queue Scheduling Algorithm

Another class of scheduling algorithms has been created for situations in which processes are easily
classified into different groups.For example, A common division is made between foreground
processes and background processes. These two types of processes have different response-time
requirements, and so might have different scheduling needs. In addition, foreground processes may
have priority over background processes.

 A multi-level queue scheduling algorithm partitions the ready queue into several separate
queues.

 The processes are permanently assigned to one queue, generally based on some property of the
process, such as memory size, process priority, or process type. Each queue has its own
scheduling algorithm.

 For example, separate queues might be used for foreground and background processes. The
foreground queue might be scheduled by the Round Robin algorithm, while the background
queue is scheduled by an FCFS algorithm.

 In addition, there must be scheduling among the queues, which is commonly implemented as
fixed-priority preemptive scheduling. For example, The foreground queue may have absolute
priority over the background queue.

Let us consider an example of a multilevel queue-scheduling algorithm with five queues:

24
 1. System Processes

2. Interactive Processes

3. Interactive Editing Processes

4. Batch Processes

5. Student Processes

 Each queue has absolute priority over lower-priority queues. No process in the batch queue,
for example, could run unless the queues for system processes, interactive processes, and
interactive editing processes were all empty.

 If an interactive editing process entered the ready queue while a batch process was running, the
batch process will be preempted.

Fig: multi-level queue scheduling

In this case, if there are no processes on the higher priority queue only then the processes on the low
priority queues will run. For Example: Once processes on the system queue, the Interactive queue,
and Interactive editing queue become empty, only then the processes on the batch queue will run.

The Description of the processes in the above diagram is as follows:

 System Process The Operating system itself has its own process to run and is termed as
System Process.

 Interactive Process the Interactive Process is a process in which there should be the same
kind of interaction.

 Batch Processes Batch processing is basically a technique in the Operating system that
collects the programs and data together in the form of the batch before the processing starts.

 Student Process The system process always gets the highest priority while the student
processes always get the lowest priority.

25
In an operating system, there are many processes, in order to obtain the result we cannot put all
processes in a queue; thus this process is solved by Multilevel queue scheduling.

Advantages of Multilevel Queue Scheduling

With the help of this scheduling we can apply various kind of scheduling for different kind of
processes:

 For System Processes: First Come First Serve(FCFS) Scheduling.

 For Interactive Processes: Shortest Job First (SJF) Scheduling.
 For Batch Processes: Round Robin(RR) Scheduling
 For Student Processes: Priority Scheduling

Disadvantages of Multilevel Queue Scheduling

 The main disadvantage of Multilevel Queue Scheduling is the problem of starvation for lower-
level processes.

 Due to starvation lower-level processes either never execute or have to wait for a long amount of
time because of lower priority or higher priority process taking a large amount of time.

 Processes are permanently assigned to a queue on entry to the system. Processes do not move
between queues.

 This setup has the advantage of low scheduling overhead, but the disadvantage of being
inflexible.

Multilevel Feedback Queue Scheduling

Multilevel feedback queue scheduling, however, allows a process to move between queues. The idea
is to separate processes with different CPU-burst characteristics. If a process uses too much CPU time,
it will be moved to a lower-priority queue. Similarly, a process that waits too long in a lower-priority
queue may be moved to a higher-priority queue. This form of aging prevents starvation.

In general, a multilevel feedback queue scheduler is defined by the following parameters:

 The number of queues.

 The scheduling algorithm for each queue.

 The method used to determine when to upgrade a process to a higher-priority queue.

 The method used to determine when to demote a process to a lower-priority queue.

 The method used to determine which queue a process will enter when that process needs
service.

26
 Fig: Multilevel feedback queue scheduling
The definition of a multilevel feedback queue scheduler makes it the most general CPU-scheduling
algorithm. It can be configured to match a specific system under design. Unfortunately, it also requires
some means of selecting values for all the parameters to define the best scheduler. Although a
multilevel feedback queue is the most general scheme, it is also the most complex.

A multilevel feedback queue uses two basic rules:

1. A new process gets placed in the highest priority queue.

2. If a process does not finish its quantum (that is, it blocks on I/O) then it will stay at the same
priority level (round robin) otherwise it moves to the next lower priority level

With this approach, a process with long CPU bursts will use its entire time slice, get preempted and
get placed in a lower-priority queue. A highly interactive process will not use up its quantum and will
remain at a high priority level. Although not strictly necessary for the algorithm, each successive
lower-priority queue may be given a longer quantum. This allows a process to remain in the queue
that corresponds to its longest CPU burst.

Advantages of MFQS

 This is a flexible Scheduling Algorithm

 This scheduling algorithm allows different processes to move between different queues.

 In this algorithm, A process that waits too long in a lower priority queue may be moved to a
higher priority queue which helps in preventing starvation.

Disadvantages of MFQS

 This algorithm is too complex.

 As processes are moving around different queues which leads to the production of more CPU
overheads.

 In order to select the best scheduler this algorithm requires some other means to select the
values

Multiple-Processor Scheduling
Our discussions thus far assumed an environment where a single process gets to run at a time. Other
ready processes wait until the scheduler switches their context in and gives them a chance to run. If
multiple CPUs are available, load sharing becomes possible. With multiple CPUs, more than one

27
thread of execution can be scheduled at a time. The scheduler simply allows more than one process to
be in the running state at one time.

Approaches to Multiple-Processor Scheduling

Two Approaches for Multiple-Processor Scheduling are:

 Asymmetric multiprocessing(AMP)
 Symmetric multiprocessing(SMP)

Asymmetric multiprocessing: One approach to CPU scheduling in a multiprocessor system has all
scheduling decisions, I/O processing, and other system activities handled by a single processor-the
“master server”. The other processors execute only user code. This asymmetric multiprocessing is
simple because only one processor accesses the system data structures, reducing the need for data
sharing.
Symmetric multiprocessing: A second approach uses symmetric multiprocessing (SMP), where each
processor is self-scheduling. All processes may be in a common ready queue, or each processor may
have its own private queue of ready processes. Each processor has access to the same memory and
devices. If we have multiple processors trying to access and update a common data structure, the
scheduler must be programmed carefully: We must ensure that two processors do not choose the same
process and that processes are not lost from the queue. Virtually all modern operating systems support
SMP, including Windows XP, Windows 2000, Solaris, Linux, and Mac as X.

Issues concerning SMP systems.

 Processor Affinity
 Load Balancing
 Symmetric Multithreading

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

Load Balancing: On SMP systems, it is important to keep the workload balanced among all
processors to fully utilize the benefits of having more than one processor. Otherwise, one or more
processors may sit idle while other processors have high workloads along with lists of processes
awaiting the CPU. Load balancing attempts to keep the workload evenly distributed across all
28
processors in an SMP system. It is important to note that load balancing is typically only necessary on
systems where each processor has its own private queue of eligible processes to execute. There are
two general approaches to load balancing: “push migration” and “pull migration”.

 With push migration, a specific task periodically checks the load on each processor and-if it
finds an imbalance-evenly distributes the load by moving (or pushing) processes from
overloaded to idle or less-busy processors.
 Pull migration occurs when an idle processor pulls a waiting task from a busy processor.
 Push and pull migration need not be mutually exclusive and are in fact often implemented in
parallel on load-balancing systems.
 For example, the Linux scheduler (described in Section 5.6.3) and the ULE scheduler available
for FreeBSD systems implement both techniques. Linux runs its load balancing algorithm
every 200 milliseconds (push migration) or whenever the run queue for a processor is empty
(pull migration).

Symmetric Multithreading: SMP systems allow several threads to run concurrently by providing
multiple physical processors. An alternative strategy is to provide multiple logical rather than
physical-processors. Such a strategy is known as symmetric multithreading (SMT); it has also been
termed hyperthreading technology on Intel processors.

The idea behind SMT is to create multiple logical processors on the same physical processor,
presenting a view of several logical processors to the operating system, even on a system with only a
single physical processor. Each logical processor has its own architecture state, which includes
general-purpose and machine-state registers. Furthermore, each logical processor is responsible for its
own interrupt handling, meaning that interrupts are delivered to-and handled by-logical processors
rather than physical ones. Otherwise, each logical processor shares the resources of its physical
processor, such as cache memory and buses. The Following Figure illustrates a typical SMT
architecture with two physical processors, each housing two logical processors.

From the operating system's perspective, four processors are available for work on this system.

System call interface for Process Management

29
System call provides the services of the operating system to the user programs via Application
Program Interface (API). It provides an interface between a process and operating system to allow
user-level processes to request services of the operating system. System calls are the only entry points
into the kernel system.
Process management uses certain system calls
 To create a new process – fork () is used.
 To run a new program - exec () is used.
 To make the process to wait - wait () is used.
 To terminate the process – exit () is used.
 To suspends execution of the current process- waitpid() is used.
 To find the unique process id – getpid () is used.
 To find the parent process id – getppid () is used.

fork(): In traditional Unix the only way to create a process is using the fork() system call.
fork(), System call is used to create a child process. The child is almost an identical clone of the
parent. After fork()both the parent and the child are executing the same program. fork() is a special
system call. You call it once, but the function returns twice: Once in the parent, and once in the child
process. fork() increases the number of processes in the system by one.

The “exec()” System Call: exec() loads programs into processes that already exist. In other words,
the exec()call replaces a current process’ image with a new one. The new image is either regular
executable binary file or a shell script. Upon success, exec()never returns to the caller. It replaces the
current process image, so it cannot return anything to the program that made the call. If it does return,
it means the call failed.

The “wait()” system call :

Forces the parent to suspend execution, i.e. wait for its children or a specific child to die (terminate).
When the child process dies, it returns an exit status to the operating system, which is then returned
to the waiting parent process. The parent process then resumes execution. A child process that dies
but is never waited on by its parent becomes a zombie process. Such a process continues to exist as
an entry in the system process table even though it is no longer an actively executing program.
The wait() causes the parent to wait for any child process. The waitpid() waits for the child with
specific PID. pid: pid of (child) process that the calling process waits for. status: a pointer to the
location where status information for the terminating process is to be stored. options: specifies
optional actions. The return value is: PID of the exited process, if no error (-1) if an error has
happened
The “exit()” system call : This function is used for normal process termination. The status of the
process is captured for future reference. exit() is a system call, It decrements the number of processes
in the system by one. This call gracefully terminates process execution. Gracefully means it does
clean up and release of resources, and puts the process into the zombie state.

30
By calling wait(), the parent cleans up all its zombie children. When the child process dies, an exit
status is returned to the operating system and a signal is sent to the parent process. The exit status can
then be retrieved by the parent process via the wait system call.
The process states
Zombie: has completed execution; still has an entry in the process table
Orphan: parent has finished or terminated while this process is still running
Daemon: runs as a background process, not under the direct control of an interactive user

waitpid(): suspends execution of current process until a child as specified by pid arguments has
exited or until a signal is delivered. waitpid suspends the calling process until a specified process
terminates. When the specified process ends, status information from the terminating process is stored
in the location pointed to by statusPtr and the calling process resumes execution. If the specified
process has already ended when the waitpid function is called and the system has status information,
the return from waitpid occurs immediately. A return from the waitpid function also occurs if a signal
is received and is not ignored.

**********************************************************************
Important Questions from Previous Papers:
1. What is a scheduler process? Explain its role(2M)
2. Describe the differences between short-term scheduler and long-term schedule(3M)
3. Explain various system calls for process(5M)
4. Following is the snapshot of a CPU Process CPU Burst Arrival Time
PID BT AT
P1 10 0
P2 29 1
P3 03 2
P4 07 3

31
Draw the Gantt chart and calculate the turnaround time and waiting time of the jobs for FCFS (First
Come First Served), SJF (Shortest Job First), SRTF (Shortest Remaining Time First) and RR (Round
Robin with time quantum 10) scheduling algorithms. [10M]
5. Following is the snapshot of a CPU .Draw the Gantt chart and calculate the turnaround time and
waiting time of the jobs for FCFS (First Come First Served), SJF (Shortest Job First), SRTF
(Shortest Remaining Time First) and RR (Round Robin with time quantum 15) scheduling
algorithms.(10M)

Process CPU Burst Arrival Time

P1 75 0
P2 40 10
P3 25 10
P4 20 80
P5 45 85

6. Explain process(5M)
7. What is preemptive Scheduling? How is it different from non-preemptive?(3M)
8. Explain FCFS, RR and SJF scheduling algorithm with illustrations.(10M)
9. Explain about multiple-processor scheduling and real time(10M)
10. How are processes managed in LINUX? (3M)
11. What resources are used when a thread is created? How do they differ from those used when a
process is created?(5M)
12. Construct the Gantt chart for a) Shortest job first b) Round Robin with q=3 c) Round robin with
q=4 d) shortest remaining time first scheduling algorithms for the following.(10M)

13. Explain various system calls for process management.(5M)

14. What is the difference between a process and a thread? (2M)

15. Explain in detail about process management.(5M)

16. What is process scheduling? Discuss about round-robin scheduling.(5M)

THE END

32
33