ASSIGNMENT I MENU

Question number 1
a. Using FCFS method to find completion time of each jobs
b . Turn around time  . . . of each job

Question number 2
a . SJF algorithm
b . SRTF algorithm
c . Round Robin method

Question number 3
a . Non-preemptive priority algorithm
b . Preemptive priority algorithm

Question number 4
Write a paragraph about the life of a process
 

1. Consider the following jobs:
 

Job
Arrival time
Run time
A
0
5C, 3I, 4C, 5I, 3C
B
2
3C, 6I, 4C
C
6
4C, 3I, 7C
 
7
 
A
8 = 5C + 3I
 
 
.
.
.
 
B
14 = 5C + 3C + 6I
 
C
15 = 5C + 3C + 4C + 3I
 
 
.
.
.
 
A
21 = 5C + 3C + 4C + 4C + 5I
 

a. Using the FCFS method, compute the completion time of each job:

We only have to concern about the arrival times (see table) of given jobs and run them completely in FCFS format.  Therefore, the given job will be run in this order: A, B, C, A, B, C, A
            -*- The Gantt chart:
        From the Gantt chart, we have:

                  Completion time of job A = 30
                  Completion time of job B = 20
                  Completion time of job C = 27

Back to Menu
b. Using the results in (a) compute the turn around time for each job:

        Apply the formula:

 
Turn around time = Completion time - Arrival time
        Apply the formula:
 
Weighted turn around time    =
Turn around time
---------------------------
Run time
 
Weighted turn around time of job A    = 
30
-------------
5 + 4 + 3
 = 
30
-------
12
  =   2.5
         
CPU utilization    =
 30 x 100 %
-----------------
30
  =    100 %
Back to Menu
2. Consider the following jobs:
 
Job
Arrival time
Run time
A
0
5
B
2
5
C
3
4
D
6
2

a. Using SJF method, compute the completion times of the jobs and average

Run the first job, job A, completely.  After job A is finished running, the time is only 5.Choose the shortest job in the rest three jobs; B, C, D which has already arrived with the arrival time is less than or equal 5.  By this reason, we cannot choose D because its arrival time is 6 even its run time is the shortest one, 2.  Therefore, we have to choose job C and let it runs completely.After job C is finished running, the time is 9, completion time of  job A is 5 and job C is 4 .  Hence, we don't care about the arrival time of the rest two jobs; B's arrival time is 2, and D's arrival time is 6.  We only have to concern about which one has the shortest run time.  Thus, we choose D, and run it completely at time 11.

Finally, B is the last job. We complete it at time 16.

From the Gantt chart, we have:
Completion time of job A = 5
Completion time of job B = 16
Completion time of job C = 9
Completion time of job D = 11
        From the Gantt chart and the given data table, we have:
 
Waiting time 
= 0 + (11 - 2) + (5 - 3) + (9 - 6)
= 0 +       9     +      2     +     3 
= 14
 =>   Average waiting time   = 
14
----------- 
   =   3.5
Back to Menu
b. Using SRTF method, compute the completion times of the jobs and average waiting time
SRTF is SJF with preemption.

First, we run the first job, job A.

At time 2, job B arrives.  The remaining time of job A is 3 while the run time of job B is 5.  Thus, job A continue its running.

At time 3, job C comes.  Now, the remaining time of job A is 2, and C's run time is 4.  Job A still is continued until the time is 5.  Therefore, job A is finished at 5.

