C Programming Disk Scheduling Lab-Harvard University .

Disk Scheduling Lab This lab project addresses the implementation of IO-scheduling algorithms in an operating system. Each IO request in an operating system is managed by using a data structure called the Request Control Block (RCB). An RCB contains the request ID, arrival timestamp, cylinder, address, and the ID of the process that posted the request. The RCB struct is defined as follows and is accessible from the rest of the code in this lab project by including the header file oslabs.h in your source code files: struct RCB { int request_id; int arrival_timestamp; int cylinder; int address; int process_id; } The set of IO requests in the operating system that are to be processed are tracked in an IO Request Queue. This data structure is an array of RCBs of the requests. The NULLRCB is defined as [RID:0, AT:0, CYL:0, ADDR:0, PID:0] To determine the schedule of servicing the IO requests in an operating system, we consider three policies: 1. First-Come-First-Served Scheduling (FCFS) 2. Shortest-Seek-Time-First Scheduling (SSTF) 3. LOOK Scheduling (LOOK) In order to implement the above policies, we need to develop methods that handle the arrival of IO requests and the completion of IO requests. That is, when a new IO request arrives, we need to figure out whether to service it immediately or to store it in the IO Request Queue. Whenever an IO request is completed, we need to figure out the next request from the IO Request Queue that needs to be serviced. The details of these methods are described below in the specification and you need to develop code for these methods that follow the specification and place the code in a file named disk.c. You should include the oslabs.h file. handle_request_arrival_fcfs This method implements the logic to handle the arrival of a new IO request in a First-Come-First-Served Scheduler. Specifically, it takes five inputs: 1. 2. 3. 4. 5. the request queue (an array of RCB structs) The number of items in the request queue the RCB of the currently-serviced request the RCB of the newly-arriving request the current timestamp. The method returns the RCB of the newly-arriving request if the disk is free (indicated by the third parameter being a NULLRCB), otherwise, it returns the RCB of the currently-serviced request after adding the newly-arriving request to the request queue. The signature of the method is as follows: struct RCB handle_request_arrival_fcfs(struct RCB request_queue[QUEUEMAX], int *queue_cnt, struct RCB current_request, struct RCB new_request, int timestamp); A sample execution input and output: input/output parameter value input request_queue EMPTY input queue_cnt 0 input current_request [RID:51, AT:1, CYL:53, ADDR:53, PID:51] input new_request [RID:52, AT:2, CYL:54, ADDR:54, PID:52] input timestamp 2 output request_queue [RID:52, AT:2, CYL:54, ADDR:54, PID:52] output queue_cnt 1 output RCB [RID:51, AT:1, CYL:53, ADDR:53, PID:51] Please refer to Section 5.4.3 of the Modern Operating Systems book for a detailed discussion of the First-Come-First-Served algorithm. handle_request_completion_fcfs This method implements the logic to handle the completion of servicing an IO request in a First-Come-First-Served Scheduler. Specifically, it takes a single input: 1. the request queue (an array of RCB structs). 2. The number of items in the request queue The method determines the request to service next and returns its RCB. If the request queue is empty, the method returns a NULLRCB, indicating that there is no request to service next. Otherwise, the method finds the RCB in the request queue that has the earliest arrival time. It then removes this RCB from the request queue and returns it. The signature of the method is as follows: struct RCB handle_request_completion_fcfs(struct RCB request_queue[QUEUEMAX],int *queue_cnt); A sample execution input and output: input/output parameter value input request_queue [RID:1, AT:10, CYL:124323, ADDR:124323, PID:1] input queue_cnt 1 output request_queue EMPTY output queue_cnt 0 output RCB [RID:1, AT:10, CYL:124323, ADDR:124323, PID:1] Please refer to Section 5.4.3 of the Modern Operating Systems book for a detailed discussion of the First-Come-First-Served algorithm. handle_request_arrival_sstf This method implements the logic to handle the arrival of a new IO request in a Shortest-Seek-First (also known as Shortest-Seek-Time-First) Scheduler. Specifically, it takes five inputs: 1. 2. 3. 4. 5. the request queue (an array of RCB structs) The number of items in the request queue the RCB of the currently-serviced request the RCB of the newly-arriving request the current timestamp. The method returns the RCB of the newly-arriving request if the disk is free (indicated by the third parameter being NULLRCB), otherwise, it returns the RCB of the currently-serviced request after adding the newly-arriving request to the request queue. The signature of the method is as follows: struct RCB handle_request_arrival_sstf(struct RCB request_queue[QUEUEMAX],int *queue_cnt, struct RCB current_request, struct RCB new_request, int timestamp); A sample execution input and output: input/output parameter value input request_queue EMPTY input queue_cnt 0 input current_request [RID:51, AT:1, CYL:53, ADDR:53, PID:51] input new_request [RID:52, AT:2, CYL:54, ADDR:54, PID:52] input timestamp 2 output request_queue [RID:52, AT:2, CYL:54, ADDR:54, PID:52] output queue_cnt 1 output RCB [RID:51, AT:1, CYL:53, ADDR:53, PID:51] Please refer to Section 5.4.3 of the Modern Operating Systems book for a detailed discussion of the Shortest-Seek-First algorithm. Handle_request_completion_sstf This method implements the logic to handle the completion of servicing an IO request in a Shortest-Seek-Time-First Scheduler. Specifically, it takes three inputs: 1. the request queue (an array of RCB structs) 2. The number of items in the request queue 3. the current cylinder. The method determines the request to service next and returns its RCB. If the request queue is empty, the method returns NULLRCB, indicating that there is no request to service next. Otherwise, the method finds the RCB in the request queue whose cylinder is closest to the current cylinder. If there are multiple requests with the closest cylinder, then the method picks the request among these that has the earliest arrival_timestamp. The method then removes the RCB of the selected request from the request queue and returns it. The signature of the method is as follows: struct RCB handle_request_completion_sstf(struct RCB request_queue[QUEUEMAX],int *queue_cnt,int current_cylinder); A sample execution input and output: input/output parameter value input request_queue [RID:1, AT:72, CYL:45, ADDR:45, PID:1], [RID:2, AT:71, CYL:47, ADDR:47, PID:2], [RID:3, AT:73, CYL:43, ADDR:43, PID:3] input queue_cnt 3 input current_cylinder 48 output request_queue [RID:1, AT:72, CYL:45, ADDR:45, PID:1], [RID:3, AT:73, CYL:43, ADDR:43, PID:3] output queue_cnt 2 output RCB [RID:2, AT:71, CYL:47, ADDR:47, PID:2] Please refer to Section 5.4.3 of the Modern Operating Systems book for a detailed discussion of the Shortest-Seek-First algorithm. Handle_request_arrival_look This method implements the logic to handle the arrival of a new IO request in a LOOK (also known as Elevator) Scheduler. Specifically, it takes five inputs: 1. the request queue (an array of RCB structs) 2. The number of items in the request queue 3. the RCB of the currently-serviced request 4. the RCB of the newly-arriving request 5. the current timestamp. The method returns the RCB of the newly-arriving request if the disk is free (indicated by the third parameter being NULLRCB), otherwise, it returns the RCB of the currently-serviced request after adding the newly-arriving request to the request queue. The signature of the method is as follows: struct RCB handle_request_arrival_look(struct RCB request_queue[QUEUEMAX],int *queue_cnt, struct RCB current_request, struct RCB new_request, int timestamp); A sample execution input and output: input/output parameter value input request_queue EMPTY input queue_cnt 0 input current_request [RID:51, AT:1, CYL:53, ADDR:53, PID:51] inpu
t new_request [RID:52, AT:2, CYL:54, ADDR:54, PID:52] input timestamp 2 output request_queue [RID:52, AT:2, CYL:54, ADDR:54, PID:52] output queue_cnt 1 output RCB [RID:51, AT:1, CYL:53, ADDR:53, PID:51] Please refer to Section 5.4.3 of the Modern Operating Systems book for a detailed discussion of the LOOK algorithm. Handle_request_completion_look This method implements the logic to handle the completion of servicing an IO request in a LOOK Scheduler. Specifically, it takes four input parameters: 1. the request queue (an array of RCB structs), 2. The number of items in the request queue 3. the current cylinder 4. the scan direction. The method determines the request to service next and returns its RCB. If the request queue is empty, the method returns NULLRCB, indicating that there is no request to service next. Otherwise, it picks the next request to service from the request queue. If there are requests in the queue with the same cylinder as the current cylinder, the method picks the one among these requests with the earliest arrival time. Otherwise, if the scan direction is 1 and there are requests with cylinders larger than the current cylinder, the method picks the one among these whose cylinder is closest to the current cylinder. Otherwise, if the scan direction is 1 and there are no requests with cylinders larger than the current cylinder, the method picks the request whose cylinder is closest to the current cylinder. Otherwise, if the scan direction is 0 and there are requests with cylinders smaller than the current cylinder, the method picks the one among these whose cylinder is closest to the current cylinder. Otherwise, if the scan direction is 0 and there are requests with cylinders larger than the current cylinder, the method picks the request whose cylinder is closest to the current cylinder. After picking the RCB from the request queue, as described above, the method removes the RCB from the queue and returns it. The signature of the method is as follows: struct RCB handle_request_completion_look(struct RCB request_queue[QUEUEMAX],int *queue_cnt, int current_cylinder, int scan_direction); A sample execution input and output: input/output parameter value input request_queue [RID:1, AT:52, CYL:58, ADDR:58, PID:1], [RID:2, AT:51, CYL:58, ADDR:58, PID:2], [RID:3, AT:53, CYL:58, ADDR:58, PID:3] input queue_cnt 3 input current_cylinder 58 input scan_direction 1 output request_queue [RID:1, AT:52, CYL:58, ADDR:58, PID:1], [RID:3, AT:53, CYL:58, ADDR:58, PID:3] output queue_cnt 2 output RCB [RID:2, AT:51, CYL:58, ADDR:58, PID:2] Please refer to Section 5.4.3 of the Modern Operating Systems book for a detailed discussion of the LOOK algorithm. AUTOGRADER SCORE 4.0 / 6.0 handle_request_arrival_fcfs (1.0/1.0) FAILED TESTS handle_request_arrival_look (1.0/1.0) handle_request_completion_fcfs (0.0/1.0) handle_request_completion_look (0.0/1.0) PASSED TESTS handle_request_arrival_sstf (1.0/1.0) handle_request_completion_fcfs (0.0/1.0) handle_request_arrival_fcfs (1.0/1.0) handle_request_arrival_look (1.0/1.0) handle_request_arrival_sstf (1.0/1.0) handle_req st_completion_sstf (1.0/1.0) Test Failed: ‘Expecting returned_rcb.request_id value of 1 and received 21866’ != ‘Passed All Tests’ handle_request_completion_look (0.0/1.0) Test Failed: ‘Expecting request_queue[1].request_id value of 3 and received 2\nExpecting returned_rcb.request_id va handle_request_completion_sstf (1.0/1.0)