File System Interface PDF

File-System Interface  File Concept Computers can store information on various storage media, such as magnetic disks, magnetic tapes, and optical disks. So that the computer system will be convenient to use, the operating system provides a uniform logic...

File-System Interface  File Concept Computers can store information on various storage media, such as magnetic disks, magnetic tapes, and optical disks. So that the computer system will be convenient to use, the operating system provides a uniform logical view of stored information. The operating system abstracts from the physical properties of its storage devices to define a logical storage unit, the file. Files are mapped by the operating system onto physical devices. These storage devices are usually nonvolatile, so the contents are persistent between system reboots. Contiguous logical address space Types: Data numeric character binary Program Contents defined by file’s creator Many types Consider text file, source file, executable file  File-System Structure File structure Logical storage unit Collection of related information File system resides on secondary storage (disks) Provided user interface to storage, mapping logical to physical Provides efficient and convenient access to disk by allowing data to be stored, located retrieved easily Disk provides in-place rewrite and random access I/O transfers performed in blocks of sectors (usually 512 bytes) File control block – storage structure consisting of information about a file Device driver controls the physical device File system organized into layers  File Attributes Name – only information kept in human-readable form Identifier – unique tag (number) identifies file within file system Type – needed for systems that support different types Location – pointer to file location on device Size – current file size Protection – controls who can do reading, writing, executing Time, date, and user identification – data for protection, security, and usage monitoring Information about files are kept in the directory structure, which is maintained on the disk Many variations, including extended file attributes such as file checksum Information kept in the directory structure File info Window on Mac OS X Some newer file systems also support extended file attributes, including character encoding of the file and security features such as a file checksum  File Operations File is an abstract data type Creating a file. Two steps are necessary to create a file. First, space in the file system must be found for the file. Second, an entry for the new file must be made in the directory Write – at write pointer location, system call Read – at read pointer location, system call, current location position Reposition within file - seek Delete – space deallocate, remove entry Truncate – Only file attributes remains Open(Fi) – search the directory structure on disk for entry Fi, and move the content of entry to memory Close (Fi) – move the content of entry Fi in memory to directory structure on disk  File Operations File is an abstract data type Create Write – at write pointer location Read – at read pointer location Reposition within file - seek Delete create() and delete() are Truncate system calls that work with closed rather than open files. Open(Fi) – search the directory structure on disk for entry Fi, and move the content of entry to memory Close (Fi) – move the content of entry Fi in memory to directory structure on disk create() and delete() are system calls that work with closed rather than open files.  Open Files Several pieces of data are needed to manage open files: Open-file table: tracks open files File pointer: pointer to last read/write location, per process that has the file open File-open count: counter of number of times a file is open – to allow removal of data from open-file table when last processes closes it Disk location of the file: cache of data access information Access rights: per-process access mode information  Open File Locking Provided by some operating systems and file systems Similar to reader-writer locks Shared lock similar to reader lock – several processes can acquire concurrently Exclusive lock similar to writer lock Mediates access to a file Mandatory or advisory: Mandatory – access is denied depending on locks held and requested Advisory – processes can find status of locks and decide what to do  File Types – Name, Extension The system uses the extension to indicate the type of the file and the type of operations that can be done on that file. Only a file with a.com,.exe, or.sh extension can be executed, for instance. The.com and.exe files are two forms of binary executable files, whereas the.sh file is a shell script containing, in ASCII format, commands to the operating system.  File Structure None - sequence of words, bytes Simple record structure Lines Fixed length Variable length Complex Structures Formatted document Relocatable load file Can simulate last two with first method by inserting appropriate control characters Who decides: Operating system Program File Structure  Access Methods Sequential Access read next write next reset no read after last write (rewrite) Direct Access – file is fixed length logical records read n write n position to n read next write next rewrite n n = relative block number also called as relative access / dynamic access Relative block numbers allow OS to decide where file should be placed See allocation problem in Ch 12 Sequential-access File Simulation of Sequential Access on Direct-access File  Allocation Methods – 1. Contiguous An allocation method refers to how disk blocks are allocated for files: Contiguous allocation – each file occupies set of contiguous blocks Best performance in most cases Simple – only starting location (block #) and length (number of blocks) are required Problems include finding space for file, knowing file size, external fragmentation, need for compaction off-line (downtime) or on-line  Allocation Methods – 1. Contiguous Mapping from logical to physical Q LA/512 R Block to be accessed = Q + starting address Displacement into block = R Advantages: It is simple to implement – Both Sequential & dynamic access] Best suited for sequential files Disadvantages Difficult to find out contiguous block: External fragmentation File size unknown priorly  Allocation Methods – 1. Contiguous Extent-Based Systems Many newer file systems (i.e., Veritas File System) use a modified contiguous allocation scheme Extent-based file systems allocate disk blocks in extents An extent is a contiguous block of disks Extents are allocated for file allocation A file consists of one or more extents  Allocation Methods – 2. Linked Linked allocation – each file a linked list of blocks File ends at nil pointer No external fragmentation Each block contains pointer to next block No compaction, external fragmentation Free space management system called when new block needed Improve efficiency by clustering blocks into groups but increases internal fragmentation Reliability can be a problem Locating a block can take many I/Os and disk seeks  Allocation Methods – 2. Linked (Cont.) FAT (File Allocation Table) variation Beginning of volume has table, indexed by block number Much like a linked list, but faster on disk and cacheable New block allocation simple  2. Linked Allocation No External Fragmentation But needs number of pointer needed is more Direct Access is difficult If pointer fails? 2. Linked Allocation File-Allocation Table  Allocation Methods - Indexed Indexed allocation Each file has its own index block(s) of pointers to its data blocks Logical view Example of Indexed Allocation Indexed Allocation  I/O Systems Operating System Concepts – 9th Silberschatz, Galvin and Gagne ©2013  Overview The role of the operating system in computer I/O is to manage and control I/O operations and I/O devices. I/O management is a major component of operating system design and operation Important aspect of computer operation I/O devices vary greatly [So, I/O sub systems of kernels ] Various methods to control them Performance management New types of devices frequent Ports, busses, device controllers connect to various devices Device drivers encapsulate device details The device drivers present a uniform device-access interface to the I/O subsystem, much as system calls provide standard interface between the application and the operating system.  I/O Hardware Incredible variety of I/O devices Storage (disks, tapes) Transmission (modems, n/w cards) Human-interface (screen, keyboard mouse) Device Communicate through cable or air Common concepts – signals from I/O devices interface with computer Port – connection point for device Bus - daisy chain or shared direct access PCI bus common in PCs and servers, PCI Express (PCIe) expansion bus connects relatively slow devices Controller (host adapter) – electronics that operate port, bus, device Sometimes integrated Sometimes separate circuit board (host adapter) Contains processor, microcode, private memory, bus controller, etc – Some talk to per-device controller with bus controller, microcode, memory, etc  I/O Hardware Buses are used widely in computer architecture and vary in their signaling methods, speed, throughput, and connection methods. A PCI bus (the common PC system bus) connects the processor–memory subsystem to fast devices, and an expansion bus connects relatively slow devices, such as the keyboard and serial and USB ports. In the upper-right portion of the figure, four disks are connected together on a Small Computer System Interface (SCSI) bus plugged into a SCSI controller. Other common buses used to interconnect main parts of A computer include PCI Express (PCIe),withthroughputofupto16GB per second, and HyperTransport,withthroughputofupto25GB per second. A Typical PC Bus Structure  I/O Hardware (Cont.) I/O instructions control devices Devices usually have registers where device driver places commands, addresses, and data to write, or read data from registers after command execution Data-in register, data-out register, status register, control register Typically 1-4 bytes, or FIFO buffer Devices have addresses, used by Direct I/O instructions Memory-mapped I/O Device data and command registers mapped to processor address space Especially for large address spaces (graphics) Device I/O Port Locations on PCs (partial)  Polling For each byte of I/O 1. Read busy bit from status register until 0 2. Host sets read or write bit and if write copies data into data-out register 3. Host sets command-ready bit 4. Controller sets busy bit, executes transfer 5. Controller clears busy bit, error bit, command-ready bit when transfer done Step 1 is busy-wait cycle to wait for I/O from device – access status register again and again until busy bit is cleared Reasonable if device is fast But inefficient if device slow CPU switches to other tasks? But if miss a cycle data overwritten / lost The hardware mechanism that enables a device to notify the CPU is called an interrupt.  Interrupts Polling can happen in 3 instruction cycles Read status, logical-and to extract status bit, branch if not zero How to be more efficient if non-zero infrequently? CPU Interrupt-request line triggered by I/O device Checked by processor after each instruction Interrupt handler receives interrupts – Accepts address CPU catches interrupt and dispatch to interrupt handler CPU has toe interrupt request lines Non-maskable interrupt, which is reserved for events such as unrecoverable memory errors. maskable: it can be turned off by the CPU before the execution of critical instruction sequences that must not be interrupted. The maskable interrupt is used by device controllers to request service.  Interrupts interrupt-controller hardware Interrupt vector to dispatch interrupt to correct handler Contains the memory addresses of specialized interrupt handlers. Context switch at start and end Based on priority Some nonmaskable Interrupt chaining if more than one device at same interrupt number Implementation of system calls – Software Interrupt or trap Interrupt-Driven I/O Cycle Intel Pentium Processor Event-Vector Table  Interrupts (Cont.) Interrupt mechanism also used for exceptions Terminate process, crash system due to hardware error Page fault executes when memory access error System call executes via trap to trigger kernel to execute request Multi-CPU systems can process interrupts concurrently If operating system designed to handle it Used for time-sensitive processing, frequent, must be fast  Direct Memory Access Used to avoid programmed I/O (one byte at a time) for large data movement Requires DMA controller -Handshaking between the DMA controller and the device controller is performed via a pair of wires called DMA-request and DMA-acknowledge Bypasses CPU to transfer data directly between I/O device and memory OS writes DMA command block into memory Source and destination addresses Read or write mode Count of bytes Writes location of command block to DMA controller Bus mastering of DMA controller – grabs bus from CPU Cycle stealing from CPU but still much more efficient When done, interrupts to signal completion Version that is aware of virtual addresses can be even more efficient - DVMA Six Step Process to Perform DMA Transfer  Application I/O Interface I/O system calls encapsulate device behaviors in generic classes Device-driver layer hides differences among I/O controllers from kernel New devices talking already-implemented protocols need no extra work Each OS has its own I/O subsystem structures and device driver frameworks Devices vary in many dimensions Character-stream or block Sequential or random-access Synchronous or asynchronous (or both) Sharable or dedicated Speed of operation read-write, read only, or write only  I/O Requests to Hardware Operations Consider reading a file from disk for a process: Determine device holding file Translate name to device representation Physically read data from disk into buffer Make data available to requesting process Return control to process Life Cycle of An I/O Request  Chapter 14: Protection Operating System Concepts – 9th Silberschatz, Galvin and Gagne ©2013  A computer system is a collection of processes and objects. By objects, we mean both hardware objects (such as the CPU, memory segments, printers, disks, and tape drives) and software objects (such as files, programs, and semaphores). Each object has a unique name that differentiates it from all other objects in the system, and each can be accessed only through well-defined and meaningful operations. Objects are essentially abstract data types. Access Matrix  Use of Access Matrix Allowing controlled change in the contents of the access-matrix entries requires three additional operations: copy, owner,and control The ability to copy an access right from one domain (or row) of the access matrix to another is denoted by an asterisk (*) appended to the access right. The copy right allows the access right to be copied only within the column Access Matrix of Figure A with Domains as Objects  Access Matrix of Figure A with Domains as Objects Rows-Domains, Columns-Objects Representation  Use of Access Matrix The copy and owner rights allow a process to change the entries in a column. A mechanism is also needed to change the entries in a row. The control right is applicable only to domain objects. If access(i, j) includes the control right, then a process executing in domain Di can remove any access right from row j.  Implementation of Access Matrix Generally, a sparse matrix Option 1 – Global table Store ordered triples in table A requested operation M on object Oj within domain Di -> search table for < Di, Oj, Rk > with M ∈ Rk But table could be large -> won’t fit in main memory Difficult to group objects (consider an object that all domains can read)  Implementation of Access Matrix (Cont.) Option 2 – Access lists for objects Each column implemented as an access list for one object Resulting per-object list consists of ordered pairs defining all domains with non-empty set of access rights for the object Easily extended to contain default set -> If M ∈ default set, also allow access  Implementation of Access Matrix (Cont.) Each column = Access-control list for one object Defines who can perform what operation Domain 1 = Read, Write Domain 2 = Read Domain 3 = Read Each Row = Capability List (like a key) For each domain, what operations allowed on what objects Object F1 – Read Object F4 – Read, Write, Execute Object F5 – Read, Write, Delete, Copy  Rather than associating the columns of the access matrix with the objects as access lists, we can associate each row with its domain.  Implementation of Access Matrix (Cont.) Option 3 – Capability list for domains Instead of object-based, list is domain based Capability list for domain is list of objects together with operations allows on them Object represented by its name or address, called a capability Execute operation M on object Oj, process requests operation and specifies capability as parameter Possession of capability means access is allowed Capability list associated with domain but never directly accessible by domain Rather, protected object, maintained by OS and accessed indirectly Like a “secure pointer” Idea can be extended up to applications  Access Control Protection can be applied to non-file resources Oracle Solaris 10 provides role-based access control (RBAC) to implement least privilege Privilege is right to execute system call or use an option within a system call Can be assigned to processes Users assigned roles granting access to privileges and programs Enable role via password to gain its privileges Similar to access matrix  Revocation of Access Rights Various options to remove the access right of a domain to an object Immediate vs. delayed Selective vs. general Partial vs. total Temporary vs. permanent Access List – Delete access rights from access list Simple – search access list and remove entry Immediate, general or selective, total or partial, permanent or temporary End of Chapter