ICAROS' Disk Driver
A few words about the disk driver
This driver uses the LOOK algorithm for handling disk requests.This means that requests are stored in two queues, one for the requests for sectors greater than the current head position, and one for the lesser ones.
The algorithm can be sinthesized this way:
head_direction = FROM_LESSER_TO_GREATER; // Doesn't really matters... it's just to initialize it
while (TRUE)
{
wait_for_request();}
if ( not(IsEmpty(queue[head_direction])) )
{
satisfy_request();}
/* Here I assume that not(not(head_direction))==head_direction... */
else if ( not(IsEmpty(queue[not(head_direction)])) )
{
head_direction=not(head_direction);}
satisfy_request();
Requests for the current position of the head are queued on the queue NOT related to the current head direction (this allows us to avoid starvation problems).
We have choosed the LOOK algorithm because it's the more efficient, and it's not too complicated.
In our opinion it's better than SCAN and C-SCAN, because it doesn't moves "blindly" until the end of the disk before switching directions.
The drawback is that LOOK isn't a fair algorithm. Central sectors on average are reached faster than outer sectors.
Anyway, we think that this is a margianal drawback.
Consider this: the difference between C-SCAN and LOOK are that C-SCAN lowers performances on all sectors to guarantee a fair behaviour.
LOOK isn't fair, but surely it is NOT slower than SCAN or C-SCAN, even for outer sectors.
We thought also about a LOOK+elevator algorithm (increase priority of request while they are kept in queue to avoid too much waiting), and probably it would have been a better solution, but we decided that it wasn't worth it, and we choosed the "KISS" way (Keep It Simple and Stupid). :-)
A closer look
The source files for ICAROS disk driver are in the disk_driver directory.There you will find 5 cpp files.
Blockdq.cpp and hthash.cpp were developed during the first phase of the project. They provide the classes needed for the disk cache.
Blockdq.cpp defines the class Block (a single cache block), BlockDQueue (the list of allocated blocks) and BlockFreeList (the list of free blocks).
Hthash.cpp defines the classes needed fot an hash table, which speeds up the search for a block in the cache. The hash table function is at the end of the hthash.cpp file, and is a simple module:
// calculate the hash function
int THash::hash_func(int i)
{
/ * result MUST be in the range [0,HASHTABLESIZE[ */}
return (i % HASHTABLESIZE);
The file heap.cpp provides a generic heap, implemented as a binary tree. It's used by the class DiskQueue defined in disk_queue.cpp.
I tried to keep this heap as generic as possible. The single element is a void*, so virtually anything can be put inside this heap. You'll notice also that the comparing function (needed to compare two elements of the heap) isn't defined here, but is passed to the class constructor:
Heap::Heap(int (*comp)(const void *,const void *))
{
root = NULL;}
num_elem = 0;
less_eq = comp;
The file disk_queue.cpp defines the DiskQueue class, which handles the queue of disk requests. This class provides the functions IsEmpty, Insert and GetNext. It uses the Heap class, so IsEmpty is o(1), and Insert and GetNext are o(log(n)).
There are two types of DiskQueue, one used for extracting first the element with lesser cylinder number (created by passing DQ_EXTRACT_LESSER to the constructor), the other used to extract the greater ones (created by passing DQ_EXTRACT_GREATER to the construtor).
Basically, the only difference between the two types is the function passed to the constructor of the class Heap.
Every element of the queue is a:
struct DiskQueueCell {
int request;};
int request_cyl;
int request_sect;
int request_head;
void *request_data;
int sem_endop;
The field request holds the type of operation (DD_CMD_READ, DD_CMD_WRITE or the special operation DD_CMD_TERMINATE used on system shutdown, which makes the disk driver daemon terminate gracefully).
The fields request_cyl, request_sect and request_head holds the physical coordinates of the disk for the specified operation.
The field request_data is a pointer to the virtual memory address used for this read or write.
The last field of this struct is a semaphore on which the system call will be blocked (if data isn't in cache). The disk driver daemon will use this semaphore to wake the system call (and the calling process which is waiting for it to terminate) when the read/write is complete.
The main file of this section is disk.cpp. It contains the methods of two classes: Disk and DiskDriver.
The Disk class provides the functions needed for sending commands to the disk device. It uses the generic functions defined in the file support/devices.cpp, and does some range checking to avoid sending illegal instructions.
In the DiskDriver (this class is the real core of the driver) constructor an object Disk is created and a daemon thread is started for each disk device on the system (depending on the constant MAX_DISK_NUM).
When the daemon thread is started, it executes the DiskDaemon function, where it uses semaphores for mutex and synchronization.
A process requesting a disk operation will be sent to disk_read or disk_write by the system call. There, the ProcessOp function is called.
The function ProcessOp checks if data is available in cache, and eventually copies data into user space, and exit. If data isn't in cache, it calls the Request function.
Request is the function that enqueues the disk operation request, and make the daemon start, calling a V on the semaphore start_dd[disk]. Then it sleeps on the semaphore sem_endop contained in the enququed struct DiskQueueCell. When the disk driver has completed the operation it calls V on sem_endop, and goes to sleep again, waiting for other requests.