作業系統 作業#4 Operating System Homework #4

作業系統 作業#4 Operating System Homework #4

學生:Murphy Chen
系級:電機四
老師:陳少傑

Chapter 11

Exercise 11.1

& Consider a file currently consisting of 100 blocks. Assume that the file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.

a. The block is added at the beginning.

b. The block is added in the middle.

c. The block is added at the end.

d. The block is removed from the beginning.

e. The block is removed from the middle.

f. The block is removed from the end.

 

!

 

 

 

Contiguous

Linked

Indexed

Add at 1st block

202 disk I/Os

2 disk I/Os

2 disk I/Os

Add at 51st block

102 disk I/Os

3 disk I/Os

2 disk I/Os

Add at 101st block

2 disk I/Os

3 disk I/Os

2 disk I/Os

Remove from 1st block

199 disk I/Os

2 disk I/Os

1 disk I/Os

Remove from 50th block

101 disk I/Os

3 disk I/Os

1 disk I/Os

Remove from 100th block

1 disk I/Os

2 disk I/Os

1 disk I/Os

 

a. The block is added at the beginning (1st block).

 

For contiguous allocation strategies, we need 100 disk I/Os for reading the entire file into memory, 1 disk I/O for writing the new block to disk at the beginning of the file ( in the 1st block), and 100 disk I/Os for writing the remaining 100 blocks of the file to disk starting from the 2nd block, and 1 disk I/O for writing the file control block to change the file length to 101. In total, we need 202 disk I/Os.

 

For linked allocation strategies, we first find a free block in disk, and then we need one disk I/O for writing the new block with a pointer to the first block whose disk address can be found in the file control block to disk in the free block we have found, and we need to change the pointer in the file control block to point to the new block in disk. Finally we need another disk I/O for writing the file control block back to disk. In total, we need 2 disk I/Os.

 

For indexed allocation strategies, we first find a free block in disk, and then we need one disk I/O for writing the new block in the free block we have found. Then, we have to insert the disk address of the new block the 1st entry of the disk-block array in the index block. Finally, we need another one disk I/O for writing the index block back to disk. In total, we need 2 disk I/Os.

 

 

b. The block is added in the middle (51st block).

 

For contiguous allocation strategies, we need 50 disk I/Os for reading the last half of the file into memory, 1 disk I/O for writing the new block to disk in the middle of the file (in the 51st block), and 50 disk I/Os for writing the remaining 50 blocks of the file to disk starting from the 52nd block, and 1 disk I/O for writing the file control block to change the file length to 101. In total, we need 102 disk I/Os.

 

For linked allocation strategies, we first find a free block in disk, and then we need one disk I/O for reading the 50th block of the file to get the point to disk address of the 51st block of the file. And then we need another disk I/O for writing the new block with a pointer to the 51st block to disk in the free block. Finally we need still another disk I/O for writing the 50th block with a new pointer to the new block to disk. In total, we need 3 disk I/Os.

 

For indexed allocation strategies, we first find a free block in disk, and then we need one disk I/O for writing the new block in the free block we have found. Then, we have to insert the disk address of the new block in the 51st entry of the disk-block array in the index block. Finally, we need another one disk I/O for writing the index block back to disk. In total, we need 2 disk I/Os.

 

 

c. The block is added at the end (101st block).

 

For contiguous allocation strategies, we need one disk I/O for writing the block to disk at the end of the file (in the 101st block), and 1 disk I/O for writing the file control block to change the file length to 101. In total, we need 2 disk I/Os.

 

For linked allocation strategies, we first find a free block in disk, and then we need one disk I/O for reading the 100th block of the file to store its content into memory. Then, we need another disk I/O for writing the new block with a pointer setting to nil in the free block. Finally, we change the pointer of the 100th block in memory to point to the disk address of the new block, and then we need still another disk I/O for writing the 100th block back to disk. In total, we need 3 disk I/Os.

 

For indexed allocation strategies, we first find a free block in disk, and then we need one disk I/O for writing the new block in the free block we have found. Then, we have to insert the disk address of the new block in the 101st entry of the disk-block array in the index block. Finally, we need another one disk I/O for writing the index block back to disk. In total, we need 2 disk I/Os.

 

 

d. The block is removed from the beginning (1st block).

 

For contiguous allocation strategies, we need 99 disk I/Os for reading the last 99 blocks into memory, and 99 disk I/Os for writing the 99 blocks back to disk at the beginning of the file, and one disk I/O for writing the file control block to change the file length to 99 blocks. In total, we need 199 disk I/Os.

 

For linked allocation strategies, we need one disk I/O for reading the 1st block of the file into memory, in order to get the pointer to the disk address of the 2nd block of the file. Then, we change the pointer in the file control block to point to the 2nd block of the file, and we need need one disk I/O for writing the file control block to disk. Finally, we collect the 1st block in a pool of free blocks. In total, we need 2 disk I/Os.

 

