Operating Systems: Assignment 2 Solution

Problem 1




(10 pts) The processes are assumed to have arrived in the order of P1, P2, P3, P4 and P5 at time 0. Consider multi-level feedback queue scheduling where a process starts at rst level and then if it is not nished in its quantum, it is moved from Queue i to the next level queue (Queue-i + 1). Queue-1, which is the rst level queue, is given a quantum of 4ms, Queue-2 is given a quantum of 8 ms, Queue-3 is given a quantum of 12 ms, and Queue-4 is scheduled as FCFS.




Process
Burst Time (ms)




P1
10
P2
20
P3
27
P4
18
P5
30







Draw the Gantt chart illustrating the execution of these processes. Calculate the average turnaround time. Assume no context-switch overhead.


































































1
COMP 304- Operating Systems ( ): Assignment 2 PROBLEM 1







b) Calculate the average turnaround time when the context switch overhead is 1 ms.












































































Compare multi-level queue scheduling with the round-robin scheduling using only the rst level queue (queue-1) in terms of number of context switches. Which scheduling introduces less overhead? Show your work with by drawing the gantt chart for round-robin scheduling.












































































































Student Name: Page 2 of 4
COMP 304- Operating Systems ( ): Assignment 2 PROBLEM 3










#define MAX_LICENSES 5



int available_resources = MAX_LICENSES;



3

/* decrease available resources by count resources */
/* return 0 if sufficient resources available, otherwise return -1 */



6




int decrease_count(int count) {



8 i f (available_resources < count)




return -1;



10else {




available_resources -= count;



return 0;



}



}
/* increase available resources by count */



int increase_count(int count) {



available_resources += count;



return 0;



}






Problem 2




(6 pts) Many commercial software packages provide a given number of licenses, indicating the number of applications that may run concurrently. When the application is started, the license count is decremented. When the application is terminated, the license count is incremented. If all licenses are in use, requests to start the application are denied. Such requests will only be granted when an existing license holder terminates the application and a license is returned. The program segment is used to manage a nite number of instances of an available license.




The preceding program segment produces a race condition.




Identify the data involved in the race condition.



Identify the location (or locations) in the code where the race condition occurs.



Using a semaphore or mutex lock, x the race condition.






Problem 3




(15 pts) A well-known dentist has an o ce in Sariyer but he has a bad habit of taking several naps during day. His o ce consists of a waiting room with N chairs and the treatment room can accommodate only one patient. If there are no patients to be served, the dentist takes a nap. If a patient enters the dentist o ce and all chairs are occupied, then the patient leaves the o ce. If the dentist is busy with a patient but chairs are available, then the patient sits in one of the free chairs. If the dentist is asleep, the patient wakes him up. You can assume patients come in through one door and leave through the other. Only one patient can move at a time.
















Student Name: Page 3 of 4
COMP 304- Operating Systems ( ): Assignment 2 PROBLEM 5







Write a monitor (in pseudocode) that coordinates the dentist and its patients. Represents dentist and each patient as separate threads. Explain the purpose of using each semaphore, mutex or condition variable that you include in your solution.




In your implementation, have the following monitor procedures:




get dental treatment: called by the patient, returns when treatment is done







get next patient: called by the dentist to serve a patient







nish treatment: called by the dentist to let a patient out of the o ce










Problem 4




(15 pts) In this question, you will learn the di erences between fork, clone and pthread create. The thread(s) created simply executes a hello world function. Consider the code segment listed below:







pid_t pid;



2




pid = create_process(); //1
4 i f (pid == 0) { /* Child process */




create_process(); //2



...



create_thread(...); //executes hello world only



...



}



create_process();//3






Implement the above code using pthread create and linux fork() system call to create threads and processes respectively and determine



Number of unique processes created Number of unique threads created




Draw a process/thread tree and indicate processes as circles and the threads as rectangles.



Implement above code only using clone() system call for both creating threads and pro-cesses.









Problem 5




(4 pts) Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Is this system is deadlock free? Show your work.






















Student Name: Page 4 of 4