Operating System

Class Projects. CS630 Operating Systems, 10/5/15 Karl W. D. Seifert

1. (40 pts) Given the following actual CPU burst for a task, {6, 4, 6, 4, 13, 13, 13}, and an initial "best guess" at the burst as 10, develop a simulation to predict the length of the task's next CPU burst using the following formula. Execute the simulation using an αof 0.1, 0.5, and 0.9. Include in the simulation the calculation of average burst time for each α and its comparison with the "true" average.

τ = α t + (1 – α) τ

n+1 n n

2. (40 pts) Develop a simulation program to implement the FCFS, SJF and RR scheduling algorithms utilizing data from deterministic modeling. Determine process start, stop times; wait times and overall average wait time for each process.

Process Burst for quantum = 1, 3, and 10.

P1 10

P2 1

P3 2

P4 1

P5 5

Also run simulation of FCFS, SJF and RR against P1 – P5 of (10, 29, 3, 7, 12) for quantum = 1, 3, 5.

3. (40 pts) The Poisson function,

r -C

P(r) = C * e / r! where C = the distribution average, is useful for modeling a distribution when the probability of any one occurrence of P(r) is extremely small and r is the number of occurrences of the event. Applying this average to message volumes and interarrival rates, C = λ * T where λ = message volume and T = interarrival rate, would imply:

r (- λT)

P(r) = (λ T) * e / r!

Assume the special case r = 0 (no messages arrive for a specific length of time) -- ie

0 (- λT) (- λT)

(λT) * e / 0! = e

t=T

Let us say that ∫ f(t)dt represents the probability of "one arrival within T units of

t=0

time after prior arrival." Therefore the probability of no messages

(- λT) t=T t=T (- λT)

e = 1 - ∫ f(f)dt and ∫ f(t)dt = 1 - e

t=0 t=0

For purposes of simulation let the integral be represented by a random number RN such that 0 <= RN < 1.

(- λT) (-λT)

Thus 1 - e = RN, (1 - RN) = e , LN(1 - RN) = - λT and

-1/ λ * LN(1 - RN) = T = interarrival time.

Develop a simulation program to accomplish the following:

1) Ask for and accept message volume per hour, Lambda.

2) Convert this volume to message volume per second, Lambda/3600.

3) Ask for and accept the number of simulations desired.

4) Ask for and accept a random number generator seed.

5) Perform the simulation loop to determine and print interarrival

times for Lambda where RN is determined by a random number

generator function.

6. Compute the average message interarrival time = sum of all interarrival times / count.

Use volumes of 3600 and 7200 with 100 simulations each.

4. (40 pts) Code the Bankers' algorithm for deadlock avoidance as described in lecture. Apply this algorithm against the following data displaying the Work, Need and Allocation matrices for each pass of the algorithm provided a safe state exists.

Process Allocation Max Available

A B C D A B C D A B C D

P0 0 0 1 2 0 0 1 2 1 5 2 0

P1 1 0 0 0 1 7 5 0

P2 1 3 5 4 2 3 5 6

P3 0 6 3 2 0 6 5 2

P4 0 0 1 4 0 6 5 6 Against request of (1,0,0,0) for P2.

Do the same for the following data:

Process Allocation Max Available

A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2

P1 2 0 0 3 2 2

P2 3 0 2 9 0 2

P3 2 1 1 2 2 2

P4 0 0 2 4 3 3 Against requests of (1, 2, 1) and (3, 3, 0). For P0.

5. (40 pts) Implement the FIFO and the LRU virtual memory page replacement algorithms as described in lecture against the following reference string:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 for a page file of 3 and a page file of 5. Show the number of page faults for each simulation. Do the same for the following reference string: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 for a page file of 3.

6. (40 pts) Develop a program to determine the average seek length for the FIFO, SSTF, and SCAN and C/SCAN disk scheduling algorithms. Use the following simulation queue: 55, 58, 39, 18, 90, 160, 150, 38, 184. In addition to determining average seek length, show the processing order for each queue entry for each algorithm.

7. (40 pts) Develop a program to perform a monoalphabetic substitution cryptographic cipher implementation using the following keyword “welcome”.

Encrypt and decrypt the following statement, “these are the times that try mens souls”.

Analysis assignment (20 pts).

Part 1 Develop the pseudo code for the Bakery deadlock avoidance algorithm.

Part 2 Develop the pseudo code for the OPT (Optimal) page replacement algorithm.