Mass Storage Structure

prepared and instructed by

Shmuel Wimer
Eng. Faculty, Bar-Ilan University

January 2017 Mass Storage Structure 1

 Magnetic Disks
Magnetic disks is the bulk of secondary storage.
There are thousands of concentric cylinders. Each track
contains hundreds of sectors. Common disk drives
capacity is terabytes.
Common drives spin at 5,400, 7,200, 10,000, and 15,000
RPM.
Disk speed has two parts:
Transfer rate, the rate at which data flow between the
drive and the computer. Several .
Positioning time, or random-access time, has two parts:
January 2017 Mass Storage Structure 2
 Moving-head disk mechanism.
January 2017 Mass Storage Structure 3
Seek time, time to move the disk arm to the desired
cylinder, and rotational latency, time of desired sector
to rotate to disk head. Several .
Disk drive is attached to computer by I/O bus (e.g. serial
advanced technology attachment (SATA), universal serial
bus (USB)).
Host controller is the controller at the computer end of
the bus. Disk controller is built into each disk drive.
Computer places a command into the host controller,
which sends the command via messages to the disk
controller, operating the disk-drive.

January 2017 Mass Storage Structure 4

 Solid-State Disks (SSD)
SSD is nonvolatile memory used like hard drive.
More reliable (no moving parts), faster (no seek time or
latency) and consume less power.
More expensive per MB and shorter life spans.
Since SSDs are much faster, hence standard bus
interfaces limit throughput. Direct connection to system
bus (e.g. PCI) is possible.
Can replace disk drives, or used as a new cache between
magnetic disks and main memory to optimize
performance.

January 2017 Mass Storage Structure 5

 Disk Scheduling
Access time and bandwidth can be improved by
managing order in which disk I/O requests are serviced.
A process issues I/O service system call specifying:
• Whether it is input or output
• Disk address for the transfer
• Memory address for the transfer
• The number of sectors to be transferred
If disk and controller are available, new request is
serviced immediately. Otherwise, requests are queued.
OS chooses which to service next.

January 2017 Mass Storage Structure 6

 FCFS Scheduling
Example: Requests for I/O to blocks on cylinders , disk
head initially at cylinder 53. Total head movement of 640
cylinders.

January 2017 Mass Storage Structure 7

 Shortest-Seek-Time-First (SSTF) Scheduling
SSTF service requests close to current head position
before moving head far away to service other requests.
Total head movement to 236 cylinders.

January 2017 Mass Storage Structure 8

SSTF is a form of shortest-job-first (SJF) scheduling, and
like SJF may cause starvation.
Suppose requests 14 and 186 in queue, and while 14 is
being serviced, a new request near 14 arrives.
This new will be serviced next, making 186 wait.
Continual requests near one another could cause
request for cylinder 186 waiting indefinitely.
SSTF is not optimal. Moving head from 53 to 37, then to
14, before turning to service 65, 67, 98, 122, 124, and
183, yields total movement of 208 cylinders.

January 2017 Mass Storage Structure 9

 SCAN Scheduling
SCAN moves the disk arm forth and back from one end
toward the other end, servicing requests as it reaches
each cylinder.
Scheduling requires knowing the direction of head
movement in addition to head’s current position.
Arm moving toward 0 with head positioned at 53, ,
services 37 and 14, then reversed at 0, servicing 65, 67,
98, 122, 124, 183.
Request arriving in the queue just in front of the head is
serviced immediately, arriving just behind will wait.

January 2017 Mass Storage Structure 10

January 2017 Mass Storage Structure 11
Assuming uniform distribution of requests for cylinders,
when head reaches one end few requests are just in
front.
The heaviest density is at the other end of the disk,
waited the longest.
Circular SCAN (C-SCAN) scheduling is a variant providing
more uniform wait time.
Commonly the arm does not go to disk ends but only as
far as the final request in each direction.
Versions of SCAN and C-SCAN are called LOOK and C-
LOOK scheduling.
January 2017 Mass Storage Structure 12
January 2017 Mass Storage Structure 13
 Selection of Scheduling Algorithm
SSTF is common and has a natural appeal because it
increases performance over FCFS.
SCAN and C-SCAN perform better for heavy disk load
because less likely starvation.
Requests for disk service are greatly influenced by file-
allocation method.
Program reading contiguously allocated file generates
close requests, yielding limited head movement.
Linked or indexed file may include blocks scattered on
the disk, yielding greater head movement.

