Operating System: Module 2

MODULE 2
Chapter 3: Process Concept

3.1 Overview:
• An operating system executes a variety of programs.

• Batch system executes jobs, whereas a time-shared system has user program or tasks.

3.1.1 The Process:

• A process is a program in execution; process execution must progress
in sequential fashion

• A process includes:
program counter
stack
data section
• Process memory is divided into four sections as shown in the figure below:

1. The stack is used to store local variables, function parameters, function return values,
return address etc.
2. The heap is used for dynamic memory allocation.
3. The data section stores global and static variables.

4. The text section comprises the compiled program code.

Figure 3.1: Process in Memory

• Note that, there is a free space between the stack and the heap.
• When the stack is full, it grows downwards and when the heap is full, it grows upwards.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 1

Operating System: Module 2

3.1.2 Process State:

• As the process executes, it changes state. The state of a process is defined in part by the
current activity of that process.
• A Process has 5 states. Each process may be in one of the following states –
1. New - The process is being created.
2. Ready - The process is waiting to be assigned to the processor.

3. Running – Instructions are being executed.

4. Waiting - The process is waiting for some event to occur. For example the process may
be waiting for keyboard input, disk access request, inter-process messages, a timer to go
off, or a child process to finish.
5. Terminated - The process has completed its execution.

Figure 3.2: Diagram of Process State.

3.1.3 Process Control Block:

• Each process is represented in the OS by process control block (PCB) – also called a task
control block.
• The PCB simply serves as the repository for any information that may vary from process
to process.
• A PCB contains many pieces of information associated with a specific process, including
these:
Process State – The state of the process may be new, ready, running, waiting, and so
on.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 2

Operating System: Module 2
Program counter– The counter indicates the address of the next instruction to be
executed for this process.

CPU scheduling information- This information includes a process priority, pointers to

scheduling queues, and any other scheduling parameters.

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. Along with the program counter, this state information must be saved
when an interrupt occurs, to allow the process to be continued correctly afterward.

Memory-management information – This include information such as the value of the

base and limit registers, the page tables, or the segment tables.

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.

Figure 3.3: Process control block (PCB)

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 3

Operating System: Module 2

Figure 3.4: Diagram showing CPU switch from process to process.

3.1.4 Threads:

• A process is a program that performs a single thread of execution.

• A thread is a light weight process.
• For example, when a process is running a word-processor program, a single thread of
instructions is being executed.
• This single thread of control allows the process to perform only one task at a time.
• For example, the user cannot simultaneously type in characters and run the spell checker
within the same process.
• Many modern OS have extended the process concept to allow process to have multiple
threads of execution and thus to perform more than one task at a time.

3.2 Process Scheduling:

• The objective of multiprogramming is to have some process running at all times, to

maximize CPU utilization.
• The objective of time sharing is to switch the CPU among processes so frequently that
users can interact with each program while it is running.
• To meet these objectives, the process scheduler selects an available process for program
execution on the CPU.
• For a single-processor system, there will never be more than one running process.
• If there are more processes, the rest will have to wait until the CPU is free and can be
rescheduled.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 4

Operating System: Module 2

3.2.1 Scheduling Queues:

• All processes admitted to the system are stored in the job queue.
• Processes in main memory and ready to execute are placed in the ready queue.
• Processes waiting for a device to become available are placed in device queues. There is
generally a separate device queue for each device.
• These queues are generally stored as a linked list of PCBs. A queue header will contain two
pointers - the head pointer pointing to the first PCB and the tail pointer pointing to the last
PCB in the list. Each PCB has a pointer field that points to the next process in the queue.
• When a process is allocated to the CPU, it executes for a while and eventually quits,
interrupted, or waits for the completion of an I/O request. Since there are many processes in
the system, the disk may be busy with the I/O request of some other process. The process
therefore may have to wait for the disk in the device queue.

Figure 3.6: Queuieng diagram representation of process scheduling.

• A common representation of process scheduling is a queueing diagram.

• Each rectangular box in the diagram 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 in the ready queue until it is selected for execution and is given the CPU.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 5

Operating System: Module 2

• 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 subprocess and wait for its 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.

3.2.2 Schedulers:

• Schedulers are software which selects an available program to be assigned to CPU.

