Secondary Storage and System Software - YUynucc.yu.ac.kr/~hrcho/Courses/FS/Chapter03.pdf · 4. Storage as a Hierarchy Registers RAM RAM disk and disk cache Direct-access Serial Archival

Chapter 3 - 1

÷�öOF fj¶�j� æbÚ

Chapter 3

Secondary Storage and System Software

Chapter 3 - 1÷�öOF fj¶�j� æbÚ

TABLE OF CONTENTS

● Disks

● Magnetic Tape

● Disk versus Tape

● Storage as a Hierarchy

● Buffer Management

Chapter 3 - 2


1. Disks

z ��

✔ Direct access storage devices (DASD)↔ serial devices (magnetic tape)

✔ Hard disk, Floppy disk, Optical disk


1.1 Disk��

Platters Spindle Read /write heads Boom

Chapter 3 - 3


Tracks Sectors

Gaps

FIGURE 3.2 Surface of the disk showing tracks and sectors.


FIGURE 3.3 Schematic illustration of disk drive viewed

Seven cylinders

Tentracks

Chapter 3 - 4


1.2 Estimating Capacities and Space Needs

z Storage Capacity✔ Track capacity = sectors /track × bytes /sector✔ Cylinder capacity = tracks /cylinder × track capacity✔ Drive capacity = # of cylinders × cylinder capacity

z Example

File Size : 20,000 recordNumber of bytes per sector = 512Number of sectors per track = 40Number of tracks per cylinder = 11Number of cylinders = 1,331


✔ Data record � 256byte��, �� cylinder �– � sector �� record � : 2– �� sector � : 20,000/2 = 10,000– cylinder � sector � : 40 × 11 = 440– �� cylinder � : 10,000/440 = 22.7

�� cylinder ��.

Chapter 3 - 5


1.3 Organizing Tracks by Sector

z Two ways to organize data on a disk✔ by sector✔ by user-defined block

z Physical Placement of Sectors✔ Configure sectors adjacently

– sequential processing � ��

✔ Interleaving sectors ← interleaving factor✔ ��, 1 : 1 interleaving ��


12345

67

8

9

1011

1213 14 15 16 17 18 19 20 21

2223

24

25

2627

2829303132

11427821

215

28

9

223

1629 10 23 4 17 30 11 24 5

1831

12

25

619

321326720

(a)

(b)FIGURE 3.4 Two views of the organization of sectors on a 32-sector track.

Chapter 3 - 6


z Clusters✔ � – Fixed number of contiguous sectors✔ ��

– Reduce seek time– File allocation table (FAT) ��

✔ Cluster ��?


3

1

2

Cluster Clusternumber location

123• •• •• ••

•••

File allocation table(FAT)

The Part of theFAT pertainingto our file

FIGURE 3.5 The file manager determines which cluster in the file has the sector that is to be accessed.

Chapter 3 - 7


z Extents✔ � – Contiguous clusters✔ As the number of extents in a file increases :

– The file becomes more spread out on the disk.– The amount of seeking increases.


(a)

(b)FIGURE 3.6 File extents ( shaded area represents space on disk used by a single file).

Chapter 3 - 8


z Fragmentation✔ � : record size = 300 bytes, sector = 512 bytes

– 1 record /sector : �� , internal fragmentation– 1.x record /sector : �� ×, �� I/O

✔ Cluster �� internal fragmentation


1.4 Organizing Tracks by Block

z Track �� block ��

✔ Block ��

✔ Fragmentation ��

✔ Blocking factor : � block �� record �✔ �� block ��

– count sub-block : block �� (bytes �)– key sub-block : block �� record key

� non-data overhead � ��. (3.1.5 ��)

Chapter 3 - 9


FIGURE 3.8 Sector organization versus block organization.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ¦ 2 2 2 2 2 2 2 2 ¦ 3 3 3 ¦ 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ¦ 5 5 5 . . .

1 1 1 1 1 1 1 1 1 1 1 . . . 1 1 1 1 1 1 1 1 ¦ 2 2 2 . . . 2 2 ¦ 3 3 3 ¦ 4 4 4 4 4 4 . . . 4 4 4 4 4 4 ¦ 5 5 5 . . .

Sector 1 Sector 2 Sector 3 Sector 4 Sector 5 Sector 6

(a)

(b)


. . . . . .

. . . . . .

Countsubblock

Datasubblock

Countsubblock

Datasubblock

Countsubblock

Keysubblock

Datasubblock

Countsubblock

Keysubblock

Datasubblock

