Description
Problem 1
(20 points) Consider the following set of processes, with the length of the CPU-burst time
given in milliseconds:
Process Burst Time Priority
P1 8 3
P2 5 1
P3 3 3
P4 1 4
P5 10 2
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
a) Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF,
a non- preemptive priority (a smaller priority number implies a higher priority), and RR
(quantum = 4 ms) scheduling.
b) If the context-switch overhead is 1 ms, calculate the waiting time of each process for
each of the scheduling algorithms in part (a). Which of the schedules results in the minimal
average waiting time?
c) Calculate average turnaround time for each of the scheduling algorithms in part (a).
Assume no context-switch overhead.
Problem 2
(20 points) Now assume that the context-switching overhead is equivalent to 0.5 ms. Calculate the CPU utilisation for all four scheduling algorithms in Problem 1.
1
COMP 304- Operating Systems ( Spring 2019): Assignment 2 PROBLEM 4
1 //PROBLEM 3
2
3 #define MAX_CONNECTIONS 5000
4 int available_connections = MAX_CONNECTIONS;
5
6 /* When a thread wishes to establish a connection with the server,
7 it invokes the connect() function:*/
8
9 int connect() {
10 i f (available_connections < 1)
11 return -1;
12 e lse
13 available_connections–;
14 return 0;
15 }
16
17 /* When a thread wishes to drop a connection with the server,
18 it invokes disconnect() */
19 int disconnect() {
20 available_connections++;
21 return 0;
22 }
Problem 3
(20 points) Consider the code example above that creates threads for opening connections
at a server.
a) Identify the race condition(s) in the provided program.
b) If you have identified any race conditions, use locks to prevent the race condition(s).
Provide the code snippet.
c) To prevent race condition(s), could we replace the integer variable available connections
with atomic integer, which allows atomic update of a variable of this type? Explain your
answer.
atomic t available connections = MAX CONNECTIONS;
Problem 4
(20 points) A hotel management would like to use online reservation system for their rooms.
The hotel has M rooms available for online reservation. If all the rooms are occupied, the
hotel will not accept any more customers until a room becomes available again (a party
leaves the hotel).
Give an algorithm for the hotel using semaphore primitives to limit the number of reserved
rooms so that it does not exceed M. Note that a room can accommodate up to 4 customers.
If a party more than 4 customers arrives, multiple rooms may be needed. If the required
number of rooms is not available, the room request for the entire party will be declined.
Provide a pseudo-code and briefly explain your algorithm in a short paragraph.
Student Name: Page 2 of 3
COMP 304- Operating Systems ( Spring 2019): Assignment 2 PROBLEM 5
Problem 5
(20 points) Suppose processes P and Q share data item d1, processes Q and R share data
item d2, and processes R and S share data item d3. Show how these processes can use
semaphores to coordinate access to data items d1, d2, and d3 so that critical section problem
does not occur. Show the codes for four processes, and explain the semaphores that you use
and their initial values.
