Homework #2

43. Measurements of a certain system have shown that the average process runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For round-robin scheduling with quantum Q, give a formula for the CPU efficiency for each of the following: a. Q=∞
Answer:
No involuntary context switches will occur. Each process will pay 1 context switch per CPU burst.

Efficiency=TT+S

b. Q>T
Answer:
As long as the quantum Q is larger than T, then no involuntary context switches will occur.

Efficiency=TT+S

c. S<Q<T
Answer:
Efficiency=QQ+S

d. Q=S
Answer:
Efficiency=QQ+S=Q=50%

e. Q nearly 0
Answer:
Efficiency=0%

44. Five jobs are waiting to be run. Their expected run times are 9, 6, 3, 5, and X. In what order should they be run to minimize average response time? (Your answer will depend on X.)
Answer:
For X, 3, 5, 6, 9 order: 0<X≤3
For 3, X, 5, 6, 9 order: 3<X≤5
For 3, 5, X, 6, 9 order: 5<X≤6
For 3, 5, 6, X, 9 order: 6<X≤9
For 3, 5, 6, 9, X order: 9<X

45. Five batch jobs. A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead.

a. Round robin. b. Priority scheduling. c. First-come, first-served (run in order 10, 6, 2, 4, 8). d. Shortest job first.

For (a), assume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For (b) through (d), assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
Answer:
a. Round Robin. Preemptive multiprogramming. Each job gets its fair share of CPU.

Initially, all five processes are running, so they each get 15 of the CPU, which means they take 5 times longer to run. This means that it will take 10 minutes for C (the shortest job) to complete.

After 10 minutes each job will have used 2 minutes of CPU time each, so A will have 8 minutes left, B 4, D 2, and E will have 6. Since there are now 4 jobs they will each get 14 the CPU time, which means they will take four times as long to run. So, it will take 8 minutes for D to complete. (So, D took 10+8=18 minutes.)

Now, A will have 6 minutes left, B 2, and E 4. Each process gets 13 of the CPU. Hence, B will complete execution in 6 minutes. (B took 10+8+6=24 minutes.)

Now, A will have 4 minutes and E 2 minutes left. Each process gets 12 of the CPU, so E will finish executing in 4 minutes. (E took 24+4=28 minutes.)

Since A has only 2 minutes left to run and it is the only job on the CPU, it will finish in two minutes with a total time of 28+2=30 minutes.

Averaging, we get 10+18+24+28+305=1105=22 minutes average turnaround.

b. Priority. Each job runs to completion without being preempted.

Since B has the highest priority it will run first, followed by E, followed by A, followed by C, and finally D. There is no preemption, so B completes after 6 minutes, E after 6 minutes of waiting for B and 8 minutes of processing (14 minutes total), A after 14 minutes of waiting for B and E, and 10 minutes processing (24 minutes total), C after 24 minutes of waiting for B, E, and A, and 2 minutes processing (26 minutes total), and D after 26 minutes of waiting for B, E, A, and C and 4 minutes of processing (30 minutes total). The average is 6+14+24+26+305=1005=20 minutes.

c. First Come First Served. Processes run to completion in the order of arrival.

A completes after 10 minutes, B completes after 10+6=16 minutes, C completes after 16+2=18 minutes, D completes after 18+4=22 minutes, and E completes after 22+8=30 minutes.

The average is 10+16+18+22+305=965=19.2 minutes.

d. Shortest job first. Processes will run to completion in the order: C, D, B, E, A

C completes after 2 minutes, D completes after 2+4=6 minutes, B completes after 6+6=12 minutes, E completes after 12+8=20 minutes, and A completes after 20+10=30 minutes.

The average is 2+6+12+20+305=705=14 minutes.

49. The aging algorithm with a=12 is being used to predict run times. The previous four runs, from oldest to most recent, are 40, 20, 40, and 15 msec. What is the prediction of the next time?
Answer:
If it take all four previous run times into consideration, the prediction is 40+202+402+152=30+402+152=35+152=25 or if it take only two previous run times into consideration, the prediction is 40+152=27.5.

50. A soft real-time system has four periodic events with periods of 50, 100, 200, and 250 msec each. Suppose that the four events require 35, 20, 10, and x msec of CPU time, respectively. What is the largest value of x for which the system is schedulable?
Answer:
35500+20100+10200+X250<1
1920+X250<1
475+2X500<1
475+2X<500
2X2<252
X<12.5

To be schedulable, the fraction of CPU used should be <1, so X should be <12.5.