January 2017 Mass Storage Structure 14

The location of directories and index blocks is also
important.
Opening file requires searching the directory structure,
the directories will be accessed frequently.
Caching directories and index blocks in main memory
helps reducing arm movement, mostly for read requests.
Disk-scheduling algorithm is written as separate OS
module, so it can be replaced if necessary.
Rotational latency is as large as seek time, but difficult
for OS to schedule for improved rotational latency.

January 2017 Mass Storage Structure 15

Manufacturers alleviate the problem by implementing
scheduling algorithms in the disk drive controller HW.
If the OS sends a batch of requests to the controller,
queuing and schedule them to improve seek time and
rotational latency.
If I/O performance were the only consideration, OS
would turn over scheduling responsibility to disk HW.
OS however has other service scheduling constraints.
Demand paging is prior over application I/O. Writes are
prior over reads if memory is running out of free pages.

January 2017 Mass Storage Structure 16

 Disk Formatting and Boot Block
Before disk can store data, it is divided into sectors,
called low-level formatting, so controller can R/W.
Low-level formatting fills the disk with a special data
structure for each sector, comprising a header, data area
(e.g. 512 bytes), and trailer.
Header and trailer contain information for controller,
such as a sector number and an ECC, calculated and
updated at each normal I/O.
The controller automatically does the ECC processing
whenever a sector is read or written.

January 2017 Mass Storage Structure 17

Low-level formatting is done at factory, enabling test the
disk and map from logical block numbers to defect-free
sectors on the disk.
Formatting with a larger sector size (e.g. 1024 bytes)
means fewer sectors can fit on each track, also fewer
headers and trailers overhead.
Before using the disk to hold files, OS needs to record its
own data structures on the disk, done in two steps.
First partitions disk into groups of cylinders, treating
partitions as separate disks.

January 2017 Mass Storage Structure 18

One partition holds a copy of the OS’s executable code,
while another holds user files.
Second step is logical formatting, creating of a file
system, where OS stores the initial file-system data
structures onto the disk.
Data structures include maps of free and allocated space
and an initial empty directory.
The bootstrap program is stored in ROM, which cannot
be infected by a computer virus.
A problem is that changing this bootstrap code requires
changing the ROM hardware chips.
January 2017 Mass Storage Structure 19
Most systems store tiny bootstrap loader program in the
boot ROM, bringing in full bootstrap program from disk.
A disk that has a boot partition is called a boot disk or
system disk.
The full bootstrap program loads the entire OS from disk
and starts OS running.
MS Windows divides hard disk into partitions, one
identified as boot partition, containing OS and device
drivers.
Boot code is placed in the first sector on the hard disk,
called master boot record (MBR).
January 2017 Mass Storage Structure 20
 Booting from disk in MS Windows.
January 2017 Mass Storage Structure 21
ROM’s boot directs the system to read the boot code
from the MBR.
MBR contains also a table listing the partitions for the
hard disk and a flag indicating which partition the system
is to be booted from.
Once the system identifies the boot partition, it reads
the first sector from that partition (called boot sector).
It continues with the remainder of the boot process,
which includes loading various subsystems and system
services.

January 2017 Mass Storage Structure 22

 Swap-Space Management
VM uses disk space as an extension of main memory.
Swap-space management is low-level OS task, aiming at
providing best throughput for VM.
Swap space size varies from MBs to GBs, depending on
the amount of physical memory, amount of VM it is
backing, and the way VM is used.
Overestimate is safer than underestimate, running out of
swap space forces abort processes and even crash.
Linux allows using multiple swap spaces, placed on
separate disks, spreading over system’s I/O bandwidth.

January 2017 Mass Storage Structure 23

Swap space is usually a separate raw partition. No file
system or directory structure is placed in it.
A separate OS swap-space storage manager allocates
and deallocates its blocks.
It optimizes speed rather than storage efficiency,
because swap space is accessed much more frequently
than file system.
Since swap space is reinitialized at boot time, any
fragmentation is short-lived.
In Linux each swap area consists of a series of 4-KB page
slots, holding swapped pages.
January 2017 Mass Storage Structure 24
Associated with swap area is swap map, integer array,
corresponding to page slots in the swap area.
0 indicates the corresponding page slot is available,
indicates swapped page is mapped to processes (occurs
if page stores memory shared by processes).

January 2017 Mass Storage Structure 25