4. Operating System – Process State Diagram and CPU Scheduling Basics

Operating System – Process State Diagram and CPU Scheduling Basics.

By Shritam Bhowmick
Web Application Penetration Tester
LinkedIn: https://www.linkedin.com/profile/view?id=281014248&trk=nav_responsive_tab_profile
Academia: https://independent.academia.edu/ShritamBhowmick
Facebook: https://www.facebook.com/coded32

Previous post discussed about CPU scheduling and an introduction towards Process Management; This post will take it further to an introduction to the process management which is required for WBUT 3rd Semester BCA candidates. Particularly this post is dedicated to process state diagram and will cover the entire aspect of the same.

To start off with the details, a program when needs to be executed goes through a process. This process has several state changes in the entire operation until termination of the program. Upon successful termination, the program would get useful results to the user. This entire process progression goes through state changes which are mention below in steps:

  1. The process enters a state called NEW STATE.
  2. The process then enters the READY STATE.
  3. The process then goes to an ACTIVE STATE/RUNNING STATE (Execution of the program starts here).
  4. The process ends with the HALT STATE/TERMINATED STATE (after all the program BURST’s are over. The program might be terminated forcibly or else is terminated normally.)

The following PROCESS STATE DIAGRAM would show the entire operation:

Diagram of process state

Note, there is a intermediary state which is known to be the WAITING STATE/BLOCKED STATE.  The program goes through this particular state when the CPU is busy with interaction with the I/O devices during I/O operations (this is called I/O BURST). During I/O BURST, since the CPU time is being wasted, to avoid this; the pending jobs are brought up from the queue by the CPU Scheduler and then this new job is executed with first READY STATE and then after the whole operation is finished, the original Job is picked up and executed from middle-way. This way, the CPU saves significant amount of time and maintains the efficiency. The following describes the process timeline:

 

programterminationdiagramiooperationtimeline

 

CPU SCHEDULING

According to the process timeline, it could be observed that the program initiation starts with a CPU BURST and is terminated with a CPU BURST as well. During the entire process progression, the CPU has to interact with I/O devices and hence the pending jobs are completed during this time. The original job is held with a WAITING STATE/BLOCKED STATE status and upon completion of the pending process, the original job is taken. From the previous post we had discussed about two types of CPU Scheduling:

  • FCFS (First Come First Serve) CPU Scheduling.
  • SJF (Shortest Job First) CPU Scheduling.

SJF CPU Scheduling saves the time and is an efficient way to schedule jobs. This is done by the CPU Scheduler. Contrary to SJF CPU Scheduling, FCFS CPU Scheduling cannot save time and prediction for the next CPU BURST could not be determined (we need to determine or calculate the amount of time the next CPU BURST would be going to take to maintain an efficiency!) cannot be done. FCFS CPU Scheduling has a strict rule to take a Job, process and execute it and only after the termination of the original job, the next job could be taken by the CPU. Hence there is no real time efficiency scheduling been done with FCFS CPU Scheduling; the job which comes first is executed first and therefore prediction for the next CPU BURST could be applied for the SJF Scheduling algorithm. Since, SJF CPU Scheduling algorithm takes time efficiency into consideration, the CPU must predict the amount of time the CPU has to spend it’s time on NEXT CPU BURST.

CPU BURST: The amount of time spent by the CPU for a program in order to execute the program, process it for the execution.
I/O BURST: The amount of time spent by the CPU for a program interacting with I/O devices for I/O operations.

Now, since a calculated prediction of the NEXT CPU BURST could only be determined for SJF CPU Scheduling, the following is considered as the standard process to calculate an estimate of the amount of time spent for the NEXT CPU BURST which would be yet to occur for a program process:

image018image019

 

Now, there is yet another calculated special case of SJF algorithm which could be used for efficiency purposes. This special case of SJF CPU Scheduling algorithm is known as PRIORITY SCHEDULING. In case of priority scheduling, the priority levels could be  set. In that case the job which has the highest priority should be executed first. Low priority jobs will be executed only after high specified priority jobs had been executed. It could be said that PRIORITY SCHEDULING could be considered as the reciprocal of the NEXT CPU BURST.

NON-PREEMPTIVE CPU SCHEDULING

Now, all of these scheduling algorithms, that is:

  1. FCFS
  2. SJF
  3. Priority

are known to be NON-PREEMPTIVE SCHEDULING. The reason it is known to be NON-PREEMPTIVE Scheduling is since the processing of jobs once allocated, the CPU cannot be taken out of the job until that entire CPU BURST is complete. At the end of the current CPU BURST, another Job could be assigned to the CPU by the CPU Scheduler.