1. A long-term scheduler or Job scheduler – selects jobs from the job pool (of secondary
memory, disk) and loads them into the memory.

If more processes are submitted, than that can be executed immediately, such processes
will be in secondary memory. It runs infrequently, and can take time to select the next
process.

2. The short-term scheduler, or CPU Scheduler – selects job from memory and assigns
the CPU to it. It must select the new process for CPU frequently.

3. The medium-term scheduler - selects the process in ready queue and reintroduced into
the memory.

• The long-term scheduler controls the degree of multiprogramming.

• 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 longer interval between executions, the long term scheduler can afford to take
more time to decide which process should be selected for execution.
• Processes can be described as either:

a. I/O-bound process – spends more time doing I/O than computations,

b. CPU-bound process – spends more time doing computations and few

I/O operations.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 6

Operating System: Module 2

• An efficient scheduling system will select a good mix of CPU-bound processes and I/O
bound processes.
a. If the scheduler selects more I/O bound process, then I/O queue will be full and
ready queue will be empty.

b. If the scheduler selects more CPU bound process, then ready queue will be full
and I/O queue will be empty.

• Time sharing systems employ a medium-term scheduler.

• It swaps out the process from ready queue and swap in the process to ready queue.

• When system loads get high, this scheduler will swap one or more processes out of the ready
queue for a few seconds, in order to allow smaller faster jobs to finish up quickly and clear
the system.

Figure 3.7: Addition of medium-term scheduling to the queueing diagram.

• Advantages of medium-term scheduler –
1. To remove process from memory and thus reduce the degree of multiprogramming
(number of processes in memory).
• 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.
2. Swapping is necessary to make a proper mix of processes (CPU bound and I/O bound)
because a change in memory requirements have overcommitted available memory,
requiring memory to be freed up.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 7

Operating System: Module 2

3.2.3 Context Switch:

• When interrupt occurs, the system needs to save the current context of the process
currently running on the CPU so that is can restore that context when its processing is
done, essentially suspending the process and then resuming it.

• Context of a process represented in the PCB, it includes the value of CPU registers, the
process state, and memory management information.

• Switching the CPU to another process require performing a state save of the current
process and a state restore of different process. This task is known as context switching.

• Context-switch time is overhead, because the system does no useful work while switching.

• Its speed varies from machine to machine, depending on the memory speed, the number of
registers that must be copied, and the existence of special instructions.

3.3 Operations on Processes:

3.3.1 Process Creation:

• A process may create several new processes.

• 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.
• Every process has a unique process ID (pid).
• In Solaris systems, the process at the top of the tree is the ‘sched’ process with PID of 0.
• The ‘sched’ process creates several children processes – init, pageout and fsflush.
• Pageout and fsflush are responsible for managing memory and file systems.
• The sched process also creates the init process, which serves as a parent process for all user
processes.
• A process will need certain resources (CPU time, memory, files, I/O devices) to accomplish
its task.
• When a process creates a subprocess, the subprocess may be able to obtain its resources:
directly from the operating system or subprocess may take the resources of the parent
process.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 8

Operating System: Module 2

Figure 3.8: A tree of processes on a typical Solaris system.

• The parent may have to partition its resources among its children or it may be able to
Share the resources among several children.
• 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 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).
2. The child process has a new program loaded into it.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 9

Operating System: Module 2

• A new process can be created by fork( ) system call.

• The fork system call, if successful, returns the PID of the child process to its parents and
returns a zero to the child process. If failure, it returns -1 to the parent.
• Process IDs of current process or its direct parent can be accessed using the getpid( ) and
getppid( ) system calls respectively.
• The parent waits for the child process to complete with the wait( ) system call.
• When the child process completes, the parent process resumes from the call to wait( ),
where it completes using the exit( ) system call. This is illustrated in figure 3.10

Figure 3.11: Process Creation.

• In windows the child process is created using the function createprocess( ).

• The createprocess( ) returns 1, if the child is created and returns 0, if the child is not
created.

3.3.2 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 to its parent process (via wait( ) system
call).
• A process can cause the termination of another process by using appropriate system call.
• The parent process can terminate its child processes by knowing of the PID of the child.
• A parent may terminate the execution of children for a variety of reasons, such as:

1. The child has exceeded its usage of the resources, it has been allocated.

2. The task assigned to the child is no longer required.

3. The parent is exiting, and the operating system does not allow a child to continue if its
parent terminates. This phenomenon is referred as cascading termination.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 10

 Operating System: Module 2

3.4 Interprocess Communication:

• Processes executing concurrently in the OS may be either co-operative or independent

processes.

1. Independent Processes – processes that cannot affect other processes or be affected

by other processes executing in the system.

2. Cooperating Processes – processes that can affect other processes or be affected by

other processes executing in the system.

• There are several reasons for providing an environment that allows process cooperation:

• Information Sharing - There may be several processes which need to access the
same file. So the information must be accessible at the same time to all users.

• Computation speedup - Often a solution to a problem can be solved faster if the

problem can be broken down into sub-tasks, which are solved simultaneously
( particularly when multiple processors are involved. )

• Modularity - A system can be divided into cooperating modules and executed by

sending information among one another.

• Convenience - Even a single user can work on multiple task by information

sharing.
Cooperating processes require some type of inter-process communication. This is
allowed by two models :

1) Shared Memory systems

2) Message Passing systems.

• In shared-memory model, a region of memory that is shared by 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
exchanges between the cooperating process.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 11

Operating System: Module 2

The two communications models are contrasted in figure 3.12

Figure 3.12: Communication models. (a) Message passing. (b) Shared memory.

3.4.1 Shared-Memory Systems:

• A region of shared-memory is created within the address space of a process, which needs
to communicate.
• Other processes that needs to communicate uses this shared memory.

• OS tries to prevent one process from accessing another process’s shared memory.
• 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 data and the location are determined by these processes and are not under
OS control.
• The processes are also responsible for ensuring that they are not writing to the same
location simultaneously.

Producer-Consumer Example Using Shared Memory:

• Paradigm for cooperating processes, producer process produces information that is

consumed by a consumer process.

• For example, a complier may produce assembly code, which is consumed by the
assembler.
• The assembler, in turn, may produce object modules, which are consumed by the loader.

• The data is passed via an intermediary buffer (shared memory).

• The producer puts the data to the buffer and the consumer takes out the data from the
buffer.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 12

Operating System: Module 2

• 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.

• In this situation, the consumer must wait until an item is produced.

• There are two types of buffers into which information can be put –

1. Unbounded buffer

2. Bounded buffer

• With Unbounded buffer, there is no limit on the size of the buffer, and so on the
data produced by producer. But the consumer may have to wait for new items.

• With bounded-buffer, there the buffer size is fixed.

• The producer has to wait if the buffer is full and the consumer has to wait if the buffer is
empty.

• This example uses shared memory as a circular queue.

• The in and out are two pointers to the array.

• Note in the code below that only the producer changes "in", and only the consumer
changes "out".
• First the following data is set up in the shared memory area:

#define BUFFER_SIZE 10 //buffer size typedef

struct {
...

} item;
item buffer[ BUFFER_SIZE ]; int
in = 0;
int out = 0;

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 13

Operating System: Module 2
• Bounded-Buffer – Producer:

