3. Operating System – CPU Management

CPU Management – A step towards Process Management

 

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

Last post, I talked about the coverage of the series on operating system and the introductory post with the importance of operating system, as well as defining the operating system. In this post, I’d discuss CPU management and hence go closer into process management. The CPU is known by Central Processing Unit and it is hence obvious CPU is a process manager of the computer system. It processes the given data into desired output which is useful for the user. The process which takes place in the CPU should be in the main memory, that is the data which is to be executed via processing should be in the main memory (Random Access Memory or RAM).  A multi-user system uses processes, and a process does not mean a multiple CPU handling these processes, it means that the processes are handled by the same CPU but with optimization in time and processing efficiency. The data provided by the user is fed to the CPU which is a ‘Job’, this Job needs processing to be done and hence result in execution in the CPU, the Jobs require the dependency data to be present in the main memory. Jobs are the tasks which the CPU has to undertake in order to process them, and then execute and write the results to the secondary devices (special I/O devices as discussed in y previous posts) or directly as a output to a video terminal, or printer, etc.

The terms which would be required for CPU management are:

  1. Waiting Time
  2. Turnaround Time

What is Waiting Time?

The gap in time between the given job for execution to the CPU and the actual time when the CPU begins to execute the given job is known as the waiting time. Or in other words the time the processing for the given job to be executed/processed remains in the ready queue for the CPU to begin processing or executing is termed as the waiting time.

Let t(0) be the time the user has given a certain job for processing or execution to the CPU. And let the actual time when the CPU begins processing/executing the given job be t(i). The time difference between t(i) and t(0) i.e: t(i) – t(0) = t(w) {Waiting time} is termed as the waiting time. So the equations are:

T(i) - T(0) = T(w)

Where,

  1. T(i) = Time at which the user had supplied the job for processing or execution to the CPU.
  2. T(0) = Time at which the CPU actually starts processing or execution of the supplied job.
  3. T(w) = Waiting Time.

Now for the CPU to give an output, there must be some time taken by the CPU in order to process the job. This time on a timeline of the whole processing from job given, to job initialization by the CPU and the output could be shown as below:

 

Waiting Time Demonstration

 

As shown, the processed job by the CPU is at the last entry which is marked as T (p), this would be the output time stamp when the job is done by the CPU.  Now, the concept of turnaround time hops in.

What is Turnaround Time?

The time taken for a job to complete it’s processing or execution from the point of the job submission to the CPU until it’s processing has been completed is termed as turnaround time. Or in other words, turnaround time is the total time taken between the submission of a program/process/thread/task  for execution and the return of the complete output to the user.

Now, as we had assumed the time stamp when the job is completed to be T (p), the turnaround time would be as following described by the equation:


T (t) = T (p) - T (0)

Where,

  1. T (t) = Turnaround Time
  2. T (p) = Processed or executed job by the CPU returned to the user or written in the special I/O device or outputted.
  3. T (0) = The time stamp when the user submitted the job/task to the CPU.

Diagrammatically, it would be:

Turnover Time

Having said that, the users would always want the waiting time and the turnaround time to be minimum in order to accomplish processing and outputting of the given jobs. But the CPU handles multi-jobs simultaneously and hence this isn’t possible or realistic. Jobs should be executed in first come first served (FCFS) basis and hence certain waiting time has to be allotted to the incoming jobs. Let’s assign these incoming jobs to be:

J1, J2, J3, J4 which would be incoming from ascending order, i.e: 1st J1 is fed to the CPU, then J2, J3 and finally J4. Hence the processing by the CPU should also be in accordance. That is if FCFS (First Come First Served) method is applied, J1 should be undertaken first and then the rest and hence the processing of J1 will be first then the rest. Applying that:

J1 = 15 time units of execution.
J2 = 8 time units of execution.
J3 = 10 time units of execution.
J4 = 3 time units of execution.

The jobs have been assigned with there respective time units of execution, that is each job is actually undertaken by the CPU at a certain time lapse, which until then it’s a waiting time. Assuming the jobs have arrived to the CPU progressively as J1, J2, J3 and then J4, I draw a general timeline:

 

Calculate Average Waiting Time

 

