techtud's picture
Process

A process is a program in execution. Process is not as same as program code but a lot more than it. A process is an 'active' entity as opposed to program which is considered to be a 'passive' entity. Attributes held by process include hardware state, memory, CPU etc.

Process memory is divided into four sections for efficient working :

  • The text section is made up of the compiled program code, read in from non-volatile storage when the program is launched.
  • The data section is made up the global and static variables, allocated and initialized prior to executing the main.
  • The heap is used for the dynamic memory allocation, and is managed via calls to new, delete, malloc, free, etc.
  • The stack is used for local variables. Space on the stack is reserved for local variables when they are declared.

Contributor's Info

Created: Edited:
0Comment
Process and Process State Model

Process: Generally, a process is  program in execution. A process includes current activity, contents of the processor’s registers, process stack, and data section. A process may include a heap. Heap is a memory that dynamically allocated during process runtime. Abstraction view of a process is given below:

     7.jpg           

 

There is two types of processes:
(i) System process: These process can not be preempted and executed in privileged mode.

(ii) User process: These process can be preempted and executed in user mode.

 

Every process has three parts first is executable program or code section, second is data section and third is context section. Context section of a process contains stack and process control information which managed by operating system. Code and data section of a program are called as user address space.
       8.jpg         

 

Process Control Block(PCB): Each process has its own process(or task) control block(PCB).

 

      9.jpg

We can differentiate processes using process id. Process state defines current state of process; process state can be new, ready, running, waiting etc. Program counter contains address of next instruction to be executed. I/O status information includes list of allocated open devices, list of allocated open files etc. Generally, every PCB has three grouped informations:

  • Process identification data contains has numeric identifier, parent identifier, user identifier etc.

  • Process control information contains process state information, links to other process memory privileges, scheduling etc.

  • CPU state information contains stack pointers, user visible registers, control and status registers etc.

       

Process  State Models

There are various types of process state model. Process state defines current state of a process. The process states are new, ready, running, waiting, suspended waiting, terminated etc.
 

  1. New state: The process is being created.

  2. Ready state: The process is ready to run, but waiting to be assigned a processor.

  3. Running state: Program is running in other words instructions are being executed.

  4. Waiting state: Process preempted and switched from running state to waiting state because of process is waiting for some event to occur such as I/O completion.

  5. Terminated state: This state is final state, when process is completed or finished execution it moves from running state to terminated state.  

Two more states are suspended ready and suspended blocked. A process moves from ready state to suspended ready due to more priority for other processes. A process moves from waiting state to suspended blocked state due to process might be consuming more memory.

 

Note that ready state, running state and waiting state are always resides in main memory and new state, suspended ready and suspended blocked state resides in secondary memory.   

There are four types of process model:

(i) Two state process model:

 11.PNG

 

(ii) Five state process model:

  12.PNG

(iii) Six state process model:

   16.PNG

(iv) Seven state process model:

    17.PNG

 

Where R = Running, W = Waiting, T = Terminated, SB = Suspended block, and SR = Suspended ready state. Preemption, dispatch, schedule , suspend, created, active, terminated etc. are actions that performed by operating system.

 

Process Transitions:

  • Transition from new state to ready state occurs when a process is created.

  • Transition from ready state to running state occurs when CPU decides(using process scheduling algorithm) which process will run next.

  • Transition from running state to ready state occurs when process preempted.

  • Transition from running state to waiting state occurs when process required I/O event.

  • Transition from waiting state to ready state occurs when I/O event has completed.

  • Transition from running state to terminated state occurs if process has finished its execution.

 

Types of Process: There is three type of process:

  1. CPU - Bound: Process needs more service by CPU than I/O service.

  2. I/O - Bound: Process needs more I/O service than CPU service.

  3. Interactive: Process spends more time in waiting queue than CPU burst time.

 

Contributor's Info

Created: Edited:
0Comment
Process Schedulers | Long-term scheduler | Medium-term scheduler | Short-term scheduler

The selection process is carried out by the appropriate scheduler for scheduling purpose. There are three types of schedulers: Long-term scheduler, Medium-term scheduler and Short-term scheduler.

  1. Long-term scheduler: Also known as Job scheduler. The primary goal of long-term scheduler is maintaining/controlling good degree of multiprogramming. When a process moves state from new to ready state then there is long term scheduler. It decides next process to go ready state and loads it into main memory.

  2. Short-term scheduler: Also known as CPU scheduler. The primary goal of short term scheduler is enhance the performance of CPU. It determines next process to go running state. So, sometime it's called as Dispatcher. Short term scheduler is faster than long term scheduler. It provides lesser control of degree of multiprogramming.

  3. Medium-term scheduler: It reduces degree of multiprogramming. Medium term scheduler moves process from main memory to secondary memory, so it's a part of swapper. It transit job from ready state(or suspended waiting state) to suspended ready. Speed of medium term scheduler is between both short term and long term scheduler.