item nextProduced;
while (true) { /* Produce an item */
while (((in = (in + 1) % BUFFER SIZE count) == out)

; /* do nothing -- no free buffers

*/ buffer[in] = item;
in = (in + 1) % BUFFER SIZE;
}

• Bounded Buffer – Consumer:

item nextConsumed;
while (true) {
while (in == out)
; // do nothing
nextConsumed =
buffer[out];
out = (out + 1) % BUFFER SIZE; /*consume the item in nextConsumed
*/
}

3.4.2 Message-Passing Systems:

• Message-passing system provides a mechanism to allow processes to communicate and to

synchronize their actions without sharing same address space.
• It is used in distributed systems.
• Message passing systems uses system calls for "send message" and "receive message".
• A communication link must be established between the cooperating processes before
messages can be sent.
• There are three methods of creating the link between the sender and the receiver-

1. Direct or indirect communication ( Naming )

2. Synchronous or asynchronous communication (Synchronization)

3. Automatic or explicit buffering.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 14

Operating System: Module 2

[Link] Naming:

• The processes that wants to communicate should have a way to refer each other.
• Direct communication the sender and receiver must explicitly know each others name.
• The syntax for send( ) and receive( ) functions are as
follows- send (P, message) – send a message to process P
receive(Q, message) – receive a message from process Q

• Properties of communication link :

1. A link is established automatically between every pair of processes that wants to

communicate. The processes need to know only each other's identity to
communicate.

2. A link is associated with exactly two (a pair) processes.

3. Between each pair, there exists exactly one link.

• Types of addressing in direct communication –

1. Symmetric addressing – the above described communication is symmetric

communication. Here both the sender and the receiver processes have to name each other
to communicate.
2. Asymmetric addressing – Here only the sender name is mentioned, but the receiving
data can be from any system.

• The send( ) and receive( ) primitive is defined as follows:

send(P, message) -- Send a message to process P

receive(id, message) -- Receive a message from any

process

• Disadvantages of direct communication – any changes in the identifier of a process,

may have to change the identifier in the whole system(sender and receiver), where the
messages are sent and received.

• Indirect communication uses shared mailboxes, or ports.

• A mailbox or port is used to send and receive messages.

• Mailbox is an object into which messages can be places by processes and from which
messages can be removed.
• Each mailbox has a unique identifier (unique ID).

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 15

Operating System: Module 2
• Two processes can communicate only if they have a shared mailbox.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 16

 Operating System: Module 2

• The send( ) and receive( ) functions are –

send(A, message) – send a message to mailbox A receive(A,

message) – receive a message from mailbox A

• Properties of communication link:

1. A link is established between a pair of processes only if they have a shared mailbox

2. A link may be associated with more than two processes

3. Between each pair of communicating processes, there may be any number of links, each
link is associated with one mailbox.

Example: Now suppose that processes P1, P2, and P3 all share mailbox A.

• Process P1 sends a message to A, while both P2 and P3 execute a receive( ) from A.

• Which process will receive the message sent by P1?

The answer depends on following methods which we choose:

1. Allow a link to be associated with at most two processes.

2. Allow only one process at a time to execute a receive operation.

3. Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was.

• A mail box can be owned by the operating system. It must take steps to –

1. create a new mailbox.

2. send and receive messages from mailbox.

3. delete mailboxes.

[Link] Synchronization:

• The communication between processes takes place through calls to send( ) and receive( )
primitives.
• Message passing may be either blocking or non-blocking also known as synchronous and
asynchronous.

1. Blocking send - sending process is blocked (waits) until the message is received by
receiving process or the mailbox.

2. Non-blocking send - sends the message and continues (does not wait)

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 17

 Operating System: Module 2
3. Blocking receive - The receiving process is blocked until a message is available

4. Non-blocking receive - receives the message without block. The received message may
be a valid message or null.

[Link] Buffering:

• When messages are passed, a temporary queue is created. Such queue can be of three
capacities:

1. Zero capacity – The buffer size is zero (buffer does not exist). Messages are not stored
in the queue. The senders must block until receivers accept the messages.

2. Bounded capacity - The queue is of fixed size(n). If the queue is not full when the new
message is sent , the message is placed in the queue. Senders must block if the queue is
full. After sending ‘n’ bytes the sender is blocked.

3. Unbounded capacity - The queue is of infinite capacity. Thus any number of message
can wait in it. The sender never blocks.

Likhitha B, Asst. Prof., Dept. of CS&E, VVCE Page 18

Operating System Module
2
Chapter 4: Multithreaded Programming
4.1 Overview:

• A thread is a basic unit of CPU utilization. It consists of a thread ID, program counter, a
stack, and a set of registers.

• Thread shares with other threads belonging to the same process its code section, data
section, and other OS resources, such as open files and signals.

• Traditional processes have a single thread of control. It is also called as heavyweight

process.

• If a process has multiple threads of control, it can perform more than one task at a time.

• A multi-threaded application have multiple threads within a single process, each having
their own program counter, stack and set of registers, but sharing common code, data, and
certain structures such as open files.

• Such process are called as lightweight process.

• Figure 4.1 illustrates the difference between a traditional single-threaded process and
multithreaded process.

Figure 4.1: Single threaded and multithreaded process

4.1.1 Motivation:

• Many software packages that run on modern desktop PCs are multithreaded.

• An application typically is implemented as a separate process with several threads of

control.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 19

Operating System Module
2
• For example in a word processor, a background thread may check spelling and grammar
while a foreground thread processes user input ( keystrokes ), while yet a third thread
loads images from the hard drive, and a fourth does periodic automatic backups of the file
being edited.

• In a web browser – one thread is used to display the images and another thread is used to
retrieve data from the network.

• In certain situations, a single application may be required to perform several similar

tasks.

• For example, in a web server - Multiple threads allow for multiple requests to be served
simultaneously. A thread is created to service each request; meanwhile another thread
listens for more client request.

Figure 4.2: Multithreaded server architecture.

4.1.2 Benefits:

• The four major benefits of multi-threading are:

1. Responsiveness - One thread may provide rapid response while other threads are
blocked or slowed down doing intensive calculations.

• Multithreading allows 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 other resources of the
process to which they belong.

• The benefits of sharing data and code is that it allows multiple tasks to be performed
simultaneously in a single 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 economical to create and
context-switch threads.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 20

Operating System Module
2
• In general, creating and managing threads is much faster than performing the same tasks
for processes.

4. Utilization of multiprocessor architecture – The benefits of multithreading can be

greatly increased in a multiprocessor architecture, where thread 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.

4.3 Multithreading Models:

• There are two types of threads to be managed in a modern system: User threads and
kernel threads.

• User threads are the threads that application programmers would put into their programs.
They are supported above the kernel, without kernel support.

• Kernel threads are supported within the kernel of the OS itself. All modern OS support
kernel level threads, allowing the kernel to perform multiple tasks simultaneously.

• Virtually all contemporary OS- including Windows XP, Linux, Mac OS X, Solaris etc.,
support kernel threads.

• There must exists a relationship between user threads and kernel threads, using one of the
following models.

4.3.1 Many-to-One Model:

• In the many-to-one model, many user-level threads are all mapped onto a single kernel
thread.
• Thread management is handled by the thread library in user space, which is very
efficient.
• If a blocking system call is made by one of the threads, then the entire process blocks.
Thus blocking the other user threads from continuing the execution.
• Only one user thread can access the kernel at a time, as there is only one kernel thread.
Thus the threads are unable to run in parallel on multiprocessors.
• Green threads of Solaris and GNU Portable Threads implement the many-to-one model.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 21

Operating System Module
2

Figure 4.3: Many-to-One model

4.3.2 One-to-One Model:

• The one-to-one model maps each user thread to a kernel thread.

• It provides 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 drawback of 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 the
application.

Figure 4.4: One-to-One Model.

• This model places a limit on the number of threads created.

• Linux and Windows from 95 to XP implement the one-to-one model for threads.

4.3.3 Many-to-Many Model:

• The many-to-many model multiplexes any number of user threads onto an equal or
smaller number of kernel threads, combining the best features of the one-to-one and
many-to-one models.

• Users have no restrictions on the number of threads created.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 22

 Operating System Module
2

Figure 4.5: Many-to-Many Model.

• When a thread performs a blocking system calls, it do not block the entire
process, instead kernel can schedule another thread for execution.

• Processes can be split across multiple processors.

• This model is also called as two-tier model.

• It is supported by operating system such as IRIX, HP-UX, and Tru64 UNIX.

Figure 4.6: Two level Model

4.6 Threading Issues:

4.6.1 The fork( ) and exec( ) System Calls:

• The fork( ) system call is used to create a separate, duplicate process.

• When a thread program calls fork( ),

 The new process can be a copy of the parent, with all the threads.

 The new process is a copy of the single thread only (that invoked the process)

• If the thread invokes the exec( ) system call, the program specified in the parameter
to exec( ) will be executed by the thread created.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 23

Operating System Module
2
4.6.2 Cancellation:

• Thread cancellation is a task of terminating the thread before it has completed.

• Example: Multiple threads required in loading a webpage is suddenly cancelled, if

the browser window is closed.

• The thread to be cancelled is called target thread.

• Cancellation of a target thread may occur in two different scenarios:

1. Asynchronous Cancellation – one thread immediately terminates the target thread.

2. Deferred Cancellation – the target thread periodically check whether it has to

terminate, thus gives an opportunity to the thread, to terminate itself in an orderly
fashion.

• In this method, the operating system will reclaim all the resources before cancellation.

4.6.3 Signal Handling:

• A signal is used to notify a process that a particular event has occurred.

• A signal may be received either synchronously or asynchronously, depending on

the source of and the reason for the event being signaled.

• All signals follow same path-

1. A signal is generated by the occurrence of a particular event.

2. A generated signal is delivered to a process.

3. Once delivered, the signal must be handled.

• A signal can be invoked in 2 ways: synchronous or asynchronous.

1. Synchronous signal – when a running program performs either of these actions, a signal
is generated, and are delivered to the same program. E.g. – illegal memory access, divide
by zero error.

2. Asynchronous signal – When a signal is generated by a n event external to a running

process, that process receives the signal asynchronously. E.g. signals includes terminating
a process with specific keystrokes (Ctrl +c) and having timer expire.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 24

Operating System Module
2
• A signal can be handled by one of the two ways –

1. Default signal handler - signal is handled by OS.

2. User-defined signal handler - User overwrites the OS handler.

• In a single-threaded program, the signal is sent to the same thread.

• But, in multi-threaded environment, the signal is delivered in variety of ways,

depending on the type of signal –

1. Deliver the signal to the thread, to which the signal applies.

2. Deliver the signal to every threads in the process.

3. Deliver the signal to certain threads in the process.

4. Deliver the signal to specific thread, which receive all the signals.

4.6.4 Thread Pools:

• In multithreading process, thread is created for every service. E.g. – In web server,
thread is created to service every client request.

• Creating new threads every time, when thread is needed and then deleting it when it
is done can be inefficient, as –

 Time is consumed in creation of the thread.

 A limit has to be placed on the number of active threads in the system.

Unlimited thread creation may exhaust system resources, such as CPU time or
memory.

• One solution to this issue is to use a thread pool.

• The general idea behind a thread pool is to create a number of threads at process
startup and place them into a pool, where they sit and wait for work.
• Threads are allocated from the pool when the server receives a request, and returned to
the pool when no longer needed (after the completion of request).

• When no threads are available in the pool, the server may have to wait until one becomes
available.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 25

Operating System Module
2
• Benefits of Thread pool –

 Servicing a request with an existing thread is faster than waiting to create a thread.

 The thread pool limits the number of threads in the system. This is important on systems
that cannot support a large number of concurrent threads.

• The ( maximum ) number of threads available in a pool may be determined by parameters

like the number of CPUs in the system, the amount of memory and the expected number
of client request.

4.6.5 Thread-Specific Data:

• Threads belonging to a process share the data of the process.

• This sharing of data provides one of the benefits of multithreaded programming.

• In some circumstances, each thread might need its own copy of certain data. Such data is
known as thread-specific data.

• Example – if threads are used for transactions and each transaction has an ID. This
unique ID is a specific data of the thread.

• Most thread libraries - including Pthreads, Win32, Java provide support for thread-
specific data.

4.6.6 Scheduler Activations:

• A final issue to be considered with multithreaded programs concerns communication

between kernel and the thread library, which may be required by many-to-many and two-
level models.

• Many systems implementing either many-to-many or two level model place an

intermediate data structure between the user and kernel threads.

• This data structure typically known as a lightweight process or LWP. Figure 4.9

Kavitha D N, Asst. Prof., CS&E, VVCE Page 26

Operating System Module
2
• One scheme for communication between user thread library and kernel is known as
scheduler activation.

• It works as follows:

 The kernel provide an application with a set of virtual processors (LWPs), and
the application can schedule user threads onto available virtual processor.

 Further, the kernel must inform the application about certain events.
This procedure is called as an upcall.

 Upcalls are handled by the thread library with an upcall handler, and
upcall handler must run on virtual processor.

• One event that triggers an upcall occurs when an application thread is about to block.

• Example - The kernel makes an upcall to the thread library informing that a thread is
about to block and also informs the specific ID of the thread.

• The kernel then allocates a new virtual processor to the application.

• The upcall handler handles this thread, by saving the state of the blocking thread and
relinquishes the virtual processor on which the blocking thread is running.

• The upcall handler then schedules another thread that is eligible to run on the virtual
processor.

• When the event that the blocking thread was waiting for occurs, the kernel makes another
upcall to the thread library informing it that the previously blocked thread is now eligible
to run.

• Thus assigns the thread to the available virtual processor.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 27

Operating System Module
2
Chapter 5: Process Scheduling
5.1 Basic Concept:

• In a single-processor system, only one process can run at a time; other processes
must wait until the CPU is free.

• The objective of multiprogramming is to have some process running at all times

in processor, to maximize CPU utilization.

• In multiprogramming, 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.

• This pattern continues.

• Every time one process has to wait, another process can take over use of the CPU.

• Scheduling of this kind is a fundamental operating-system function.

• Almost all computer resources are scheduled before use.

• The CPU is one of the primary computer resources. Thus, its scheduling is central
to operating-system design.

5.1.1 CPU-I/O Burst Cycle:

• Process execution consists of a cycle of CPU execution and I/O wait.

• The state of process under execution is called CPU burst and the state of process
under I/O request & its handling is called I/O burst.

• Process execution begins with CPU burst. It is followed by an I/O burst, which is
again followed by another CPU burst, then another I/O burst and so on.

• The final CPU burst ends with a system request to terminate execution. (Fig 5.1)

Kavitha D N, Asst. Prof., CS&E, VVCE Page 28

Operating System Module
2

Figure 5.1 Alternating sequence of CPU and I/O burst.

• The duration of CPU bursts have been measured extensively.

• They vary greatly from process to process and from computer to computer, they tend
to have a frequency curve.

Figure 5.2: Histogram of CPU-burst durations.

5.1.2 CPU Scheduler:

• Whenever the CPU becomes idle, the OS must select one of the processes in the
ready queue to be executed.

• The selection process is carried out by short-term scheduler.

• The scheduler selects the process from the processes in the memory that are ready
to execute and allocate the CPU to that process.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 29

Operating System Module
2
5.1.3 Preemptive Scheduling:

• CPU scheduling decisions may take place, when a process:

1. Switches from running to waiting state.

2. Switches from running to ready state.

3. Switches from waiting to ready state.

4. Terminates.

• Scheduling under 1 and 4 is non-preemptive. All other scheduling is preemptive.

• Non-Preemptive 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.

• Preemptive Scheduling – The process under execution, may be released from the CPU,
in the middle of execution due to some inconsistent state of the process.

Figure: for reference purpose.

5.1.4 Dispatcher:

• Dispatcher is the module that gives control of the CPU to the process selected by the
short-term scheduler; this involves:

 switching context

 switching to user mode

 jumping to the proper location in the user program to restart that program.

• Dispatch latency –is the time it takes for the dispatcher to stop one process and start
another process running.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 30

 Operating System Module
2
5.2 Scheduling Criteria:

• CPU utilization – keep the CPU as busy as possible.

• Throughput – number of processes that complete their execution per time unit.

• Turnaround time – amount of time to execute a particular process.

• Waiting time – amount of time a process has been waiting in the ready queue.

• Response time – amount of time it takes from when a request was submitted until
the first response is produced, not output (for time-sharing environment).

 Maximize - CPU utilization and throughput.

 Minimize - Turnaround time, waiting time and response time.

5.3 SCHEDULING ALGORITHMS:

• CPU scheduling deals with the problem of deciding which of the processes in the
ready queue is to be allocated the CPU.

5.3.1. First-Come, First-Served Scheduling:

• First-Come-First-Served algorithm is the simplest scheduling algorithm.

• Processes are executed on first come, first serve basis in ready queue.

• It is non-preemptive algorithm.

• Its implementation is based on FIFO queue.

Advantage:

• Easy to understand and implement.

• More predictable than other schemes since it offers time.

Disadvantages:

• Short jobs(process) may have to wait for long time.

• Important jobs (with higher priority) have to wait.

• Cannot guarantee good response time.

• Average waiting time and turnaround time is often quite long.

• Lower CPU and device utilization.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 31

 Operating System Module
2
Example 1:

Process Burst Time

P1 24

P2 3
P3 3

Calculate the average waiting time. (Answer solved in class.)

5.3.2 Shortest-Job-First Scheduling:

• This 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 either preemptive or non-preemptive.

Advantage:

• SJF is optimal – gives minimum average waiting time for a given set of processes.

Disadvantage:

• SJF cannot be implemented at the level of short-term CPU scheduling because there is
no way to know the length of the next CPU burst.

• Example 2:

Process Arrival Time Burst Time

P1 0 8
P2 1 4

P3 2 9
P4 3 5

Calculate average waiting time and turnaround time. (Answer solved in class.)

Kavitha D N, Asst. Prof., CS&E, VVCE Page 32

Operating System Module
2
5.3.3 Priority Scheduling:

• A priority number (integer) is associated with each process.

• The CPU is allocated to the process with the highest priority. (smallest integer =
highest priority)

• Process with same priority are executed on FCFS basis.

• Priority scheduling can be either preemptive or non-preemptive.

• Priority can be decided based on memory requirement, time requirement, or any other
resource requirement

• Problem with priority scheduling is indefinite blocking or starvation – low

priority processes may never execute

• Solution to that is aging – as time progresses increase the priority of the process.

• Example 3:

Process Burst Time Priority

P1 10 3

P2 1 1

P3 2 4
P4 1 5
P5 5 2

Calculate the average waiting time. (Answer solved in class.)

5.3.4 Round-Robin Scheduling:

• Each process gets a small unit of CPU time (called as time quantum), usually 10-
100 milliseconds.

• After this time has elapsed, the process is preempted and added to the end of the
ready queue.

• It is a preemptive scheduling algorithm.

• If there are n processes in the ready queue and the time quantum is q, then each
process gets 1/n of the CPU time in chunks of at most q time units at once.

• Context-switching is used to save states of preempted processes.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 33

Operating System Module
2
• The performance of RR depends on the size of time quantum.

• If time quantum is large, the RR uses FIFO policy.

Figure 5.4 The way in which a smaller time quantum increases context switches.

Example 4: with Time Quantum = 4

Process Burst Time

P1 24

P2 3
P3 3

Calculate average waiting time. (Answer solved in class.)

5.3.5 Multilevel Queue Scheduling:

• In multilevel queue scheduling, the ready queue is partitioned into separate queues:
foreground (interactive) and background (batch) processes.

• Each queue has its own scheduling algorithm.

• Foreground queue is scheduled by RR, whereas background queue is scheduled by FCFS.

• These two types of processes have different response-time requirements and so may
have different scheduling needs.

• In addition, foreground processes may have priority (externally defined) over

background processes.

• Scheduling must be done between the queues.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 34

Operating System Module
2
• Example of a multilevel queue scheduling algorithm with five queues, listed below
in order of priority:

1. System processes
2. Interactive processes

3. Interactive editing processes

4. Batch processes
5. Student processes

Figure 5.6: Multilevel queue scheduling.

• Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation.

• Time slice – each queue gets a certain amount of CPU time which it can schedule
amongst its processes; i.e., 80% to foreground in RR, 20% to background in
FCFS.

5.3.6 Multilevel Feedback-Queue Scheduling:

• A multilevel feedback queue scheduling algorithm allows a process to move between

the various queues; aging can be implemented this way.

• Multilevel-feedback-queue scheduler defined by the following parameters:

1. The number of queues.

2. The scheduling algorithms for each queue.

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

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

Kavitha D N, Asst. Prof., CS&E, VVCE Page 35

Operating System Module
2
5. The method used to determine which queue a process will enter when that process
needs service.

Example of Multilevel Feedback Queue:

• Consider three queues:

Q0 – RR with time quantum 8 milliseconds

Q1 – RR time quantum 16 milliseconds

Q2 – FCFS

Figure 5.7: Multilevel feedback queues.

Working of the Scheduling:

• A new process entering the ready queue is put in queue Q0.

• A process in Q0 is given a time quantum of 8 milliseconds. If it does not finish in

8 milliseconds, process is moved to queue Q1.

• At Q1 process is given a quantum of 16 milliseconds. If it still does not complete, it

is preempted and moved to queue Q2.

• Processes in Q2 run on FCFS basis, but run only when Q0 and Q1 are empty.

• This scheduling algorithm gives highest priority to any process with a CPU burst of
8 milliseconds or less.

• The long processes automatically sink to Q2 and are served in FCFS order with any
CPU cycles left over from Q0 and Q1.

Kavitha D N, Asst. Prof., CS&E, VVCE Page 36