Class 11 | Process and Process Scheduling | Operating System Notes

Class 11 | Process and Process Scheduling | Operating System Notes
UNIT 2
Class 11 Operating System Process & Scheduling

Process and Process Scheduling

Original Scanned PDF – View Notes

Open PDF Full Screen
Open Original PDF
01

Process

  • A process is program in execution.
  • In computing, a process is an instance of a computer program that is being executed.
  • It contain the program code and its current activity.
  • A process is an active entity with a program counter specifying the next instruction to execute and a set of associated resources.
  • A program is passive entity such as file containing a list of instruction stored on disk (often called executable file).
  • A program becomes a process when an executable file is loaded in main memory.
  • A part of a computer program that perform a well defined task is known as an algorithm.
  • A collection of computer programs, libraries and related data are referred as a software.
02

Process Memory

Process Memory is divided into four sections:

  1. Text section: comprises the compiled code.
  2. Data section: stores global and static variable allocated and initialized prior to execution main.
  3. Heap: heap is used for dynamic memory allocation and it managed via calls to new, delete, malloc, free etc.
  4. Stack: stack is used for local variables.
Process memory divided into stack, heap, data and text sections Stack Heap Data Text
Fig: Process memory
03

Process State

  • When process executes, it passes different states.
  • The state of process is defined in part by the current activity of that process.
  • These stages may differ in different OS, and the names of these states are also not standardized.

A Process May Be in One of the Following States

  1. New: The process is in the stage of being created.
  2. Ready: The process has all the resources available that it needs to run, but the CPU is not currently working on this process’s instruction.
  3. Running: The CPU is executing the process.
  4. Waiting: The process can not run at the moment, because it is waiting for some resources to become available or for some event to occur such as I/O completion or reception of signal.
  5. Terminated: The process has finished execution.
Life cycle of process execution with New, Ready, Running, Waiting and Terminated states New Ready Running Waiting Terminated admitted scheduler dispatch interrupt I/O or event wait I/O or event completion exit
Fig: Life cycle of process execution
04

Process Control Block (PCB)

  • PCB is a data structure used by operating system to store all the information about process.
  • When a process is created, the OS creates corresponding PCB.
  • A PCB keeps all information needed to keep track on a process.
  • It contains many pieces of information associated with a specific process.
Process Control Block containing process ID, state, pointer, priority, program counter, CPU register, I/O information and accounting information Process ID State Pointer Priority Program Counter CPU Register I/O Information Accounting Information
Fig: Process Control Block (PCB)

1. Process State

The state may be new, ready, running and so on.

2. Pointer

It is a stack pointer which is required to be saved when the process is switches from one state to another to return the current position.

3. Process ID

Every process is assigned with a unique number known as Process ID or PID which stores process identification.

4. Program Counter

It indicates the address of the next instruction to be executed for the process.

5. Register

These are CPU register which includes accumulator, stack pointer, general purpose register etc.

6. I/O Information

It includes list of I/O devices allocated to this process, a list of open files etc.

7. Accounting Information

It includes amount of CPU and real time used, account number, process number etc.

05

Process Scheduling

The process scheduling is the activity of the process manager that handles the removal of the selection of another process on the basis of particular strategy.

Process scheduling is an essential part of a multiprogramming OS. Such operating system allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing.

06

Process Scheduling Queues

  • The OS maintains all the Process Control Blocks (PCBs) in process scheduling queues.
  • The OS maintains a separate queue for each of the process states and PCBs of all processes.
  • The same execution states are placed in the same queue.
  • When the state of a process is changed, its PCB is unlinked from the current queue and moves to its new state queue.

The OS Maintains the Following Important Process Scheduling Queues

  1. Job queue: This queue keeps all processes in the system.
  2. Ready queue: This queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue.
  3. Device queue: The process which are blocked due to unavailability of an I/O devices constitutes this queue.
Process scheduling queues showing job queue, ready queue, CPU, exit, I/O and device queue Job queue Ready queue CPU Exit I/O Device queue or I/O queue
Fig: Process scheduling queues
07

