COURSE: OPERATING SYSTEMS

Topic Name: PROCESS MANAGEMENT AND SCHEDULING

UNIT: #2

Faculty Name: Dr G APPARAO

Gitam School of Computer Science Engineering

 MODULE 2
PROCESS MANAGEMENT AND SCHEDULING
Process Management:
Process concepts, process scheduling, Operations on
processes, inter- process communication

CPU Scheduling:
Scheduling-criteria, scheduling algorithms, Thread scheduling,
Multiple processor scheduling, algorithm evaluation,
Multithreaded programming, Multi-core Programming, Multi-
threading Models, Thread Libraries.

Gitam School of Computer Science Engineering

 Process Concept
➢ A process is a program in execution.
➢ The status of the current activity of a process is represented by the value of
the program counter and the contents of the processor’s registers.
➢ The memory layout of a process is typically divided into multiple sections.
➢ These sections include:
❑ Text section—the executable code
❑ Data section—global variables
❑ Heap section—memory that is dynamically allocated during program run
time
❑ Stack section—temporary data storage when invoking functions (such as
function parameters, return addresses, and local variables)

Gitam School of Computer Science Engineering

 Process Concept

Gitam School of Computer Science Engineering

Gitam School of Computer Science Engineering
 Process State
➢ As a 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. The process is being created.
❑Running. Instructions are being executed.
❑Waiting. The process is waiting for some event to occur (such as
an I/O completion or reception of a signal).
❑Ready. The process is waiting to be assigned to a processor.
❑Terminated. The process has finished execution.

Gitam School of Computer Science Engineering

Gitam School of Computer Science Engineering
 Process Control Block
➢ Each process is represented in the operating system by a process
control block (PCB)—also called a task control block.
➢ It contains many pieces of information associated with a specific
process,including these:
❑ Process state. The state may be new, ready, running, waiting,
halted, and so on.
❑ 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, and general-
purpose registers, plus any condition-code information.
Gitam School of Computer Science Engineering
 Process Control Block
➢ It contains many pieces of information associated with a specific
process,including these:
• Along with the program counter, this state information must be
saved when an interrupt occurs, to allow the process to be
continued correctly afterward when it is rescheduled to run.
❑ CPU-scheduling information. This information includes a
process priority, pointers to scheduling queues, and any other
scheduling parameters.
❑ Memory-management information. This information may
include such items as the value of the base and limit registers and
the page tables, or the segment tables, depending on the memory
system used by the operating system
•
Gitam School of Computer Science Engineering
 Process Control Block
➢ It contains many pieces of information associated with a specific
process,including these:
❑ Accounting information. This information includes the amount
of CPU and real time used, time limits, account numbers, job or
process numbers, and so on.
❑ 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.

Gitam School of Computer Science Engineering

Gitam School of Computer Science Engineering
 Threads
➢ A process is a program that performs a single thread of
execution.
➢ For example, when a process is running a word-processor
program, a single thread of instructions is being executed.
➢ Most modern operating systems have extended the process
concept to allow a process to have multiple threads of execution
and thus to perform more than one task at a time.
➢ This feature is especially beneficial on multicore systems, where
multiple threads can run in parallel.

Gitam School of Computer Science Engineering

 Process Scheduling
➢ The objective of multiprogramming is to have some process running at all
times so as to maximize CPU utilization.
➢ The objective of time sharing is to switch a CPU core among processes so
frequently that users can interact with each program while it is running.
➢ The process scheduler selects an available process (possibly from a set of
several available processes) for program execution on a core.
➢ Each CPU core can run one process at a time.
➢ For a system with a single CPU core, there will never be more than one
process running at a time, whereas a multicore system can run multiple
processes at one time.
➢ If there are more processes than cores, excess processes will have to wait
until a core is free and can be rescheduled.

Gitam School of Computer Science Engineering

 Process Scheduling
➢ The number of processes currently in memory is known as the
degree of multiprogramming.
➢ In general, most processes can be described as either I/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.

Gitam School of Computer Science Engineering

 Scheduling Queues

Gitam School of Computer Science Engineering

 Scheduling Queues
