1.
Three concurrent processes P1, P2, and P3 are running on a single processor system. Each process Pi, among other code segments, invokes a function Ai() only once during its execution as shown below. In addition, P3 invokes another function B3() at some point. B3() is placed sequentially after A3().
Process P1: Process P2: Process P3:
. . .
. . .
. . .
. . .
A1(); A2(); A3();
. . .
B1(); . .
We want to make sure that:
– A3() can start to execute only when both A1() and A2() have fully completed, and,
– B1() can start to execute only when A3() has fully completed.
Show how you can solve this problem using semaphores by providing pseudo-code (similar to what we gave in our semaphore problem examples in class)
Important: A1(), A2(), A3(), and B1() functions are given to you, but you cannot edit them. Add your pseudo-code in other places in the codes of P1, P2 and P3 (i.e., before and/or after A1(), A2(), A3() and B1()). Achieve the specified behavior by using semaphores. From a given process, you can’t call a function defined in another process. For full credit, you shouldn’t force the processes to execute in an order not specified in the question; for example you shouldn’t force P2 to wait for P1.
Make sure to indicate the initial values of all your semaphore vari
2.
A certain bank account is shared by multiple persons. That is, any of the account owners should be able to deposit money to or withdraw money from the account. The exact number of account owners is not given to you (and you don’t need to know it in order to solve this problem).
To prevent race conditions while accessing the shared account, you will write a monitor construct. The monitor will have two procedures: withdraw(X) and deposit(X). withdraw(X) will be executed by a transaction that deducts X dollars from the balance. Similarly, deposit(X) will be executed by a transaction that adds X dollars to the balance. Each of the processes can execute either withdraw() or deposit(). Assume the balance is initialized with the value of zero.
Your monitor construct should suspend the transaction (process) invoking the withdraw function if and only if there are no sufficient funds. The balance should never be negative during the execution.
Multiple withdraw operation(s) may be all suspended if the balance is low. Following a deposit, suspended withdraw operation(s) must be completed subject to the availability of funds. (For example, if balance = 100 and one process is suspended during the withdraw(500) transaction, a deposit of 200 dollars shouldn’t enable the completion of the pending withdraw operation.)
When possible, multiple suspended withdraw operation should be resumed after a deposit. You can resume the suspended withdraw processes in any order you want; however you should avoid situations where a process remains blocked even though the balance is large enough to complete its pending withdraw operation.
Write the monitor construct including withdraw(X) and deposit(X) procedures to solve this problem. You will assume that standard monitor wait and monitor signal operations are available for condition variables (as discussed during the lectures). If multiple processes are suspended on a condition variable C, the execution of C.signal() by Process A will resume the p
3.
Consider the following set of processes on a single-processor system.
Process Name Arrival Time CPU Burst Length
P1 0 12
P2 1 12
P3 6 3
P4 18 3
Show the Gantt chart for a system with multi-level feedback queue with the following rules (see the last paragraph on how you can give the Gantt chart information without drawing figures).
A newly arriving process joins the first queue, where Round Robin scheduling policy with Quantum Size = 4 is used.
If a process from the first queue does not complete within its first time quantum, it is demoted to the second queue where Round Robin scheduling policy with Quantum Size = 8 is used.
The processes in the first queue have higher priority than processes in the second queue. You will assume preemptive scheduling when solving this problem. Also, assume that a process executing in the second queue is immediately preempted if a new process arrives to the first queue.
Directions for giving Gantt charts in writing: Assume in your solution, the process A runs from time = 0 to 10, process B runs from time = 10 to 15, the CPU is idle from time = 15 to 20, and finally the process C runs from time = 20 to 25. Then you can write:
CPU: A [0, 10], B [10, 15], idle [15, 20], D [20, 25]
4.
Consider three processes P1, P2, and P3, all ready to run at time = 0. Each process has two CPU bursts, separated by a single I/O burst. When its first CPU burst is completed, each process requests a blocking I/O operation on an I/O device. It becomes ready for the second CPU burst only when its I/O burst completes.
The CPU scheduling policy is non-preemptive Shortest-Job-First (SJF). The system has only one CPU.
The lengths of the CPU bursts of the processes are given below:
P1 : 5 ms (each CPU burst)
P2: 8 ms (each CPU burst)
P3: 6 ms (each CPU burst)
When a process starts receiving service for I/O, its I/O burst takes 10 ms.
a. Assume each process Pi performs I/O on a separate I/O device Di. Assume FCFS scheduling on all I/O devices.Give the Gantt charts for the CPU, D1, D2, and D3 separately (See the note below on how to give timing information for Gantt charts without drawing a chart). Finally, give the average turnaround times for these processes.
b. Now, assume each process Pi performs I/O on the same I/O device D. Assume FCFS scheduling on the I/O device D.Give the Gantt charts for the CPU and D separately (See the note below on how to give timing information for Gantt charts without drawing a chart). Finally, give the average turnaround times for these processes.
Directions for giving Gantt charts in writing: Assume in your solution for the CPU, the process A runs from time = 0 to 10, process B runs from time = 10 to 15, the CPU is idle from time = 15 to 20, and finally the process C runs from time = 20 to 25. Then you can write:
CPU: A [0, 10], B [10, 15], idle [15, 20], D [20, 25]
5.
Consider the “Mutual Exclusion with Test-and-Set” solution we discussed in class (Slide 4.13).
If the TAS R1, LOCK instruction is replaced by the following two instructions, would the resulting code still satisfy Mutual Exclusion?
LOAD R1, LOCK
STORE LOCK, #1
Why or why not? To get credits, you must provide a correct justification: If you believe it still works, provide a valid argument. If you believe it no longer works, provide a concrete execution scenario with more than one process, in which one can clearly see that the mutual exclusion is not satisfied.
6.
Briefly explain the function of the medium-term scheduler. How can it improve the system performance? Explain your answer.