CS-350 - Fundamentals of Computing Systems
Final Exam
Fall 2022
Problem 1
Label each of the statements below with either True (T) or False (F):
Statement T/F
a. Two single-processor systems A and B have identical input tra c and mean service time. If the standard deviation of the service time in A is less than in B, A is expected to exhibit lower response time.
b. A discrete event simulator cannot be used to study the behavior of queuing systems with limited queue size, like an M/M/1/K system.
c. The input tra c to an M/M/1 queuing system must be Poisson-distributed. In which case, the output tra c will also be Poisson-distributed.
d. In a complex system, the resource which constitutes the bottleneck may vary over time if the behavior of the users changes.
e. A typical magnetic disk can be modeled as a stateful resource, and the same is true for a traditional DRAM memory controller.
f. In global real-time multi-processor scheduling, tasks are never allowed to migrate from one processor to another to prevent deadline misses.
g. In a system where real-time scheduling is performed, no more than two processes can be in the ready state at the same time.
h. Performing a signal operation on a semaphore might trigger a state transition from blocked to ready in some process.
i. Like Dekker's Algorithm, the Peterson's Algorithm guarantees 2-party mutual ex- clusion on in-order CPUs.
j. FIFO and SJN are non-preemptive and work-conserving schedulers, therefore they always perform identically in terms of average response time.
k. If resource A has higher availability than B, then A will likely operate continuously and correctly over a longer time window compared to B.
l. Consider two jobs that have waited inside the ready queue for the same amount of time before being processed. Their slowdown might still be di erent.
m. If the average response time of a resource at steady-state is Tq , then its average throughput can be computed as 1/Tq .
n. Only at most 4 processes can be involved in a deadlock.
o. EDF-FF is always capable of producing a valid task-to-CPU assignment for tasksets where RM-FF fails to do so.
p. EDF and RM are both instances of static-priority real-time schedulers.
q. If a process is unable to enter a critical section protected by a spinlock, it will perform busy-waiting until it is able to do so.
r. When using Exponentially Weighted Moving Averages (EWMA) with parameter Q = 0.5, only the most recent 5 observations determine the next predicted value.
Note: There are 18 questions. A correct answer will get you 2 points; an incorrect answer -1 points; a blank answer 0 points. The score is capped at 24.
Problem 2
A system accepts requests from a pool of in nite users. These have been found to submit, in total, 2000 requests per second. The inter-arrival time between any two consecutive requests is exponentially distributed.
All the requests initially arrive at the pre-processing (PRE) server. The PRE server is a dual-processor machine that uses a single global queue to hold pending requests. The next request in order of arrival is dispatched for service to one of the two processors as soon as one becomes available. The service time of each request is exponentially distributed with mean 0.6 milliseconds.
Only after completing service at the PRE server the request type is known by the system. With 80% probability, the current request needs incremental processing. In this case, it is routed to the single-processor INC machine. Service at the INC server takes, on average, 0.36 milliseconds. After completing service at the INC server, 55 out of 100 requests (on average) require no further service and leave the system. Otherwise, upon leaving the INC server, they are routed back to the PRE machine as if they were new requests.
If, after processing at the PRE stage, the request is determined to be of bulk type, it is routed to the BLK server. The BLK server is a single-processor machine which takes on average 1.58 milliseconds to serve a request. After completing processing at the BLK machine, a request always leaves the system.
(a) [3 points] Provide a diagram of the system which shows the inter-connections between the PRE, INC, and BLK machines. Describe the queuing models used for each machine, the known parameters, and the assumptions you will employ to solve the system.
(b) [5 points] Which resource (i.e., PRE, INC, or BLK) constitutes the bottleneck of the system? Motivate your answer.
(c) [5 points] What is the average response time for a generic request arriving at the system?
(d) [5 points] What is the total time spent by a generic request waiting for service inside the system, on average?
Problem 3
A traditional magnetic disk is shared by two processes, namely P1 and P2. The disk sched- uler can be process-aware, in which case it must keep track of which process has submitted each pending request.
Table 1 reports a list of requests submitted by P1 and P2, along with their target cylinder ID and arrival time (in μs).
At time 0, the disk head is positioned at cylinder 5. The disk has 13 cylinder in total, numbered 0 through 12. Once the disk head is in position, it takes 0 μs to serve a request. The disk head can move by 1 cylinder for every μs.
If any of the schedulers you will consider below develops any tie, break ties by lowest process ID rst.
P1 Requests
|
#
|
Arrival (us)
|
Cylinder ID
|
|
1
|
1
|
2
|
|
2
|
2
|
3
|
|
3
|
3
|
8
|
|
4
|
7
|
0
|
|
5
|
9
|
0
|
P2 Requests
|
Arrival (us)
|
Cylinder ID
|
|
1
|
6
|
|
2
|
7
|
|
6
|
4
|
|
8
|
6
|
|
9
|
7
|
Table 1: List of disk requests submitted by P1 and P2.
(a) [6 points] A pending request is considered ready if, at the time when the scheduling decision is made, it targets a cylinder ID which is within ±1 from the current disk head position. Use the grid below to draw the schedule produced by the FR-FCFS scheduler. The FR-FCFS is NOT process-aware, so it will consider all the requests together regardless of the originating process.
(b) [6 points] Schedule the pending disk requests using Priority-based SCAN. If any P1's pending request exists when the scheduling decision is made, P2's requests are ignored and P1's request are served following SCAN. P2's requests are also served following SCAN but only if no P1's requests are pending. Consider an implementation of SCAN in which the disk head does not need to reach the top/bottom cylinder ID in order to switch direction.
(c) [6 points] Schedule the pending disk requests using Round Robin scheduling. The scheduler keeps P1's and P2's requests in two separate queues and in their order of arrival. It then serves a SINGLE request for the process that has been waiting the longest since the last time one of its requests was served.
Problem 4
A robotic surgery machine uses four periodic tasks to control the trajectory of the multi-joint robotic arm that performs incisions. Joint position (JP) is sensed at a rate of 200 Hz and it takes 2 millisecond to be performed. Next, actuation commands (AC) to all the joints are forwarded at a rate of 100 Hz, taking a total of 2 milliseconds to complete. Image recognition (IR) to detect safe operation boundaries is carried out every 13 milliseconds and takes 2 ms to complete. Finally, trajectory planning (TP) is performed every 15 milliseconds and takes 3 milliseconds.
NOTE: in all the questions below, if you decide that you need to draw the schedule, make conclusions about schedulability based on what you observe between time 0 ms and 30 ms.
(a) [4 points] Assume that we want to schedule the system using Earliest Deadline First (EDF) on a single-processor system. Is the system schedulable? Use the grid below only if strictly needed.
(b) [4 points] Assume that we want to schedule the system using xed-priority preemptive scheduling on a single-processor system. The priority are assigned as follows, from highest priority to lowest priority: JP, TP, AC, IR. Is the system schedulable? Use the grid below only if strictly needed.
(c) [5 points] Assume that we want to schedule the system using xed-priority preemptive scheduling on a single-processor system. The priority are assigned as follows, from highest priority to lowest priority: JP, AC, IR, TP. Is the system schedulable? Use the grid below only if strictly needed.
(d) [5 points] Assume that we want to schedule the system using Non-Preemptive Rate Monotonic (NP-RM) on a single-processor system. This scheduler is identical to RM, except for the fact that preemptions are NOT allowed. Is the system schedulable? Use the grid below only if strictly needed.
Problem 5
What follows are a number of template implementations for multi-producer/single-consumer and multi-producer/multi-consumer interactions between processes. The processes are able to share data structures such as semaphores and queues. But queues need to be appropriately protected against data races if shared between two or more processes.
You are tasked with completing the code to ensure the safe implementation of the intended logic, while maximizing the degree of parallelism. Each blank line can contain at most one statement; but not all the blank lines might need to be lled. You also need to provide the initialization value of any variable for which an initialization value is not already provided in the code.
(a) [8 points] A rst solution involves N > 1 Producer processes. All the producers append new integer values in a queue called the input_queue. A single Consumer pro- cess pops values from the input_queue, performs some computation with the retrieved value, and appends the result into a second queue, called output_queue. Complete the code of the rst solution using semaphores.
(b) [8 points] A second solution involves N > 1 Producer processes as well as M > 1 Consumer processes. Once again, the producers append new integer values in a queue called the input_queue. Consumer processes pop values from the input_queue, per- forms some computation with the retrieved value, and appends the result into a second queue, called output_queue. Complete the code of the rst solution using semaphores.
Problem 6
Consider as system with 5 processes P1 , . . . P5 sharing 3 resources R1 , . . . , R3 .
(a) [5 points] The immutable system parameters are provided in Table 2, while the state of the system at a given point in time is provided in Table 3. Complete the tables with the missing parameters.
(b) [5 points] Determine if the current state would be deemed safe by the Banker's Algo- rithm for deadlock avoidance. Provide your reasoning for full marks.
(c) [6 points] While the system is in the state described by Table 2 and 3, P5 submits an allocation request for 4 units of R1 , 2 unit of R2 , and 0 unit of R3 . Can the request be safely granted? You may use Table 6 to answer the question.