At the time job A is finished, the time is 5, there are only two jobs are available to be run; job B and job C.  Hence, we choose one of them which has the shorter running time, job C (B's running time is 5, and
C's running time is 4).

Job C runs until time 6, and its remaining time is 3.  At this time, job D comes.  Compare C's remaining time and D's running time, we see that job D should be run (D's running time is 2).

Now, we don't have to concern about the job's arrival time any more.  We only have to think about which job has the shortest running time (or remaining time).  The jobs will be run completely in order.  Start with the job which has smallest running time (or remaining time) to the biggest one.  Thus, job D runs completely first, and next is job C.

Finally, job B is the last one.  Check the data table and the Gantt chart for clearer information.

From the Gantt chart, we have:

Completion time of job A = 5

Completion time of job B = 16

Completion time of job C = 11

Completion time of job D = 8

From the Gantt chart and the given data table, we have:

Waiting time 
= 0 + (11 - 2) + (5 - 3) + (8 - 6) + (6 - 6) 
= 0 +     9      +     2     +     2     +     0 
= 13
=>   Average waiting time = 
13
----------
4
  =  3.25
Back to Menu
c. Using the Round Robin method (with time slice = 2 units), compute the time of jobs:
In this problem, first we have to concern about the arrival times of given jobs.  Second, we have to determine the time the current running job is kicked out because the time slice is over, especially the job is still not finished.  The time when that job was kicked out is its next arrival time.  By this technique, we have the table below.  Just one by one, run the jobs completely in FCFS order.
 
Job
Arrival Time
Run Time
A
0
5
B
2
5
A
2
3 (Remaining time)
C
3
4
B
4
3 (Remaining time)
D
6
2
A
6
1 (Remaining time)
C
8
2 (Remaining time)
B
10
1 (Remaining time)

                    From the Gantt chart, we have:

                    Completion time of job A = 13

                    Completion time of job B = 16

                    Completion time of job C = 15

                    Completion time of job D = 10

                    From the Gantt chart and the given data table, we have:

Waiting time 
=   (4 - 2) + (12 - 6) + (2 - 2) + (8 - 4)
    + (15 - 10) + (6 - 3) + (13 - 8) + (10 - 6)
=   2 + 6 + 0 + 4 + 5 + 3 + 5 + 4
=   29
 =>   Average waiting time  = 
29
---------
4
=  7.25
Back to Menu
3. Assuming that Job A has low priority, Job B has medium priority, and Job C & D have high priority:
 
Priority
Job
Arrival time
Run time
Low
A
0
5
Medium
B
2
5
High
C
3
4
High
D
6
2
a. Using non-preemptive priority algorithm, compute the completion times of each jobs and the average waiting time

In non-preemptive priority algorithm, if one job is chose, it will be run completely.  The first job, job A, is always chose first because it is the only job comes at that time.  In case two or several jobs those come at the same time, we have to concern about their priorities.  In this problem, we don't have this case.  Thus, job A is chose and run completely.

When we concern about the jobs' priority we have to choose the job which has highest priority (depend on the set up of system which is used to run these jobs, some systems choose the lowest priority) and run it completely. If two or several jobs have the same priority, we have to think about their running times and arrival times; choose the job which has already come and its running time is the shortest.  Do the same like this for next job until the last job is run.

As I said before, in this problem, job A is chose and run completely at time 5, and the rest three jobs are B, C, D.  We see that job C and job D have the same high priority, so we have to concern about their running times and arrival times.  Job D has the shorter running time, 2, but it has not come
yet (its arrival time is 6 while the time now is 5).  Job B was not chose because its priority (Medium) is lower than the priority of job C and job D (High).  Therefore, we have to choose job C is the second job and run it completely at time 9.

After job C is finished, we only have 2 jobs, B and D.  At this time, job D can be run first because its priority is higher than job B's priority.  And it is finished at time 11.

Finally, job B is the last one and it is finished at time 16.

From the Gantt chart, we have:

Completion time of job A = 5

Completion time of job B = 16

Completion time of job C = 9

Completion time of job D = 11

From the Gantt chart and the given data table, we have:

Waiting time 
= 0 + (11 - 2) + (5 - 3) + (9 - 6)
= 0 +       9     +      2     +     3
=  14
=>   Average waiting time    =
14
----------
4
=   3.5
Back to Menu
b. Using preemptive priority algorithm, compute the completion times of each jobs and the average waiting time
In preemptive priority algorithm, first we have to concern about the arrival times of coming jobs.  compare the first current coming job's priority with the priority of the current running job.  If the current running job's priority is smaller, the current running job has to stop its running, and the one just come is run.

If there is no job comes during the running time of one job, that job can be continued to run completely.  Otherwise, do the same like the step above until the last job comes.

After the last job has come, the remained jobs will be run in the same algorithm as non-preemptive priority algorithm. (see non-preemptive priority algorithm)

In this problem, job A is the first job (its arrival time is 0). It runs until time 2, and job B comes.  Job A has to stop because its priority (Low) is smaller than job B's priority (Medium).  At time 2, remaining time of job A is 3.

Job B runs until time 3, and job C comes.  Job B has to stop its running because its priority is lower than . . . . At this time, job B's remaining time is 4.

Job C runs until time 6, job D comes.  At this time, job C's remaining time is 1 is smaller than job D's running time.  Therefore, job C can continue to run because job C and job D have the same priority (High).  Since, job C is run completely at time 7.

Now, job D is run first (its priority is the highest), next is job B (its priority is Medium), and the last one is A.

From the Gantt chart, we have:

Completion time of job A = 16

Completion time of job B = 13

Completion time of job C = 7

Completion time of job D = 9

From the Gantt chart and the given data table, we have:

Waiting time 
= 0 + (13 - 2) + (2 - 2) + (9 - 3) + (3 - 3) + (7 - 6)
= 0 +      11     +     0     +     6     +     0      +    1
=  18
=>   Average waiting time    =
18
----------
4
=   4.5
Back to Menu
4. Write a paragraph about the life of a process

            The life of a process is like the activities of an auto repair center
 

New: The driver drives his car to the auto repair center entrance and asks to enter.
Ready: The car is in the garage and waits for serving.
Interrupt: Garage manager asks the driver what he can help.
Running: And then he checks for the vehicle number, model, make, year . . .
Interrupt: Garage manager asks the driver to go inside to sign the paper.
Running: And then he lets a mechanic do the customer's request (the driver's request).  Example:  Checking the brakes.
I / O waiting: The driver is waiting for the estimated information.
Running : The mechanic is checking the brakes.
Interrupt: The mechanist found something wrong with the brakes.  The brakes' life time are over.  The garage manager asks the driver if he wants to change new ones.  The driver agrees to make the changing.
Running: And then the mechanist replaces the old brakes with the new ones.
I / O waiting: The driver is waiting in the waiting room.
Ready: The mechanist finishes brakes changing, and the car is ready for the driver.
Interrupt: The customer (driver) asks for a road test to make sure if the brakes are done well.
Running: The mechanist and the customer are in the car.  The customer is driving and trying to apply the brakes.
I /O waiting: The driver and the mechanist are waiting for a good brake.
 Ready: Then, they are sure the brakes were done well, and they return to the garage.
Interrupt: The garage manager gives the customer the bill.
Running: The driver goes to the cashier to pay the bill and get the change.
Terminated: The driver says "good bye" to the garage manager and "thank you" for the good service .  And then he takes his car and drives away.
Back to top