(a)

(b)

FIGURE 3.9 Block addressing requires that each physical data block be accompanied by one or more subblocks containing information about its contents.

Chapter 3 - 10


1.5 The Cost of a Disk Access

z Seek Time✔ �� track (cylinder)� access arm ��

✔ �� (10ms ~ 40ms)✔ ��, ��

✔ average seek time = 1/3 of worst case

z Rotational Delay (Rotational Latency)✔ �� sector �� disk ��

✔ Hard disk : 3,600 rpm ← 16.7ms /��, RD = 8.3ms– Floppy disk�� 360 rpm ← RD = 83.3ms

✔ Track staggering : disk head switching time ��


z Transfer Time✔ Disk head �� data ��

Transfer time = × rotation time

✔ Transfer time for one sector?

number of bytes transferrednumber of bytes on a track

Chapter 3 - 11


Example 1.

Average seek time 18 msecRotational delay 8.3 msecMaximum transfer rate 16.7 msec/track, or 1,229bytes/msecBytes per sector 512Sectors per track 40Tracks per cylinder 11Cluster size 8 sectorsSmallest extent size 5 clusters


z 2,048 Kbytes File (8,000 256-bytes records��)✔ Sequential access ��

– 2 records /sector ⇒ 80 records /track ⇒ 100 track– Track �� seek time � rotational delay– Track �� : ( 18 + 8.3 + 16.7 ) = 43 msec– �� : 43 msec × 100 = 4.3 seconds

✔ Random access ��

– �� cluster ��

( 18 + 8.3 + 16.7 / 5 ) = 29.6 msec– �� : 29.6 msec × 8,000 = 236.8 �

Chapter 3 - 12


1.6 Disk as Bottleneck

z Observation✔ disk access time >> CPU � network ��

✔ Solution : multiprogramming, parallelism, buffering

z Multiprogramming✔ I/O �� CPU �� job ��

✔ � process � I/O ��.


z Striping : parallelism ��

✔ File �� disk ��

✔ � disk �� I/O ← RAID

z Disk cache✔ File manager �� buffer (RAM) ��

✔ I/O request � buffer ��

✔ locality of reference ��

Chapter 3 - 13


2. Magnetic Tape2.1 Organization of Data on Tapes

0

1

1

0

1

0

0

1

0

Track Frame

Gap Data block Gap

FIGURE 3.11 Nine-track tape.


z Three quantities of a tape✔ Tape density : 6,250 bits per inch (bpi)

– 6,250 bpi 9 track tape means 6,250 bytes per inch✔ Tape speed : 30 ~ 200 inches per second (ips)✔ Size of IBG : 0.3 inch ~ 0.75 inch

Chapter 3 - 14


2.2 Estimating Tape Length Requirements

z Question :

100 byte record � 1,000,000, �� file IBG � 0.3 inch � 6,250 bpi tape ��

��. �� tape ��?


z Answer✔ What take up space on the tape?

– b : physical length of a data block– g : length of an IBG– n : number of data blocks⇒ s = n × ( b + g ) g = 0.3 inch

✔ Blocking factor � 1 � ��

– b = 100 / 6,250 = 0.016 inch– s = 1,000,000 × ( 0.016 + 0.3 ) = 316,000 inches

✔ Blocking factor � 50 ��

– b = 5,000 / 6,250 = 0.8 inch– s = 20,000 × ( 0.8 + 0.3 ) = 22,000 inches

Chapter 3 - 15


z Effective Recording Density

✔ blocking factor = 1 ⇒ ERD = 316.4 bpi << 6,250 bpi

number of bytes per block

number of inches required to store a block


2.3 Estimating Data Transmission Times

z Transmission rate✔ Nominal rate = tape density (bpi) × tape speed (ips)

– 6,250 × 200 = 1,250 Kbytes /sec✔ Effective transmission rate

– IBG �� nominal rate ��

– Blocking factor � 1 � �� : 316.4 × 200

⇐ Blocking factor ��

Chapter 3 - 16


2.4 Tape Applications

z Sequential processing �

✔ �� file ��

�� on-line ��?✔ old master + transaction = new master ��

z Backup ��

✔ Disk � = 30 × Tape �


3. Disk versus Tape

Disk Tape

Cost Expensive Cheap

Speed Fast Slow

Access Type Random Access Sequential Access

Chapter 3 - 17


4. Storage as a Hierarchy

Registers

RAM

RAM diskand

disk cache

Direct-access

Serial

Archivaland

backup

Types ofmemory

