Deadlock/Scheduling/Virtual Memory - Operating Systems
PROBLEM A:
Write a program to model deadlock detection. The program will accept a list of processes, resources, requests, and releases in the following format:
A req R
A req S
A rel R
A rel S
B req S
B req R
B rel S
B rel R
The program will then produce possible orderings of the resource requests/releases. Orderings within a process cannot be rearranged (so A must always request R before it can request S in the example above), however orderings across processes can be rearranged (B can request S and R before A requests R). Each ordering will be output with a header, the ordering, and an indication if the order causes a deadlock or not.
For example:
ORDER 1: A req R, A req S, A rel R, A rel S, B req S, B req R, B rel S, B rel R ORDER 2: A req R, A req S, A rel R, B req S, A rel S, B req R, B rel S, B rel R
...
ORDER x: A req R, B req S, A req S, B req R DEADLOCK!
Try your program with the following input files:
--------------File 1------------
A req R A req S A rel R A rel S B req S B req R B rel S B rel R
--------------File 2------------
A req R A req S A rel R A rel S B req S B req T B rel S B rel T C req T C req R C rel T C rel R
PROBLEM B:
Design, implement, and gather results for a set of experiments to determine:
- the OS quantum
- the OS context switch overhead
Hints (you can ignore these if you have your own idea):
- Use a HIGH RESOLUTION TIMER
- You may need more than one thread/process for this
- You can look up the number of context switches that process has performed
- For the quantum measurement, you want your thread/processes to be doing work, you can also check your result against: sched_rr_get_interval. This method may work for you... I've had some success with it... however I've also had students with problems with this method... it simply returns a quantum of 0. Try it.
- For the context switch overhead measurement, you want your thread/process to not be doing work
Place your results in a README.TXT file.
PROBLEM C:
Write a program that simulates a paging system using the following reference string: 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1
Assume that the computer can hold only FOUR page frames at any one time. Your program should output the number of page faults when simulating the following page replacement algorithms:
- Optimal (do not hard code this, you must determine this from the reference string in your program)
- FIFO
- LRU
Based on the results from the simulation. Which algorithm is the best? Which algorithm is the worst? Why?