Khoa học máy tính - Chapter 14: Implementations of file operations

Chapter 14Implementations of File OperationsCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionLayers of the Input-Output Control SystemOverview of I/O OrganizationI/O DevicesDevice-Level I/OThe Physical IOCSDevice DriversDisk Scheduling2Operating Systems, by Dhananjay Dhamdhere*Introduction (continued)Buffering of RecordsBlocking of RecordsAccess MethodsDisk and File CachesUnified Disk CacheCase Studies3Operating Systems, by Dhananjay Dhamdhere*Layers of the Input-Output Control SystemInput-output control system (IOCS) holds some file data in memory to provide efficient file processing and high device throughput4Operating Systems, by Dhananjay Dhamdhere*Layers of the Input-Output Control System (continued)Two layers:Access method layer provides efficient file processingPhysical IOCS layer provides high device throughput5Operating Systems, by Dhananjay Dhamdhere*Layers of the Input-Output Control System (continued)6Operating Systems, by Dhananjay Dhamdhere*Overview of I/O OrganizationI/O organization was discussed in Chapter 2Each device controller has a unique numeric idEach device connected to it has a unique numeric device idA device address is (controller_id, device_id)An I/O operation involves:Operation to be performed—read, write, etc.Address of the I/O deviceNumber of bytes of data to be transferredAddresses of areas in memory and on the I/O device that are to participate in the data transfer7Operating Systems, by Dhananjay Dhamdhere*I/O OperationsThe 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_addrI/O_command_addr is start address of the memory area containing the following two I/O commands:Position disk heads on track track_idRead record record_id into the memory area with the start address memory_addr8Operating Systems, by Dhananjay Dhamdhere*I/O DevicesCan be classified using the following criteria:Purpose: Input, print and storageNature of access: Sequential and random-accessData transfer mode: Character and block modeThe I/O time for a record is the sum of its access time and transfer time:910I/O Devices (continued)11Operating Systems, by Dhananjay Dhamdhere*Magnetic TapesStrip of magnetic materialInformation is recorded in the form of 1s and 0sRecording on a tape is multitrackEach track records a bit of a byte or a parity bitOperations:read/write, skip, rewindOlder technologies inserted interrecord gapsStreaming tapes contain a single record stored without a break irrespective of its sizeInterrecord gaps do not exist even when a large volume of data is recorded on a tape12Operating Systems, by Dhananjay Dhamdhere*Magnetic DisksCRCs used for error detectionRecords of a track are given serial numbers with respect to the start-of-track position markAccess time:Seek time: Disk head movementRotation latencyCommands:seek (cylinder number, surface number)read/writeTracks are organized into sectors13Operating Systems, by Dhananjay Dhamdhere*Data Staggering TechniquesSector interleaving addresses problems caused by data transfer time14Operating Systems, by Dhananjay Dhamdhere*Data Staggering Techniques (continued)Head skewing addresses the problems caused by head switch time15Operating Systems, by Dhananjay Dhamdhere*Data Staggering Techniques (continued)Cylinder skewing addresses the problems caused by seek time16Operating Systems, by Dhananjay Dhamdhere*Sector Interleaving17Operating Systems, by Dhananjay Dhamdhere*Disk Attachment TechnologiesIntegrated device electronics (IDE) or ATAPrimarily work with programmed I/O modesSmall computer system interconnect (SCSI)Provides functionality traditionally done by the IOCS:Disk schedulingBad block recoveryPrefetching of dataEnhanced integrated device electronics (EIDE)Supports new DMA modes18Operating Systems, by Dhananjay Dhamdhere*Disk Attachment Technologies (continued)Network-Attached Storage and Storage Area Networks:19Redundant Array of Inexpensive Disks (RAID)An array of cheap disks is used instead of a single diskDifferent RAID arrangements provide three benefitsReliabilityStore data redundantly (remember stable storage?)Read / write redundant data records in parallel Fast data transfer ratesStore file data on several disks in the RAIDRead / write file data in parallelFast accessStore two or more copies of dataTo read data, access the copy that is accessible most efficientlyOperating Systems, by Dhananjay Dhamdhere*20Disk stripingA 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 RAIDData written on strips in a disk stripe can be read in parallelThis arrangement provides high data transfer ratesOperating Systems, by Dhananjay Dhamdhere*21RAID22Operating Systems, by Dhananjay Dhamdhere*Optical DisksData is recorded by creating changes in reflectivity of the diskA compact disc (CD) is an optical diskISO Standard 966023Overview of device-level I/OI/O instructions and I/O commandsI/O instructionAn I/O instruction initiates an I/O operation; it involves the CPU, DMA, device controller and deviceAn I/O operation may consist of several distinct taskse.g., reading from a disk involves positioning disk heads, locating a sector and performing data transferIndividual 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 performedI/O commandPerforms a specific task in an I/O operatione.g., positioning disk heads, reading data, etc.Does not involve the CPUOperating Systems, by Dhananjay Dhamdhere*24Operating Systems, by Dhananjay Dhamdhere*Device-Level I/O25Operating Systems, by Dhananjay Dhamdhere*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 routine26Operating Systems, by Dhananjay Dhamdhere*The Physical IOCSPurpose of physical IOCS is to:Simplify the code of user processes by hiding the complexity of I/O operationsEnsure high system performancePurpose achieved through:Handling device level I/OSynchronizing a process with completion of an I/O operationI/O scheduling27Operating Systems, by Dhananjay Dhamdhere*Logical DevicesLogical device: an abstraction employed for a variety of useful purposesIn simplest case, it is merely a name for a physical I/O deviceIts use solves a practical difficulty: the address of a physical device is not known when code is writtenA logical device can also be a virtual deviceKernel has to map the logical device into a part of a physical device28Operating Systems, by Dhananjay Dhamdhere*Physical IOCS Data Structures29Operating Systems, by Dhananjay Dhamdhere*Organization of Physical IOCSWays in which physical IOCS is activated:Through start-io or await-io callsThrough occurrence of an I/O completion interrupt30Operating Systems, by Dhananjay Dhamdhere*Implementation of Physical IOCSWhen 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 OFT31Operating Systems, by Dhananjay Dhamdhere*Device DriversIn modern OSs, the physical IOCS provides generic support for I/O operationsInvokes a specialized device driver (DD) module for handling device-level detailsDevice drivers are not part of the physical IOCS32Operating Systems, by Dhananjay Dhamdhere*Disk SchedulingTotal seek time involved in a set of I/O operations depends on the order in which they are performedDisk scheduling aims to achieve high disk throughputFirst-come, first-served (FCFS) schedulingShortest seek time first (SSTF) schedulingSCAN schedulingScan: Disk heads moved from one end of platter to anotherA scan is followed by a reverse scanLook scheduling: a variant that starts reverse scan when no more disk operations can be serviced in a scanCircular SCAN or CSCAN schedulingNo reverse scans performed; Variant: Circular look (C-look)33Disk Scheduling Policies34Operating Systems, by Dhananjay Dhamdhere*Buffering of RecordsAn access method for sequential files reduces the wait times faced by a process through the technique of buffering of recordsTries to overlap I/O and CPU activities in the processAchieved through:PrefetchingPostwritingI/O buffer (or buffer): memory area temporarily used to hold the data involved in an I/O operation35Parallel activitiesSequential activities36File processing with a single bufferOperation of Single_buf_P proceeds as followsAfter 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*37Operating Systems, by Dhananjay Dhamdhere*Use of Multiple BuffersUse of multiple buffers is irrelevant if a process manipulates each record individuallyIt makes a significant difference if a process manipulates many records togetherMany buffers may be full when the process needs a few records together38Blocking of records reduces effective I/O time per record by reading/writing many records in a single I/O operationOperating Systems, by Dhananjay Dhamdhere*Blocking of Records39Operating Systems, by Dhananjay Dhamdhere*Blocking of Records (continued)40Operating Systems, by Dhananjay Dhamdhere*Buffered Processing of a File Containing Blocked Records41Operating Systems, by Dhananjay Dhamdhere*Access MethodsThe IOCS may provide access methods for the following kinds of processing:Unbuffered processing of sequential-access filesBuffered processing of sequential-access filesProcessing of direct-access filesUnbuffered processing of index sequential-access filesBuffered processing of index sequential-access files42Operating Systems, by Dhananjay Dhamdhere*Access Methods (continued)43Operating Systems, by Dhananjay Dhamdhere*Disk and File CachesA 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 disk44Operating Systems, by Dhananjay Dhamdhere*Unified Disk CacheThe virtual memory manager has a page cache A unified disk cache is a single cache used for both paging and file I/OIt reduces number of copy operations45Operating Systems, by Dhananjay Dhamdhere*Case StudiesUnixLinuxFile Processing in Windows46Operating Systems, by Dhananjay Dhamdhere*UnixDevices have an entry in the directory hierarchy, and are accessed by using the same calls as filesMain components of the UNIX IOCS:Device driversTwo parts: top half and bottom halfBuffer cacheDisk cache organized as a pool of buffersEach buffer is the same size as a disk block47Operating Systems, by Dhananjay Dhamdhere*Unix Buffer CacheA hash table is used to speed up the search for a required disk block48Operating Systems, by Dhananjay Dhamdhere*LinuxLinux IOCS is analogous to Unix IOCSLinux kernel modules—which include device drivers—are dynamically loadableRead operations are performed at a higher priority than write operationsI/O operations involving adjoining disk blocks are combined when possibleEach buffer in the disk cache has a buffer header that is allocated in a slab of the slab allocatorDirty buffers in the disk cache are written to the cache when the cache is too full49File processing in LinuxProvides four I/O schedulersNo-op scheduler: performs FCFS schedulingDeadline scheduler: Look scheduling with additionsWrite operations may delay reads, thus blocking their processes, hence read and write operations have deadlines of 0.5 and 5 secs, resp.Completely fair queuingPerforms round-robin between I/O operations of processesAnticipatory schedulerTries to perform the next I/O operation of a process before disk heads are movedOperating Systems, by Dhananjay Dhamdhere*50Operating Systems, by Dhananjay Dhamdhere*File Processing in WindowsUses layered device driversPerforms file cachingVista has added prioritized I/O51Operating Systems, by Dhananjay Dhamdhere*SummaryThe file system implements sharing and protection of files; the IOCS implements file operationsIOCS layers: access methods and physical IOCSData staggering techniques, disk attachment technologies, and redundant arrays of inexpensive disks improve I/O throughputDisk scheduling performs the I/O operations directed at a disk52Operating Systems, by Dhananjay Dhamdhere*Summary (continued)An access method improves the performance of a file processing activity within a process using buffering and blocking of recordsCaching reduces the number of I/O operations performed to access data stored in filesPhysical IOCS implements a disk cacheAn access method implements a file cacheThe virtual memory handler uses a page cacheOSs use a unified disk cache to reduce copying and eliminate the need for multiple copies of pages53