CS372: 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 |
| |
| | |
- How many entries can appear in a maximum-sized directory?
(Each entry is a pair of integers)
- List all directories stored on this disk (full path names) along
with the names of the files stored in each directory.
| directory path name |
inumber |
indirect blocks |
data blocks |
contents (subdirectories) |
/
 |
0
|
| | |
- Modify the above data structures to add an empty directory
called "87" to directory "/"
| directory path name |
inumber |
indirect blocks |
data blocks |
contents (subdirectories) |
/87
|
|
| | |
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.
-
What is the storage capacity of the disk?
-
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?
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.
List Game's synchronization and state variable here:
Game::Game() // constructor
{
}
Game::myTurn(int color)
{
}
Game::doneTurn()
{
}