14 Aug - OS - File Management

Duration: 1 hr 8 min

This video lesson is available to enrolled students.

Enroll to watch — GATE Guidance by Sanchit Sir

AI Summary

An AI-generated summary of this video lecture.

This lecture covers disk scheduling algorithms and file system allocation methods, focusing on solving GATE exam problems. The instructor begins with a GATE 2018 problem on Shortest Seek Time First (SSTF) scheduling, calculating power consumption based on head movement and direction reversals. He then moves to GATE 2015 problems involving disk access time, calculating total read times based on seek time, rotational latency, and transfer rates. The lecture transitions to file allocation methods, explaining Contiguous, Linked, and Indexed allocation with diagrams. Finally, he solves a GATE 2014 problem on calculating the maximum file size in a Unix-like file system using an inode with direct and indirect pointers.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The video begins with a GATE 2018 problem concerning disk scheduling and power consumption. The system is a storage disk with 4 platters, 200 cylinders, and 256 sectors per track. Six disk requests are provided in the format [sector, cylinder, platter]: [120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3], [56, 116, 2], and [118, 16, 1]. The head is currently at sector 100 of cylinder 80 and is moving towards higher cylinder numbers. The problem asks for the total power consumption in milliwatts to satisfy all requests using the Shortest Seek Time First (SSTF) algorithm. Power dissipation is defined as 20 milliwatts for moving the head over 100 cylinders and 15 milliwatts for reversing the direction of movement once. Rotational latency and platter switching power are negligible.

  2. 2:00 – 5:00 02:00-05:00

    The instructor starts solving the SSTF problem by focusing on the cylinder numbers, as seek time depends on cylinder movement. The current cylinder is 80. The request cylinders are 72, 134, 20, 86, 116, and 16. He calculates the distance from the current cylinder (80) to each request cylinder to determine the shortest seek. The distances are |80-72|=8, |80-134|=54, |80-20|=60, |80-86|=6, |80-116|=36, and |80-16|=64. The shortest distance is 6, corresponding to cylinder 86. He begins to map out the sequence of head movement on the disk tracks.

  3. 5:00 – 10:00 05:00-10:00

    The instructor continues the SSTF sequence. After cylinder 86, the remaining cylinders are 72, 134, 20, 116, 16. From 86, the closest is 72 (distance 14). From 72, the closest is 116 (distance 44). From 116, closest is 134 (18). From 134, closest is 20 (114). From 20, closest is 16 (4). The sequence is 80 -> 86 -> 72 -> 116 -> 134 -> 20 -> 16. He calculates the total seek distance and the number of direction reversals to compute the total power consumption. He notes that the power for movement is proportional to distance (20mW per 100 cylinders) and reversal is a fixed cost (15mW).

  4. 10:00 – 15:00 10:00-15:00

    The video transitions to a GATE 2015 problem about disk access time. The disk pack has a seek time of 4 milliseconds and a speed of 10000 rotations per minute (RPM). It has 600 sectors per track, and each sector stores 512 bytes of data. A file stored on the disk contains 2000 sectors. The problem assumes that every sector access necessitates a seek, and the average rotational latency for accessing each sector is half the time for one complete rotation. The goal is to find the total time in milliseconds needed to read the entire file.

  5. 15:00 – 20:00 15:00-20:00

    The instructor solves the GATE 2015 problem by first calculating the time for one complete rotation. With 10000 RPM, one rotation takes 60 seconds / 10000 = 6 milliseconds. The average rotational latency is half of this, which is 3 milliseconds. Since every sector access requires a seek, the seek time of 4 milliseconds is added for each of the 2000 sectors. He sets up the formula for total time: Total Time = Number of Sectors * (Seek Time + Average Rotational Latency + Transfer Time).

  6. 20:00 – 25:00 20:00-25:00

    The instructor completes the calculation for the GATE 2015 problem. He calculates the transfer time for one sector. The transfer rate is not explicitly given as a rate but can be derived or the transfer time is considered negligible or calculated based on rotation. However, the instructor calculates the total time as 1420 ms. This implies he summed (4ms + 3ms) * 2000 + transfer time. 7ms * 2000 = 14000ms? No, that's too high. Let's look at the instructor's writing. He writes "2000 x (4ms + 3ms/2) + ...". No, he writes "2000 x (4ms + 3ms) + ...". Then he writes "14000ms + ...". Then he writes "1420ms". This is confusing. Let's assume the instructor's calculation is the ground truth for the summary. He arrives at 1420 ms.

  7. 25:00 – 30:00 25:00-30:00

    A new problem from GATE 2015 is introduced. It involves a typical disk rotating at 15000 RPM with a transfer rate of 50 x 10^6 bytes/sec. The average time of the disk is twice the average rotational delay. The controller's transfer time is 10 times the disk transfer time. The task is to find the average time in milliseconds to read or write a 512-byte sector of the disk.

  8. 30:00 – 35:00 30:00-35:00

    The instructor solves the GATE 2015 problem. He calculates the rotation time: 60 seconds / 15000 = 4 milliseconds. The average rotational delay is half of this, which is 2 milliseconds. The problem states the average time of the disk is twice the average rotational delay, so the average time is 4 milliseconds. He then calculates the disk transfer time for a 512-byte sector using the transfer rate of 50 x 10^6 bytes/sec.

  9. 35:00 – 40:00 35:00-40:00

    The instructor finishes the GATE 2015 problem. He calculates the controller's transfer time as 10 times the disk transfer time. He sums the average time (4ms) and the controller transfer time to get the total average time. The disk transfer time is 512 / (50 * 10^6) seconds = 10.24 microseconds. The controller transfer time is 10 * 10.24 = 102.4 microseconds. The total time is 4ms + 0.1024ms = 4.1024ms? Wait, the instructor writes "6.11264ms". Let's re-evaluate. Maybe "average time of the disk" includes seek? No, usually it's latency. Let's trust the instructor's final number of 6.11264 ms.

  10. 40:00 – 45:00 40:00-45:00

    The lecture shifts to File Allocation methods. The instructor lists three major methods: Contiguous, Linked, and Indexed. He explains that the main aim is effective disk space utilization and quick access. He notes that while some systems support all three, it is more common for a system to use one method for all files. He introduces the concept of file allocation as a way to manage disk space.

  11. 45:00 – 50:00 45:00-50:00

    The instructor explains Contiguous Allocation. He shows a diagram of a disk with numbered blocks. He explains that each file occupies a set of contiguous blocks. He displays a directory table showing the file name, start block, and length. He mentions that accessing block b+1 after block b normally requires no head movement, which is efficient for sequential access. However, it can lead to external fragmentation.

  12. 50:00 – 55:00 50:00-55:00

    The instructor explains Linked Allocation. He shows a diagram where disk blocks are linked in a list. He explains that blocks can be scattered anywhere on the disk. The directory contains a pointer to the first and last blocks. He mentions this solves the external fragmentation problem of contiguous allocation because blocks do not need to be contiguous. However, it can lead to slow random access.

  13. 55:00 – 60:00 55:00-60:00

    The instructor explains Indexed Allocation. He shows a diagram with an index block. He explains that this method brings pointers together into one location. He details the structure of an inode, showing direct blocks, single indirect, double indirect, and triple indirect pointers. This solves problems of both contiguous and linked allocation by allowing non-contiguous blocks while maintaining fast access to all blocks via the index.

  14. 60:00 – 65:00 60:00-65:00

    A problem from GATE 2014 is presented regarding the maximum file size in a Unix-like file system. The inode has 12 direct, one single indirect, and one double indirect pointers. The disk block size is 4KB, and a block address is 32-bits long. The goal is to find the maximum possible file size in GB. The instructor highlights the key parameters: 12 direct pointers, 1 single indirect, 1 double indirect, 4KB block size, and 32-bit addresses.

  15. 65:00 – 68:21 65:00-68:21

    The instructor solves the GATE 2014 problem. He calculates the number of addresses per block: 4KB / 4B = 1024 addresses. He calculates the size contributed by direct pointers: 12 * 4KB = 48KB. He calculates the size for single indirect: 1024 * 4KB = 4MB. He calculates the size for double indirect: 1024 * 1024 * 4KB = 4GB. He sums these up to find the total maximum file size, which is approximately 4 GB. He emphasizes that the double indirect pointer dominates the size.

The lecture provides a comprehensive review of disk scheduling and file system management, crucial for operating systems exams. It begins with practical problem-solving on disk scheduling algorithms like SSTF, emphasizing the calculation of seek time and power consumption. The instructor then transitions to disk access time calculations, breaking down the components of seek time, rotational latency, and transfer time. The second half of the lecture focuses on file allocation methods, detailing the mechanisms of Contiguous, Linked, and Indexed allocation. The session concludes with a complex problem on calculating maximum file size using an inode structure, reinforcing the understanding of direct and indirect pointers. This progression from scheduling to allocation provides a holistic view of disk management.