This post explains the calculations that the operating system question of Unit 5 asks in Paper II. Every new-syllabus Paper II from 2019 to 2026 has them. They need only division, powers of 2 and one table lookup.
The post has four parts:
- The idea behind both: one table turns a number into a place, and the Sinhala-medium words (section 1).
- Files on the disk: following a FAT chain, counting blocks and wasted space, and choosing an allocation method (sections 2 to 4).
- Memory: splitting an address into page and offset, and translating it to a physical address (sections 5 and 6).
- Practice: past paper questions to try, sorted by type (section 7).
1. One idea behind both calculations
Both calculations are a lookup. A number goes into a table, and the table gives back a place. For a file, the FAT gives the next block on the disk. For a process, the page table gives the frame in physical memory.
The syllabus asks for both. Level 5.2 lists "Storage allocation" with contiguous, linked and indexed allocation, and the file systems "FAT etc" (Syllabus 5.2, pages 15 and 16) (විෂය නිර්දේශය 5.2, පිටුව 15). Level 5.4 asks students to "briefly explain paging and mapping" (Syllabus 5.4, page 17) (විෂය නිර්දේශය 5.4, පිටු 16 සහ 17).
How often the papers ask them
Both levels appear in all eight new-syllabus papers, 2019 to 2026. File management (5.2) holds 3 MCQs and 27 Paper II marks. Resource management (5.4) holds 5 MCQs and 33 Paper II marks. Not every one of those marks is a calculation, because these levels also cover disk formatting, swapping and device drivers.
The question moves inside Paper II. It is Part A, Q4 in 2019, 2020, 2025 and 2026, and Part B, Q10 from 2021 (held 2022) to 2024.
The words in Sinhala-medium papers
The Sinhala-medium papers and books use these words. Learn them with the English word, because the papers print both.
- FAT: "ගොනු විභජන වගුව" in 2025 Paper II, A, Q4(c), and "ගොනු විබෙදුම් වගුව" in 2026 Paper II, A, Q4(a).
- Block: "කාණ්ඩය" in 2020 to 2025, and "කට්ටිය" in 2024 Paper I, Q17 and 2026 Paper II, A, Q4(a).
- Directory entry: "නාමාවලි තොරතුර" or "නාමාවලි පිවිසුම".
- Page, frame, page table: "පිටුව", "රාමුව", "පිටු වගුව". The Sinhala Teachers' Guide calls paging "පිටුකරණය" and virtual memory "අතථ්ය මතකය" (ගුරු අත්පොත 5.4, පිටු 152 සහ 153).
- Offset: "නෙරුව" in 2020 Paper II, A, Q4(c) and 2022 (held 2023) Paper II, B, Q10(c).
- Valid bit: "වලංගුතාව" in 2024 and 2025, and "ඇත/නැත" in 2020 and 2022 (held 2023).
2. Follow a FAT chain
A FAT chain is read one entry at a time. The directory entry gives the first block of the file. The FAT entry of that block gives the next block. The chain ends at the block whose entry is -1.
The Teachers' Guide shows linked allocation as a link inside each block, and names "MSDOS FAT file system" as its example (Teachers' Guide 5.2, page 130) (ගුරු අත්පොත 5.2, පිටුව 141). In a real FAT, the links sit together in one table, the FAT, and not inside the data blocks. The papers draw it that way, so read the table.
Find a start block that is not given
The start block of a file is the block that no FAT entry points to. Every other block of a chain has an entry before it. So list the numbers that appear inside the FAT, and the block numbers missing from that list are the start blocks.
2025 Paper II, A, Q4(c)(i) gives entries 100 to 106 with no directory entries. The values inside are 102, 103, -1, 105, 100, 106 and -1. Blocks 101 and 104 never appear inside, so the two files start at 101 and 104. The official marking scheme gives 101 and 104, in any order. The chains are 101, 103, 105, 106 and 104, 100, 102.
2026 Paper II, A, Q4(a)(i) gives the start blocks of File 1 and File 2, 20 and 21. File 1 is 20, 22. File 2 is 21, 24, 25. The blocks left are 23, 26, 27 and 28, and nothing points to 23. So File 3 is 23, 28, 26, 27. This is our own worked answer, because 2026 has no official scheme yet.
Add a block to a file
When a file grows by one block, two entries change. The old last block stops holding -1 and holds the new block number. The new block holds -1.
In 2020 Paper II, A, Q4(b), maximum.py uses 301, 300, 303, 304, which is four 4 KB blocks. To reach 20 KB, it needs a fifth block. The official scheme says entry 304 changes to 302 (or another free block), and entry 302 changes to -1. 2023 (held 2024) Paper II, B, Q10(f)(iii) asks the same move with test.py on 218 and 220 and a new block 219. So entry 220 holds 219, and entry 219 holds -1. That is our own worked answer.
3. Count the blocks and the wasted space
A file always takes whole blocks. So the number of blocks is the file size divided by the block size, rounded up. The disk space used is that number of blocks times the block size. The space left empty in the last block is internal fragmentation.
These are the steps for the past paper questions:
- 2024 Paper I, Q17 has 512-byte blocks and a 1959-byte file. 1959 divided by 512 is 3.8, so the file takes 4 blocks, which is 2048 bytes. The wasted space is 2048 minus 1959, which is 89 bytes, option (1). The key is a third-party copy of the scheme.
- 2021 (held 2022) Paper I, Q12 has 4 KB blocks. myprog.py runs 103, 100, 101, so it starts at 103 and takes 3 blocks, which is 12 KB. That is option (4), the official key.
- 2022 (held 2023) Paper I, Q14 has 4 KB blocks. average.py runs 203, 201, 200, 202, so it starts at 203 and takes 16 KB. That is option (4), from a third-party copy of the key.
- 2026 Paper II, A, Q4(a)(ii) asks the space for File 1 and File 3 with 4 KB blocks. File 1 has 2 blocks and File 3 has 4 blocks. So 6 blocks take 6 times 4 KB, which is 24 KB. That is our own worked answer.
Small blocks or large blocks
The block size is a trade-off. 2025 Paper II, A, Q4(c)(ii) asks one drawback of each. The official scheme accepts, among others, these answers:
- Small blocks: the FAT needs more entries and gets bigger, and one file is spread over more blocks, so reading it takes more seeks.
- Large blocks: a small file still takes a whole block, so more space is lost to internal fragmentation.
4. Choose an allocation method
Each method keeps a different thing in the directory entry, and that one thing decides its strengths. The Teachers' Guide lists the three methods (Teachers' Guide 5.2, pages 129 to 131) (ගුරු අත්පොත 5.2, පිටු 140 සහ 141).
- Contiguous allocation keeps the start block and the length. A file in adjacent blocks is fast to read, but it cannot grow when the next block is taken. Free gaps between files cause external fragmentation (2024 Paper II, B, Q10(e)(ii)).
- Linked allocation keeps the start block. A file grows easily, but reaching block k means following every link before it.
- Indexed allocation keeps the index block, which lists every block number of the file (2024 Paper II, B, Q10(e)(i)). Any block is found in one step, and the file grows by adding one number to the index.
Match the method to the use
The question gives a use, and the use points to one strength. 2026 Paper II, A, Q4(a)(iii) describes large video files that grow over time and need fast access to any part. Linked allocation grows easily but must follow the chain from the start. Indexed allocation grows easily and jumps to any block through the index. So the answer is indexed allocation. This is our own worked answer.
2019 (New Syllabus) Paper II, A, Q4(b)(iii) asks why contiguous allocation suits a CD-ROM. A CD-ROM is written once and read many times, so its files never grow. The weakness of contiguous allocation never matters there, and its fast reads remain.
Both Guides also put linked allocation lines under "Indexed Allocation", such as "File ends at nil pointer" (Teachers' Guide 5.2, page 131) (ගුරු අත්පොත 5.2, පිටුව 141). That error and its correct reading are in the learning order post. The Sinhala Guide calls the three methods "යාබද විභජනය", "සබැඳි විභජනය" and "සූචක/අනුක්රමික විභජනය". 2026 Paper II, A, Q4(a)(iii) uses other words, "සම්බන්ධිත වෙන්කිරීම" for linked and "දර්ශක වෙන්කිරීම" for indexed.
5. Split an address into page and offset
Every paging number comes from three sizes, each written as a power of 2. The page size gives the offset bits. The rest of the virtual address is the page number. The physical memory size minus the offset bits gives the frame number bits.
Use these four lines for every question:
- Offset bits = the power of 2 in the page size. 4 KB is 2^12, so 12 bits.
- Page number bits = virtual address bits minus offset bits.
- Frames = physical memory size divided by page size. Frame number bits = the power of 2 in the physical size minus offset bits.
- Virtual address space = 2 to the power of the virtual address bits, in bytes.
The Teachers' Guide divides physical memory into "fixed-sized blocks called frames" and logical memory into "blocks of same size called pages" (Teachers' Guide 5.4, page 141). The Sinhala Guide says page size and frame size must be equal (ගුරු අත්පොත 5.4, පිටුව 153). The Sinhala Guide also starts by calling a page the unit used to store and read data in secondary storage (ගුරු අත්පොත 5.4, පිටුව 152). Keep the two words apart in the exam. A block is the unit of a file on the disk (section 2). A page is the unit of a process's virtual memory.
The past paper numbers
- 2020 Paper II, A, Q4(c)(i): 16-bit addresses and 4 KB pages. The page number needs 16 minus 12, which is 4 bits. That is the official answer.
- 2024 Paper II, B, Q10(d)(i): 32 KB of physical memory and 4 KB pages. 32 divided by 4 gives 8 frames.
- 2023 (held 2024) Paper II, B, Q10(e)(i) and (ii): 32-bit addresses, 1 GB (2^30) of memory and 4 KB pages. There are 2^30 divided by 2^12, which is 2^18 frames. Each page table entry holds an 18-bit frame number plus 4 more bits, so 22 bits. A process has 2^20 pages, so the table is 2^20 x 22 bits, and p = 20, q = 22.
- 2026 Paper II, A, Q4(c)(i) and (ii): 48-bit addresses, 8 GB (2^33) of memory and 4 KB pages. The virtual address space is 2^48 bytes. The frame number needs 33 minus 12, which is 21 bits.
The answers for 2023 (held 2024), 2024 and 2026 are our own worked answers.
6. Translate a virtual address
Translation changes only the page part of the address. The page number goes into the page table and comes back as a frame number. The offset is copied across unchanged. The Teachers' Guide figure shows the same move: virtual address (2, 4) becomes physical address (0, 4), because row 2 of the page table holds frame 0 (Teachers' Guide 5.4, page 141) (ගුරු අත්පොත 5.4, පිටුව 153).
In binary
Cut the address after the page number bits. Look up that page in the table. Write the frame bits in front of the same offset bits.
- 2025 Paper II, A, Q4(b)(ii): 16-bit addresses and 4 KB pages, so the first 4 bits are the page. P1 asks 0001 0001 0001 0001, which is page 1. Row 1 of P1 holds frame 1001. So the physical address is 1001 0001 0001 0001. That is the official answer.
- 2024 Paper II, B, Q10(d)(ii): 0010 0000 0000 0100 is page 2. Row 2 holds frame 110. Physical memory is 32 KB, 2^15, so the address has 15 bits: 110 0000 0000 0100.
- 2022 (held 2023) Paper II, B, Q10(c): 0001 0000 0000 0011 is page 1, with valid bit 1 and frame 101. So the page is in memory, and the address is 101 0000 0000 0011.
- 2020 Paper II, A, Q4(c)(ii): 0011 0000 0000 0010 is page 3 with offset 0000 0000 0010. Row 3 holds frame 110. So the address is 110 0000 0000 0010, the official answer.
The 2024 and 2022 (held 2023) answers are our own worked answers.
In decimal
Divide the address by the page size. The whole number part is the page, and the remainder is the offset. Then the physical address is frame times page size, plus the offset.
- 2019 (New Syllabus) Paper II, A, Q4(c)(i): 4 KB pages, address 8200. 8200 = 2 x 4096 + 8, so page 2, offset 8. Row 2 holds frame 010, which is 2. So the physical address is 2 x 4096 + 8 = 8200, the official answer.
- 2023 (held 2024) Paper II, B, Q10(e)(iii): 4097 = 1 x 4096 + 1, so page 1, offset 1. It maps to frame 2, so the address is 2 x 4096 + 1 = 8193.
- 2026 Paper II, A, Q4(c)(iii): 8193 = 2 x 4096 + 1, so page 2, offset 1. It maps to frame 2, so the address is 2 x 4096 + 1 = 8193.
In 2019 and 2026, the answer equals the question's address, because the page sits in the frame with the same number. Do not change a correct answer because it looks too easy. The 2023 (held 2024) and 2026 answers are our own worked answers.
A valid bit of 0
A valid bit of 0 means the page is not in physical memory. An access to it causes a page fault, and the OS must bring the page from the disk. 2025 Paper II, A, Q4(b)(iii) asks one virtual address of P0 that needs this. Rows 3 and 4 of P0 have valid bit 0. So any address that starts 0011 or 0100 is right. The official scheme accepts only these. The frame column of a row with valid bit 0 holds no real frame, so never build an address from it.
2020 Paper II, A, Q4(c)(iii) follows one page fault. Page 1 was not in memory. The OS took frame 111 from page 6 and gave it to page 1. So 0001 0000 0000 0000 now maps to 111 0000 0000 0000, the official answer.
Two notes on the Teachers' Guides
Both Guides first explain the MMU with a base register: "if the base register value is 10000", address 100 becomes 10100 (Teachers' Guide 5.4, page 141) (ගුරු අත්පොත 5.4, පිටුව 152). That is relocation, an older scheme. Paging questions never add a base value. They use the page table, as above.
The Sinhala Guide explains its figure in words. Row 0 of the page table holds 1, and it says page 0 maps to "පළමු වන රාමුව", the first frame (ගුරු අත්පොත 5.4, පිටුව 154). Frames are numbered from 0, as the papers say. So frame 1 is the second frame, and the figure itself shows A, B, C, D in the second frame.
7. Past paper questions to try
Try each question with the steps in its section, then check the answer given there. Questions without an answer in this post are for practice.
- Follow a FAT chain (section 2): 2020 Paper II, A, Q4(b), 2023 (held 2024) Paper II, B, Q10(f)(i) and (iii), 2025 Paper II, A, Q4(c)(i), 2026 Paper II, A, Q4(a)(i).
- Count blocks and space (section 3): 2021 (held 2022) Paper I, Q12, 2022 (held 2023) Paper I, Q14, 2024 Paper I, Q17, 2023 (held 2024) Paper II, B, Q10(f)(ii), 2025 Paper II, A, Q4(c)(ii), 2026 Paper II, A, Q4(a)(ii).
- Choose an allocation method (section 4): 2019 (New Syllabus) Paper II, A, Q4(b), 2021 (held 2022) Paper II, B, Q10(c)(iii), 2022 (held 2023) Paper II, B, Q10(e), 2024 Paper II, B, Q10(e), 2026 Paper II, A, Q4(a)(iii).
- Count frames and bits (section 5): 2020 Paper II, A, Q4(c)(i), 2023 (held 2024) Paper II, B, Q10(e)(i) and (ii), 2024 Paper II, B, Q10(d)(i), 2026 Paper II, A, Q4(c)(i) and (ii).
- Translate an address (section 6): 2019 (New Syllabus) Paper II, A, Q4(c)(i), 2020 Paper II, A, Q4(c)(ii), 2022 (held 2023) Paper II, B, Q10(c), 2023 (held 2024) Paper II, B, Q10(e)(iii), 2024 Paper II, B, Q10(d)(ii), 2025 Paper II, A, Q4(b)(ii), 2026 Paper II, A, Q4(c)(iii).
- A valid bit of 0 (section 6): 2019 (New Syllabus) Paper II, A, Q4(c)(iii), 2020 Paper II, A, Q4(c)(iii), 2022 (held 2023) Paper II, B, Q10(d), 2024 Paper II, B, Q10(d)(iii) and (iv), 2025 Paper II, A, Q4(b)(iii).
The old-syllabus papers asked the same calculations. Try these for more practice.
- 2011 Paper II, A, Q2(b): page bits from the address.
- 2012 Paper II, B, Q3(a): the address space of 16-bit addresses and the page number bits.
- 2018 Paper II, A, Q4(d): frames and the page table.