PREEMPTIVE CPU SCHEDULING

The situation with PREEMPTIVE CPU SCHEDULING is wherein the job is in it’s CPU BURST but could be made PREEMPTIVE by allocating another JOB (the current job has to be stopped before it’s natural completion). As per the three CPU Scheduling we have seen so far, the FCFS CPU Scheduling cannot be PREEMPTIVE CPU SCHEDULING because  FCFS has to follow the strict rules regarding the jobs which are sent first must be completed first (executed first), and only after the normal completion of the first job execution, other pending jobs should be executed. The remaining two, that is SJF CPU Scheduling and Priority Scheduling algorithm could be modified to get PREEMPTIVE CPU SCHEDULING.

Let’s take an example of jobs which are in the READY Queue with SJF CPU Scheduling modified to suit PREEMPTIVE CPU SCHEDULING that is SHORTEST REMAINING TIME FIRST CPU SCHEDULING (SRT):

J1 – 15
J2 – 9
J3 – 3
J4 – 5

These jobs are in the ready queue with their CPU BURST time. As per the SJF CPU SCHEDULING, the shortest execution time required has to be picked up which in this case would be J3, since J3 has 3 units of time requirement and others have a longer span of time requirement. Let’s consider the execution has been started and the J3 job has spent 1 unit of time with the CPU Processing:

J3

|———–|
1 UNIT

There are remaining 2 UNITS of time completion left for job J3, but another job which is Job J5 arrives which requires an execution CPU BURST time of 1 unit, so, now on the READY Queue we have:

J1 – 15
J2 – 9
J3 – 2 (Since 1 unit has already been completed, the left over is 2 time units.)
J4 – 5
J5 – 1 (new job which has arrived with time unit 1)

Now, the CPU Scheduler has to check the ready queue to find out which job has the minimum of time requirement as per the policy of SJF CPU SCHEDULING algorithm. The CPU Scheduler would find that the new job which has arrived only requires 1 time unit and hence will allocate the job J5 by PREEMPTIVE procedure of job J3 which was in the middle of the execution; the job J5 will be processed for execution:

J3              J5               2 UNIT LEFT

|———–|———–|______________|
1 UNIT     1 UNIT

So, the Job J5 will be executed since it has been scheduled to be executed in the middle of Job J3’s execution. After completion of Job J5, the CPU Scheduler would again check the READY QUEUE to check the status, and the CPU BURST requirement would be:

J1 – 15
J2 – 9
J3 – 2 (This is the minimum time unit)
J4 – 5
J5 – 0 (Since it is finished)

Assuming no new jobs came to the READY QUEUE with lower time unit requirement as compared to that of Job J3 time unit (which was left!), the CPU Scheduler would assign the CPU to execute J3 which requires 2 time units:

J3              J5                        J3

|———–|———–|———————-|
1 UNIT     1 UNIT              2 UNIT

After the completion of the job J3, the CPU Scheduler yet again has to check the READY QUEUE:

J1 – 15
J2 – 9
J3 – 0
J4 – 5
J5 – 0

Now, the modified SJF algorithm will treat Job J4 to be minimum and start executing it assuming no newer jobs were upfront available in the READY QUEUE. This is how the SJF CPU Scheduling algorithm can be used to maintain efficiency in CPU processing with modification which is known to be SRT (SHORTEST REMAINING TIME FIRST) CPU Scheduling.

Now there must be a way to modify the Priority Scheduling algorithm to obtain an efficient result. This could be done using the same logic but using ‘priority’ in mind. The higher priority job must be executed first. But there would be a conflict using priorities since if a job which always have a high priority in the READY QUEUE than the others has to be executed first and this job comes coming over and again to the READY QUEUE, the lower priority jobs will starve for CPU time and hence might not get executed ever. Now, this situation is unwanted, a concept called ‘aging‘ is used. While the job remains in the READY QUEUE, at regular intervals of time, the CPU will go incrementing the priority of the jobs. Now the priority of the job isn’t decided by the user or the administrator, but it’s decided by the time spent by the CPU for a particular job while other incrementing pending jobs were getting higher priority hits since it’s been aging for CPU time. At one point the maximum priority level will be reached by the job(s) pending, and when it reaches this priority level, the CPU will start executing that job leaving the current job to the WAIT/BLOCK status.

