GATE CS

File systems and disk scheduling

A file system decides how files and directories are laid out on disk blocks, how a block is found from a file offset, and how free space is tracked. Disk scheduling then orders the requests to cut head movement. The standard calculations here are the largest file size under i-node and linked schemes, disk access time, bit-vector and FAT sizes, and total head movement for a request queue.

6 previous-year questions · 6 solved · 5 practice questions

Files and directories

A file is a named collection of related bytes kept on secondary storage. The operating system stores its attributes (name, size, owner, permissions, times, and where its blocks are) in a file control block, which in UNIX-style systems is the i-node. A directory maps names to these control blocks (or to i-node numbers). Disk space is handed out in fixed-size blocks; a block is one or more sectors.

Directory structure	Idea	Main drawback
Single-level	One directory for all files	Names must be unique across all users
Two-level	One directory per user under a master directory	Users cannot easily share files
Tree (hierarchical)	Directories inside directories; a file has exactly one path	Sharing needs a copy or a link
Acyclic graph	Tree plus links, so a file or directory can have several names	Deletion needs a link count or back-references
General graph	Cycles allowed	Needs cycle detection or garbage collection to traverse and delete safely

Links and directory implementation

A hard link is another directory entry pointing to the same i-node; the i-node keeps a link count, and the file's i-node and blocks are freed only when the count reaches 0 and no process still has the file open. A hard link cannot cross file systems (i-node numbers are local to one file system), and most systems do not allow hard links to directories.
A soft (symbolic) link is a small file holding a path name; it can cross file systems and can dangle if the target is deleted.
A directory can be a linear list of (name, i-node) entries (simple, search time proportional to the number of entries) or a hash table (faster lookup, fixed table size and collisions to handle).

File allocation methods

Convention used here: $B$ is the block size in bytes, $p$ the size of a block pointer (or address) in bytes, $K = 2^{10}$ , $M = 2^{20}$ and $G = 2^{30}$ , byte-addressable storage unless a question says otherwise, and the blocks of a file are numbered from 0.

Method	How blocks are found	Strengths	Weaknesses
Contiguous	Directory stores start block and length; block $i$ (counting from 0) is at start $+ i$	Fast sequential and direct access, minimal seeks	External fragmentation; file size must be known or the file may need moving to grow
Linked	Each block holds a pointer to the next; directory stores first block	No external fragmentation; files grow easily	No efficient direct access: reaching block $i$ (counting from 0) needs $i + 1$ block reads along the chain; pointer space lost per block; one damaged pointer loses the rest of the file
Linked with FAT	The pointers are moved into a File Allocation Table indexed by block number; entry $j$ gives the block after $j$	With the table in memory, a block is located by table lookups alone, then read with one data-block read	The table has one entry per disk block and must be cached in memory
Indexed	An index block lists all the file's block addresses	Direct access, no external fragmentation	Index block overhead; a single index block limits file size unless indexes are chained or multi-level

LINKED ALLOCATION

usable bytes per block (linked) = B - p, blocks for a file of S bytes = ⌈ \frac{S}{B - p} ⌉

Applies when each data block stores its own next-block pointer of $p$ bytes.

WIDTH OF A BLOCK ADDRESS

bits per block address \geq ⌈ lo g_{2} N_{blocks} ⌉

A pointer or FAT entry must be able to name every one of the $N_{blocks}$ blocks; questions usually round this up to whole bytes.

FAT SIZE

FAT size = N_{blocks} \times (entry size in bytes)

One entry per disk block; the entry must be wide enough to hold any block number.

POINTERS PER BLOCK

P = \frac{B}{p}

Number of block addresses that fit in one index (indirect) block.

A UNIX-style i-node holds $D$ direct pointers to data blocks, one single indirect pointer (to a block of $P$ data-block addresses), one double indirect pointer (to a block of $P$ single-indirect blocks) and one triple indirect pointer (to a block of $P$ double-indirect blocks).

LARGEST FILE WITH AN I-NODE

Max file size = (D + P + P^{2} + P^{3}) \times B

With direct, single, double and triple indirect pointers. Drop the terms for levels the i-node does not have. This is the limit imposed by the pointer scheme; a pointer width or file-size field can impose a smaller limit.

WORKED EXAMPLE

A file system has block size 1 KB and block pointers of 4 bytes. Each i-node has 10 direct pointers and one each of single, double and triple indirect pointers. Find the maximum file size, and the number of disk accesses needed to read a data block reached through the double indirect pointer if the i-node is already in memory and no caching is used.

Solution