New state has job queue, ready state has ready queue and suspended blocked state has device queue.

Contributor's Info

Created:
0Comment
Process Scheduling Metrics| Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time | Response Time | Throughput | Processor Utilization

Scheduling Metrics: Scheduling metrics use to measure something, there are different metrics.

  1. Arrival Time(AT): The time which the process became ready.

  2. Burst Time(BT): Also called as service or execution or processing time is time spent executing in CPU.

  3. Completion Time(CT): Also called as finish time is the time at the process completed its execution in CPU.

  4. Turn Around Time(TAT): It is total time spent waiting for CPU and execution in CPU, i.e.,
    TAT = WT + BT = CT - AT
    Average TAT = ( Total TAT ) / (Total number of processes)
     

  5. Waiting Time(WT): The time spent waiting for CPU.

    WT = TAT - BT
    Average WT = ( Total WT ) / (Total number of processes)
     

  6. Response Time(RT): The time it takes to start responding to a request. It from first submission of the process until the first running.

    RT = ( Time of first response ) - ( Time of submission of request )
     

  7. Throughput: The number of processes that are completed per unit time.

    Throughput = (Number of processes completed) / (Time unit)
     

  8. Processor Utilization: The percentage of the time that CPU is busy, means not idle.

    Processor utilization = (Processor busy time) / (Processor busy time + Processor idle time)
     

Co-operative(non-preemptive) versus preemptive scheduling : There is two kind of CPU/Process scheduling algorithms:

  1. Non preemptive scheduling: A running process can not be preempted till completed its execution in CPU,e.g., FIFO process scheduling, shortest job first(non-preemptive).

  2. Preemptive scheduling: A running process can be preempted and CPU can be scheduled for another process, e.g., Round robin algorithm, Shortest remaining time first algorithm etc.

 

Contributor's Info

Created:
0Comment
Process Scheduling Algorithms

First come first serve(FCFS), Shortest job first(SJF), and Shortest remaining time first(SRTF) are used in batch system. Round robin(RR), Highest response ratio next(HRRN), Priority scheduling with multilevel queue, and priority with multilevel feedback queue are used in interactive system.

Contributor's Info

Created:
0Comment
Various Scheduling Examples | FCFS | Shortest-Job-First (SJR) | Round Robin (RR)

FCFS :

Process Burst Time
  P1 24
  P2 3
  P3   3

Suppose that the processes arrive in the order: P1, P2, P3
The Gantt Chart for the schedule is:

P1

P2

P3

0 ............................................  24 .............................. 27........................................................ 30

  Waiting time for P1 = 0; P2 = 24; P3 = 27

  Average waiting time: (0 + 24 + 27)/3 = 17

Suppose that the processes arrive in the order: P2 , P3 , P1 .

The Gantt chart for the schedule is:

P2

P3

P1

0 ..................................................3.....................................6....................................................30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than the previous case.

Convoy effect short process behind long process

Shortest-Job-First (SJR) Scheduling:
Associate with each process the length of its next CPU 
burst. Use these lengths to schedule the process with the shortest time.
Two schemes:
1.  non-preemptive – once CPU has given to the process it cannot 
be preempted until completes its CPU burst.
2. preemptive – if a new process arrives with CPU burst length less than remaining time of the currently executing process, preempt. This scheme is known as the Shortest-Remaining-Time-First (SRTF).

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

 Process   Arrival Time Burst Time
P1  0.0     7
P2    2.0      4
P3  4.0   1
P4 5.0      4

SJF (non-preemptive):

P1

P3

P2

P4

0.................................. 7................................. 8 ........................12.........................................16

Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4

SJF (preemptive)

P1

P2

P3

P2

P4

P1

0 ................... 2......................4........................5..................... 7..................... 11...................16

Average waiting time = (9 + 1 + 0 +2)/4 =3
Determining Length of Next CPU Burst Can only estimate the length. Can be done by using the length of previous CPU bursts, using exponential averaging.

Round Robin (RR):
Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

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. No process waits for more than (n-1)q time units.

Performance:

1. q large _ FIFO

2. q small _ q must be large with respect to context switch, otherwise overhead is too high.

Example of RR with Time Quantum = 4

Process Burst Time
  P1 24
  P2 3
  P3   3

The Gantt chart is:

P1

P2

P3

P1

P1

P1

P1

P1

0.............4...............7.............10............14............18 ............22.............26............ 30

Average waiting time =    [(30-24)+4+7]/3  = 17/3 =5.66

Note: If the burst time of the processes are matching then schedule the process which has lowest arrival time and if arrival time matching then schedule the process which has lowest process id

Contributor's Info

Created: Edited:
0Comment
FCFS with overhead
Content covered: 

FCFS with overhead 