Schedulers

  • Schedulers are special system software which handle process scheduling in various ways.
  • Their main task is to select the jobs to be submitted into the system and to decide which process to run.
  • Schedulers are three types: long term scheduler, short term scheduler, medium term scheduler.

1. Long-Term Scheduler

  • It is also called a job scheduler.
  • It determines which programs are admitted to the system for processing, selects processes from the queue and loads them into memory for execution.
  • Process loads into the memory for CPU scheduling.
  • The primary objective of the job scheduler is to provide a balanced mix of jobs such as I/O bound and processor bound.
  • It also controls 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 process leaving the system.
  • Time sharing OS have not long-term schedulers.
  • When process changes the state from new to ready then this is use of long-term scheduler.

2. Short-Term Scheduler

  • It is also called scheduler.
  • Its main objective is to increase system performance in accordance with the chosen set of criteria.
  • It is the change of ready state to running state of the process.
  • It selects a process among the process that are ready to execute and allocates CPU to one of them.
  • It is also known as dispatcher as it makes the decision of which process to execute next.
  • It is faster than long-term scheduler.

3. Medium-Term Scheduler

  • It is a part of swapping.
  • It removes the processes from the main memory.
  • It reduces the degree of multiprogramming.
  • A running process may become suspended if it makes an I/O request.
  • A suspended process can not make any progress toward completion.

In this condition, to remove the process from memory and make space for another processes, the suspended process is moved to the secondary memory. This process is called swapping and this process is said to be swapped out or rolled out.

08

Comparison of Scheduler

S.N. Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler
1.It is a job scheduler.It is a CPU scheduler.It is a process / swapping scheduler.
2.Speed is lesser than short term scheduler.Speed is faster among other two.Speed is between both long and short scheduler.
3.It controls degree of multiprogramming.It provides lesser control over degree of multiprogramming.It reduces the degree of multiprogramming.
4.It is almost absent or minimal in time sharing system.It is also minimal in time sharing system.It is a part of time sharing system.
5.It selects processes from pool and loads them into memory for execution.It selects those processes whose processes are ready to execute.It can re-introduce the process into memory and execution can be continued.
09

Categories of Scheduling

1. Preemptive Scheduling

  • In this scheduling, OS allocate the resource to a process for a fixed amount of time.
  • During resource allocation, the process switches from running state to ready state or from waiting state to ready state.
  • CPU may give priority to other processes and replace the process with higher priority with the running process.
  • It is CPU scheduling technique that works by dividing time slots of CPU to a given process.
  • The time set given might be able to complete the whole process or might not be able to.
  • When burst time of the process is greater than CPU cycle it is placed back into the ready queue.

Preemptive scheduling algorithm are: Round Robin (RR), priority, shortest Remaining Time First (SRTF) etc.

2. Non-Preemptive Scheduling

  • In this type, resource cannot be taken from a process until the process completes execution.
  • The switching of resources occurs when the running process terminated and moves to a waiting state.

Non-preemptive scheduling algorithms are: First-Come-First-Serve (FCFS) and Shortest Job First (SJF).

10

Difference Between Preemptive & Non-Preemptive Scheduling

S.N.PreemptiveNon-Preemptive
1.Resources are allocated according to the cycles or limited time.Resources are used and then held by the process until it gets terminated.
2.The process can be interrupted, even before the completion.The process is not interrupted until its life cycle is completed.
3.Starvation may be caused due to the insertion of priority process in the queue.Starvation can occur when a process with large burst time occupies the system.
4.Maintaining queue & remaining time needs storage overhead.No such overhead required.
5.Example: RR, Priority, Shortest etc.Example: FCFS and SJF.
11

Some Scheduling Algorithms

1. First-Come-First-Serve (FCFS)

  • It is an operating system algorithm that automatically executes queued request and processes in order of their arrival.
  • In this type of algorithm, process which request the CPU first gets the CPU allocation first.
  • This is managed by FIFO queue.
  • As the process enters the ready queue, its PCB is linked with the tail of the queue. When the CPU becomes free, it should be assigned to the process at the beginning of the queue.

Characteristics of FCFS Algorithm

  • It supports non-preemptive scheduling algorithm.
  • Jobs are always executed on a first-come-first-serve (FCFS) basis.
  • It is easy to implement and use.
  • This method is poor in performance and general waiting time is quite high.

