File systems — exam-style exercises with blocks, FAT, i-nodes and links (and the shortcut that pointed to nothing)

Answer: A named object that stores persistent information, still there after switching off

Persistent means non-volatile, durable: the information survives the computer being switched off. The rest are structures the OS uses to manage it.

• The user → A durable data structure
• The system call interface (Unix) → A collection of bytes
• The OS kernel → A collection of blocks

The user sees a document; read() and write() see bytes without caring what they mean; the kernel stores and reads it in blocks (the transfer unit, bigger than a sector).

Answer: The size · The creation and modification dates · The location on the device · The protection information (permissions)

The attributes in the notes are name, type, location, size, protection, dates and version. Remember this question penalises: ticking a distractor subtracts.

• T — open() copies the file’s control information into main memory so as not to go to the directory on every operation.
• T — In Unix, the descriptor returned by open() is the index of the entry reserved in the process’s open-file table.
• F — Every read() searches for the file name in the directory on disk again.
• F — close() deletes the file from the disk if nobody else has it open.

Opening exists precisely to avoid repeating the search: the directory is looked up once and then the RAM copy is used through the descriptor.

close() only frees the resources the file was using in memory; the file stays on the disk.

Answer: It still exists, with its attributes, but with size 0

Truncate: the contents go, the directory entry and the attributes stay (name, permissions, dates…). Delete takes everything.

On Windows the type is deduced from the extension of the name; on Unix the operating system does not recognise file types; even so, every OS must understand at least the format of the executable file.

Windows looks at the last letters of the name; Unix treats the contents as plain bytes; and every OS needs to recognise executables to load and start them.

Answer: The operating system module that provides the file and directory services · The organisation of information created on the disk to store files and directories

One is software (the OS module) and the other is the data structure written on the device (for example, a disk formatted as ext4 or FAT32).

Answer: Sequential

It is the basic model of Unix and Windows: open → read → read… The current position advances by itself.

Answer: lseek

lseek(fd, offset, SEEK_SET) moves the position; the next read() starts there, without going through what comes before.

• Sequential → A tape that only moves forward or back
• Direct → An array of blocks you jump into by position
• Indexed (ISAM) → A sorted table queried by a key

In indexed access, the OS keeps one or more hidden index files to search by key (for example, a surname). Today it is done outside the kernel, in databases.

Correct order:

1. Single level
2. Two levels
3. Tree
4. Acyclic graph
5. General graph

Each model adds something: separating users (two levels), subdirectories (tree), sharing without copying (acyclic) and unrestricted links, with cycles (general).

Answer: Single level

It is the simplest and the one that scales worst: name clashes between users and slow searches when there are many files.

Answer: /home/laura/ic2/grupo/notas.txt

The absolute path starts at the root, which is the leading /. Do not write “/root/…”: root is another directory (the administrator’s).

Answer: practica/Makefile

The relative path starts at the working directory, so you remove the common beginning (/home/sergio/ic2/) and it does not start with /.

• T — With two levels, sergio and laura can each have a file called practica.c.
• F — The tree model lets one file hang from two different paths.
• T — In an acyclic graph, both paths lead to the same object, not to a copy.
• T — In a general graph, a program that walks the directories may never finish.

The tree has exactly that drawback: it does not allow sharing. The acyclic graph solves it with links, and the general one allows links to directories higher up, which form cycles.

Answer: The data is still reachable through copia-laura.csv; the i-node’s link count drops from 2 to 1

A hard link is another name for the same i-node. While any name remains (count > 0), the data stays.

• ln -s apuntes.md atajo.md → A symbolic link
• ln apuntes.md otro.md → A hard link
• cp apuntes.md copia.md → An independent copy

The s in -s stands for symbolic. Without -s, ln creates another name for the same i-node. cp duplicates the data: if you change one, the other does not change.

Answer: Allow links only to files, not to directories · Garbage collection for whatever becomes unreachable · Use algorithms that detect cycles while traversing

The three are the solutions in the notes. The first is the one Unix uses for hard links: they cannot point to directories.

Answer: Mounted the stick’s file system on the mount point /media/usb

Before using a file system you must mount it: its tree hangs from a directory of the existing tree.

Answer: Access control lists (ACL) · Passwords · Encryption

An ACL is a list of <user, permissions> pairs. Encryption protects even if someone takes the physical disk.

Correct order:

