Description
1 Overview
In this programming assignment you will design a multi-threaded device driver for an emulated hard disk drive (HDD). This assignment has two required tasks and two extra credit tasks.
2 Background
A hard disk drive (HDD) is a device that allows storage and retrieval of digital information using one or more rigid rapidly rotating disks (platters) coated with a magnetic material. Each platter is paired with a ”disk head,” which can read/write to the platter surface. We studied HDDs in some depth in Lecture 25 (Nov. 30). You will work with a simple emulated HDD (E-HDD) that we have written for you. E-HDDhasasingleplatterconsistingof100tracksandeachofthesetracksisinturncomposed of 10000 sectors. A sector is 512 bytes in size and is the granularity of read/write for our disk (meaning both that it is the smallest size of a request to the disk and that a requesttoread/writeasectorisguaranteedtobeatomicbythedisk). E-HDDhasafixed lengthbuffer(intermsofnumberofrequests,irrespectiveoftheirsizes)forrequestscoming from the device driver. Requests may be re-ordered once the buffer fills up according to the disk’s scheduling algorithm. Requests are issued to the disk head whenever the buffer fills up or a timer expires, whichever occurs earlier. This timer is reset every time requests are issued to the disk head. Clearly, the number of requests coming from the device driver threads can sometimes exceed the buffer size. This requires a certain type of synchronization to be achieved so that none of the requests are lost despite the finite buffer size.
3 Description of Tasks
We are providing you the code for E-HDD that exposes the following interface to our multi-threaded device driver: (i) int read disk(int sector number) and (ii) int write disk(int data, int sector number). If an access is made to an invalid
1
sector, the disk outputs BAD SECTOR, else prints the value read (in case of read) or the valuewritten(incaseofwrite)inthesector. E-HDDisprovidedasa1-dimensionalarray, defined as int disk[SECTORS*TRACKS]. Both TRACKS and SECTORS are defined as macros in driver.h. Since this is an emulation, we have introduced a delay caused by movement of head from one track to another. The delay is calculated as: |source track – destination track|x1 + 2 msec (where 2 msec is the average rotational delay for a HDD with rotational speed of 15,000 RPM). Each device driver thread will receive a sequence of two types of requests from (implicit) applications with one device driver thread servicing one application-level request inourdesign. Theserequestswillbespecifiedviaaninputfileandwillhavethefollowing aspects: • op name: IO call which is either ”read” or ”write”, return values have same interpretation as those for read disk and write disk. Both the read disk() and write disk()arevoidfunctions,i.e.,theydon’treturnanyvaluebutsimplyprint their outputs on the console. • sector number: argument to the above call • arrival time: describes when this request is to be issued by a device driver thread (real time) as an offset from the start time of the program. We will use pthreads for creating our multi-threaded device driver. Each incoming request is handled by a newly-created thread whose properties relevant to our emulation are defined within a structure called thread info. Each of these requests/threads will have: int tid which is the thread id, char[] op name, int sector number, int data, int arrival time and struct timespec exit time. These threads will call the thread handler() function which in turn will call either read disk() orwrite disk()basedonop name. Afterarequesthasbeenserviced,itwillrecordthe currenttimeasanoffsetfromthestarttimeoftheprogramandstoreitinthe exit time in the thread structure. The difference between arrival time and exit time will represent how long it took for the request to get serviced. We are going to assume that the device driver threads have access to the disk buffer through shared memory. The disk buffer/head will be implemented as a separate thread inthesameaddressspaceasthedevicedriverthreads. Inpractice,theymustmakeuseof privileged IO instructions. A disk operation has the effect of appending a request to the diskbufferifthereisroom. Ifthereisnoroom,thedevicedriverthreadblockswaitingfor there to be room. A new disk request is added as a buffer node which has: op name denoting the operation to be performed by the head, sector number and data which is to be written onto the given sector number if its a write operation. Each buffer node has a request id given by int req id to help the disk thread signal the appropriate device driver thread after its request has been serviced. The buffer has an upper limit on the number of requests it can hold, given by the variable limit. The buffer limit is hard coded in the code base, its value can be changed inside the init() function. The requests are issued to the disk head whenever the buffer fully fills up.
2
3.1 Task 1: Implement Disk Buffer You are to implement a mechanism to attach disk requests emerging from the device driver to the buffer and issue them to the disk head at appropriate times. Keep in mind that the incoming requests are being issued by concurrent threads accessing a shared buffer. Therefore,thistaskrequiresthatyoupreventanydataracesduetothis. Youmust ensure the following: • The number of requests in the buffer should not exceed its limit. • Requests are only issued to the disk when the buffer is full. • Requests are be allowed to be added to the buffer concurrently with the disk head servicing requests.
3.2 Task 2: Implement the Elevator Algorithm for Disk Head Scheduling Thedisk ops(int algo)functionreadsthebufferandservicesalltherequestsissuing them to the disk. The parameter algo tells the function whether to use FCFS or Elevator as the disk scheduling algorithm. Both read disk() and write disk() functions can call the disk ops() function when required. The function disk ops(int algo), by default, uses FCFS to service requests stored in the buffer, i.e., the disk executes the operations in the same order as they were appended to the buffer. This can cause unwanted movementoftheheadresultingintimelyoverheads. YourtaskistoimplementtheElevatoralgorithm. Youshoulddothisbyaddingthealgorithmintheexistingdisk ops(int algo) function. The parameter algo should be interpreted as follows: • 0: FCFS • 1: Elevator 3.3 Task 3: Extra Credit During relatively idle periods, requests may wait in the buffer for too long. One way toovercomethisproblemistostartatimerwheneverrequestsareissuedtothedisk. The expiration of this timer is then used as the next time to issue any requests in the buffer even if the buffer has not fully filled up by then. You are to implement this mechanism. This timer is reset every time requests are issued to the disk head. Make sure that the requests are issued to the disk head if the buffer is full before the timer expires.
3.4 Task 4: Extra Credit Since there can be multiple concurrent reads and writes issued to the same sector, our devicedriverthreadsmayfaceareaders-writerslikeproblem. Youaretosolvethisproblem to offer the following behavior. Whenever a request comes in the read disk() or write disk()operation,beforeaddingitselftothebuffer,itcallsENTER OPERATION(char
3
*op name, int sector number) function. This function decides whether an incoming request follows the Readers/Writers Protocols correctly or not. If it does, the request should be allowed to add itself to the buffer, if not, must be blocked. But this is not all. Aftertherequestisserviced,itshouldwakeupanyrequest(s)whichwas/wereblockedin theENTER OPERATION(). ThisisdonebymakingtherequestcallEXIT OPERATION(char *op name, int sector number)beforeleavingtheread disk()orwrite disk() function. The purpose of this function is to signal appropriate blocked request(s) before finally returning to the thread handler() function.
4 Submission and Grading
Same as the previous assignment, PA5 will be done in groups of 2. A group may choose either members repository as their workplace. Do remember to list both members names in all files you submit (including your report). Your project won’t be graded if you don’t have a name on your report. You are supposed to submit your assignment with your private GitHub repository. Therefore, accept the invitation to access your private repository. If you still need instructions for working with git or adding your teammate to your repository, refer to the included Git manual file. The TAs will grade you by inspecting your code, running some test cases for your code (apart from the ones already provided as sample test cases), and by looking at your report.
4.1 Code and Report You must push and commit to your private repository all your source files (*.c and *.h) andreportfileandaMakefilethattheTAswillusetocompileyourcode. Youshouldalso create a short README with instructions on how to compile and run your code. Thequalityandperformanceofyourcodealongwiththeclarityofreportwillcontribute towards your grade. Roughly, the TAs will be looking at these aspects when assigning your grade: (i) the quality and clarity of your implementation (complemented by reading your description in your report), (ii) adherence to constraints regarding the buffer and readers/writers protocol (iii) correct synchronization with no deadlock. Your report should have the following two components: • Pseudo code explaining the synchronization, implementation of readers/writers protocol [if attempted] and buffer timer [if attempted]. • Average service times for the provided inputs for FCFS vs. Elevator. If you are doing the extra credit tasks, you need to report times with the extra functionality.
4.2 Grading Rubric • Task 1 : Implementing Buffer – 5 Points Major synchronization bugs : 3 point deduction Other minor implementation issues : 2 point deduction
4
• Task 2 : Elevator Algorithm – 5 Points Partial grading based on implementation • Task 3 (Extra Credit) : Implementing buffer timer – 4 Points No partial grading • Task 4 (Extra Credit) : Readers/Writers Protocol – 6 Points No partial grading
5 Additional Information • Before starting, make sure you understand the code base and its components. • You are given a Makefile for the code base which generates an executable named disk simulation. Your repository will have some sample input files. To run the executable with an input, type: disk simulation < sample input.txt • Wehaveincluded4sampleinputfilesalongwiththeirexpectedcorrespondingoutput files. The buffer limits while testing against the input files were set as follows:
Sample Input File | Buffer Limit sample input.txt 1 sample input 2.txt 2 sample input 3.txt 3 sample input 4.txt 5
ThesebufferlimitsareHardCodedintheCodeBaseitself,bydefaulthavingavalue of 1. You can change this value within the init() function. Note that these outputs are expected outputs, the order of thread execution and/or output may change depending on actual implementation. Regardless of the order, the output must follow the buffer constrains [and readers/writers constraints].