$P = 1024/4 = 256$ pointers per block.
Blocks addressable: $10 + 256 + 25 6^{2} + 25 6^{3} = 10 + 256 + 65536 + 16777216 = 16843018$ blocks.
Maximum size $= 16843018 \times 1 KB = 16843018$ KB, a little over 16 GB.
Through the double indirect pointer: read the double-indirect block (1), read the single-indirect block it points to (2), read the data block (3).

Answer: 16843018 KB; 3 disk accesses for a data block reached through the double indirect pointer.

EXAM TIP

Check what limits the file size. If the question gives a pointer width, the number of blocks the disk can address is at most $2^{8 p}$ for $p$ bytes, so a file cannot usefully have more blocks than the disk has. For the linked scheme remember the pointer eats into every block: the data per block is $B - p$ , not $B$ . With any block-based method the last block of a file is only partly used, wasting up to $B - 1$ bytes (internal fragmentation).

Free-space management

Method	How it works	Space cost	Notes
Bit vector (bitmap)	One bit per block; 1 = free, 0 = allocated (or the reverse, as the question states)	$N$ bits for $N$ blocks	Easy to find the first free block or a run of $k$ contiguous free blocks; the bitmap should fit in memory
Linked list	Free blocks chained through each other; a head pointer is kept	One pointer inside each free block, no extra table	Finding a run of contiguous free blocks is slow; allocating one block is quick
Grouping	The first free block stores the addresses of $n$ free blocks; the first $n - 1$ of these are free blocks, and the last one stores the addresses of the next $n$	Inside free blocks	Many free blocks found with one read
Counting	Each entry stores a first free block and the number of consecutive free blocks	Pairs (address, count)	Compact when free space comes in long runs

BIT VECTOR SIZE

Bit vector size (bytes) = \frac{N _{blocks}}{8} = \frac{disk size}{8 \times B}

One bit per block of size $B$ bytes.

EXAM TIP

When counting bits needed in a bit vector, divide the disk size by the block size, not the sector size, unless the question says the unit of allocation is the sector.

Disk structure and access time

A disk has one or more platters, each with two surfaces. Every surface has concentric tracks, each divided into sectors, the smallest unit transferred. The tracks at the same position on all surfaces together form a cylinder. All read/write heads move together, so moving to a new cylinder is a single seek.

DISK CAPACITY

Capacity = surfaces \times \frac{tracks}{surface} \times \frac{sectors}{track} \times \frac{bytes}{sector}

Assumes the same number of sectors on every track.

LINEAR SECTOR NUMBER FROM (CYLINDER, HEAD, SECTOR)

sector number = (c \times H + h) \times S + s

$H$ heads (surfaces), $S$ sectors per track, and $c$ , $h$ , $s$ all numbered from 0, with sectors numbered across a whole cylinder before moving to the next cylinder. If sectors are numbered from 1, use $s - 1$ in place of $s$ .

DISK ACCESS TIME

T_{access} = T_{seek} + T_{rotational latency} + T_{transfer}

Add controller or queueing overhead only if the question gives it.

ROTATION TIME AND AVERAGE LATENCY

T_{rot} = \frac{60}{RPM} s, average rotational latency = \frac{T _{rot}}{2}

On average the wanted sector is half a turn away. If the question says worst case, use a full $T_{rot}$ .

TRANSFER TIME

T_{transfer} = \frac{bytes to transfer}{bytes per track} \times T_{rot}

The head reads one full track per rotation, so time is the fraction of a track passed under the head times the rotation time.

DATA TRANSFER RATE

data transfer rate = bytes per track \times \frac{RPM}{60} bytes/s

One track passes under the head per rotation.

EXAM TIP

Keep time units consistent: $T_{rot}$ in milliseconds is $60000/ RPM$ . Reading several sectors on one track costs one seek and one latency, plus transfer for all of them. Reading each of $n$ scattered blocks separately costs $n$ seeks and $n$ latencies.

Disk scheduling

For scattered requests, seek time is usually the largest part of access time, so the OS orders pending cylinder requests. Convention used in the notes: head movement is counted in cylinders; the cylinder range is the one the question states (0 to 199 in the examples here); the head starts at the given cylinder and has the stated direction; ties in distance are broken toward the request that arrived first.

Algorithm	Rule	Notes
FCFS	Serve in arrival order	Fair; no starvation; usually the most head movement
SSTF	Serve the request nearest the current head position	Can starve far-away requests; the only algorithm in this table that can
SCAN (elevator)	Move in one direction serving requests, go all the way to the disk end, then reverse	Goes to the physical end even if no request is there
C-SCAN	Serve in one direction to the end, return to the other end without serving, then continue in the same direction	More uniform waiting time; the return trip is counted as movement unless the question excludes it
LOOK	Like SCAN but reverse at the last request in the current direction	No travel to the empty end
C-LOOK	Like C-SCAN but go only as far as the last request, then jump to the lowest pending request	The jump is counted as movement unless the question excludes it

