CS372: Solutions for Homework 10

Problem 1:

Consider a very simple file system for a tiny disk. Each sector on the disk holds 2 integers, and all data blocks, indirect blocks, and inodes are 1 disk sector in size (each contains 2 integers). All files stored on disk are interpreted as directories by the file system (there are no "data files"). The file system defines the layout for the following data types on disk:
inode = 1 pointer to a data block + 1 pointer to indirect block

indirect block = 2 pointers to data blocks

directory = a regular file containing zero or more pairs of integers; the first integer of each pair is a file name and the second is the file's inumber

The value "99" signifies a null pointer when referring to a disk block address or directory name. An empty directory has one disk block with the contents "99   99". The inumber for root directory is "/" is 0.

The following data are stored on disk:

inode array:
0 1  2  3  4   5  6  7   8   9  10 11 12 13 14 15
10
6		 7
99		    8
99		       3
99		                           

disk blocks:
 0  1  2  3  4   5  6 7 8  9  10 11 12 13 14 15
   32
3		    96
1		       1
99		 99
99		 99
99		    57
6		               

  1. How many entries can appear in a maximum-sized directory? (Each entry is a pair of integers)

    Solution: 3 ( one data block and two other data blocks pointed by the one indirect block)

  2. List all directories stored on this disk (full path names) along with the names of the files stored in each directory.

    Solution:

    directory path name inumber indirect blocks data blocks contents (subdirectories)

    /

    0

    6

    		  10 1  /32,  /57

    /32

    3

    n/a

    		  8  n/a

    /57

    6

    n/a

    		  3  /57/96

    /57/96

    1

    n/a

    		  7  n/a
            

  3. Modify the above data structures to add an empty directory called "87" to directory "/"

    Solution:
    directory path name inumber indirect blocks data blocks contents (subdirectories)

    /87

    9

    n/a

    		 14 n/a

    /

    0

    6

    		  10  1  13  /32,  /57, /87

     
    0 1  2  3  4   5  6  7   8   9  10 11 12 13 14 15
    10
    6    		 7
    99    		    8
    99    		       3
    99    		       14
    99          		                  

    disk blocks:
     0  1  2  3  4   5  6 7 8  9  10 11 12 13 14 15
       32
    3    		    96
    1    		       1
    13    		 99
    99    		 99
    99    		    57
    6    		       87
      9    		 99
    99          		   

Problem 2:

The MegaGiga hard disk rotates at 5400 rpm with an arm seek time given by = 4 + 0.05t msec, where t is the number of tracks the arm seeks. Assume a block size of 512 bytes, and 1024 tracks with 512 sector/track. The disk controller and DMA read or write data from/to disk at a rate of 4MB/sec.
  1. What is the storage capacity of the disk?
    Solution:
    The storage capacity of the disk is
    (sector size) * (number of sectors/track) * (number of tracks)

  2. Assume that we are reading a 16K-bytes file where the sectors happen to be allocated contiguously on the same track. Compute the maximum and minimum disk throughput that is possible while reading the file?
    Solution:
    Maximum disk throughput occurs when the head is right on top of the required sector. In this case we can transfer the 32 sectors that constitute the file immediately without seeking or paying rotational latency overhead. But we do not write instantaneously, we need to compute the time it takes for the head to travel over the 32 sectors. This time can be computed as follows:
    It takes the rotational latency for the head to travel 512 sectors (sectors per track).
    Therefore from one sector to the next = rotational latency/512
    = (60/5400) / 512
    = 22 microseconds (rounded up)

    Therefore, to get the 16K bytes out of the disk, it takes 32 sectors * 22 microseconds/sector = 694 microseconds. Note that the bandwidth of the disk itself is therefore about 23MB/s. But, we also have to pay the DMA overhead, which is

    16K/(4*1024*1024) = 3.9msec

    So, the total time is 3.9 ms + .694 ms = 4.59 ms. The transfer time is dominated by the DMA overhead, and the throughput is slightly less than the 4MB/sec rate of the DMA controller (4.59 ms per 16KB = 3.49 MB/s).

    Moral of the story: When we make a transfer and the disk head does not have to move, then we transfer data at the maximum speed that the disk controller electronics allow.

    Minimum throughput: This will occur when the disk head has to travel the maximum distance to get to the data. In this case, at worst, it has to go over the entire platter, and then wait for an entire rotation before it gets to the beginning of the file. The time to do this is:

    seek time + latency time = (4 + 0.05 * 1024) + (60/5400)
    =  55.2 (seek) + 11.11 (rotation)
    = 66 msec

    The DMA overhead is the same as above. Therefore, the overhead is dominated by the cost of seeking and waiting for the head to get to the right sector on the track. The result is 16 KB/66ms = 247KB/sec (about 7% of the sequential throughput).

    Moral of the story: When the head has to move, the throughput drops considerably, and you can see that the effect may produce only 7% of the controller bandwidth on a read or write (and with a better DMA controller the peak bandwidth would be higher and the long seek and rotation would reduce the bandwidth to about 1% of peak).
    Exercise: Compute the same if the sectors were not contiguous. You will see that 7% of the max bandwidth may not be even reachable if the sectors are scattered throughout the disk. Sequential allocation is good!!

Problem 3 (review multi-threads programming)

We have 3 teams: red, green, and blue. A team member calls Game::myTurn(int color) when she or he wants to do something and calls Game::doneTurn() when she or he is done. At most one team may be doing something at a time. Each team gets a turn in the order red, green, blue, red, green, blue, and so on. If a team is not ready when the previous team is done with its turn, the team is skipped and the next ready team gets a chance. If no team is ready, the first team to request a turn gets the next turn. Note that many team members of the same color may want to take a turn; model each as an independent thread. Write the Game class using condition variables and locks. Follow the coding standards specified in class.

Solution 1:
List Game's synchronization and state variable here:

Mutex lock;
Cond donePlaying;

public:
static const int RED = 0;
static const int GREEN = 1;
static const int BLUE = 2;
static const int NCOLORS = 3;

private:
int waiting[NCOLORS];
int previousColor;
bool busy;

public
Game::Game() // constructor
{
  waiting[0] = waiting[1] = waiting[2] = 0;
  previousColor = BLUE;
  busy = FALSE;
}

public
Game::myTurn(int color)
{
  lock.acquire();
  waiting[color]++;
  while (iShouldWait(color) ) {
    donePlaying.wait(&lock);
  }
  busy = TRUE;
  waiting[color]--;
  previousColor = color;
  lock.release();
}

public
Game::doneTurn()
{
  lock.acquire();
  busy = false;
  donePlaying.broadcast(&lock);
  }

private:
int Game::iShouldWait(int color)
{
    assert(lock is held);
    if(busy){
       return TRUE;
    }
    if(color == (previousColor + 1) % NCOLORS){
        return FALSE;
    }
    if((color == (previousColor + 2) % NCOLORS) && (waiting[(previousColor + 1) % NCOLORS] == 0){
         return FALSE;
    }
    if((color == (previousColor + 3) % NCOLORS) && (waiting[(previousColor + 2) % NCOLORS] == 0){
         assert(color == previousColor);
         assert((waiting[(color + 1) % NCOLORS] == 0) && (waiting[(color + 1) % NCOLORS] == 0));
         return FALSE;
    }
    return TRUE;
}

 

 

 

Solution 2:

List Game's synchronization and state variable here:

Mutex lock;
Cond No_One_Play;

Boolean Busy;
Queue q[3];
int Id_Count;
int nextId;
int previous_color;

Game::Game() // constructor
{
  Busy = false;
  q[0] = q[1] = q[2] = NULL;
  Id_Count = 0;
  nextId = -1;  // -1 means no one is waiting
  previous_color = -1;
}

Game::myTurn(int color)
{
  int myId;

  lock.acquire();

  myId = Id_Count;
  Id_Count++;
  q[color].enque(myId);
  while (Busy || ((nextId >= 0) && (myId !=  nextId)) )
  {
    No_One_Play.wait(&lock);
  }
  q[color].deque();
  Busy = true;
  previous_color = color;

  lock.release();
}

Game::doneTurn()
{
  lock.acquire();
  Busy = false;

  //compute the next one who should go if there's anyone waiting.
  next_id = -1;

  int next_color = (previous_color+1)mod 3;
  if ( !q[next_color].isEmpty()){
    nextId = q[next_color].front();
  } else{
    next_color = (next_color+1)mod 3;
    if ( !q[next_color].isEmpty()){
    nextId = q[next_color].front();
    } else 
    if(!q[previous_color].isEmpty())
   {
     nextId = q[previous_color].front();
   }
 }

 No_One_Play.broadcast(&lock);
  lock.release();
}