➢ As processes enter the system, they are put into a ready queue, where they
are ready and waiting to execute on a CPU’s core
➢ This queue is generally stored as a linked list; a ready-queue header contains
pointers to the first PCB in the list, and each PCB includes a pointer field
that points to the next PCB in the readyqueue.
➢ Processes that are waiting for a certain event to occur — such as completion
of I/O — are placed in a wait queue.
➢ A common representation of process scheduling is a queueing diagram.
➢ Two types of queues are present: the ready queue and a set of wait queues.
➢ The circles represent the resources that serve the queues,and the arrows
indicate the flow of processes in the system

Gitam School of Computer Science Engineering

 Scheduling Queues

Gitam School of Computer Science Engineering

 Scheduling Queues
➢ One of several events could occur:
❑A new process is initially put in the ready queue. It waits there
until it is selected for execution, or dispatched.
❑The process could issue an I/O request and then be placed in an
I/O wait queue.
❑The process could create a new child process and then be placed
in a wait queue while it awaits the child’s termination.
❑The process could be removed forcibly from the core, as a result
of an interrupt or having its time slice expire, and be put back in
the ready queue.

Gitam School of Computer Science Engineering

 CPU Scheduling
➢ The role of the CPU scheduler is to select from among the processes
that are in the ready queue and allocate a CPU core to one of them.
➢ The CPU scheduler must select a new process for the CPU frequently.
➢ Some operating systems have an intermediate form of scheduling,
known as swapping, whose key idea is that sometimes it can be
advantageous to remove a process from memory and thus reduce the
degree of multiprogramming.
➢ This scheme is known as swapping because a process can be “swapped
out” from memory to disk, where its current status is saved, and later
“swapped in” from disk back to memory, where its status is restored.

Gitam School of Computer Science Engineering

 Context Switch
➢ Switching the CPU core 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.
➢ 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-switch times are highly dependent on hardware support.

Gitam School of Computer Science Engineering

Gitam School of Computer Science Engineering
 Operations on Processes
➢ There are different situations in which a new process is created.
➢ There are different ways to create new process.
➢ A new process can be created at the time of initialization of operating
system or when system calls such as fork () are initiated by other processes.

➢ The process, which creates a new process using system calls, is called
parent process while the new process that is created is called child process.

➢ The child processes can create new processes using system calls.
➢ A new process can also create by an operating system based on the
request received from the user.
Gitam School of Computer Science Engineering
 Operations on Processes

Gitam School of Computer Science Engineering

 Operations on Processes
➢ Process termination is an operation in which a process is terminated after the
execution of its last instruction.
➢ This operation is used to terminate or end any process. When a process is
terminated, the resources that were being utilized by the process are released by the
operating system.
➢ When a child process terminates, it sends the status information back to the parent
process before terminating.
➢ The child process can also be terminated by the parent process if the task performed
by the child process is no longer needed.
➢ In addition, when a parent process terminates, it has to terminate the child process
as well became a child process cannot run when its parent process has been
terminated.

Gitam School of Computer Science Engineering

 Operations on Processes

Gitam School of Computer Science Engineering

 Interprocess Communication
➢ Processes executing concurrently in the operating system may be either
independent processes or cooperating processes.
➢ A process is independent if it does not share data with any other processes
executing in the system.
➢ 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 cooperating
process.
➢ There are several reasons for providing an environment that allows process
cooperation:
Information sharing. Since several applications may be interested in the same
piece of information (for instance, copying and pasting), we must provide an
environment to allow concurrent access to such information.

Gitam School of Computer Science Engineering

 Interprocess Communication
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. Notice that such a speedup can be achieved only if the computer has
multiple processing cores.

Modularity We may want to construct the system in a modular fashion,

dividing the system functions into separate processes or threads

➢ Cooperating processes require an interprocess communication (IPC)

mechanism that will allow them to exchange data— that is, send data to and
receive data from each other

Gitam School of Computer Science Engineering

 Interprocess Communication
➢ There are two fundamental models of
interprocess communication: shared
memory and message passing.
➢ In the shared-memory model, a region
of memory that is shared by the
cooperating processes is established.
Processes can then exchange
information by reading and writing
data to the shared region.
➢ In the message-passing model,
communication takes place by means
of messages exchanged between the
cooperating processes.

Gitam School of Computer Science Engineering

 Interprocess Communication
