Unit 2: Process Management
Process Concept
Process is a program in execution; process execution must progress in sequential fashion.
The process contains Multiple parts
The structure of a process in memory is
Process Concept
Program is passive entity stored on disk (executable file), process is active
Execution of program started via GUI mouse clicks, command line entry of its name, etc
One program can be several processes
As a process executes, it changes state
new: The process is being created
running: Instructions are being executed
waiting: The process is waiting for some event to occur
ready: The process is waiting to be assigned to a processor
terminated: The process has finished execution
�
Process State Diagram
Each process is represented in the operating system by a process control block (PCB)-also called a task control block.
A PCB is shown in Figure 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.
�
Process Control Block
�
Process Control Block
• 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.
In brief, the PCB simply serves as the repository for any information that may vary from process to process.
CPU switch from process to process
�
Process Scheduling
�
Representation of Process Scheduling
�
Representation of Process Scheduling
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.
�
Schedulers
A process migrates among the various scheduling queues throughout its lifetime. The operating system must select, for scheduling purposes, processes from these queues in some fashion. The selection process is carried out by the appropriate scheduler.
There are three types of schedulers 1.Longterm scheduler 2. Short term scheduler 3. Medium term scheduler
1.Long-term scheduler (or job scheduler) – selects processes which are submitted and loads them into memory for execution. Put them in ready queue.
2. Short-term scheduler (or CPU scheduler) – selects from among the processes that are ready to execute and allocates the CPU to one of them.
�
Schedulers
3. Medium-term scheduler can be added if degree of multiple programming needs to decrease
�
Schedulers
CPU switch from process to process
�
Operations on Processes
The processes in most systems can execute concurrently, and they may be created and deleted dynamically. Thus, these systems must provide a mechanism for process creation and termination.
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 (including UNIX and the Windows family of 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 (CPU time, memory, files, 1/0 devices) to accomplish its task. When a process creates a subprocess, that subprocess 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 (such as memory or files) 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 subprocesses.
�
Resource sharing options
1. Parent and children share all resources
2. Children share subset of parent’s resources
3. Parent and child share no resources
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).
2. The child process has a new program loaded into it.
UNIX examples
fork() system call creates new process
exec() system call used after a fork() to replace the process’ memory space with a new program
�
C Program Forking Separate Process
�
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 using abort() system call , Usually, such a system call can be invoked only by the parent of the process that is to be terminated.
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.
�
Process Termination
Some operating systems do not allow child to exists if its parent has terminated. If a process terminates, then all its children must also be terminated.
The parent process may wait for termination of a child process by using the wait()system call. The call returns status information and the pid of the terminated process
pid = wait(&status);
If no parent waiting (did not invoke wait()) process is a zombie
If parent terminated without invoking wait , process is an orphan
Inter Process Communication
Interprocess Communication
Communications Models
(a) Message passing. (b) shared memory.
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.
Recall that, normally, the operating system tries to prevent one process from accessing another process's 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 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.
To illustrate the concept of cooperating processes, let's consider the producer-consumer problem, which is a common paradigm for cooperating processes.
Producer – Consumer Problem
A producer process produces information that is consumed by a consumer process. For example, a compiler may produce assembly code, which is consumed by an assembler. The assembler, in turn, may produce object modules, which are consumed by the loader.
The producer-consumer problem also provides a useful metaphor for the client-server paradigm. We generally think of a server as a producer and a client as a consumer. For example, a web server produces (that is, provides) HTML files and images, which are consumed (that is, read) by the client web browser requesting the resource.
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.
Producer – Consumer Problem
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:
#define BUFFER_SIZE 10
typedef struct { . . . } item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Producer – Consumer Problem
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
The producer process has a local variable nextProduced in which the new item to be produced is stored. The consumer process has a local variable nextConsumed in which the item to be consumed is stored.
Bounded-Buffer – Producer
item next_produced;
while (true) {
/* produce an item in next produced */
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
}
Bounded-Buffer – Consumer
item next_consumed;
while (true) {� while (in == out)
; /* do nothing */� next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;�
/* consume the item in next consumed */
}
Inter process Communication – 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, where the communicating processes may reside on different computers connected by a network. For example, a chat program used on the World Wide Web could be designed so that chat participants communicate with one another by exchanging messages.
A message-passing facility provides at least two operations: send(message) and receive(message).
Messages sent by a process can be of either fixed or variable size.
2. variable-sized messages
Message Passing (Cont.)
• Direct or indirect communication
• Synchronous or asynchronous communication
• Automatic or explicit buffering
Direct Communication
Direct Communication
Indirect Communication
In 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. 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, however. The send() and receive () primitives are defined as follows:
Properties of communication link will be
Indirect Communication
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 (who can only receive messages through this mailbox) and the user (who can only send messages to the 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. The operating system then must provide a mechanism that allows a process to do the following:
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. Of course/ this provision could result in multiple receivers for each mailbox.
Synchronization
Buffering
1. 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.(rendezvous). This is a system with no buffering.
2. 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. If the link is full, the sender must block until space is available in the queue. This is a system with bounded buffering
Threads
A thread is a basic unit of CPU utilization; it comprises a thread ID, a program counter, a register set, and a stack. It shares with other threads belonging to the same process its code section, data section, and other operating-system resources, such as open files and signals. A traditional (or heavyweight) process has a single thread of control. If a process has multiple threads of control, it can perform more than one task at a time.
Motivation
Many software packages that run on modern desktop PCs are multithreaded. A web browser might have one thread display images or text while another thread retrieves data from the network, for example. A word processor may have a thread for displaying graphics, another thread for responding to keystrokes from the user, and a third thread for performing spelling and grammar checking in the background.
A busy web server may have several (perhaps thousands) of clients concurrently accessing it. If the web server ran as a traditional single-threaded process, it would be able to service only one client at a time.
One solution is to have the server run as a single process that accepts requests. When the server receives a request, it creates a separate process to service that request.
Threads also play a vital role in remote procedure call (RPC) systems. Typically, RPC servers are multithreaded. When a server receives a message, it services the message using a separate thread. This allows the server to service several concurrent requests.
Finally, many operating system kernels are now multithreaded; several threads operate in the kernel, and each thread performs a specific task, such as managing devices or interrupt handling.
Benefits
The benefits of multithreaded programming are
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. For instance, a multithreaded web browser could still allow user interaction in one thread while an image was being loaded in another thread.
2. Resource sharing. By default, threads share the memory and the resources of the process to which they belong.
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. In Solaris, for example, creating a process is about 30 times slower than is creating a thread, and context switching is about five times slower.
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.
Multithreading Models
Support for threads may be provided either at the user level, for user threads, or by the
kernel, for kernel threads.
User threads are supported above the kernel and are managed without kernel support, whereas kernel threads are supported and managed directly by the operating system.
three common ways of establishing a relationship between user threads and kernel threads.
1. Many-to-One Model: The many-to-one model
Multithreading Models
2. One-to-One Model
restricted due to overhead.
Examples
3. Many-to-Many Model
Examples
Solaris prior to version 9, Windows with the ThreadFiber package.
CPU Scheduling
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 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.
CPU-scheduling decisions may take place under the following four circumstances:
The scheduling can be preemptive or non preemptive
Under 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.
Dispatcher
The dispatcher is the module that gives control of the CPU to the process selected
by the short-term scheduler. This function involves the following:
• 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
For choosing which Scheduling algorithm to use in a particular situation, we must consider the following criteria:
• CPU utilization. We want to keep the CPU as busy as possible. Conceptually,
CPU utilization can range from 0 to 100 percent.
• Throughput. The number of processes that are completed per time unit, called throughput.
• 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. The amount of time that a process spends waiting in the ready queue.
• Response time. the time from the submission of a request until the first response is produced. This measure, called response time.
We have to choose a scheduling algorithm to maximize CPU utilization and throughput and to minimize turnaround time, waiting time, and response time.
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.
First-Come, First-Served Scheduling
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:
Process Burst Time
P1 24
P2 3
P3 3
First-Come, First-Served Scheduling
Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:
�
Turn Around Time
P1 -> Job completion time – job submission time = 24 – 0 = 24
P2 -> 27 – 0 = 27
P3 -> 30 – 0 = 30
Average Turn Around Time = (24+27+30) / 3 = 81/3 = 27 milli sec
Waiting Time
P1 -> Turn Around Time – Burst time = 24 – 24 = 0
P2 - > 27 – 3 = 24
P3 -> 30 – 3 = 27
The average waiting Time = (0+24+27) /3 = 51/3 = 17 milli sec
Response Time
P1 -> First response time – Arrival time = 0 – 0 = 0
P2-> 24 – 0 = 24
P3 -> 27 – 0 = 27
The Average Response Time is = (0+24+27)/3=51/3 = 17 milli sec
First-Come, First-Served Scheduling
If the processes arrive in the order P2, P3, P1,however, the results will be as shown in the following Gantt chart:
.
Turn Around Time
P1 -> Job completion time – job submission time = 30 – 0 = 30
P2 -> 3 – 0 = 3
P3 -> 6 – 0 = 6
Average Turn Around Time = (30+3+6) / 3 = 39/3 = 13 milli sec
Waiting Time
P1 -> Turn Around Time – Burst time = 30 – 24 = 6
P2 - > 3 – 3 = 0
P3 -> 6 – 3 = 3
The average waiting Time = (6+0+3) /3 = 9/3 = 3 milli sec
Response Time
P1 -> First response time – Arrival time = 6 – 0 = 6
P2-> 0 – 0 = 0
P3 -> 3 – 0 = 3
The Average Response Time is = (6+0+3)/3=9/3 = 3 milli sec
First-Come, First-Served Scheduling
The CPU-bound process will get and hold the CPU. During this time, all the other processes will finish their I/O and will move into the ready queue, waiting for the CPU. While the processes wait in the ready queue, the I/O devices are idle.
Eventually, the cpu-bound process finishes its CPU burst and moves to an I/O device. All the I/O-bound processes, which have short CPU bursts, execute quickly and move back to the I/O queues. At this point, the CPU sits idle. The CPU-bound process will then move back to the ready queue and be allocated the CPU. Again, all the I/O processes end up waiting in the ready queue until the CPU-bound process is done. There is a convoy effect as all the other processes wait for the one big process to get off the CPU. This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.
The FCFS scheduling algorithm is nonpreemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.
The FCFS algorithm is thus particularly troublesome for time-sharing systems.
Shortest-Jab-First Scheduling
In shortest-job-first (SJF) scheduling algorithm. 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.
This is the shortest-next-CPU-burst algorithm, because scheduling depends on the length of the next CPU burst of a process, rather than its total length.
As an example of SJF scheduling, consider the following set of processes, with the length of the CPU burst given in milliseconds:
SJF scheduling chart
Shortest-Jab-First Scheduling
Turn Around Time :
P1 -> completion time – arrival time = 9 – 0 = 9
P2 -> 24 – 0 = 24
P3 -> 16 – 0 = 16
P4 -> 3 – 0 = 3
Average Turn Around Time = ( 9+24+16+3)/4 = 52/4 = 13 milli sec
Waiting Time :
P1 -> TAT – BT = 9 – 6 = 3
P2 -> 24 – 8 = 16
P3 -> 16 – 7 = 9
P4 -> 3 – 3 = 0
Average Waiting Time = ( 3+16+9+0)/4 = 28/4 = 7 milli sec
Response Time :
P1 -> starting time – arrival time = 3 – 0 = 3
P2 -> 16 – 0 = 16
P3 -> 9 – 0 = 9
P4 -> 0 – 0 = 0
Average Response Time = ( 3+16+9+0)/4 = 28/4 = 7 milli sec
Shortest-Jab-First Scheduling
The waiting time is 3 milliseconds for process PI, 16 milliseconds for process
P2, 9 milliseconds for process P3, and 0 milliseconds for process P4 . Thus,
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.
Although the SJF algorithm is optimal, it cam10t be implemented at the level of short-term CPU scheduling. There is no way to know the length of the next CPU burst.
Preemptive version called shortest-remaining-time-first
As an example, consider the following four processes, with the length of the CPU burst given in milliseconds:
Shortest-Jab-First Scheduling
ProcessA arri Arrival TimeT Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
0th milli sec -> only P1 – 8 ( P1)
1st Milli Sec -> P1 – 7 , P2 – 4 ( P2)
2nd Milli Sec -> P1 – 7 , P2 – 3, P3 – 9 (P2)
3rd Milli Sec - > P1 – 7, P2 – 2, P3-9 , P4 – 5 (P2)
Shortest-Jab-First Scheduling
Turn Around Time :
P1 -> completion time – arrival time = 17 – 0 = 17
P2 -> 5 – 1 = 4
P3 -> 26 – 2 = 24
P4 -> 10 – 3 = 7
Average Turn Around Time = ( 17+4+24+7)/4 = 52/4 = 13 milli sec
Waiting Time :
P1 -> TAT – BT = 17 – 8 = 9
P2 -> 4 – 4 = 0
P3 -> 24 – 9 = 15
P4 -> 7 – 5 = 2
Average Waiting Time = (9+0+15+2)/4 = 26/4 = 6.5 milli sec
Response Time :
P1 -> starting time – arrival time = 0 – 0 = 0
P2 -> 1– 1 = 0
P3 ->17 – 2 = 15
P4 -> 5– 3 = 2
Average Response Time = ( 0+0+15+2)/4 = 17/4 = 4.25 milli sec
Priority Scheduling
A priority is associated with each process,
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.
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 low priority processes waiting indefinitely.
Problem ≡ Starvation – low priority processes may never execute
Solution ≡ Aging – as time progresses increase the priority of the process
Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.
Priority Scheduling
ProcessA arri Burst TimeT Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority Scheduling
Turn Around Time :
P1 -> job completion time – job submission time = 16 - 0=16
P2-> 1 – 0 = 1
P3 -> 18 – 0 = 18
P4 -> 19 – 0 = 19
P5 -> 6 – 0 = 6
Average Turn Around Time = ( 16+1+18+19+6)/5 = 60/5 = 12 milli sec
Waiting Time
P1 -> TAT – BT = 16 - 10=6
P2-> 1 – 1 = 0
P3 -> 18 – 2 = 16
P4 -> 19 – 1 = 18
P5 -> 6 – 5 = 1
Average Waiting Time = (6+0+16+18+1)/5 =41/5 = 8.2 milli sec
Response Time
P1 -> starting time – Arrival time = 6 - 0=6
P2-> 0 – 0 = 0
P3 -> 16 – 0 = 16
P4 -> 18 – 0 = 18
P5 -> 1 – 0 = 1
Average Response Time = (6+0+16+18+1)/5 =41/5 = 8.2 milli sec
Priority Scheduling ( Preemptive)
1st Milli Sec -> P1-9-3, P2-1-1, ( P2)
2ND Milli Sec -> P1-9-3, P3-2-4 (P1)
3RD Milli Sec -> P1-8-3, P3-2-4, P4-1-3 ( P1)
4TH Milli Sec -> P1-7-3, P3-2-4, P4-1-3, P5-5-2 (P5)
Priority Scheduling
Turn Around Time :
P1 -> job completion time – job submission time = 16 - 0=16
P2-> 2 – 1 = 1
P3 -> 19 –2 = 17
P4 -> 17 – 3 = 14
P5 -> 9 – 4 = 5
Average Turn Around Time = ( 16+1+17+14+5)/5 = 53/5 = 10.6 milli sec
Waiting Time
P1 -> TAT – BT = 16 - 10=6
P2-> 1 – 1 = 0
P3 -> 17 – 2 = 15
P4 -> 14 – 1 = 13
P5 -> 5 – 5 = 0
Average Waiting Time = (6+0+15+13+0)/5 =34/5 = 6.8 milli sec
Response Time
P1 -> starting time – Arrival time = 0 - 0=0
P2-> 1 – 1 = 0
P3 -> 17 – 2 = 15
P4 -> 16 – 3 = 13
P5 -> 4 – 4 = 0
Average Response Time = (0+0+15+13+0)/5 =28/5 = 5.6 milli sec
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.
If the process may have a CPU burst of less than 1 time quantum. In this case, the process itself will release the CPU voluntarily.
Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off . 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.
Round Robin Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Round Robin Scheduling
Turn Around Time :
P1 -> job completion time – job submission time = 30 - 0=30
P2-> 7 – 0 = 7
P3 -> 10 –0 = 10
Average Turn Around Time = ( 30+7+10)/3 = 47/3 = 15.66 milli sec
Waiting Time
P1 -> TAT – BT = 30 - 24=6
P2-> 7 – 3 = 4
P3 -> 10 – 3 = 7
Average Waiting Time = (6+4+7)/3 =17/3 = 5.66 milli sec
Response Time
P1 -> starting time – Arrival time = 0 - 0=0
P2-> 4 – 0 =4
P3 -> 7 – 0 = 7
Average Response Time = (0+4+7)/3 =11/3 = 3.66 milli sec
Multilevel Queue
Multilevel Queue Scheduling
Multilevel Feedback Queue
Example of Multilevel Feedback Queue