1. Logical layer
2. Block control layer
3. Basic commands layer
4. Driver layer

Logical: directories and i-nodes. Block control: from logical to physical block. Basic commands: reading and writing blocks, buffers. Driver: talking to the controller and interrupts.

• Contiguous → The first block and the length
• Linked → The first block (and sometimes the last); the other links live inside the blocks
• Indexed → The number of the index block

With contiguous allocation start + length is enough because the blocks are consecutive. With linked allocation, each block says which is the next. With indexed allocation, all pointers are together in the index block.

Answer: Linked

The number of the next block was inside the damaged block: the chain breaks there.

Answer: Multilevel indexed (direct pointers and single, double and triple indirect)

Unix solved the index-block limit with several levels: some pointers lead to data and others to index blocks.

• T — Contiguous allocation suffers external fragmentation: there can be free space in total and a file still does not fit.
• F — Linked allocation suffers external fragmentation.
• T — With indexed allocation, a file with a single data block takes two blocks.
• T — The FAT is a variant of linked allocation.

In the article’s IC2 practical, informe.pdf did not fit with contiguous allocation with 11 free blocks because the largest hole was 4.

Linked and indexed allocation use any free block, so they have no external fragmentation (only internal fragmentation in the last block).

Answer: The links are together and can be cached or brought whole into RAM · Data blocks do not lose bytes to the number of the next one

The FAT takes the links out of the blocks and gathers them in a table at the start of the disk: walking the chain means looking at the table, not reading block by block.

In a bitmap there is one bit per block; in a linked list each free block points to the next; and on a FAT disk the table itself marks the free ones.

The bitmap is traditional Unix’s. In the linked list, the OS only keeps a pointer to the first free block (or uses that first free block as an index block listing the others).

Answer: 1024

The index block holds 2048 / 4 = 512 pointers, so the file has at most 512 blocks: 512 × 2 KiB = 1024 KiB (1 MiB).

Answer: The single indirect

With 4 KiB and 4 B pointers, an index block holds 1024 pointers: the single one covers 1024 blocks, from 12 to 1035.

Answer: 3

40,000 is greater than 1035 and less than 1,049,612: it goes through the double indirect. Reads: top index block + bottom index block + data block = 3.

• T — A linear list of entries is easy to program, but very slow with thousands of files.
• T — NTFS and ext4 use B-trees (or variants) for large directories.
• F — With a hash table you have to compare the name with every entry.
• F — The directory only exists in RAM; only the data is on the disk.

The hash table computes the slot from the name and goes straight there. The directory is stored on the disk (in RAM, at most, a copy to go faster).

Blocks = size / useful space, rounded up. With contiguous, FAT and indexed allocation the whole block holds data (2048 B); with linked allocation each block loses 4 B to the number of the next one: 2044 useful bytes.

notas.txt: 3000 / 2048 = 1.46 → 2 in every method (and 2 + 1 = 3 with indexed).

grupo.c is the trap: 6144 = 3 × 2048 fits exactly in 3 blocks, but with linked allocation 3 × 2044 = 6132 < 6144: it is 12 bytes short and needs a fourth block.

memoria.pdf: 9000 / 2048 = 4.39 → 5 and 9000 / 2044 = 4.40 → 5; with indexed, 5 + 1 = 6.

Totals: 10, 11, 10 and 13. Indexed allocation spends one index block per file, however small the file is.

Contiguous: block k is at start + k; it is computed without reading anything else: always 1 read.

Linked: the number of block k is only known by reading block k − 1, and so on backwards: k + 1 reads (1, 4 and 5).

FAT in RAM: the hops along the chain happen in the table, in memory, and then only the data block is read: 1 read.

Indexed: first the index block (its entry k is the address) and then the data block: 2 reads for any k.

Pointers per index block: 2048 / 4 = 512. Each level multiplies by 512: 10, 512, 512² = 262,144 and 512³ = 134,217,728 blocks.

Cumulative (blocks × 2 KiB): 10 × 2 = 20 KiB; (10 + 512) × 2 = 1,044 KiB; (522 + 262,144) × 2 = 525,332 KiB; and with the triple one, 134,480,394 blocks × 2 = 268,960,788 KiB.

In GiB: 268,960,788 / 1,048,576 = 256.5 GiB. The triple level contributes almost everything: 512³ × 2 KiB = 2^27 × 2^11 B = 2^38 B = 256 GiB.

