📄 solution3.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://remus.rutgers.edu/cs416/nguyen/S04/solution3.html -->
<!-- saved from url=(0022)http://internet.e-mail --><HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2900.2627" name=GENERATOR></HEAD>
<BODY>
<CENTER>
<H3>Homework 3 solution</H3></CENTER>Explain the difference between internal and
external fragmentation for segmentation/paging <BR>and allocation of files on
disk.
<P><B>Answer:</B>
<P><B>Segmentation: </B> Segments are of variable size, the allocation is
dynamic. When all blocks of free memory are too small to accommodate a segment,
it results in external fragmentation.
<P><B>Paging:</B> Memory is allocated in fixed-sized unit (page frames), when
the request is smaller than page size or can not be evenly divided by page size,
at least part of one page (the last page) won't be used by the requester and
unavailable for use by others, which is internal fragmentation.
<P><B>Allocation of files on disk:</B> <BR>If following contiguous allocation
method, as files are allocated and deleted, the free disk space will be broken
into chunks and suffer from external fragmentation when the largest contiguous
chunk is not sufficient for a request.
<P>In case of linked allocation and indexed allocation, file blocks need not to
be contiguous but they are allocated in unit of blocks, so internal
fragmentation would still possibaly happen. <BR>
<P>11.7 Explain the purpose of the open and close operations.
<P><B>Answer: </B> The open operation informs the system that the
named file is about to become active. The close operation informs
the system that the named file is no longer in active use by the user who issued
the close operation.
<P>12.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.
<P> a. The block is added at the beginning.
<BR> b. The block is added in the middle.
<BR> c. The block is added at the end. <BR>
d. The block is removed from the beginning. <BR> e. The block
is removed from the middle. <BR> f. The block is removed from
the end.
<P><B>Answer:</B>
<BR>
Contiguous
Linked
Indexed
<BR>
a.
201
1
1
<BR>
b.
101
52
1
<BR>
c.
1
3
1
<BR>
d.
198
1
0
<BR>
e.
98
52
0
<BR>
f.
0
100
0 <BR>
<P>12.5 Consider a system that supports the strategies of contiguous, linked,
and indexed allo-cation. What criteria should be used in deciding which strategy
is best utilized for a particular file?
<P><B>Answer: </B>
<BR>
Contiguous -- if file is usually accessed sequentially, if file is
relatively small.
<BR> Linked
-- if file is large and usually accessed sequentially.
<BR>
Indexed -- if file is large and usually accessed randomly.
<P>13.8 How does DMA increase system concurrency? How does it complicate
hardware design?
<P><B>Answer:</B> DMA increases system concurrency by allowing the CPU to
perform tasks while the DMA system transfers data via the system and memory
busses. Hardware design is compli-cated because the DMA controller must be
integrated into the system, and the system must allow the DMA controller to be a
bus master. Cycle stealing may also be necessary to allow the CPU and DMA
controller to share use of the memory bus.
<P>14.2 Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The
drive is currently serving a request at cylinder 143, and the previous request
was at cylinder 125. The queue of pending requests, in FIFO order, is
<BR> 86, 1470,
913, 1774, 948, 1509, 1022, 1750, 130 <BR>Starting from the current head
position, what is the total distance (in cylinders) that the disk arm moves to
satisfy all the pending requests, for each of the following disk-scheduling
algorithms?
<P>a. FCFS <BR>b. SSTF <BR>c. SCAN <BR>d. LOOK <BR>e. C-SCAN
<P><B>Answer:</B>
<P>a. The FCFS schedule is 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130.
The total seek distance is 7081. <BR>b. The SSTF schedule is 143, 130, 86, 913,
948, 1022, 1470, 1509, 1750, 1774. The total seek distance is 1745. <BR>c. The
SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The
total seek distance is 9769. <BR>d. The LOOK schedule is 143, 913, 948, 1022,
1470, 1509, 1750, 1774, 130, 86. The total seek distance is 3319. <BR>e. The
C-SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 86, 130.
The total seek distance is 9813. <BR>f. (Bonus.) The C-LOOK schedule is 143,
913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130. The total seek distance is
3363.
<P>14.17 The term fast wide SCSI-II denotes a SCSI bus that operates
at a data rate of 20 megabytes per second when it moves a packet of bytes
between the host and a device. Suppose that a fastwideSCSI-II disk drive spins
at 7200 RPM, has a sector size of 512 bytes, and holds 160 sectors per track.
<P>a. Estimate the sustained transfer rate of this drive in megabytes per
second. <BR>b. Suppose that the drive has 7000 cylinders, 20 tracks per
cylinder, a head switch time <BR>(from one platter to another) of 0.5
millisecond, and an adjacent cylinder seek time <BR>of 2 milliseconds. Use this
additional information to give an accurate estimate of the <BR>sustained
transfer rate for a huge transfer. <BR>c. Suppose that the average seek time for
the drive is 8 milliseconds. Estimate the I/Os <BR>per second and the effective
transfer rate for a random-access workload that reads <BR>individual sectors
that are scattered across the disk. <BR>d. Calculate the random-access I/Os per
second and transfer rate for I/O sizes of 4 <BR>kilobytes, 8 kilobytes, and 64
kilobytes. <BR>e. If multiple requests are in the queue, a scheduling algorithm
such as SCAN should <BR>be able to reduce the average seek distance. Suppose
that a random-access work-load <BR>is reading 8-kilobyte pages, the average
queue length is 10, and the scheduling <BR>algorithm reduces the average seek
time to 3 milliseconds. Now calculate the I/Os <BR>per second and the effective
transfer rate of the drive.
<P><B>Answer:</B>
<P>a. The disk spins 120 times per second, and each spin transfers a track of 80
KB. Thus, the sustained transfer rate can be approximated as 9600 KB/s.
<P>b. Suppose that 100 cylinders is a huge transfer. The transfer rate is total
bytes divided by total time. Bytes: 100 cyl * 20 trk/cyl * 80 KB/trk, i.e.,
160,000 KB. Time: rotation time + track switch time + cylinder switch time.
Rotation time is 2000 trks / 120 trks per sec, i.e., 16.667 s. Track switch time
is 19 switch per cyl * 100 cyl * 0.5 ms, i.e., 950 ms. Cylinder switch time is
99 * 2 ms, i.e., 198 ms. Thus, the total time is 16.667 + 0.950 + 0.198, i.e.,
17.815 s. (We are ignoring any initial seek and rotational latency, which might
add about 12 ms to the schedule, i.e. 0.1%.) Thus the transfer rate is 8981.2
KB/s. The overhead of track and cylinder switching is about 6.5%.
<P>c. The time per transfer is 8 ms to seek + 4.167 ms average rotational
latency + 0.052 ms (calculated from 1 / (120 trk per second * 160 sector per
trk)) to rotate one sec-tor past the disk head during reading. We calculate the
transfers per second as 1/(0.012219), i.e., 81.8. Since each transfer is 0.5 KB,
the transfer rate is 40.9 KB/s.
<P>d. We ignore track and cylinder crossings for simplicity. For reads of size 4
KB, 8 KB, and 64 KB, the corresponding I/Os per second are calculated from the
seek, rota-tional latency, and rotational transfer time as in the previous item,
giving (respec-tively) 1/(0.0126), 1/(0.013), and 1/(0.019). Thus we get 79.4,
76.9, and 52.6 transfers per second, respectively. Transfer rates are obtained
from 4, 8, and 64 times these I/O rates, giving 318 KB/s, 615 KB/s, and 3366
KB/s, respectively.
<P>e. From 1/(3+4.167+0.83) we obtain 125 I/Os persecond.From8KBperI/O we obtain
1000 KB/s. </P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -