Design of Operating Systems
Design of Operating Systems CSE 585
Popular in Course
Popular in Computer Engineering
This 69 page Class Notes was uploaded by David Mayert on Wednesday October 21, 2015. The Class Notes belongs to CSE 585 at Syracuse University taught by Staff in Fall. Since its upload, it has received 47 views. For similar materials see /class/225567/cse-585-syracuse-university in Computer Engineering at Syracuse University.
Reviews for Design of Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/21/15
Chapter 6 File Systems 61 Files 62 Directories 63 File system implementation 64 Example file systems Longterm Information Storage Must store large amounts of data Information stored must survive the termination of the process using it Multiple processes must be able to access the information concurrently File Naming Extension Meaning filebak Backup file filec C source program filegif Compuserve Graphical Interchange Format image filehlp Help file filehtml World Wide Web HyperText Markup Language document filejpg Still picture encoded with the JPEG standard filemp3 Music encoded in MPEG layer 3 audio format filempg Movie encoded with the MPEG standard fileo Object file compiler output not yet linked filepdf Portable Document Format file fileps PostScript file filetex Input for the TEX formatting program filetxt General text file filezip Compressed archive Typical file extensions IHHWHHHWWHH A m V File Structure 1 Byte 1 Record lllml ll Cat Cow Dog Goat Lion Owl Pony Rat Worm IIWII b C 0 Three kinds of files byte sequence record sequence tree File Types Mod Magic number H d name e Text size Data size D t a e g BSS size E Symbol table size Eggs Owner Entry point Protection s Flags H d e Te t Obje t modul Dat He d Relocat bits Obje t modul N Symbol quotV I table a b a An executable file b An archive File Access 0 Sequential access read all bytesrecords from the beginning cannot jump around could rewind or back up convenient when medium was mag tape 0 Random access bytesrecords read in any order essential for data base systems read can be 0 move file marker seek then read or 0 read and then move file marker File Attributes Attribute Meaning Protection Who can access the file and in what way Password Password needed to access the file Creator ID of the person who created the file Owner Current owner Readonly flag 0 for readwrite 1 for read only Hidden flag 0 for normal 1 for do not display in listings System flag 0 for normal files 1 for system file Archive flag 0 for has been backed up 1 for needs to be backed up ASCIIbinary flag 0 for ASCII file 1 for binary file Random access flag 0 for sequential access only 1 for random access Temporary flag 0 for normal 1 for delete file on process exit Lock flags 0 for unlocked nonzero for locked Record length Number of bytes in a record Key position Offset of the key within each record Key length Number of bytes in the key field Creation time Date and time the file was created Time of last access Date and time the file was last accessed Time of last change Date and time the file has last changed Current size Number of bytes in the file Maximum size Number of bytes the file may grow to Possible file attributes File Operations 1 Create 2 Delete 3 Open 4 Close 5 Read 6 Write 7 Append 8 Seek 9 Get attributes 10Set Attributes 1 1Rename An Example Program Using File System Calls 12 File copy program Error checking and reporting is minimal include ltsystypeshgt include necessary header files include ltfcntlhgt include ltstdlibhgt include ltunistdhgt int mainint argc char argv ANSI prototype define BUFSIZE 4096 use a buffer size of 4096 bytes define OUTPUTMODE 0700 protection bits for output file int mainint argc char argv int infd outfd rdcount wtcount char bufferBUFSIZE if argc 3 exit1 syntax error if argc is not 3 An Example Program Using File System Calls 22 Open the input file and create the output file infd openargv1 ORDONLY open the source file if infd lt 0 exit2 if it cannot be opened exit outfd creatargv2 OUTPUTMODE create the destination file if outfd lt 0 exit3 if it cannot be created exit Copy loop while TRUE rdcount readinfd buffer BUFSIZE read a block of data if rdcount lt 0 break if end of file or error exit loop wtcount writeoutfd buffer rdcount write data if wtcount lt 0 exit4 wtcount lt 0 is an error Close the files closeinfd closeoutfd if rdcount 0 no error on last read exitO else exit5 error on last read Memory Mapped Files Program Program text text I Data I Data Xyz a b a Segmented process before mapping files into its address space b Process after mapping existing file abc into one segment creating new segment for xyz Directories Single Level Directory Systems I Root directory 0 A single level directory system contains 4 files owned by 3 different people A B and C TWO level Directory Systems lt Root directory Letters indicate Owners of the directories and files Hierarchical Directory Systems lt Root directory A hierarchical directory system Path Names bin lt Root directory A UNIX directory tree 15 Directory Operations 1 Create 2 Delete 3 Opendir 4 Closedir 5 Readdir 6 Rename 7 Link 8 Unlink File System Implementation Entire disk Partition table Disk partition Hi J l Boot block Super blockl Free space mgmt I Inodes I Root dir Files and directories A possible file system layout Implementing Files 1 File A File C File E File G 4 blocks 6 blocks 12 blocks 3 blocks r r r r l39lllll39l J l f J J File B File D File F 3 blocks 5 blocks 6 blocks a File A File C File E File G l1 HJ f J 4 File B 5 Free blocks 6 Free blocks 390 a Contiguous allocation of disk space for 7 files b State of the disk after files D and E have been removed 18 Implementing Files 2 File A File File File File File block block block block block 0 1 2 3 4 4 7 2 1O 12 File B File File File File block block block block 0 1 2 3 3 11 14 Physical 6 block Physical block Storing a file as a linked list of disk blocks Implementing Files 3 Physical block 0 File A starts here File B starts here mummhmm n LALLL WN lOLO Unused block n 01 Linked list allocation using a file allocation table in RAM 20 Implementing Files 4 File Attributes Address of disk block 0 Address of disk block 1 Address of disk block 2 Address of disk block 3 Address of disk block 4 Address of disk block 5 Address of disk block 6 Address of disk block 7 Address of block of pointers An example i node Disk block containing additional disk addresses 21 Implementing Directories 1 games attributes mail attributes news attributes work attributes a Data structure containing the attributes a A simple directory fixed size entries disk addresses and attributes in directory entry b Directory in which each entry just refers to an inode 22 Implementing Directories 2 File 1 entry length r Pointer to file 139s name File 1 attributes File 1 attributes Entry Pointer to file 239s name for one p r o J file 9 C T b u d g e t gt14 File 2 attributes File 2 entry length Pointer to file 339s name File 2 attributes File 3 attributes p e r s o n n e I IZI File 3 entry length File 3 attributes a Dl39DC39m39O j rICOs comma0 o ooco b l Entry for one file Heap 0 TWO ways of handling long file names in directory a In line b In a heap 23 Shared Files 1 Root directory Shared file File system containing a shared file 24 Shared Files 2 C39s directory B39s directory C39s directory B39s directory Owner C Owner C Owner C Count 1 Count 2 Count 1 a C b a Situation prior to linking b After the link is created CAfter the original owner removes the file 25 Disk Space Management 1 1000 o o 1000 Disk space utilization 6 800 so I m 3 N m E s 5 600 60 5 g a 8 2 E m g E 400 4o gv 8 i 200 20 D Data rate J J 0 0 128 256 512 1K 2K 4K 8K 16K 0 Block size Dark line left hand scale gives data rate of a disk Dotted line right hand scale gives disk space efficiency All files 2KB 26 dew 1K1 v q 1811 p9gt1u1112 no 1811 991 am BHUOJS 12 p v M lush JJOJJJJJOJJJOJJJ OJJJUJJJOJHOJJJ JJOOJOOOJJJOJJJJ JOJHOJJOJJOJJJJ OOOOJHOJJOJOJJJ JJOJJOJDJOOOJJJJ JJJOJHOJJJOHJJ ONOJJONOJJJON JUJOJJONOJJOJJU s SSPll q2K PIOCK unwpelz v J KB max DIOCK calI uolq see me as m 310 180 NS ses 350 139 33 318 180 54 99 533 93 1620 553 N 34 no 33 NS 55 30 945 gal J39 Jes 53 15 330 39 OJJONDJJJJJOJJJ Else QBK PIOCKZC 1839 1339 13 JUOJJUJJOJJOJJOO z 1U91119813U13W QOBdS qsyq Disk Space Management 3 D39 k Main IS g g a Almostfull block of pointers to free disk blocks in RAM three blocks of pointers on disk b Result of freeing a 3bloek file C Alternative strategy for handling 3 free blocks shaded entries are pointers to free disk blocks 28 Disk Space Management 4 Open file table Quota table Attributes Soft block limit disk addresses Hard block limit User 8 Current of blocks Quota pointer Block warnings left Soft file limit Hard file limit Current of files File warnings le k Quota record for user 8 Quotas for keeping track of each user s disk use 29 File System Reliability 1 Root directory 6 0 I e Directory that has not changed 6 9 File that 9 B haschanged g Filethathas not changed 0 A file system to be dumped squares are directories circles are files shaded items modified since last dump each directory amp file labeled by i node number 30 File System Reliability 2 a 1 2 3 4 5 6397 39839 91011121314151617181920212223242526272829303132 b l1 2 3 4 5 6 7 8 9 1o11121314151617181920212223242526272829303132 c l1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031I32 d l1 2 3 4 5 6397 8 91011121314l1516171819202122232425262728l29l3031l32 Bit maps used by the logical dumping algorithm 31 File System Reliability 3 DIUUK HUIHUeI DIUCK HUIHUBI 012 3 4 5 5 7 23 9101112131415 012 3 4 5 5 7 23 9101112131415 110101111001110oBIocksinuse 1101011110011100Blocksinuse 0010100001 10o011Free blocks 00001000o110o011FreebIocks a b 012 3 4 5 6 7 8 9101112131415 012 3 4 5 6 7 a 9101112131415 110101111001110oBIocksinuse 1101021110011100Blocksinuse 0010200001 100011Free blocks 00101o00011l00011FreebIocks File system states a consistent b missing block C duplicate block in free list d duplicate data block 32 Hash table File System Performance 1 Front LRU The block cache data structures Rear MRU File System Performance 2 lnodes are Disk is divided into located near cylinder groups each the start with its own inodes of the disk Cylinder group 4339quot s e e39 a b Inodes placed at the start of the disk 0 Disk divided into cylinder groups each with its own blocks and i nodes LogStructured File Systems 0 With CPUs faster memory larger disk caches can also be larger increasing number of read requests can come from cache thus most disk accesses will be writes LFS Strategy structures entire disk as a log have all writes initially buffered in memory periodically write these to the end of the disk log when file opened locate inode then find blocks 35 Example File Systems CDROM File Systems Padding es 1 1 8 8 7 1 2 4 1 I I I Location offile FileSize Date andtimeI I I CD ILI File name I Flags I n Interleave Extended attribute record length Directory entry length The ISO 9660 directory entry 36 The CPM File System 1 Address OXFFFF BIOS CPM Shell User program 0X100 Zero page Memory layout of CPM The CPM File System 2 Bytes 1 8 3 1 6 1 2 I l Filename l l l l l User code File type Extent Block count extension 1 Disk blocI numbers The CPM directory entry format Bytes The MS DOS File System 1 2 2 2 The MSDOS directory entry The MS DOS File System 2 Block size FAT12 FAT16 FAT32 05 KB 2 MB 1 KB 4 MB 2 KB 8 MB 128 MB 4 KB 16 MB 256 MB 1 TB 8 KB 512 MB 2 TB 16 KB 1024 MB 2 TB 32 KB 2048 MB 2 TB Maximum partition for different block sizes The empty boxes represent forbidden combinations The Windows 98 File System 1 Bytes 8 3 1 1 1 4 2 2 4 2 4 N Creation Last Last write Base name EXt l T l datetime access datetime Flle Slze Att 39b t T n U es Sec Upper 16 bits Lower 16 bits of starting of starting block block The extended MOS DOS directory entry used in Windows 98 41 The Windows 98 File System 2 Bytes 1 10 1 1 1 12 2 4 l 5 characters l O l l 6 characters O 2 characters Sequence Attributes Checksum An entry for part of along file name in Windows 98 42 The Windows 98 File System 3 Last N Creation S Bytes An example of how a long name is stored in Windows 98 43 The UNIX V7 File System 1 Bytes 2 14 File name k T Inode number A UNIX V7 directory entry Disk addresses The UNIX V7 File System 2 node Attributes Single 1 indirect 7 block Double indirect block A UNIX inode Triple indirect block Addresses of data blocks 45 The UNIX V7 File System 3 Block 132 Inode 26 Block 406 Inode 6 is usr is for is usrast Root directory is for lusr directory usrast directory 1 6 n 26 Mode Mode 1 size 1 size 5 39 39 I times I times 4 bin 19 dle 64 grants 7 dev 132 30 erik 406 92 books 14 lib 51 jim 60 mbox 9 etc 26 ast 81 minix 6 usr 45 bal 17 src 8 tmp Inode 6 Inode 26 Looking up says that usrast says that usrastmbox usr yields usr is in is inode usrast is in is inode inode 6 block 132 26 block 406 60 The steps in looking up usrastmb0x 46 Chapter 3 Deadlocks 31 Resource 32 Introduction to deadlocks 33 The ostrich algorithm 34 Deadlock detection and recovery 35 Deadlock avoidance 36 Deadlock prevention 37 Other issues Resources anything that can be used by only a single process at any instant of time Examples of computer resources 7 printers tape drives tables network 7 variables data structures Processes need access to resources in reasonable order Suppose a process holds resource A and requests resource B 7 at same time another process holds B and requests A 7 both are blocked and remain so Resources Deadlocks can occur when processes are granted exclusive access to devices we refer to these devices generally as resources 7 occur with non preemptable resources Preemptable resources can be taken away from a process with no ill effects Nonpreernptable resources will cause the process to fail if taken away Resources Sequence of events required to use a resource 1 request the resource 2 use the resource 3 release the resource Must wait if request is denied requesting process may be blocked may fail with error code Acquiring Resources typedef int semaphore semaphore resourceJ void processAvoid ownampresource1 seresource1 upampresource1 0 a typedef int semaphore semaphore resourceJ semaphore resource2 void processAvoid downamp 1 Fig 31 Using a semaphore to protect resources a One resource b Two resources Potential Deadlock typwef int semaphore semaphore resourceJ semaphore resourceJ semaphore resource2 semaphore resource2 void processAvo39d void processAvo39d downampr downampre usebothresources upampresource2 upampresource1 upampresource1 void processBvoid void processBvoid down down ampresource1 ampresource 2 downampresourc 2 downampresource1 bot r sources th resources upampresource1 upampresource1 upampresource2 a b Fig 32 a Deadlockfree code b Code with a potential deadlock Introduction to Deadlocks Formal definition A set ofprocesses is deadlocked if each process in the set is waitng for an event that only anotherproeess in the set can cause Usually the event is release of a currently held resource Each member of the set of deadlocked processes is waiting for a resource that is owned by a deadlocked process 7 This assumes that there is no other event that can occur that can cause a process in the set to release a resource 7 Interrupts that signal events that wake up processes is an example None of the processes can 7 run 7 release resources 7 be awakened Four Conditions for Deadlock Coffman et al Mutual exclusion condition each resource assigned to exactly 1 process or is available Hold and wait condition process holding resources can request additional No preemption condition previously granted resources cannot be forcibly taken away Circular wait condition must be a circular chain of 2 or more processes each is waiting for resource held by next member of the chain Deadlock Modeling Modeled with directed graphs a resource R assigned to process A b process B is requestingwaiting for resource S c process C and D are in deadlock over resources T and U a b C Process 0 Resource El A requests R Deadlock Modeling A Request R Request 8 Release R Release 6 S Deadlock B Request 5 Release T b C RequeslT Requesl R Release T Release R 9 96 e 9 Deadlock Modeling No Deadlock A B C Request R Request S RequestT Requests Request T Request R Release R Release 8 Release T Release 8 Release T Release R a b C 1 ArequeslsR 2 C t T 5355 4 C requests R 5 A leas R a elliiiafgcf E IEI I k l m n This graph occurs because it is assumed the OS has some way of knowing that deadlock could occur if the A B and C were round robined in the manner shown previously Hence the OS knows not to schedule Process B which avoids the Deadlock It should be noted that this is fictitious The OS is usually not that smart But the point of these slides is to show how directed graphs can be used to map out deadlock possibilities Deadlock Modeling Strategies for dealing with Deadlocks 1 Ignore the problem and pretend that deadlocks never occur in the system 0 used by most operating systems including Windows amp UNIX 7 detection and recovery 3 dynamic avoidance careful resource allocation 4 prevention structurally negate one of the four necessary conditions The Ostrich Algorithm An Acceptable Technique for Dealing With Deadlock Stick your head in the sand and pretend there is no problem Reasonable if 7 deadlocks occur veryrarely 7 cost ofprevention is high UNIX and Windows takes this approach 7 assume most users would prefer an occasional deadlock to a rule of restricting all users to one process one open file etc 7 Price is too high for eliminating all deadlocks It is a trade off between 7 convenience 7 correctness 39Ostrich Algorithm is an acceptable technique for dealing with deadlocks 39OS process table size is limited Forks could fail If a parent sat in a loop until it could fork we have potential deadlock 39Number open files is limited by the inode table size If it fills up a process could be infinitely blocked on an open call 39Same with swap space 39Same with all OS tables that mange resources 39Should we abolish all abilities for a process to create add ional processes because of potential deadlocks No Deadlock Detection and Recovery Instead of sticking our head in the sand Deadlock Detection Single resource of each type Multiple resources of each type Deadlock Recovery Preemption Rollback Elimination Killing Processes Deadlock Detection Detection with Only One Resource of Each Type Six 6 Resources Seven 7 Processes Current State Process Holds Wants A S B T C S D U S T E T V F W S G V U Is System Deadlocked Deadlock Detection Detection with Only One Resource of Each Type E gt G a b Note the resource ownership and requests A cycle can be found within the graph denoting deadlock 16 Easy to detect deadlock with graph and human eye but OS programs need an algorithm Algorithms exist which detect cycles in directed graphs The key to these slides is that we can programmatically create the directed graph and we can programmatically detect if it has a cycle 16 Deadlock Detection Detection with Multiple Resources of Each Type Resources in existence Resources available E1 E2 E3 Em A1 A2 A3 Am Current allocation matrix Request matrix C11 C12 C13 39 Cirn R11 R12 R13 39 Rim C21 22 23 39 39 39 2m R21 22 23 39 39 R2m f Cnl C39n2 Cn3 Cnrn Rm an Rn3 I an Row n is current allocation Row 2 is what process 2 needs to process n Data structures needed by deadlock detection algorithm 11 2 Cij Aj Ej i1 l7 Deadlock Detection Detection With Multiple Resources of Each Type lt29 0 be re 09 06 be ea 06 06 Q 2 Q 0 g Q 29 lt2 03 00 2Q lt2 e0 9 E 4 2 3 1 A2 1 O 0 Current allocation matrix Request matrix 0 010 2 o 01 e 2 o 01 R 1010 012 o 21 o 0 After Process 3 Runs A 2 2 2 0 AfterProcess2RunsA422l An example for the deadlock detection algorithm With no deadlock 18 Process 1 cannot run because it needs a CD ROM and there are none Process 2 cannot run because it needs a Scanner and there are none 18 Deadlock Detection Detection With Multiple Resources of Each Type 9 42 Q 9 4 Q 9 0 lt9 0 6 Q lt0 Q16 0amp8 00 lt29 96 0 8 90 Q9 29 Q a0 00 Q lt2 e0 9 E 4 2 3 1 A 2 1 o 0 Request matrix 0 0 1 0 2 0 O 1 C 2 0 0 1 R 1 0 1 O 1 2 0 2 1 O No Process can run An example for the deadlock detection algorithm With deadlock Note error in book Process 3 requests were updated NOT Process 2 l9 Deadlock Recovery Traffic only in one direction Each section of a bridge can be Viewed as a resource If a deadlock occurs it can be resolved if one car backs up preempt resources and rollback or if a car is removed Several cars may have to be backed up if a deadlock occurs Starvation is possible 20 Recovery from Deadlock Preemption Recovery through preemption take a resource from some other process depends on nature of the resource 39 Difficult if not impossible to implement in IIIOSI cases Preemption 7 take the case of the dining philosophers final solution A resource really cannot be taken away since a resource is a semaphore which represent the philosophers themselves This really does not make sense This does make sense in the case of the solution where we use semaphores to represent the individual forks which ends up in a deadlock Preemption of resources might fix this problem But what do we do for a thread that has it s forks taken away Can the OS really take the semaphore fork away without letting the program within the thread know 21 Recovery from Deadlock Rollback Deadlock Recovery through rollback checkpoint a process periodically use this saved state After Rollback restart the process if it is found deadlocked 22 Rollback We could probably checkpoint a process but what about a single thread in that process Since memory is shared among threads in the process it would not be possible to checkpoint say the state of a single philosopher
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'