Operating Systems Lecture Notes PDF

Dr. Arwa E. Abulwafa  Introduction  File System Management  Storage Management  Process Management  CPU Scheduling  Threading  Memory Management  Virtual Memory Management 2 Lecture (2)  Generally a file system consists of three parts:  A collection of fi...

Dr. Arwa E. Abulwafa  Introduction  File System Management  Storage Management  Process Management  CPU Scheduling  Threading  Memory Management  Virtual Memory Management 2 Lecture (2)  Generally a file system consists of three parts:  A collection of files,  Each storing related data  A directory structure,  Which organizes and provides information about all the files in the system  Partitions,  Which are used to separate physically or logically large collections of directories 4  The basic function of the file system:  It provides the mechanism for managing and accessing of both data and programs. 5  Physical Storage Unit:  They are the different storage media, such as magnetic disks, magnetic taps, and optical disks.  Logical Storage Units:  They are files (generally, files are mapped, by the operating system, onto physical devices) 6  A file is a named collection of related information that is recorded on secondary storage.  It is a sequence of bits, bytes, lines or records which is defined by the file’s creator and user.  It is the smallest element of logical secondary storage; that is, data cannot be written to secondary storage unless they are within a file.  Generally, files represent programs (both source and object forms) and data. 7  Many types of information may be stored in a file, such as:  Source programs  Object programs  Executable programs  Data files  Which contains; numeric data, text, graphic images, sound recording and so on. 8  A file has a certain defined structure according to its type, for example: File Type Structure Sequence of characters organized into lines (and possibly Text file pages) Source file Sequence of subroutines and functions Sequence of bytes organized into blocks Object file Understandable by the system’s linker (compiled file) A series of code sections that the loader can bring into Executable file memory and execute. 9  A file has certain attributes, which vary from one operating system to another; however, general attributes are: Attributes Description Name Seen by the user A unique number identifies the file within the file system Identifier It is not seen by the user Type Needed for systems that support different file types A pointer to: Location The physical device (on which the file is stored) The location of the file on that device 10  Attributes Description The current size of the file (in bytes, words, or blocks) Size And possibly the maximum allowed size Access-control information determines who can do reading, Protection writing, executing and so on Time and Date Date and time for creation, last modification and last use  The information about all files is kept in the directory structure that also resides on secondary storage.  Typically, the file’s entry contains the different file attributes. 11  OS provides System Calls to create, write, read, reposition, delete and truncate files.  There are 12 different file operations, which are: Operation Description Space in the file system must be found for the file Create a file An entry for the new file must be made in the directory to store different attributes (name, location,..) Make write system call specifying both the name of the file Writing to a file and the information to be written to the file 12  Operation Description To read a file (to memory): Reading a file Use a read system call that specifies the name of the file and where (in memory) the file should be put Repositioning Current-file-position is set to a given value within a file This file operation is also known as File Seek Search the directory for the named file When found the associated directory entry, erase the Deleting a file directory entry So, that file space can be reused by other files 13  Operation Description Erase the contents of a file but keep its attributes unchanged Truncating a file Except the file length which is reset to zero and its file space released Append Add new information to the end of an existing file Rename Change the name attribute of the file in the directory entry Creating new file, and reading from the old and writing to Copying of a file the new 14  Operation Description You can also read the file properties to view or modify them. This is done either automatically by OS when you add some Get and Set file data to the file, for example, OS modifies the file's size. attributes You can also modify the file properties yourself, such as changing the file name. Sections Such as: Lock sections, Share sections, Map sections into Operations memory 15  Operation Description Open: Open operation search the directory, copying directory entry into open-file-table Open and Close Close: When file is no longer used, OS removes its entry from open-file-table. 16  Most of file operations involve searching the directory for the entry associated with the named file.  To avoid this constant searching, many systems require that an open system call be used before any other operation.  The operating system keeps a small table containing information (attributes) about all open files (the open- file-table). 17  When a file operation is requested, the file is specified via an index into this table, so no searching is required. 18  OS implementing file types by including the type as part of the file name.  The name is split into two parts: a name and an extension, usually separated by a period character “.” 19  For example, in MS-DOS, a name can consist of up to eight characters followed by a period “.” and terminated by an extension of up to three characters. 20  The system uses the extension to:  Indicate the type of the file and the type of the operations that can be done on that file.  For example, only a file with.corn,.exe, or.bat extension can be executed.  Specify the application programs that will open the file,  For example if the file has.doc extension, then it should be opened by Microsoft Word. 21 File Type Extension Function Executable exe, com, bin Read to run machine language program Object obj, o Compiled, machine language not linked Source Code C, java, pas, asm, a Source code in various languages Batch file bat, sh Commands to the command interpreter Text files txt, doc Textual data, documents Multimedia mpeg, mov, rm For containing audio/video information 22  Because OS uses extensions to determine:  The type of the file  Operations that can be done on the file  The application program that should open the file 23  OS organizes files into big storages, which are:  Partitions (Volume)  Directories  Disks are split into one or more partitions (mini-disks or volumes) each treated as a separate storage device or virtual disk. 24  The different directory operations are:  Search for a file  Create a file  Delete a file  List a directory  Rename a file 25  The collection of files is a file directory.  The directory contains information about the files, including attributes, location, and ownership.  Much of this information, especially that is concerned with storage, is managed by the operating system.  The directory is itself a file, accessible by various file management routines. 26  Information contained in a device directory is:  Name  Type  Address  Current length  Maximum length  Date last accessed  Date last updated  Owner id  Protection information 27  Efficiency:  A file can be located more quickly.  Naming:  It becomes convenient for users as two users can have same name for different files or may have different name for same file.  Grouping:  Logical grouping of files can be done by properties e.g. all java programs, all games etc. 28  Single-Level Directory Systems  Two-Level Directory Systems  Tree-Structure Directory Systems  Acyclic-Graph Directory Systems 29  It is the simplest form of directory system.  Having only one directory containing all the files (root directory).  Used on early personal computers; because there was only one user. 30  Advantages:  Simplicity  The ability to locate files (there is only one place to look)  Disadvantages:  In a system with multiple users, different users may accidentally use the same names for their files.  For example; if user A creates a file called mailbox, and then later a user B creates a file called mailbox, B’s file will overwrite A’s file. 31  To avoid conflicts caused by different users choosing the same file name for their own files.  Each user has his own directory called User File Directory (UFD)  All UFDs connected to a Master File Directory (MFD)  When a user starts a job, MFD is searched to point to the users UFD, and then this UFD is only searched to find the particular file. 32 33  Advantages:  Solve the naming conflict problem  Decrease time to search for a file; because the search for the file is done in the UDF only.  Disadvantages:  Isolating between users; So that when a user want to open another’s file, he must specify both (user name & file name)  For example;  open (“x”) opens a file called x in the user’s directory,  open (“nancy/x”) opens a file x in the directory of 34 another user, Nancy.  The two-level hierarchy eliminates name conflicts among users, but is not satisfactory for users with a large number of files.  Each user can create any number of directory to group similar files together.  A directory (or subdirectory) contains a set of files or subdirectories. 35  Nearly all modern file systems are organized in this manner;  Because the ability for users to create an arbitrary number of subdirectories provides a powerful structuring tool for users to organize their work.  A path name: is the path from the root directory through all subdirectories to the file.  Absolute: begins from the root.  Relative: begins from the current directory. 36 37  Allows directories to be shared between different users.  More than one user can access the subdirectories and files in the shared directory. 38  Advantages:  Flexible;  Because sharing is more useful than the existence of multiple copies.  Disadvantages:  A file may have multiple absolute path names.  Delete & update the shared files may cause problems. 39 40  File access method refers to how to access the file.  Access here means how to read and write to the file.  There are three different file access methods, which are:  Sequential Access Method  Direct Access Method  Indexed Access Method 41  A file is viewed as a fixed length of logical blocks (record), each record stores a piece of data.  Files can be accessed (read and write) in one of three methods:  Sequential  Direct (Random)  Indexed 42  Blocks are processed in order, one record (block) after another.  In this case, the Records of the file are dealt with sequentially,  So a specific record cannot be accessed for Reading unless the previous records are passed through, this is done using the Read Pointer. 43  While Writing is done at the end of the file, when the Write Pointer reaches the End Of File (EOF), this means that the file is finished. 44  Operations:  Read:  Read (next) command using a read pointer  Write:  Write (EOF, Data) append to the end of the file  Examples: text, sound, and video files. 45  Allow arbitrary blocks to be read or written in no order.  Each record has a relative block number, which is an index relative to the beginning of the file. 46  Operations:  Read: Read (N)  Write: Write (N, Data), where N is the relative block number  As shown in the previous figure:  A request Read (N) is turned to I/O request to read L bytes starting at location L*(N-1) within the file (where L is the record width in bytes).  A request Write (N, Data) is to write the data in the nth record (starting at location L*(N-1) within the file). 47  Examples: database files  The following SQL commands read the 1st and the 4th record from the shown database file: name age address Select * from Tb1 where name = “Ahmed”; Read Ahmed 25 Mansoura Select * from Tb1 where name = “Hani”; Operation Ali 34 Cairo Mona 56 Tanta Update Tb1 set age = 50 where name = “Ahmed”; Write Hani 44 Sues Update Tb1 set address = “Tanta” where age = 34; Operation Kamal 23 Alex 48  Each file has an index  The index contains pointers for each block (record), hence, it maximizes reading speed.  Example: database files with indexes. name age name age address Ahmed 3 Mona 25 Mansoura Database Ali 5 Kamal 34 Cairo File Indexed Mona 4 Ahmed 56 Tanta by Name Hani 2 Hani 44 Sues Kamal 1 Ali 23 Alex 49  The Indexed Access Method depends on creating an index for each file so that when reading or writing to the file, the record number is searched for within the index first.  Sometimes Indexed Access Method is unusable method; because with large files, the index will be too large to be kept in memory. 50  It is needed to allocate disk space to files need to be stored to achieve:  Maximum disk space utilization.  Quick file access.  There are four disk or file allocation methods:  Contiguous Allocation  Linked Allocation  Indexed Allocation  File Allocation Table (FAT) 51  Each file owns set of contiguous blocks on the disk. 52  Advantages:  Simple, only starting location and length (no. of blocks) are required.  Disadvantages:  Finding space (hole) for a new file.  We may use first fit, best fit, or worst fit.  External fragmentation (free space is fragmented into many small pieces each piece can not store a file).  The solution is compaction (compact all free space into one contiguous space)  File size need to be known when file created. 53  This file blocks are distributed anywhere on the disk in the form of a linked list of blocks.  Each block contains a pointer to the next block (lost space) 54  Advantage:  No external fragmentation  It is never necessary to compact disk  File size need not to be known during file creation  file can be extended any where in the disk 55  Disadvantages:  Limited to sequential access  To access block n we must follow blocks from the beginning  Not reliable  When pointer are lost or damaged  Lost space for pointers. 56  Each file has its own index block, which is an array of disk block addresses.  The directory contains only the file name and the address of the index block. 57  Advantages:  No external fragmentation  Simple directory entry  Disadvantages:  Pointer overhead  The problem of determining the size of the index block 58  A section of the disk at the beginning of each partition contains the FAT  FAT has one entry for each disk block and is indexed by block number  Directory entry contains the number of first block of the file  Each table entry contains the number of the next block in the file. 59  This continues until the last block which has end-of- file (EOF) value as a table entry  Unused blocks indicated by a 0 table value  Ex: a FAT structure for a file has 3 disk blocks (217, 618, 339)  Allocating a new block for a file done as following (assuming the last block number is N which contains EOF) 60   Searching for the first 0 entry (let its block no. = M)  Let Table_Entry (Block M) = EOF and  Table_Entry (Block N) = M  Advantages:  The same as Linked Allocation method  Disadvantages:  FAT must be cached in memory;  Because if not, this results in a significant of head seeks.  Not reliable;  When FAT damaged, all files can be reached. 61 62  It is to keep data safe from physical damage such as power failure, head crashes, dirt, temperature, content lose due to software bugs.  Data reliability achieved by maintaining backups (copy disk to tapes) at regular intervals. 63  It is to keep data safe from improper access by controlling file operations such as; read, append (write to the end of file), execute, delete, list file attributes. Protection can be achieved by Access Control List Password (ACL) 64  Each file and folder has an ACL.  ACL contains user names and type of access (rights) allowed for each user.  Users are classified for each file as:  Owner:  user who create the file  Group:  set of users sharing similar access  Universe:  remaining users 65  Protection using ACL achieved as following:  Problems:  ACL is usually a long list (consider situation when all users are allowed to access the file) 66  Associate a password with each file  Protection using password is achieved as following:  Problems:  This method becomes impractical (with many protected files, user need to remember many passwords) 67 68