What is the CPU IO burst cycle? How does it motivate multi-programming?
What does it mean for a process to be CPU bound or IO bound?
(b) Consider a single processor system supporting two running processes, A and B,
with the following sequential execution patterns:
A: [CPU 8 ms; IO 1 ms; CPU 8 ms; IO 1 ms; CPU 8 ms]
B: [CPU 2 ms; IO 1 ms; CPU 2 ms; IO 1 ms; CPU 2 ms]
Assume that IO operations do not interfere with each other and are blocking,
and that scheduling and context switch times are negligible.
(i) What is the total elapsed time for the two processes to run to completion?
(ii) Assume the system runs a non-preemptive scheduler where processes are
scheduled in the order in which they become runnable, and that B takes
priority over A in the event of a tie. Give the combined execution pattern
of the two processes in the format as in part (b), and determine the total
elapsed time for the two processes to run to completion. [5 marks]
(iii) Repeat part (b)(ii) with a pre-emptive scheduler operating with a time slice
of 4 ms. [5 marks]
(iv) What are the costs and the benefits of a pre-emptive over a non-preemptive
scheduler for this workload, which would you choose, and why?

Transcribed Image Text:

Objective 1: Able to understand the RDT3.0 reliable data transfer protocol Key points: The protocol consists of two finite state machines (FSM), one for the sender, the other for the receiver The basic mechanisms that make reliable data transfer include checksum, receiver feedback, sender retransmission, duplicate detection (both for data packet at the receiver and for the ACK at the sender), countdown timer . . The protocol specification is described in terms of the FSM, which consists of the states at the sender and the receiver, and for each FSM, all possible events, and the corresponding actions, as well as the state transitions. Problem. Consider the rdt3.0 protocol we have studied. The partial finite state machine for the receiver is shown below (it is in fact identical to that of the rdt2.2 protocol): rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)) udt_send(sndpkt) Wait for O from below receiver FSM fragment rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt make_pkt(ACK1, chksum) udt_send(sndpkt) Let's say a student in the class studied the protocol and decided to change the protocol such that on receiving a duplicate or corrupt packet, no action is taken. What do you think about this modification of the rdt3.0 protocol? Is the new protocol going to be functioning correctly (i.e., can it ensure reliable data transfer under the same assumption of the original RDT3.0 protocol)? Please elaborate, that is, if you think the modified protocol still works, explain why omitting sending the ack when receiving a duplicate or corrupt packet does not matter, and on the other hand, if you think the protocol would stop working, describe a specific scenario that would violate the reliable data transfer guarantee. Objective 1: Able to understand the RDT3.0 reliable data transfer protocol Key points: The protocol consists of two finite state machines (FSM), one for the sender, the other for the receiver The basic mechanisms that make reliable data transfer include checksum, receiver feedback, sender retransmission, duplicate detection (both for data packet at the receiver and for the ACK at the sender), countdown timer . . The protocol specification is described in terms of the FSM, which consists of the states at the sender and the receiver, and for each FSM, all possible events, and the corresponding actions, as well as the state transitions. Problem. Consider the rdt3.0 protocol we have studied. The partial finite state machine for the receiver is shown below (it is in fact identical to that of the rdt2.2 protocol): rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)) udt_send(sndpkt) Wait for O from below receiver FSM fragment rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt make_pkt(ACK1, chksum) udt_send(sndpkt) Let's say a student in the class studied the protocol and decided to change the protocol such that on receiving a duplicate or corrupt packet, no action is taken. What do you think about this modification of the rdt3.0 protocol? Is the new protocol going to be functioning correctly (i.e., can it ensure reliable data transfer under the same assumption of the original RDT3.0 protocol)? Please elaborate, that is, if you think the modified protocol still works, explain why omitting sending the ack when receiving a duplicate or corrupt packet does not matter, and on the other hand, if you think the protocol would stop working, describe a specific scenario that would violate the reliable data transfer guarantee.