The above diagram shows the calculation part of the average job wait time. The calculation is simple, ignore the numbers and because it’s FCFS, start from ‘0’ for the Job 1 since Job 1 never waited, the others were in queue. The numbers given are for execution time that is the time interval the job took to get over with execution and hence the waiting time for each would be calculated as:

W (j1) = 0
W (j2) = 0 + 15 = 15
W (j3) = 15 + 8 = 23
W (j4) = 23 + 10 = 33


Total Wait time = 71
______________

The last 3 units of time wasn’t a wait time, it was the time taken for the 4th job to get over with execution, the 4th job already waited for 33 units of time for it’s turn to get execution scheduled. This process undertaken by the CPU is called Job Scheduling or simply Scheduling. That comes deep later, but to calculate the average waiting time, I need to consider all the jobs which are 4 items so:

71/4 = 17.75 is the average waiting time i.e: T (wa). Hence, T (Wa) = 17.75 time units for the above example on wait time average. Now, changing the sequential order of the incoming jobs. The CPU has no control over the incoming of the jobs, but what the CPU has control of is the order in which the jobs will be given a priority for execution. This could be decided by the CPU. So, consider the order below for jobs: (considering the same queue of jobs, the situation here is re-scheduling the jobs

J4 = 3 units of time
J2 = 8 units of time
J3 = 10 units of time
J1 = 15 units of time

In this case, the execution time remains the same, however the jobs are re-shuffled according to the CPU’s preference and the priority in taking up the job. Previously, the jobs were taken first come first served basis, but here even though the jobs arrived sequentially, the CPU has the authority and control of the execution land the processing of the jobs which were given by the user. The CPU decides to execute the job in the order such that J4 was executed first, next was J2, and then J3 and finally J4 was executed.

Considering the above situation, I now wanted to determine the average waiting time for such a schedule prescribed by the CPU because the CPU has the control on the scheduling part but does not have the control over the incoming jobs. To draw a rough sketch of just occurrences with a job execution and waiting timeline:

 

Scheduling without FCFS. Rescheduling with CPU’s control over Scheduling

 

Considering the image below I had drawn (MS paint, mind not!), the time taken for execution of the jobs in previous scenario were the same, but the scheduling was done by the CPU without FCFS method but taking in priority to which jobs has to be executed first to perform optimization. The magic happens here. Now if we calculate the waiting time:

W (J4) = 0 (since it arrived first)
W (J2) = 0 + 3 = 3 (since J2 had to wait for 3 units of time because 3 units of time were wasted {rather not!} in execution of job J4)
W (J3) = 3 + 8 = 11 (since J3 had to wait until J2 was finished executing with time lapse of 8 units)
W (J1) = 11 + 10 = 21 (since J1 had to wait for J3 to finish up with execution with time lapse of 10 units)

Hence;

W (J4) = 0
W (J2) = 3
W (J3) = 11
W (J1) = 21


Total Wait Time = 35 time units
________________________________

Now, if I calculate the average waiting time T (Wa) for this, that is 35/4, it comes to 8.75 time units. So:

T (Wa) = 8.75

which is far lesser in waiting time than the previous scenario. Calculating the optimization which had occurred here and the difference, our previous FCFS achieved 17.75 of waiting time, and this scheduling by the CPU achieved 8.75. The difference in wait time optimization being:

17.75 - 8.75 = 9.00 time units

A budget of total 9 time units.  So we find that just by changing the order, the same jobs were optimized. The average waiting time were reduced drastically so naturally the CPU would now prefer the second type of scheduling rather than the first scheduling. The user wold always prefer the first scenario but the CPU won’t allow that because it has to follow optimization rules. In the second scenario, there is a pattern why the average waiting time were drastically reduced. This is achieved by executing the jobs first which take lesser time for execution because the next queue of jobs will have to ‘wait’ lesser and hence optimization could occur.There are various objectives which could be achieved, the objective achieved here was to minimize the average waiting time for the jobs together to be finished in an optimized way.

So that’d be the very touch towards process management in this post. Next post, I’d bring some more fruits to the blog. The concepts of process management is vast and does not end with this basic post.  To keep updated if you like these posts, subscribe via mail or keep visiting the blog. Cheers out!

Advertisements

2 thoughts on “3. Operating System – CPU Management

  1. Pingback: 4. Operating System – Process State Diagram and CPU Scheduling Basics | Shritam Bhowmick

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

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