The time taken by the CPU Scheduler which has to be executed by the CPU as well program should be negligible compared to the CPU BURST time of the jobs. Now for a brief overview of what we had discussed here were process block diagram where we talked that a process could migrate from READY state to the ACTIVE state and from the ACTIVE state to the WAITING STATE and then again from the WAITING state to the READY state until the job completion. But with new concepts involved such as PREEMPTIVE CPU Scheduling, there is another route of this migration of state, which hence could be also from the ACTIVE state to the READY state. Hence below is something which completes the Process State Diagram:

pathagain

The ‘blue’ color path is the new path which is available because of PREEMPTIVE CPU Scheduling. With respect to the process state diagram; in a system if there are jobs which require more amount of CPU BURST time, such jobs would be called as ‘CPU Bound Jobs‘, another type of CPU BURST time is where a process would require more I/O time and less CPU time, such jobs are referenced as ‘I/O Bound Jobs‘. Hence two types of Jobs are:

  1. CPU Bound Jobs
  2. I/O Bound Jobs

Now, assume, In the READY Queue, all the jobs are CPU Bound Jobs; this means for none of the jobs, I/O operation is much concerned which again means I/O operation in the whole processing is negligible and very less time units are spent in I/O operations whereas much time is spent over CPU processing. So in such cases, the CPU time taken will be quite high and I/O devices will remain inactive. Now contradictory to the past situation where CPU Bound Jobs were in READY QUEUE and I/O operations were negligible, there could be situation where all the jobs in the READY QUEUE are I/O operation jobs and negligible CPU process jobs, which means time spent by the CPU will be negligible for these jobs and the I/O devices will be very busy since all the jobs have I/O operations. None of the previous and the current situation are wanted or desirable. Because the efficiency lies in the point that a system should be always busy with all of it’s components and in these cases either the CPU remains inactive or the I/O devices remains inactive, hence wasting ‘time’ and resources therefore go without proper management scheduling of the jobs in the first place. To avoid this situation, or rather to schedule the jobs efficiently, there are schedulers.

Technically all of this means that there must be some kind of management at the READY QUEUE to avoid situations wherein resource time are being wasted. To address the problem, there are schedulers. There are two kind of schedulers, one which takes the job from the NEW STATE to the READY STATE (shifting the job from NEW to the main memory which is dubbed as READY QUEUE – The state diagram will describe it as the READY STATE) and another which takes the job from the READY STATE to the ACTIVE STATE. Since the procedure where the job has to be taken from the READY STATE (READY Queue) to the ACTIVE STATE is complex because of very low time span  of the CPU BURST. The CPU BURST time span being short, the Scheduler cannot decide which operation (whether the job has to be migrated from the READY STATE to the ACTIVE STATE or ACTIVE STATE to the READY STATE (READY QUEUE) because there are two routes here {see the diagram above which shows the new path in blue because of PREEMPTIVE CPU Scheduling}) to be done. So this scheduler which takes the job from the READY STATE (READY QUEUE) to the ACTIVE STATE is known to be SHORT TERM SCHEDULER. The other scheduler which takes the job from the NEW STATE to the READY STATE (READY QUEUE) is called LONG TERM SCHEDULER. Therefore the two kinds of Schedulers are:

  1. LONG TERM SCHEDULER
  2. SHORT TERM SCHEDULER

Since we discussed that in the READY QUEUE it is  not desirable to have CPU Bound Jobs or I/O Bound jobs, the LONG TERM SCHEDULER would be responsible to decide what jobs should be sent to the READY STATE (READY QUEUE). The duration of the LONG TERM SCHEDULER is quite long since it has plenty of time to decide, but the scope of time involved for SHORT TERM SCHEDULER is quite less which is the reason we can afford a complex LONG TERM SCHEDULER.

 

Advertisements

2 thoughts on “4. Operating System – Process State Diagram and CPU Scheduling Basics

  1. Pingback: 5. Operating System – Process Management: Round Robin CPU Scheduling | Shritam Bhowmick

  2. Thanks brother for such informative and lovely information

    You’re such a life saver brother
    as I’ve Operating System Exam tomorrow

    and i’ll have you know that This concept will surely help me in my exam now 🙂

    so a big thanks to you brother for WordPressing such a good and informative topic on CPU Scheduling brother 🙂

    This concept has really helped and eased me in understanding the basic concept of CPU Scheduling brother 🙂

    Hit me up soon as i’m waiting for something now 🙂

Looking for intellectual opinions. Feedbacks are welcome!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s