Operating Systems Concepts - File Management PDF

Click to edit Master text styles – Second level Operating Third level Systems Concepts – Fourth level » Fifth level Unit 5 File Management 1  File M...

Click to edit Master text styles – Second level Operating Third level Systems Concepts – Fourth level » Fifth level Unit 5 File Management 1  File Management File management is one of the functions of the OS Click to edit Master text styles The user’slevel – Second processes may request the OS to create, delete, levelopen, close, read, write … etc. a file (using copy, Third system –calls Fourthof course) level » Fifth level OS translates those requests into the form required by the appropriate device controller OS transfers this information into the controller’s registers Thanks also to the OS, the user can view the data (as information) even though the hardware stores it as sequence of bits or bytes 2  File Click A filetoisedit a named Master collection text styles of related data (not –necessarily Second level a sequence) residing in secondary memory (disk, tape, drum … etc.) and having a Third level – Fourth level certain structure » Fifth level All relevant information about files such as name, structure, location, size, protection, creation time … etc. is usually accessible directly or indirectly from file directories 3  Record Click A data itemMaster to edit whichtext canstyles be written in one write –system call, Second level and read in one read system call Third level Be aware – Fourththat level other system calls are needed before you can » Fifth levelread or write (e.g. to open the file or set the position in the file appropriately … etc.) 4  Block All the data that can be written or read in one hardware transfer operation Click to edit Master text styles Blocks may be the same as records, but usually – Second level are not Third level – Fourth level Several» records Fifth level may be contained in one block, and it is also common that a record may occupy several blocks OS also maintains data buffers. A data buffer is occupied by only one block 5  Disk Click A direct access to edit Masterdevice text styles –Data Second level can be read or written directly by Third level specifying – Fourth its leveldisk address » Fifth level A disk address consist of cylinder#, track# and sector# The size of a block is usually fixed and occupies one sector on the disk 6  Disk cont. Click to edit Master text styles – Second level Third level – Fourth level » Fifth level 7  Disk cont.  Disk = 1 or many cylinders Click to edit Master text styles  –Cylinder = many Second level platters Third level  Platter = 2 level – Fourth surfaces (except top and bottom usually) » Fifth level  Surface = many tracks  Track = many sectors  Sector = 1 block  Block = 1 or many records (or less than 1) 8  Tape By nature, a sequential access device Click to edit Master text styles –Similar Secondto an old movie reel level Third level A block– cannot Fourth levelbe read (or written) without reading (or writing) all» the Fifthpreceding level blocks Moreover, when you write a block, all the blocks stored behind (beyond) the written one are considered lost Due to the physical properties of the tape, blocks should be relatively large to ensure good tape utilization 9  File Access Methods Click Howtorecords can text edit Master be read stylesor written? – Second level In general, Third level OS supports two access methods: – Fourth level Sequential » Fifth level access Direct access Some operating systems may provide other methods like: indexed sequential access (which we will discuss later) 10  Sequential Access A file is viewed as a sequence of records (data Click to edit Master text styles items) – Second level Third level Conceptually, – Fourth level you can think of that there is a pointer associated » Fifth level with an open file Opening the file, positions the pointer at the beginning of the file (beginning of the first record) The read operation reads the next record into a record-variable: readNext(recVar) 11  Sequential Access cont. The write operation, writes the contents of the Click to edit Master text styles record variable into the next record of the file: – Second level writeNext(recVar) Third level – Fourth level Every read/write » Fifth level moves the pointer by one record (I.e. just behind the last read/written record) Sequential access works with both tapes and disks, and is associated with the problems of updating records on tapes or disks 12  Direct Access Click A filetoisedit viewed astext Master a set of numbered records styles –(usually of fixed Second level length) Third level The read operation reads a particular record – Fourth level into a record-variable: » Fifth level read(rec#, recVar) The write operation, writes the contents of the record variable into a particular record of the file: write(rec#, recVar) The OS must know the record length in order to find the location of the record being read or written 13  Direct Access cont. Click Thetorecord lengthtext edit Master is specified styles at the time of file –creation, and Second level is kept in the directory Third level Using– the Fourthrecord level length from the directory, the OS can calculate » Fifth level the disk address of the block containing the record as well as the record’s position inside the block No problems of updating records on disks 14  Direct Access Example Click to editwrite(4, Master dataA) text styles – Second level write(1, Third level dataB) – Fourth level »write(3, Fifth level dataC) 0 1 2 3 4 ……………… dataB dataC dataA ……………. 15  Disk Scheduling In contemporary mainframes, disks are Click to edit Master text styles extensively used, and often the disk transfer – Second level request comes before the previous one has Third level completed – Fourth level » Fifth level To ensure reasonable performance of the computer system, the OS must keep the Average Service Time for the disk very low This can be achieved by appropriate scheduling of disk’s access requests 16  Disk Scheduling cont. Disk access time is influenced by three factors: Click to edit Master text styles –Second Seekleveltime: time needed to move the arm to the required Third level track position (avg 5-20 ms) – Fourth level  Latency time: » Fifth leveltime needed for the desired sector to appear under the heads (below 8ms)  Transfer time: time needed to transfer the sector (fraction of the latency time) The goal for an OS is to minimize the seek time, because the other two factors are more or less hardware dependent 17  Disk Scheduling Algorithms 1.Click FCFS- First to edit Come Master First text Serve: serve the disk styles –requests in Second level the order they come in Third level 2. SSTF- Shortest – Fourth level Seek Time First: serve the disk request »that Fifth requires level the shortest seek time first 3. SCAN: the arm oscillates between the first track and the last track, and as it moves in one direction, it serves the requests on its way (similar to a bus or train route) 18  Disk Scheduling Algorithms cont. 4. C-SCAN: same as SCAN, but carries out Click to edit Master text styles requests when moving in one only of the two – Second level directions Third level (say towards 0, call it the inward direction) – Fourth level » Fifth level 5. LOOK: same as SCAN, but head only oscillates between the lowest and highest requests 6. C-LOOK: same as C-SCAN, but head only oscillates between the lowest and highest requests 19  Disk Scheduling Algorithms cont. Click Algorithms # 3 through to edit Master text styles # 5 are also –referred Second levelto as the elevator algorithms, Third levelthey are used in elevators because – Fourth level » Fifth level 20  Example Assume that you have a disk that has 261 Click to edit tracks Master text (numbered styles 0-260) and the current – Second level position is at track 60, and the arm is moving Third level inwards (towards – Fourth level track 0) » Fifth level The request queue has the following (track numbers): 30, 110, 80, 240, 20 Compute the total seek time each of the disk scheduling algorithms assuming the time needed to move from one track to the next is 1ms (for simplicity) 21  FCFS Head at: 60 moving inwards towards 0 Request Click Queue: to edit Master 30 text110 80 240 20 styles – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 30 + 80 + 30 + 160 + 220 = 520 (60-30)+(110-30)+(110-80)+(240-80)+(240-20)= 250 22  SSTF Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 20 + 30 + 80 + 10 + 220 = 360 23  SCAN Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 30 + 10 + 20 + 80 + 30 + 130 = 300 24  C-SCAN (serving inwards) Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 30 + 10 + 20 + 260 + 20 + 130 + 30 = 500 25  C-SCAN (serving outwards) Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 60 + 20 + 10 + 50 + 30 + 130 = 300 26  LOOK Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 30 + 10 + 60 + 30 + 130 = 260 27  C-LOOK (serving inwards) Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 30 + 10 + 220 + 130 + 30 = 420 28  C-LOOK (serving outwards) Head at: 60 moving inwards towards 0 Click to edit Master text styles Request Queue: 30 110 80 240 20 – Second level Third level – Fourth level » Fifth level 0 20 30 60 80 110 240 260 Disk Movement = 40+ 10 + 50 + 30 + 130 = 260 29  Complete Solution Click to edit Master text styles Algorithm – Second level Total Algorithm Total Third level Time Time – Fourth level C-SCAN FCFS 520 300 » Fifth level (serving outwards) SSTF 360 LOOK 260 C-LOOK SCAN 300 420 (serving inwards) C-SCAN C-LOOK 500 260 (serving inwards) (serving outwards) 30  Note Click On to the average, edit C-SCAN Master text styles is as fast as SCAN, –because the Second level movement when not serving is Third much faster level than the movement when serving – Fourth level SCAN however » Fifth level gives a more uniform distribution The same things can be said about C-LOOK and LOOK 31  Let’s Try This One Click Consider a sequence of disk requests as below: to edit Master text styles Request – Secondfor Track Number: level 30 Third 90level 50 140 40 170 10 195 80 – Fourth level What will be» the Fifthtotal levelhead movement, when each of the following algorithms is used: (a) FCFS b) SSTF (c) SCAN (d) C-SCAN (e) LOOK (f) C-LOOK Assume that currently the heads are positioned at track 80. You may also assume that initially the heads are moving towards track number 0, and that the disk has tracks numbered 0 through 199 on each surface. 32  Allocation Methods Three Click toallocation edit Mastermethods: text styles – Second level  Third Contiguous level allocation – Fourth level  Linked » Fifth level allocation  Indexed allocation 33  Contiguous Allocation Click A file to will edit be allocated Master a set of consecutive text styles – sectors. To Second level implement such a scheme is very simple. Third level – Fourth level The scheme supports direct access. » Fifth level To find a record (actually the sector containing the record), the Os needs:  The disk address for the beginning of the file  Size of the record  The record number 34  Contiguous Allocation cont. Click Thetoscheme alsotext edit Master supports styles sequential access, – and is level Second very fast in this case, because sectors are accessed Third level one after the other, with very little –(ifFourth any) level head movement. » Fifth level Problems:  Finding enough contiguous disk space  Fragmentations occur  If additional space is needed (and must be allocated) for the file 35  Linked Allocation Click Each sector to edit keeps Master a link text styles to the next – Second level sector in the file Third level – Fourth level The address of the first sector can be » Fifth level obtained from the file directory Supports sequential access, and does not support direct access 36  Linked Allocation cont. Directory Click to edit Master text styles – Second level Third level – Fourth level » Fifth level …… … …… … …… … …… 37  Linked Allocation cont. Good: Click to edit Master text styles – Second level No problems Third level with finding space for a file – Fourth level No problems » Fifth levelwith fragmentation No problems with adding space for a file 38  Linked Allocation cont. Bad: Click to edit Master text styles – Second Doeslevel not support direct access Third level Links occupy – Fourth level some part of the sector » Fifth level When going from one sector to another, substantial head movement may be required Problems with reliability: When a sector is modified, the link must be re- written, and if there is a transmission error, we loose the file (in addition, some other files can get damaged) 39  Linked Allocation cont. Possible Click to edit Master text styles improvements: – Second level Keep the name of the file in each sector. OS Third level – Fourth level checks the name, and does not access a » Fifth level sector whose name does not match the name of the file being accessed Use double links (a doubly linked list). A link to previous sector as well as a link to the next sector in the file. 40  Indexed Allocation Click Thetofirst edit sector Masterin text thestyles file contains an index – that identifies Second level the address of all the sectors Third level belonging to the same file – Fourth level » Fifth level So, it is like keeping a list of addresses for the file in the first sector 41  Indexed Allocation cont. Directory Click to edit Master text styles 1, 10 – Second level 0 2 Third level – Fourth level 3, 8, 2 » Fifth level 3 5 6 8 …… … …… 9 11 … …… … …… 42  Indexed Allocation cont. Good: Click to edit Master text styles – Second level No problems with fragmentation Third level – Fourth level Supports direct and sequential access » Fifth level No problems with adding space for a file. Just find a free sector and update the file’s index 43