Advantage

  • Simplest form of a CPU scheduling algorithm.
  • Easy to program.
  • First come first served.

Disadvantage

  • It is non-preemptive scheduling algorithm, so after the process has been allocated to the CPU, it will never release the CPU until it finishes executing.
  • The average waiting time is high.
  • Short processes that are back of the queue have to wait long time.
  • Not an ideal scheduling technique for time sharing system.
  • It is not very efficient due to its simplicity.
12

Shortest Job First (SJF) Algorithm

  • In this algorithm, the process having the smallest execution time is chosen for the next execution.
  • This scheduling method can be preemptive or non-preemptive.
  • It significantly reduces the average waiting time for other process awaiting execution.

Basically Two Types

  1. Non-preemptive SJF: Once the CPU cycle is allocated to process, the process holds till it reached a waiting state or terminated.
  2. Preemptive SJF: Jobs are put into the ready queue as they come. A process with shortest burst time begins execution. If a process with even a shorter burst time arrives, the current process is removed or preempted from execution and the shorter job is allocated CPU cycle.

Advantage of SJF

  • SJF is frequently used for long term scheduling.
  • It reduces the average waiting time over FIFO algorithm.

Disadvantage of SJF

  • In SJF scheduling, job completion time must be known earlier but it is hard to predict.
  • It can be implemented for CPU scheduling for the short term. It is easiest where is no specific method to predict the length of the upcoming CPU burst.
13

Shortest Remaining Time First (SRTF) Scheduling Algorithm

  • The preemptive version of shortest Job First (SJF).
  • The process having the smallest amount of time remaining until completion is selected first to execute.
  • So, processes are scheduled according to the shortest remaining time.
  • In SRTF, the execution of any process can be stopped after a certain amount of time.
  • The short-term scheduler schedules those processes from the list of available process and running processes that have the least remaining burst time.

Advantage

  • Processing of job is faster than SJF algorithm.

Disadvantage

  • Involves more overhead than SJF because it requires frequently in order to monitor the CPU time of jobs in ready queue.
  • The context switching is done a lot more time than in SJN (shortest job next).
14

Thread

  • Thread is the smallest unit of programmed instructions that can be managed independently and processing by OS.
  • A process is divided into several lightweight process, each lightweight process is said to be a thread.
  • A thread contains: Thread ID, program counter, Register and stack.

Example: In a web browser one thread can display image or text while another thread retrieves data from the network.

Process containing three threads operating over time Process Thread 1 Thread 2 Thread 3 time
Fig: Thread
15

Life Cycle of Thread

  1. Born state: A thread that has just been created.
  2. Ready state: The thread is waiting for the process CPU.
  3. Running state: The system assigns the process to the thread means that the thread is being executed.
  4. Blocked state: The thread is waiting for an event to occur or waiting for an I/O device.
  5. Sleep: A sleeping thread becomes ready after the designated sleep time expires.
  6. Dead: The execution of the thread is finished.
Thread life cycle state diagram showing Born, Ready, Running, Waiting, Sleeping, Dead and Blocked Born Ready Running Waiting Sleeping Dead Blocked
Fig: State diagram for thread life cycle
16

Difference Between Process and Thread

S.N.ProcessThread
1.Process means a program is in execution.Thread means a segment of a process.
2.Take more time to terminate.Take less time to terminate.
3.Consume more resources.Consume less resources.
4.Process is isolated.Thread share memory.
5.It does not share data.Thread share data with each other.
6.Take more time for context switching.Take less time for context switching.
7.Take more time for creation.Take less time for creation.
8.Process communication is complex.Easy and efficient communication.
9.If one process crashes, it doesn’t affect other process.If one thread crashes, all thread crashes.
KEEP LEARNING View All Posts

Discussion

Share a helpful question, idea, or explanation with other students.

Leave a Comment

Write a clear question, answer, or helpful explanation.
Your email will not be published.

Download Our Offline App

Study class-wise notes even when internet is not available. Get the app from Play Store.

Nepal eNotes offline app preview
Get it on Google Play