➢ Message passing is useful for exchanging smaller amounts of data, because
no conflicts need be avoided.
➢ Message passing is also easier to implement in a distributed system than
shared memory.
➢ Shared memory can be faster than message passing, since message-passing
systems are typically implemented using system calls and thus require the
more time-consuming task of kernel intervention.
➢ In shared-memory systems, system calls are required only to establish
shared memory regions.
➢ Once shared memory is established, all accesses are treated as routine
memory accesses, and no assistance from the kernel is required.

Gitam School of Computer Science Engineering

 IPC in Shared-Memory Systems
➢ Interprocess communication using shared memory requires communicating
processes to establish a region of shared memory.
➢ Typically, a shared-memory region resides in the address space of the
process creating the shared-memory segment.
➢ Other processes that wish to communicate using this shared-memory
segment must attach it to their address space.
➢ Shared memory requires that two or more processes agree to remove this
restriction.
➢ 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.
Gitam School of Computer Science Engineering
 IPC in Shared-Memory Systems
➢ To illustrate the concept of cooperating processes, let’s consider the
producer–consumer problem, which is a common paradigm for cooperating
processes.
➢ One solution to the producer–consumer problem uses shared memory.
➢ To allow producer and consumer processes to run concurrently, we must
have available 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.

Gitam School of Computer Science Engineering

 IPC in Shared-Memory Systems
➢ 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.

Gitam School of Computer Science Engineering

 IPC in Shared-Memory Systems

Gitam School of Computer Science Engineering

 IPC in Message-Passing Systems
➢ Another way to achieve the same effect is for the operating system to
provide the means for cooperating processes to communicate with each other
via a message-passing facility.
➢ Message passing provides a mechanism to allow processes to communicate
and to synchronize their actions without sharing the same address space.
➢ It is particularly useful in a distributed environment, where the
communicating processes may reside on different computers connected by a
network.

A message-passing facility provides at least two operations:

send(message)
and
receive(message)

Gitam School of Computer Science Engineering

 IPC in Message-Passing Systems
➢ 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.
➢ 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

Gitam School of Computer Science Engineering

 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.

Gitam School of Computer Science Engineering

 Naming
➢ A variant of this scheme employs 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 variable id is set to the name of the process with which communication has
taken place.

Gitam School of Computer Science Engineering

 Naming
➢ With indirect communication, the messages are sent to and received from
mailboxes, or ports.
➢ 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.
➢ For example, POSIX message queues use an integer value to identify a
mailbox.
➢ A process can communicate with another process via a number of different
mailboxes, but two processes can communicate only if they 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.

Gitam School of Computer Science Engineering

 Naming
➢ In this 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, a number of different links
may exist, with each link corresponding to one mailbox.

Gitam School of Computer Science Engineering

 Naming
➢ A mailbox may be owned either by a process or by the operating system.
➢ If the mailbox is owned by a process (that is, the mailbox is part of the
address space of the process), then we distinguish between the owner (which
can only receive messages through this mailbox) and the user (which can
only send messages to the mailbox).
➢ Since each mailbox has a unique owner, there can be no confusion about
which process should receive a message sent to this mailbox.
➢ 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.
➢ In contrast, 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.

Gitam School of Computer Science Engineering

 Synchronization
➢ Communication between processes takes place through calls to send() and
➢ receive() primitives.
➢ There are different design options for implementing each primitive.
➢ Message passing may be either blocking or nonblocking— also known as
synchronous and asynchronous

• Blocking send. The sending process is blocked until the message is received
by the receiving process or by the mailbox.
• Nonblocking send. The sending process sends the message and resumes
operation.
• Blocking receive. The receiver blocks until a message is available.
• Nonblocking receive. The receiver retrieves either a valid message or a
null.

Gitam School of Computer Science Engineering

 Naming
➢ A mailbox may be owned either by a process or by the operating system.
➢ 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.

Gitam School of Computer Science Engineering

 CPU scheduling
➢ CPU scheduling is the basis of multiprogrammed operating
systems.
➢ By switching the CPU among processes, the operating system
can make the computer more productive.
➢ Several processes are kept in memory at one time.
➢ When one process has to wait, the operating system takes the
CPU away from that process and gives the CPU to another
process.

Gitam School of Computer Science Engineering

 CPU–I/O Burst Cycle