For indexed allocation strategies, we need to remove the 1st entry of the disk-block array in the index block. Then, we need one I/O for writing back the index block to disk. Finally, we collect the 1st block in a pool of free blocks. In total, we need only one disk I/O.

 

 

e. The block is removed from the middle (50th block).

 

For contiguous allocation strategies, we need 50 disk I/Os for reading the last 50 blocks into memory, and 50 disk I/Os for writing the 50 blocks back to disk starting from the 50th block, and 1 disk I/O for writing the file control block to change the file length to 99 blocks. In total, we need 101 disk I/Os.

 

For linked allocation strategies, we need one disk I/O for reading the 50th block of the file into memory, in order to get the pointer to the disk address of the 51st block of the file. Then, we need another disk I/O for reading the 49th block of the file to store its content into memory. Then, we change the pointer of the 49th block into memory to point to the 51st block of the file, and we need still another disk I/O for writing the 49th block back to disk. Finally, we collect the 50th block in a poll of free blocks. In total, we need 3 disk I/Os.

 

For indexed allocation strategies, we need to remove the 50th entry of the disk-block array in the index block. Then, we need one I/O for writing back the index block to disk. Finally, we collect the 50th block in a pool of free blocks. In total, we need only one disk I/O.

 

 

f. The block is removed from the end (100th block).

 

For contiguous allocation strategies, we need only one disk I/O for writing the file control block to change the file length to 99 blocks.

 

For linked allocation strategies, we need one disk I/O for reading the 99th block of the file to store its content into memory. Then, we change the pointer of the 99th block in memory to point to nil, and we need another disk I/O for writing the 99th block back to disk. Finally, we collect the 100th block in a pool of free blocks. In total, we need 2 disk I/Os.

 

For indexed allocation strategies, we need to remove the 100th entry of the disk-block array in the index block. Then, we need one I/O for writing back the index block to disk. Finally, we collect the 100th block in a pool of free blocks. In total, we need only one disk I/O.

 

 

 

Exercise 11.6

& Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions:

a. How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)

b. If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?

!

a.

We can think of a logical block as composed of a filename and a block number.

 

For contiguous allocation strategy, given a filename, we can look it up in the directory to find the starting block of the file, and the length of the file. If the given block number is larger than the length of the file, that is an invalid access. Otherwise, the physical block is equal to the starting block plus the given block number.

 

For linked allocation strategy, given a filename, we can look it up in the directory to find the starting block of the file. We can use the pointer in one block to follow the link to the next block as many times as the number of the given block number, until we get to the desired physical block, or until we arrive at the last block of the file in the case where the given block number is larger than the total blocks of the file.

 

For indexed allocation strategy, given a filename, we can look it up in the directory to find the index block of the file. The index block is composed of an array of disk addresses of physical blocks. We can use the given block number as an index number to point to an entry of the array. If the content of that entry is equal to nil, that is an invalid access. Otherwise, the desired physical block is equal to the content of that entry.

 

 

b.

Assume the block number is counted from 0.

 

For contiguous allocation strategy, we can look up the information about the file in memory to find the starting block of the file. The desired block is equal to the starting block of the file plus 4. So, we dont need to read any physical block from the disk in order to access logical block 4.

 

For linked allocation strategy, we can look up the information about the file in memory to find the starting block of the file. To get the block address of logical block 4, we have to follow 4 links from the starting block of the file. So, we need to read 4 physical blocks (from the 0th block to the 3rd block) from the disk in order to access logical block 4.

 

For indexed allocation strategy, we can look up the information about the file in memory to find the block address of the index block. Then, we need to read one physical block from the disk to get the content of the index block. The desired block is pointed to by the 5th entry ( the 1st entry contain the poitner to the logical block 0) of the disk-address array in the index block. So, we need to read ony one physical block from the disk in order to access logical block 4.

 

 

Exercise 11.8

 

& Fragmentation on a storage device could be eliminated by recompaction of the information. Typical disk devices do not have relocation or base registers (such as are used when memory is to be compacted), so how can we relocate files? Give three reasons why recompacting and relocation of files often are avoided.

 

!

When we use the contiguous allocation method, we will encounter the problem of external fragmentation. When we use the linked or indexed allocation method, we will not encounter the problem of external fragmentation.

 

We can eliminate the problem of external fragmentation by recompaction. First, we can collect all the files on the disk, and its associated attributes such as its starting block and its length (total blocks). Then, we can sort these files according their starting blocks. Now, we look at each file one by one, to compare the sum of its starting block and its total blocks with the starting block of the next file. If this sum is less than the starting block of the next file, we know there are free blocks between the current file and the next file, so we can change the starting address (block) of the next file to this sum, and moving all the blocks belonging to the next file to the new starting address. After processing all the files, we will have all of them compacted, and there arent any free blocks between any files.

 