TOTAL HEAD MOVEMENT

Total head movement = i \sum ∣ c_{i} - c_{i - 1} ∣

Sum of absolute cylinder differences over the service order, with $c_{0}$ the starting position and the disk ends or jump included where the algorithm uses them.

WORKED EXAMPLE

Cylinders are numbered 0 to 199. The head is at 50 and is moving toward higher numbers. The pending queue, in arrival order, is 82, 170, 43, 140, 24, 16, 190. Find the total head movement for FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK. Count the return trip of C-SCAN and the jump of C-LOOK.

Solution

FCFS: $50 \to 82 \to 170 \to 43 \to 140 \to 24 \to 16 \to 190$ gives $32 + 88 + 127 + 97 + 116 + 8 + 174 = 642$ .
SSTF: from 50 the nearest is 43 (7); from 43 the nearest is 24 (19); then 16 (8); then 82 (66); then 140 (58); then 170 (30); then 190 (20). Total $7 + 19 + 8 + 66 + 58 + 30 + 20 = 208$ .
SCAN: $50 \to 82 \to 140 \to 170 \to 190 \to 199$ is $149$ ; reverse $199 \to 43 \to 24 \to 16$ is $183$ . Total $149 + 183 = 332$ .
C-SCAN: $50 \to 199$ (serving 82, 140, 170, 190) is $149$ ; return $199 \to 0$ is $199$ ; then $0 \to 16 \to 24 \to 43$ is $43$ . Total $149 + 199 + 43 = 391$ .
LOOK: $50 \to 190$ is $140$ ; reverse $190 \to 16$ is $174$ . Total $314$ .
C-LOOK: $50 \to 190$ is $140$ ; jump $190 \to 16$ is $174$ ; then $16 \to 43$ is $27$ . Total $140 + 174 + 27 = 341$ .

Answer: FCFS 642, SSTF 208, SCAN 332, C-SCAN 391, LOOK 314, C-LOOK 341 cylinders.

Algorithm	Service order (head at 50, moving up)	Total movement
FCFS	82, 170, 43, 140, 24, 16, 190	642
SSTF	43, 24, 16, 82, 140, 170, 190	208
SCAN	82, 140, 170, 190, (199), 43, 24, 16	332
C-SCAN	82, 140, 170, 190, (199, 0), 16, 24, 43	391
LOOK	82, 140, 170, 190, 43, 24, 16	314
C-LOOK	82, 140, 170, 190, (jump), 16, 24, 43	341

EXAM TIP

Read the question for three things before computing: the starting direction, whether SCAN/C-SCAN go to the disk end (they do; LOOK/C-LOOK do not), and whether the return or jump trip is counted. Without those, the answer is not unique.

Buffering and caching

Key ideas

Buffering: a memory area holds data in transit between a device and a process, to absorb speed differences and to allow the data size to differ between producer and consumer. Double buffering lets the device fill one buffer while the process uses the other.
Buffer (block) cache: recently used disk blocks are kept in main memory, so repeated reads need no disk access. Replacement is usually LRU-like.
Write policies: write-through updates the disk on every write (safe, slower); write-back (delayed write) marks the cached block dirty and writes it later (faster, risk of loss on a crash).
Read-ahead: when access looks sequential, the system fetches following blocks early.
The effective access time with a cache of hit ratio $h$ is $h \cdot t_{cache} + (1 - h) \cdot t_{disk}$ when a miss costs $t_{disk}$ in total (lookup included). If the cache lookup is paid first and the disk access is added on a miss, the miss term is $(1 - h) (t_{cache} + t_{disk})$ .

PREVIOUS-YEAR QUESTIONS

6 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.59

GATE 2026 · CS1Q.59 · 2 marks · NAT

Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7.

The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)

Answer and solution

GATE 2026 CS1 Q.59: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.59: answer and solution

GATE 2026 CS2 Q.53

GATE 2026 · CS2Q.53 · 2 marks · NAT

To keep track of free blocks in a file system, one of the two approaches is generally used – using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single pointer of size 4 bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is ____________. (answer in integer)
Note: 1K=2^10 and 1G=2^30

Answer and solution

GATE 2026 CS2 Q.53: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.53: answer and solution

GATE 2025 CS1 Q.51

GATE 2025 · CS1Q.51 · 2 marks · NAT

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = 2^10 and 1M = 2^20. The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)

