COP 4640 – Operating Systems Environments
ASSIGNMENT #1 Total Points: 45
1. Given that main memory is composed of three page frames for public use and that a program requests pages in the following order:
d c b a d c e d c b a e
a) Using the FIFO page removal algorithm, perform a page trace analysis indicating page faults with asterisks (*). Then compute the failure and success ratios.
b) Increase the size of memory so it contains four page frames for public use. Using the same page requests as above and FIFO as the page replacement algorithm, perform another page trace analysis and compute the failure and success ratios.
c) Did the result correspond with your intuition? Explain.
Use a table similar to the one given below to show your page trace analysis for question 1a.
Page request / d / c / b / a / d / c / e / d / c / b / a / ePage fault
Page Frame 1
Page Frame 2
Page Frame 3
Use a table similar to the one given below to show your page trace analysis for question 1b.
Page request / d / c / b / a / d / c / e / d / c / b / a / ePage fault
Page Frame 1
Page Frame 2
Page Frame 3
Page Frame 4
9 points
2. Given that main memory is composed of three page frames for public use and that a program requests pages in the following order:
a b a c a b d b a c d
a) Using the FIFO page removal algorithm, perform a page trace analysis indicating page faults with asterisks (*). Then compute the failure and success ratios.
b) Using the LRU page removal algorithm, perform a page trace analysis indicating page faults with asterisks (*). Then compute the failure and success ratios.
c) Which is better? Why do you think it is better? Can you make general statements from this example? Why or why not?
Use a table similar to the one given below to show your page trace analysis for questions 2a) and 2b).
Page request / a / b / a / c / a / b / d / b / a / c / dPage fault
Page Frame 1
Page Frame 2
Page Frame 3
9 points
3. Given a system with main memory and cache memory with the following characteristics:
Average Main Memory Access Time = 1200 nsec
Average Cache Memory Access Time = 100 nsec
Cost for cache memory = 0.01 cents per bit
Cost for main memory = 0.001 cents per bit
Answer the following questions:
a) What is the cost of 1 MB of main memory? Give your answers in dollars and cents.
b) What is the cost of 1 MB of main memory if it is implemented using cache memory technology? Give your answers in dollars and cents.
c) What is the hit ratio if the total number of requests is 200 and 130 of those are found in cache memory?
d) What is the Average Memory Access Time if the hit ratio is 80%? Give your answer in nsec.
5 points
4. Given the following information:
Job Number: 1 2 3 4 5
Job Arrival Time: 0 1 2 3 4
CPU Cycle: 10 2 3 1 5
Draw a timeline for each of the following scheduling algorithms.
a) FCFS
b) SJN
c) SRT
d) Round Robin (using a time quantum of 2, ignore context switching and natural wait)
Also compute the average turnaround time for each of the scheduling algorithms and determine which one gives the best result.
10 points
5. For the two systems described below, given that all of the devices are of the same type, and using the definitions presented in the discussion of the Banker’s Algorithm, answer these questions:
a) Determine the “remaining needs” for each job in each system.
b) Determine whether each of the systems is safe or unsafe.
c) If the system is in a safe state, list the sequence of requests and releases that will make it possible for all processes to run to completion.
d) If the system is in an unsafe state, state how it’s possible for deadlock to occur.
System A
System A has 12 devices; only 1 is available.
Job # Devices Allocated Maximum Required Remaining needs
1 5 6
2 4 7
3 2 6
4 0 2
System B
System B has 14 devices; only 2 are available.
Job # Devices Allocated Maximum Required Remaining needs
1 5 8
2 3 9
3 4 8
8 points
6. State how you would design and implement a mechanism to allow the operating system to detect which, if any, of the processes are starving.
4 points