Description
Introduction
In this machine problem you will investigate kernel-level device drivers on top of a simple
programmed-I/O block device (programmed-I/O LBA disk controller)1
.
The given block device
uses busy waiting to wait for I/O operations to complete. You will add a layer on top of this
device to support the same blocking read and write operations as the basic implementation, but
without busy waiting in the device driver code. The user should be able to call read and write
operations without worrying that the call may either return prematurely (i.e. before the disk is
ready to transfer the data) or tie up the entire system waiting for the device to return.
A Note about Terminology
We will follow the recommendations of the Open Source Hardware Association (OSHWA) and use
the terms master and dependent to identify the two slots of the ATA disk controller. In some
documentation and APIs you may find the deprecated terms master and slave.
Blocking Drive
In particular, you will implement a device called BlockingDisk, which is derived from the existing
low-level device SimpleDisk. The Device BlockingDisk shall implement (at least) the following
interface:
class BlockingDisk : public SimpleDisk {
public :
BlockingDisk ( DISK_ID _disk_id , unsigned int _size ) ;
/* Creates a BlockingDisk device with the given size connected to the
MASTER or DEPENDENT slot of the primary ATA controller . */
/* DISK OPERATIONS */
void read ( unsigned long _block_no , unsigned char * _buf ) ;
/* Reads 512 Bytes from the given block of the disk and copies them to the
given buffer . No error check ! */
void write ( unsigned long _block_no , unsigned char * _buf ) ;
/* Writes 512 Bytes from the buffer to the given block on the disk . */
};
Note: The thread that calls the read and write operations should not block the CPU while the
disk drive positions the head and reads or writes the data. Rather, the thread should give up the
CPU until the operation is complete. This cannot be done completely because the read and write
operations of the simple disk use programmed I/O. The CPU keeps polling the device until the
data can be read or written. You will have to find a solution that trades off quick return time from
these operations with low waste of CPU resources.
One possible approach would be to have a blocked-thread queue associated with each disk.
Whenever a thread issues a read operation, it queues up on the disk queue and yields the CPU. At
1There is no need to get into the gory details of the implementation of SimpleDisk. If you are interested, however,
you can find a brief overview at http://www.osdever.net/tutorials/view/lba-hdd-access-via-pio
regular intervals (for example each time a thread resumes execution2
) we check the status of the
disk queue and of the disk, and complete the I/O operations if possible.
Note about inaccurate emulation in Bochs: Be aware that Bochs does not very accurately
emulate disk behavior. Since the disks are emulated, and there is no actual heads moving, the IO
requests may come back much sooner than expected. Do not be surprised by this. Instead, reason
your way through what would have to be done if the requests actually were to take time on the
disk.
Opportunities for Bonus Points
OPTION 1: Support for Disk Mirroring. (This option carries 6 bonus points.) Your machine
is configured to have two 10MB disks connected to the ATA-0 controller (one is the MASTER, the
other the DEPENDENT). As part of this option you are to implement a class MirroredDisk, which
is derived from BlockingDisk (easy) or from SimpleDisk (harder, but maybe higher-performance).
Write operations are issued to both disks. Read operations are supposed to return to the caller as
soon as the first of the two disks is ready to return the data.
OPTION 2: Using Interrupts for Concurrency. (This option carries 6 bonus points. Note:
You may want to go slow with this option and give preference to other options. This one may
expose you to all kinds of race conditions.) Once you start interacting with the disk, you may
notice all kinds of unexpected (and therefore unhandled) interrupts. At least some of these come
from the disk controller. The disk may indicate through an interrupt that it needs attention. You
can make use of this to cut down on the amount of polling that you do. Rather than checking
the state of the disk at regular intervals, you register an interrupt handler, which wakes up the
appropriate waiting thread and has it complete the I/O request.
OPTION 3: Design of a thread-safe disk system. (This option carries 6 bonus points.) For
implementation purposes, you can assume that a disk is to be accessed by at most one thread at a
time. If multiple threads can access these items concurrently, there are plenty of opportunity for
race conditions. You are to describe (in the design document) how you would handle concurrent
operations to disk in a safe fashion. This may require a change to the interface.
OPTION 4: Implementation of a thread-safe disk system. (This option carries 6 bonus
points.) For this option you are to implement the approach proposed in Option 3. Note: Work
on this option only after you have addressed Option 3.
A Note about the new Main File
The main file for this MP is very similar in nature to the one for the previous MP. We have modified
the code for some of the threads to access a disk.
• The code in kernel.C instantiates a copy of a SimpleDisk. You will have to change this to
a BlockingDisk. Other parts of the code don’t need to be changed, since BlockingDisk is
publicly derived from SimpleDisk.
• The kernel.C file is very similar to the one handed out in the machine problem on threads
and scheduling. It is still scheduler-free. You will have to modify it (in the same way you did
for that MP) to bring in your scheduler. Since blocking threads give up the CPU, this MP
will make no sense unless you have a scheduler!
2Not a good solution if you have urgent threads!
A Note about the Configuration
In this MP the underlying machine will have access to two hard drives, in addition to the floppy
drive that you have been using until now. If you look at File bochsrc.bxrc, you will notice the
following lines:
# hard disks
ata0: enabled=1, ioaddr1=0x1f0, ioaddr2=0x3f0, irq=14
ata0-master: type=disk, path=”c.img”, cylinders=306, heads=4, spt=17
ata0-slave: type=disk, path=”d.img”, cylinders=306, heads=4, spt=17
This portion of the configuration file defines an ATA controller to respond to Interrupt 14, and
connects two hard disks, one as master and the other as dependent to the controller. The disk
images are given in files ”c.img” and ”d.img”, respectively, similarly to the floppy drive image in
all the previous machine problems. Note: There is no need to modify the bochsrc.bxrc file.
Note: If you use a different emulator or a virtual machine monitor (such as VirtualBox) you
will be using a different mechanism to mount the hard drive image as a hard drive on the virtual
machine. If so, follow the documentation for your emulator or virtual machine monitor.
The Assignment
1. Implement the Blocking Disk as described above. Make sure that the disk does not use busy
waiting to wait until the disk comes back from an I/O operation.
2. For this, use the provided code in file blocking disk.H and blocking disk.C, which defines
and implements class BlockingDisk. This class is publicly derived from SimpleDisk, and
the current implementation of BlockingDisk::read and BlockingDisk::write simply call
the same functions of class SimpleDisk. You need to change that, and implement
non-looping versions of these functions.
3. If you have time and interest, pick one or more options and improve your Blocking Disk.
What to Hand In
You are to hand in a ZIP file, called mp6.zip, containing the following files:
1. A design document called design.pdf (in PDF format) that describes your design and the
implementation of your Blocking Disk. If you have selected any options, likewise
describe design and implementation for each option. Clearly identify in your
design document and in your submitted code what options you have selected, if
any.
2. All the source file and the makefile needed to compile the code.
3. Any modification to the provided .H file must be well motivated and documented.
4. Clearly identify and comment the portions of code that you have modified.
5. Grading of these MPs is a very tedious chore. These handin instructions are meant to mitigate
the difficulty of grading, and to ensure that the grader does not overlook any of your efforts.
Note: Pay attention to the capitalization in file names. For example, if we request a file called
file.H, we want the file name to end with a capital H, not a lower-case one. While Windows does
not care about capitalization in file names, other operating systems do. This then causes all kinds
of problems when the TA grades the submission.
Failure to follow the handin instructions will result in lost points.