Transcript PPT Chapter 14

Chapter 14
Implementations of File Operations
Copyright © 2008
Introduction
•
•
•
•
•
•
•
Layers of the Input-Output Control System
Overview of I/O Organization
I/O Devices
Device-Level I/O
The Physical IOCS
Device Drivers
Disk Scheduling
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.2
2
Introduction (continued)
•
•
•
•
•
•
Buffering of Records
Blocking of Records
Access Methods
Disk and File Caches
Unified Disk Cache
Case Studies
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.3
3
Layers of the Input-Output Control
System
• Input-output control system (IOCS) holds some file data
in memory to provide efficient file processing and high
device throughput
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.4
4
Layers of the Input-Output Control
System (continued)
• Two layers:
– Access method layer provides efficient file processing
– Physical IOCS layer provides high device throughput
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.5
5
Layers of the Input-Output Control
System (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.6
6
Overview of I/O Organization
• I/O organization was discussed in Chapter 2
• Each device controller has a unique numeric id
– Each device connected to it has a unique numeric device
id
• A device address is (controller_id, device_id)
• An I/O operation involves:
–
–
–
–
Operation to be performed—read, write, etc.
Address of the I/O device
Number of bytes of data to be transferred
Addresses of areas in memory and on the I/O device that
are to participate in the data transfer
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.7
7
I/O Operations
• The I/O operation to read the data recorded in a disk
block with the id (track_id, block_id) is performed by
executing:
– I/O-init (controller_id, device_id), I/O_command_addr
• I/O_command_addr is start address of the memory
area containing the following two I/O commands:
– Position disk heads on track track_id
– Read record record_id into the memory area with the
start address memory_addr
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.8
8
I/O Devices
• Can be classified using the following criteria:
– Purpose: Input, print and storage
– Nature of access: Sequential and random-access
– Data transfer mode: Character and block mode
• The I/O time for a record is the sum of its access time
and transfer time:
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.9
9
I/O Devices (continued)
Magnetic Tapes
• Strip of magnetic material
– Information is recorded in the form of 1s and 0s
• Recording on a tape is multitrack
– Each track records a bit of a byte or a parity bit
• Operations:
– read/write, skip, rewind
• Older technologies inserted interrecord gaps
• Streaming tapes contain a single record stored without a
break irrespective of its size
– Interrecord gaps do not exist even when a large volume of
data is recorded on a tape
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.12
12
Magnetic Disks
• CRCs used for error detection
• Records of a track are given serial
numbers with respect to the start-oftrack position mark
• Access time:
– Seek time: Disk head movement
– Rotation latency
• Commands:
– seek (cylinder number, surface number)
– read/write
• Tracks are organized into sectors
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.13
13
Data Staggering Techniques
• Sector interleaving addresses problems caused by data
transfer time
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.14
14
Data Staggering Techniques
(continued)
• Head skewing addresses the problems caused by head
switch time
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.15
15
Data Staggering Techniques
(continued)
• Cylinder skewing addresses the problems caused by
seek time
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.16
16
Sector Interleaving
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.17
17
Disk Attachment Technologies
• Integrated device electronics (IDE) or ATA
– Primarily work with programmed I/O modes
• Small computer system interconnect (SCSI)
– Provides functionality traditionally done by the IOCS:
• Disk scheduling
• Bad block recovery
• Prefetching of data
• Enhanced integrated device electronics (EIDE)
– Supports new DMA modes
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.18
18
Disk Attachment Technologies
(continued)
• Network-Attached Storage and Storage Area Networks:
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.19
19
Redundant Array of Inexpensive Disks
(RAID)
• An array of cheap disks is used instead of a single disk
• Different RAID arrangements provide three benefits
– Reliability
• Store data redundantly (remember stable storage?)
• Read / write redundant data records in parallel
– Fast data transfer rates
• Store file data on several disks in the RAID
• Read / write file data in parallel
– Fast access
• Store two or more copies of data
• To read data, access the copy that is accessible most
efficiently
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.20
20
Disk striping
• A disk strip contains data (it is like a sector or disk
block)
• A disk stripe is a collection of identically positioned
strips on different disks in the RAID
– Data written on strips in a disk stripe can be read in
parallel
• This arrangement provides high data transfer rates
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.21
21
RAID
Optical Disks
• Data is recorded by creating changes in reflectivity of
the disk
• A compact disc (CD) is an optical disk
– ISO Standard 9660
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.23
23
Overview of device-level I/O
• I/O instructions and I/O commands
– I/O instruction
• An I/O instruction initiates an I/O operation; it involves the CPU,
DMA, device controller and device
• An I/O operation may consist of several distinct tasks
– e.g., reading from a disk involves positioning disk heads, locating a
sector and performing data transfer
• Individual tasks in I/O are performed through ‘I/O commands’
• An I/O instruction indicates the (cu, d) pair identifying a device and
specifies the commands that describe the tasks to be performed
– I/O command
• Performs a specific task in an I/O operation
– e.g., positioning disk heads, reading data, etc.
– Does not involve the CPU
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.24
24
Device-Level I/O
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.25
25
I/O Programming
• I/O flag is set to “I/O in progress”
• CPU loops at IN_PROGRESS until I/O flag is set to
“I/O complete” by the interrupt processing routine
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.26
26
The Physical IOCS
• Purpose of physical IOCS is to:
– Simplify the code of user processes by hiding the
complexity of I/O operations
– Ensure high system performance
• Purpose achieved through:
– Handling device level I/O
– Synchronizing a process with completion of an I/O
operation
– I/O scheduling
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.27
27
Logical Devices
• Logical device: an abstraction employed for a variety of
useful purposes
– In simplest case, it is merely a name for a physical I/O
device
– Its use solves a practical difficulty: the address of a
physical device is not known when code is written
• A logical device can also be a virtual device
– Kernel has to map the logical device into a part of a
physical device
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.28
28
Physical IOCS Data Structures
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.29
29
Organization of Physical IOCS
• Ways in which physical IOCS is activated:
– Through start-io or await-io calls
– Through occurrence of an I/O completion interrupt
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.30
30
Implementation of Physical IOCS
• When opening a file alpha, open constructs a file
control blocks (FCB) for it in the open files table (OFT)
and returns internal idalpha
– internal idalpha: offset of the FCB in the OFT
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.31
31
Device Drivers
• In modern OSs, the physical IOCS provides generic
support for I/O operations
– Invokes a specialized device driver (DD) module for
handling device-level details
• Device drivers are not part of the physical IOCS
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.32
32
Disk Scheduling
• Total seek time involved in a set of I/O operations
depends on the order in which they are performed
• Disk scheduling aims to achieve high disk throughput
– First-come, first-served (FCFS) scheduling
– Shortest seek time first (SSTF) scheduling
– SCAN scheduling
• Scan: Disk heads moved from one end of platter to another
• A scan is followed by a reverse scan
• Look scheduling: a variant that starts reverse scan when no
more disk operations can be serviced in a scan
– Circular SCAN or CSCAN scheduling
• No reverse scans performed; Variant: Circular look (C-look)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.33
33
Disk Scheduling Policies
Buffering of Records
• An access method for sequential files reduces the wait
times faced by a process through the technique of
buffering of records
– Tries to overlap I/O and CPU activities in the process
– Achieved through:
• Prefetching
• Postwriting
• I/O buffer (or buffer): memory area temporarily used to
hold the data involved in an I/O operation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.35
35
Sequential
activities
Parallel
activities
File processing with a single buffer
• Operation of Single_buf_P proceeds as follows
– After processing one record, it waits until I/O on the buffer
is complete, copies the record into Rec_area and
processes it
tw : Wait time per record
tee : Effective elapsed time per record
tw = (tio – tp) + tc, if tio ≥ tp
= tc, if tio < tp
tee = tw + tp = tc + max (tio, tp)
Total elapsed time = tio + (number of records -1) x tee
+ (tc + tp)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.37
37
Use of Multiple Buffers
• Use of multiple buffers is irrelevant if a process
manipulates each record individually
– It makes a significant difference if a process manipulates
many records together
• Many buffers may be full when the process needs a few
records together
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.38
38
Blocking of Records
• Blocking of records reduces effective I/O time per
record by reading/writing many records in a single I/O
operation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.39
39
Blocking of Records (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.40
40
Buffered Processing of a File
Containing Blocked Records
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.41
41
Access Methods
• The IOCS may provide access methods for the
following kinds of processing:
–
–
–
–
–
Unbuffered processing of sequential-access files
Buffered processing of sequential-access files
Processing of direct-access files
Unbuffered processing of index sequential-access files
Buffered processing of index sequential-access files
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.42
42
Access Methods (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.43
43
Disk and File Caches
• A generic technique of speeding up access to file data
is to use a memory hierarchy consisting of a part of
memory and files stored on a disk
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.44
44
Unified Disk Cache
• The virtual memory manager has a page cache
• A unified disk cache is a single cache used for both
paging and file I/O
– It reduces number of copy operations
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.45
45
Case Studies
• Unix
• Linux
• File Processing in Windows
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.46
46
Unix
• Devices have an entry in the directory hierarchy, and
are accessed by using the same calls as files
• Main components of the UNIX IOCS:
– Device drivers
• Two parts: top half and bottom half
– Buffer cache
• Disk cache organized as a pool of buffers
• Each buffer is the same size as a disk block
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.47
47
Unix Buffer Cache
• A hash table is used to speed up the search for a
required disk block
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.48
48
Linux
• Linux IOCS is analogous to Unix IOCS
• Linux kernel modules—which include device drivers—
are dynamically loadable
• Read operations are performed at a higher priority than
write operations
• I/O operations involving adjoining disk blocks are
combined when possible
• Each buffer in the disk cache has a buffer header that is
allocated in a slab of the slab allocator
• Dirty buffers in the disk cache are written to the cache
when the cache is too full
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.49
49
File processing in Linux
• Provides four I/O schedulers
– No-op scheduler: performs FCFS scheduling
– Deadline scheduler: Look scheduling with additions
• Write operations may delay reads, thus blocking their
processes, hence read and write operations have deadlines
of 0.5 and 5 secs, resp.
– Completely fair queuing
• Performs round-robin between I/O operations of processes
– Anticipatory scheduler
• Tries to perform the next I/O operation of a process before
disk heads are moved
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.50
50
File Processing in Windows
• Uses layered device drivers
• Performs file caching
• Vista has added prioritized I/O
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.51
51
Summary
• The file system implements sharing and protection of
files; the IOCS implements file operations
• IOCS layers: access methods and physical IOCS
• Data staggering techniques, disk attachment
technologies, and redundant arrays of inexpensive
disks improve I/O throughput
• Disk scheduling performs the I/O operations directed at
a disk
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.52
52
Summary (continued)
• An access method improves the performance of a file
processing activity within a process using buffering and
blocking of records
• Caching reduces the number of I/O operations
performed to access data stored in files
–
–
–
–
Physical IOCS implements a disk cache
An access method implements a file cache
The virtual memory handler uses a page cache
OSs use a unified disk cache to reduce copying and
eliminate the need for multiple copies of pages
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
14.53
53