Recompacting and relocation of files are often avoided, because:

 

1. Doing these things take a lot of time.

 

2. When we do these things, the users of the system cannot do any other things.

 

3. When we do these things, if the power is suddenly turned down, the file in process may be damaged.

 

 

 

Chapter 12

Exercise 12.2

 

& Suppose that the head of a moving-head disk with 200 tracks, numbered 0 to 199, is currently serving a request at track 143 and has just finished a request at track 125. The queue of requests is kept in the FIFO order:

 

86,147,91,177,94,150,102,175,130.

 

What is the total number of head movements needed to satisfy these requests for the following disk-scheduling algorithms?

 

a. FCFS scheduling

b. SSTF scheduling

c. SCAN scheduling

d. LOOK scheduling

e. C-SCAN scheduling

 

!

a. For FCFS scheduling, the head will move to the following tracks in order:

143->86->147->91->177->94->150->102->175->130

So, the total number of head movements are |86-143|+|147-86|+|91-147|+|177-91|+|94-177|+|150-94|+|102-150|+|175-102|+|130-175|=565

 

b. For SSTF scheduling, the head will move to the following tracks in order:

143->147->150->130->102->94->91->86->175->177

So, the total number of head movements are |143-147|+|150-147|+|130-150|+|102-130|+|94-102|+|91-94|+|86-91|+|175-86|+|177-175|=162

 

c. For SCAN scheduling, the head will move to the following tracks in order:

(We can see that the head is currently moving toward 199.)

143->147->150->175->177->199->130->102->94->91->86

So, the total number of head movements are |147-143|+|150-147|+|175-150|+|177-175|+|199-177|+|130-199|+|102-130|+|94-102|+|91-94|+|86-91|=169

 

d. For LOOK scheduling, the head will move to the following tracks in order:

143->147->150->175->177->130->102->94->91->86

So, the total number of head movements are |147-143|+|150-147|+|175-150|+|177-175|+|130-177|+|102-130|+|94-102|+|91-94|+|86-91|=125

 

e. For C-SCAN scheduling, the head will move to the following tracks in order:

143->147->150->175->177->199->0->86->91->94->102->130

So, the total number of head movements are |147-143|+|150-147|+|175-150|+|177-175|+|199-177|+|0-199|+|86-0|+|91-86|+|94-91|+|102-94|+|130-102|=385

 

 

 

Exercise 12.8

 

& Requests are not usually uniformly distributed. For example, the cylinders on which the file directory structures reside are accessed more frequently than are most files. Suppose that you know that 50 percent of the requests are for a small fixed number of cylinders.

a. Which of the scheduling algorithm discussed in this chapter would be best?

b. Can you suggest a new scheduling algorithm for this case? If you can, describe your algorithm.

 

!

a. I think the shortest-seek-time-first disk-scheduling algorithm would be best under such circumstances. Because 50 percent of the requests are for a small fixed number of cylinders, when we encounter a series of requests, half of them will be in a small fixed number of cylinders And using SSTF scheduling, we can make sure that this half of requests can be serviced by requiring the least number of head movements. For the other half of requests, using SSTF scheduling gives us a suboptimal solution.

 

b. We know that 50 percent of the requests are for a small fixed number of cylinders, and suppose that these cylinders are around cylinder X. Given a series of requests, we can determine which one to service next according to which one is closest to the cylinder X. First, we select the cylinders from the one side of cylinder X, after servicing all the requests from one side of cylinder X, we proceed to serve the other requests from the other side of cylinder X. Its performance will be better than SSTF scheduling.

 

 

 

Exercise 12.9

 

 

!

Latency optimization is usually not employed in disk scheduling, maybe it is because that the rotating velocity of hard disks are very fast so that the overhead of latency optimization is comparable to the performance improvement of latency optimization. So, to optimize latency time does not do much good to performance. And, it is really not easy to do this, anyway.

 

If we would like to adopt latency optimization in our standard disk-scheduling algorithms, we have to do the following things:

 

For FCFS scheduling, we always select the request that comes first. So, we cannot modify it in order to include latency optimization. Its meaningless to do so.

 

For SSTF scheduling, we can modify it to select the request with the minimum seek time plus latency time from the current head position.

 

For SCAN scheduling, we can modify it to have read-write head start at one end of the disk, and move toward the other end, servicing requests as it reaches each track, and within each track, processing the blocks from the requests that the read-write head encounters first.

 

For C-SCAN scheduling, we can modify it the same way as we modify SCAN scheduling to include latency optimization.