Answer and solution

GATE 2025 CS1 Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.51: answer and solution

GATE 2022 CS Q.63

GATE 2022 · CSQ.63 · 2 marks · NAT

Consider two files systems $A$ and $B$ , that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in $A$ and also in $B$ . Now, consider inserting a new block in the middle of the file (between 50th and 51st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in $A$ and $B$ are $n_{A}$ and $n_{B}$ , respectively, then the value of $n_{A} + n_{B}$ is ______.

Answer and solution

GATE 2022 CS Q.63: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.63: answer and solution

GATE 2020 CS Q.35

GATE 2020 · CSQ.35 · 2 marks · MCQ

Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.

(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)

Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.

Which one of the following statements is FALSE?

(A)
T is serviced before P.
(B)
Q is serviced after S, but before T.
(C)
The head reverses its direction of movement between servicing of Q and P.
(D)
R is serviced before P.

Answer and solution

GATE 2020 CS Q.35: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.35: answer and solution

GATE 2018 CS Q.53

GATE 2018 · CSQ.53 · 2 marks · NAT

Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, ... , 199), and 256 sectors per track (numbered as 0, 1, ... , 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time:

[120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3], [56, 116, 2], [118, 16, 1]

Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible.

The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is ______.

Answer and solution

GATE 2018 CS Q.53: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.53: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 12 marks · NAT

A disk rotates at 7200 RPM and has 400 sectors per track. The average seek time is 6 ms. Time is in milliseconds and controller overhead is ignored. What is the average time, in ms, to read one sector, correct to two decimal places?

Answer and solution

Answer: $10.19$ (accepted range $\pm 0.02$ )

Rotation time $= 60000/7200 = 8.3333$ ms.
Average rotational latency $= 8.3333/2 = 4.1667$ ms.
Transfer of one sector $= 8.3333/400 = 0.0208$ ms.
Total $= 6 + 4.1667 + 0.0208 = 10.1875 \approx 10.19$ ms.

PRACTICE 22 marks · NAT

A file system uses block size 4 KB and block pointers of 4 bytes ( $K = 2^{10}$ ). Each i-node has 12 direct pointers, one single indirect and one double indirect pointer, and no triple indirect pointer. What is the maximum file size in KB allowed by this pointer scheme?

Answer and solution

Answer: $4198448$

$P = 4096/4 = 1024$ .
Data blocks: $12 + 1024 + 102 4^{2} = 12 + 1024 + 1048576 = 1049612$ .
Size $= 1049612 \times 4 = 4198448$ KB.

PRACTICE 32 marks · MCQ

Cylinders are numbered 0 to 199. The head is at 100 and is moving toward lower cylinder numbers. The pending requests, in arrival order, are 30, 150, 90, 60, 180, 120. Using LOOK, the total head movement in cylinders is

(A)
220
(B)
280
(C)
250
(D)
460

Answer and solution

Answer: (A)

LOOK moving down serves 90, 60, 30 and reverses at 30: $100 - 30 = 70$ .
Then up serving 120, 150, 180: $180 - 30 = 150$ .
Total $70 + 150 = 220$ . (280 is SCAN, which goes on to 0, and also C-LOOK; 460 is FCFS.)

PRACTICE 41 mark · MSQ

Which of the following statements about file allocation methods are correct?

(A)
Contiguous allocation can suffer from external fragmentation.
(B)
In linked allocation without a FAT, the $i$ -th block of a file can be reached by reading a single pointer from the directory entry.
(C)
Indexed allocation supports direct access to any block of the file and has no external fragmentation.
(D)
In linked allocation without a FAT, a damaged pointer in one block can make the remaining blocks of the file unreachable.

Answer and solution

Answer: (A), (C), (D)

A is true: variable-size contiguous extents leave unusable gaps.
B is false: the chain must be followed from the first block.
C is true: the index block gives each block's address and any free block can be used.
D is true: the chain is broken at the damaged pointer.

PRACTICE 51 mark · NAT

A 64 GB disk is divided into blocks of 4 KB ( $K = 2^{10}$ , $G = 2^{30}$ ), and free space is tracked with a bit vector using one bit per block. What is the size of the bit vector in MB ( $M = 2^{20}$ bytes)?

Answer and solution

Answer: $2$

Blocks $= 2^{36} / 2^{12} = 2^{24}$ .
Bit vector $= 2^{24}$ bits $= 2^{21}$ bytes.
$2^{21} / 2^{20} = 2$ MB.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

I/O scheduling. … File systems

Preparing in Kolkata? IAE Academy's course for GATE CSE.