➢ The success of CPU scheduling depends on an observed property
of processes:
process execution consists of a cycle of CPU execution and I/O
wait.
➢ Processes alternate between these two states.
➢ Process execution begins with a CPU burst.
➢ That is followed by an I/O burst, which is followed by another
CPU burst, then another I/O burst, and so on. Eventually, the
final CPU burst ends with a system request to terminate
execution

Gitam School of Computer Science Engineering

Gitam School of Computer Science Engineering
 CPU–I/O Burst Cycle
➢ The frequency curve is generally characterized as exponential or
hyperexponential, with a large number of short CPU bursts and a
small number of long CPU bursts.
➢ An I/O-bound program typically has many short CPU bursts.
➢ A CPU-bound program might have a few long CPU bursts.
➢ This distribution can be important when implementing a CPU-
scheduling algorithm.

Gitam School of Computer Science Engineering

 CPU Scheduler
➢ 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 CPU scheduler, which
selects a process from the processes in memory that are ready to
execute and allocates the CPU to that process.
➢ When we consider the various scheduling algorithms, a ready queue
can be implemented as a FIFO queue, a priority queue, a tree, or
simply an unordered linked list.
➢ Conceptually, however, all the processes in the ready queue are lined
up waiting for a chance to run on the CPU.
➢ The records in the queues are generally process control blocks (PCBs)
of the processes.

Gitam School of Computer Science Engineering

 Preemptive and Nonpreemptive Scheduling
➢ There are mainly two types of CPU scheduling:

Gitam School of Computer Science Engineering

 Preemptive and Nonpreemptive Scheduling
CPU-scheduling decisions may take place under the following
four circumstances:
1. When a process switches from the running state to the waiting state
(for example, as the result of an I/O request or an invocation of wait()
for the termination of a child process)

2. When a process switches from the running state to the ready state
(for example, when an interrupt occurs)

3. When a process switches from the waiting state to the ready state
(for example, at completion of I/O)

4. When a process terminates

Gitam School of Computer Science Engineering
 Dispatcher

➢ Another component involved in the CPU-scheduling

function is the dispatcher.
➢ The dispatcher is the module that gives control of the
CPU’s core to the process selected by the CPU
scheduler.
➢ This function involves the following:
1. Switching context from one process to another
2. Switching to user mode
3. Jumping to the proper location in the user
program to resume that program

Gitam School of Computer Science Engineering

 Scheduling Criteria
The criteria include the following:
1. CPU utilization. We want to keep the CPU as busy as possible.
Conceptually,CPU utilization can range from 0 to 100 percent. In a
real system, it should range from 40 percent (for a lightly loaded
system) to 90 percent(for a heavily loaded system). (CPU utilization
can be obtained by using the top command on Linux, macOS, and
UNIX systems.)
2. Throughput. If the CPU is busy executing processes, then work
is being done. One measure of work is the number of processes
that are completed per time unit, called throughput. For long
processes, this rate may be one process over several seconds; for
short transactions, it may be tens of processes per second.

Gitam School of Computer Science Engineering

 4. Turnaround time. From the point of view of a particular process, the
important criterion is how long it takes to execute that process. 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 in the ready queue, executing on the CPU, and doing I/O.
4. Waiting time. The CPU-scheduling algorithm does not affect the amount
of time during which a process executes or does I/O. It affects only the
amount of time that a process spends waiting in the ready queue. Waiting
time is the sum of the periods spent waiting in the ready queue.
5. Response time. In an interactive system, turnaround time may not be the
best criterion. Often, a process can produce some output fairly early and
can continue computing new results while previous results are being
output to the user. Thus, another measure is the time from the submission
of a request until the first response is produced. This measure, called
response time, is the time it takes to start responding, not the time it
takesto output the response.
Gitam School of Computer Science Engineering
 Scheduling Criteria

Gitam School of Computer Science Engineering

 Scheduling Algorithms
First-Come, First-Served Scheduling
➢ The simplest CPU-scheduling algorithm is the first-come first-serve
(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.

Gitam School of Computer Science Engineering

 Scheduling Algorithms
First-Come, First-Served Scheduling
➢ Consider the following set of processes that arrive at time 0,with the
length of the CPU burst given in milliseconds:

Gitam School of Computer Science Engineering

 Thank You

Gitam School of Computer Science Engineering