With 4 KiB and 4 B pointers, 1024 pointers fit in a block. The direct pointers reach blocks 0-11, the single indirect one blocks 12-1035 and the double one blocks 1036-1,049,611.

apuntes.md: 30 / 4 = 7.5 → 8 blocks: all through direct pointers, 0 index blocks; the last one (block 7) takes 1 read.

dataset.csv: 2 MiB / 4 KiB = 512 blocks: 12 direct + 500 through the single indirect → 1 index block. The last one (511) falls in the single level: index + data = 2 reads.

grabacion.mp4: 100 MiB / 4 KiB = 25,600 blocks: 12 direct + 1024 through the single + 24,564 through the double. The double one spends its top block plus ⌈24,564 / 1024⌉ = 24 blocks below: 1 + 1 + 24 = 26 index blocks. The last block is reached through the double: 3 reads.

Everything in powers of 2: 256 GiB = 2^38 B and 8 KiB = 2^13 B → 2^38 / 2^13 = 2^25 = 33,554,432 blocks.

Bitmap: one bit per block → 2^25 bits = 2^22 bytes = 4 MiB.

FAT: one 4 B entry (2^2) per block → 2^25 × 2^2 = 2^27 B = 128 MiB: 32 times the bitmap.

Linked: useful 1024 − 8 = 1016 B; 3 MiB = 3,145,728 B; 3,145,728 / 1016 = 3,096.19 → 3,097 blocks.

With three links: useful 1024 − 24 = 1000 B; 3,145,728 / 1000 = 3,145.728 → 3,146 blocks.

Model answer:

With contiguous allocation each file takes consecutive blocks and the directory only stores the first block and the length; block k is at start + k, so sequential and direct access are very fast, but it suffers external fragmentation (there may be no hole in a row even if space is left over) and it struggles when the file grows.

With linked allocation the blocks can be anywhere and each one stores the number of the next; the directory stores the first one (and sometimes the last). External fragmentation disappears, but reaching block k means reading the k blocks before it, each block loses a few bytes to the link and, if one is damaged, everything after it is lost. The FAT is its variant with the links gathered in a table.

With indexed allocation all the file’s pointers are in an index block whose address the directory stores; there is no external fragmentation either and direct access costs two reads for any block, at the price of an extra block per file (which hurts small files) and of losing everything if the index block is damaged.

Model answer:

A hard link is another directory entry pointing to the same i-node as the original: there is no original and copy, but two names for the same file, and the i-node counts how many names it has. It is created with ln datos.csv copia.csv. If datos.csv is deleted, the count drops from 2 to 1 and the data is still reachable through copia.csv; it is only freed when the count reaches 0. It can only be made to files and within the same file system.

A symbolic link is a small file that stores the path of the original, like a Windows shortcut. It is created with ln -s datos.csv atajo.csv. It can point to directories and to other file systems, but if the original is deleted it dangles: it points to a path that no longer exists.

Model answer:

The i-node stores the file’s attributes (mode, owner, size, dates, link count) and the pointers to its blocks. A single index block would limit the file size to the pointers that fit in one block, so Unix uses several levels: 12 direct pointers lead to data blocks (small files spend no index blocks), the single indirect leads to a block of pointers, the double to a block of blocks of pointers and the triple adds one more level.

With 4096-byte blocks and 8-byte pointers, 4096 / 8 = 512 pointers fit per block. The maximum is (12 + 512 + 512² + 512³) blocks × 4 KiB = 48 KiB + 2 MiB + 1 GiB + 512 GiB, about 513 GiB. The triple level contributes almost everything: 512³ × 4 KiB = 2^27 × 2^12 B = 2^39 B = 512 GiB.

Model answer:

With a bitmap, a fixed area of the disk is reserved with one bit per block saying whether it is free or taken; it is compact and makes it easy to find holes in a row, and it is the method of traditional Unix.

With a linked list, the OS only keeps the number of the first free block and each free block stores the number of the next; it uses no extra space, but walking it means reading blocks. A variant uses the first free block as an index block listing the others.

On FAT systems no other structure is needed: the FAT entry of a free block has a value that marks it as free.

Calculation: 64 GiB / 4 KiB = 2^36 / 2^12 = 2^24 blocks, so the map has 2^24 bits = 2^21 bytes = 2 MiB.