Devices andmedia

Access times(sec)

Capacities(bytes)

Cost(cents/bit)

Primary

Secondary

Offline

Core andsemiconductors

Magnetic

Tape andmass storage

Removablemagnetic disks,optical discs,

and tapes

10-9 – 10-5

10-3 – 10-1

101 – 102

100 – 102

100 – 109 100 – 10-3

104 – 109

100 – 1011

10-2 – 10-5

10-5 – 10-7

104 – 1012 10-5 – 10-7

FIGURE 3.12 Approximate comparisons of types of storage, circa 1991.


5. Buffer Management

Buffering involves working with large chunks of data in RAM so the number of accesses to secondary storage can be reduced.

z How many buffers are used?✔ �� I/O buffer ��, buffering �� ×

– ��, ��

✔ �� buffer �� : input & output✔ I/O bound job ��, �� buffer ��

5.1 Buffer Bottlenecks

Chapter 3 - 18


þJÒ 1 þJÒ 1 ã 1

þJÒ 2

þJÒ 3

þJÒ 4

þJÒ 5

þJÒ 6

þJÒ 7

þJÒ 8

þJÒ 9

þJÒ 10

ã 2

ã 3

...

ã n

úRî�N�Âö�� zr ã¯Jr

W.��

ÚBþJÒ

W.��

ÚBã

[î² 3.1] ã¯JrÆ�N¡~îr¢÷s&N¦ò


5.2 Buffering Strategies

z Multiple Buffering✔ Double buffering

– I/O �� CPU � overlapping– 2�� buffer ��

✔ Buffer pooling– UNIX buffer cache ��

– buffer replacement : least recently used (LRU)

Chapter 3 - 19


Program data area

Program data area

I/O buffer 1

I/O buffer 2

I/O buffer 1

I/O buffer 2

(a)

(b)

To disk

To disk

FIGURE 3.17 Double buffering : (a) The contents of system I/O buffer 1 are sent to disk while I/O buffer 2 is being filled ; and (b) the contents of buffer 2 are sent to disk while I/O buffer 1 is being filled.


z Move Mode and Locate Mode✔ move mode

– system buffer cache �� user area � copy– �� memory copy ��

✔ ��

– I/O � disk �� user area �� load (��)– program �� system buffer cache ��

⇐ locate mode (��)

Chapter 3 - 20


z Scatter / Gather I/O✔ Scatter input

– �� buffer ��

– � : page header � data �� loading

✔ Gather output– �� buffer �� page�� write


Example 2 : Buffering � Hard Disk

80 Bytes /record, 7 records /block, 24 sectors /track200 tracks /surface, 20 tracks /cylinderFile size = 33,881 blocks ( 71� cylinder�� )Transfer time = 806 Kbytes /sec, Rotational delay = 8.3 msecAverage seek time = 30 msec

Chapter 3 - 21


1. File�� ?

�� = (AST + RD) × cylinder � + block � TT × block �= (30 + 8.3) × 71 / 1,000 + 560 / (806 × 1024) × 33,881= 25.7 sec

2. � block �� 0.5 msec ��, single buffering�� file ��?

�� = �� + (�� / block × block �)= 25.7 sec + 16.9 sec = 42.6 sec


3. Double buffering �� file ��

��?

• � block �� = 25.7 sec / 33,881 = 0.76 msec• �� > �� (0.5 msec) �� I/O bound job.• �� = (�� / block × block �)

+ �� block ��

= 25.7 sec + 0.5 ms

Chapter 3 - 22


[î² 3.10] {��ªÒj�zr·NÒúúþz

zr 1 :¦& zr 2 :¦& zr 1 :¦& zr 2 :¦&

50 ms 50 ms 50 ms 50 ms

�N

zr 1 �¢

zr 2 �¢

50 ms 25 ms 25 ms

CPU

zr 1 �¢

25 ms25 ms 25 ms 25 ms

Òú

. . .

. . .


[î² 3.11] úR.�ªÒj�zr·NÒúúþz

�N

CPU

Òú

zr 1 �¢ zr 2 �¢

50 ms 100 ms 100 ms

zr 1 :¦&zr 2 :¦&

zr 1 :¦&

50 ms 50 ms 50 ms50 ms 50 ms. . .

. . .

Documents

Secondary Storage and System Software - YUynucc.yu.ac.kr/~hrcho/Courses/FS/Chapter03.pdf · 4. Storage as a Hierarchy Registers RAM RAM disk and disk cache Direct-access Serial Archival