Storage

Question 1

Disks
The architecture of the disk has affected the design of the OS. In particular, it has affected the algorithms used to schedule disk requests, since those must be handled efficiently.

1. [3pts] For spinning drives, what cost are these algorithms trying to minimize?

Answer 1

Seek time

Question 2

2. [3pts] Name and describe one algorithm that reduces the cost you listed in 1

Answer 2

C-LOOK

Question 3

3. [3pts] Would the algorithm you listed in 2 be efficient for a SSD? Defend your answer.

Answer 3

No, the algorithm focuses on decreasing seek time, which is not an issue in SSDs, as there is no disk head

Question 4

1. [5pts] The minimum unit of allocation on disk is a sector, but the system often combines contiguous sectors into blocks and then considers the block the minimum allocation unit. As the system designer at Acme, Inc., you are in charge of setting the block size for the system.

What size do you choose and why? What are the disadvantages of your choice? You may assume that a sector on disk is 512 bytes.

Answer 4

I would choose a block size that is neither too big nor too small: probably 4KB. An advantage of such a block size would be, the ease of reading and writing out in blocks as it would (usually) match the page size in memory. Another advantage would be that most files are small and 4KB is small enough to not cause too much internal fragmentation. A disadvantage would be that even though this supports large files, it would not be ideal as the large file would be split into a lot of blocks.

Question 5

2. In class, two of our examples of 500 reads from a spinning disk were a set of 500 random requests and a set of 500 sequential requests. We saw that the latter set of requests was much faster than the former—19.25 milliseconds vs 7.3 seconds.
   (a) [4pts] Why is accessing 500 sequential blocks cheaper than accessing 500 random ones?

Answer 5

Seek time must be calculated for each random read, but only once for a sequential read, and seek time is the most expensive part of disk access time

Question 6

(b) [2pts] What is the other piece(s) of disk access time?

Answer 6

Transfer time

Rotational latency

Question 7

Disks
When we discussed disks, we studied both spinning disks and solid state drives. We then discussed many policies in the operating system, such as disk scheduling algorithms and file layout policies, that are optimized based on the structure and costs of the spinning disk. The solid state drive, however, is different, with characteristics like multiple independent data paths, erasure blocks, and no moving parts.

1. As of now, both the current Linux file system (ext4) and NTFS use extents as part of their file layout design.
   (a) [3pts] What is the benefit of extents on a spinning disk?

Answer 7

Extents can decrease the amount of space needed in a record, by listing a range of sectors allocated rather than each sector individually

Question 8

(b) [3pts] What is the benefit of extents on a SSD?

Answer 8

Same as spinning disk

Question 9

2. [3pts] Would the disk scheduling algorithm C-SCAN be a good choice for an SSD? Defend your answer.

Answer 9

No, SSD has no disk head or spinning disk, so C-SCAN could not be implemented in an SSD

Question 10

3. [3pts] What component(s) of a SSD should be considered in developing an algorithm for disk reads?

Answer 10

There are no moving parts in an SSD so random reads are fast

Read disturb could possibly be affected by reads

Question 11

2. [3pts] As systems move to solid state drives, will the top concern change? If so, what would the new top concern be? Defend your answer.

Answer 11

No, there are no moving parts so there is no seek time. The new top concern could be eliminating file layout fragmentation

Question 12

4. [3pts] What scheduling algorithm would be a good choice to manage requests to a solid state drive? Defend your answer.

Answer 12

None. SSDs do not have a head so no need to schedule. Just process the requests in the order received by the disk (not necessarily FIFO).

Question 13

3. [4pts] This system has chosen to put the journal on an inside track. Is that what you would choose? If not, where would you place the journal? Defend your answer.

Answer 13

Outside track would be more efficient because no matter what we always must visit the outermost track when the head jumps to the outside sector. We don’t always have to visit the innermost track

Question 14

4. [3pts] The purpose of the journal is to provide consistency for the file system. How does it do that?

Answer 14

The journal is first updated atomically with all the required updates to file system before performing the actual updates. This is done so that in case of a crash if the journal does not have a commit (incomplete journal), we do not perform any actual updates, otherwise if there is a commit, we perform all the updates. So the file system remains consistent by doing either no updates or all updates.

Question 15

(b) [4pts] We considered (so far) one way that cost might be reduced through scheduling. What sort of scheduling algorithm reduces that cost, and which one would you choose for an OS that will only access a single (spinning) disk partition at a time? Defend your answer.

Answer 15

LOOK - this is because LOOK works with any bounds for tracks and not necessarily just the inner and outer tracks of a disk.

Question 16

(c) Now consider the file layouts we studied. (Remember that we are considering spinning disks!)
i. [2pts] Which one would have the best time to write an entire very large file? Defend your answer.

Answer 16

Contiguous allocation: This is because it would require only a single seek and then only have to write data continuously (so only rotational and transfer latency would need to be worried about).

Question 17

ii. [2pts] Given a fragmented (spinning) disk, would you still choose the same file layout? Defend your answer.

Answer 17

No. If the disk is very fragmented, contiguous allocation would be bad as it would be very difficult to find contiguous spots in a fragmented disk to fit large files.

Question 18

2. For a solid state drive disk:

(a) [2pts] What is the dominant cost of a write?

Answer 18

Block erasure

Question 19

2. For a solid state drive disk:
   (b) [3pts] We considered one way that cost might be reduced through clever handling of data. Name and describe that method in 25 words or fewer.

Answer 19

Remapping - Keep an empty block to which all page writes are done. A block erasure would be needed only when the entire block fills up, amortizing its cost.