More Less
0Comment
SJF scheduling

Shortest-Job-First(SJF) Scheduling

  • Best approach to minimize waiting time.
  • Actual time taken by the process is already known to processor.
  • Impossible to implement.
  • example:-

Shortest-Job-First(SJF) Scheduling

 

In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preempted.

 

Contributor's Info

Created: Edited:
0Comment
SJF with prediction of BT
Content covered: 

SJF with prediction of BT 

More Less
0Comment
Shortest Job Remaining Time First

Shortest Remaining Time First(SRTF) algorithm: This is preemptive version of shortest job first algorithm.  It’s minimize average turn arround time. If all processes are arrived at same time, then it works as SJF.

Example: Consider the following table:

Process no.

Arrival Time

Burst Time

P1

0

6

P2

2

1

P3

4

4

P4

5

3

Find the average waiting time and average turn arround time using SRTF(preemptive) algorithm?

Solution: Using SRTF(non-preemptive) algorithm, gantt chart is:

 

21.jpg

 

Therefore,  

Waiting Time

Turn around Time

Completion Time

Process No.

Arrival Time

Burst Time

7 - 6 = 1

7 - 0 = 7

7

P1

0

6

1 - 1 = 0

3 - 2 = 1

3

P2

2

1

10 - 4 = 5

14 - 4 = 10

14

P3

4

4

5 - 3 = 2

10 - 5= 5

10

P4

5

3

 

So,
Average Turn arround time  = (7 + 1 + 10 +5) / (4) = 5.75

Average Waiting time = (1 + 0 + 5 + 2) / (4) =2

 

Contributor's Info

Created: Edited:
1Comment
Round Robin(RR) Scheduling

RR Scheduling-

  • A fixed time is allotted to each process, called quantum, for execution.
  • Once a process is executed for given time period that process is preemptied and other process executes for given time period.
  • Context switching is used to save states of preemptied processes.

example-

Round Robin(RR) Scheduling

Contributor's Info

Created:
0Comment
Highest Response Ratio Next(HRRN)
Content covered: 

Highest Response Ratio Next(HRRN) 

More Less
0Comment
Priority Based Process Scheduling (Preemptive/Non-preemptive)

Priority based (Non-preemptive) Process Scheduling: Priority can be internal or external and static or dynamic. This algorithm selects process with highest priority to execute.

Example: Consider the following table:

Process no.

Arrival Time

Burst Time

Priority

P1

0

6

2

P2

2

1

4 (Lowest)

P3

4

4

1 (Highest)

P4

5

3

3

Find the average waiting time and average turn arround time using Priority(Non-preemptive) algorithm?

Solution: Using Priority(non-preemptive) algorithm, gantt chart is:

23.jpg

 

Therefore,
 

Waiting Time

Turn around Time

Completion Time

Process No.

Arrival Time

Burst Time

Priority

6 - 6 = 0

6 - 0 = 6

6

P1

0

6

2

12 - 1 = 11

14 - 2 = 12

14

P2

2

1

4 (Lowest)

6 - 4 = 2

10 - 4 = 6

10

P3

4

4

1 (highest)

8 - 3 = 5

13 - 5 = 8

13

P4

5

3

3

 

So,
Average Turn arround time  = (6 + 12 + 5 + 8) / (4) = 8

Average Waiting time = (0 + 11 + 2 + 5) / (4) = 4.5

Priority based (preemptive) Process Scheduling: This algorithm selects process with highest priority to execute and it’s preempted lower priority process.

Example: Consider the following table:

Process no.

Arrival Time

Burst Time

Priority

P1

0

6

2

P2

2

1

4 (Lowest)

P3

4

4

1 (Highest)

P4

5

3

3

Find the average waiting time and average turn arround time using Priority(Preemptive) algorithm?

Solution: Using Priority(Preemptive) algorithm, gantt chart is:

   

 

Therefore,
 

Waiting Time

Turn around Time

Completion Time

Process No.

Arrival Time

Burst Time

Priority

10 - 6 = 4

10 - 0 = 10

10

P1

0

6

2

12 - 1 = 11

14 - 2 = 12

14

P2

2

1

4 (Lowest)

4 - 4 = 0

9 - 5 = 4

9

P3

4

4

1 (highest)

7 - 3 = 4

13 - 6 = 7

13

P4

6

3

3

 

So,
Average Turn arround time  = (10 + 12 + 4 + 7) / (4) = 8.25

Average Waiting time = (4 + 11 + 0 + 4) / (4) = 4.75

 

Contributor's Info

Created: Edited:
0Comment
Pre-emptive priority with processes contains CPU and IO time
Content covered: 

Pre-emptive priority with processes contains CPU and IO time 

More Less
0Comment
Multi level queues and multi level feedback queues
Content covered: 

Multi level queues and multi level feedback queues 

More Less
0Comment