Contiguous allocation in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Contiguous Allocation

Which of the following best describes contiguous allocation in file storage?

A Files are stored in scattered blocks linked by pointers, reducing fragmentation but slowing access.

B Files are stored in consecutive blocks on the disk, making access faster but causing external fragmentation.

C Files are divided into fixed-size blocks stored anywhere on the disk with an index table.

D Files are stored in a hierarchical directory structure without concern for physical location.

💡 Hint

Think about how files are placed physically on the disk and the impact on speed and fragmentation.

Contiguous allocation stores files in consecutive disk blocks, which allows fast access but can cause external fragmentation as free space gets divided into small chunks.

📋 Factual

intermediate

Fragmentation in Contiguous Allocation

What type of fragmentation is most commonly associated with contiguous allocation?

A Internal fragmentation due to fixed block sizes.

B Fragmentation caused by file system journaling.

C No fragmentation occurs in contiguous allocation.

D External fragmentation caused by scattered free spaces.

💡 Hint

Consider how free space is divided when files are stored in consecutive blocks.

External fragmentation happens because free space is broken into small pieces that may not be large enough for new files, a common issue in contiguous allocation.

🚀 Application

advanced

Calculating Free Space for Contiguous Allocation

A disk has 1000 blocks. Files A, B, and C occupy 200, 300, and 100 contiguous blocks respectively. If the free space is fragmented into three parts of 150, 100, and 150 blocks scattered across the disk, what is the largest file size that can be stored contiguously?

A 400 blocks

B 300 blocks

C 150 blocks

D 450 blocks

💡 Hint

Look for the largest single free space chunk available for contiguous storage.

The largest contiguous free space chunk is 150 blocks, so the largest file that can be stored contiguously must fit within that size.

🔍 Analysis

advanced

Comparing Contiguous Allocation with Other Methods

Which of the following is a key disadvantage of contiguous allocation compared to linked allocation?

A It suffers from external fragmentation and requires compaction.

B It requires more disk space for pointers.

C It cannot support random access to file blocks.

D It causes slower sequential access to files.

💡 Hint

Think about how files are stored and the impact on free space management.

Contiguous allocation causes external fragmentation because files must occupy consecutive blocks, often requiring disk compaction to reclaim space.

❓ Reasoning

expert

Effect of File Size Changes in Contiguous Allocation

If a file stored using contiguous allocation needs to grow beyond its allocated space, what is the most likely consequence?

A The file must be moved to a larger contiguous free space, causing overhead.

B The file can automatically extend into the next free block without moving.

C The file system will split the file into linked blocks to accommodate growth.

D The file size cannot be changed once allocated.

💡 Hint

Consider the requirement for contiguous blocks and what happens if the next blocks are occupied.

Since contiguous allocation requires consecutive blocks, if the file grows beyond its space, it must be relocated to a larger free contiguous area, which is costly.

Practice

1. What is the main characteristic of contiguous allocation in operating systems?

easy

A. Files are stored in one continuous block of memory.

B. Files are stored in multiple scattered blocks.

C. Files are stored using linked lists.

D. Files are stored in indexed blocks.

Solution

1. Step 1: Understand file storage methods

   Contiguous allocation means storing a file in one continuous block of memory without breaks.

2. Step 2: Compare with other methods

   Other methods like linked or indexed allocation store files in scattered blocks or use pointers.

3. Final Answer:

   Files are stored in one continuous block of memory. -> Option A

4. Quick Check:

   Contiguous allocation = continuous block storage [OK]

Hint: Contiguous means continuous block storage [OK]

Common Mistakes:

• Confusing contiguous with linked allocation
• Thinking files are scattered in contiguous allocation
• Mixing indexed allocation with contiguous

2. Which of the following is the correct way to describe contiguous allocation?

easy

A. Files are divided into fixed-size blocks scattered across memory.

B. Files use pointers to link scattered blocks.

C. Files occupy a single continuous block of memory.

D. Files are stored in a tree-like index structure.

Solution

1. Step 1: Identify the definition of contiguous allocation

   Contiguous allocation means the entire file is stored in one continuous block of memory.

2. Step 2: Eliminate incorrect options

   Options A, B, and D describe other allocation methods like linked or indexed allocation.

3. Final Answer:

   Files occupy a single continuous block of memory. -> Option C

4. Quick Check:

   Continuous block = contiguous allocation [OK]

Hint: Continuous block means contiguous allocation [OK]

Common Mistakes:

• Choosing linked or indexed allocation descriptions
• Confusing fixed-size blocks with contiguous storage
• Assuming pointers are used in contiguous allocation

3. Consider a file system using contiguous allocation. If a file of size 10 blocks is stored starting at block 50, which blocks does it occupy?

medium

A. Blocks 60 to 69

B. Blocks 40 to 49

C. Blocks 51 to 60

D. Blocks 50 to 59

Solution

1. Step 1: Understand starting block and file size

   The file starts at block 50 and occupies 10 continuous blocks.

2. Step 2: Calculate occupied blocks

   Blocks occupied are from 50 up to 50 + 10 - 1 = 59.

3. Final Answer:

   Blocks 50 to 59 -> Option D

4. Quick Check:

   Start 50 + size 10 = blocks 50-59 [OK]

Hint: Start block + size - 1 = last block [OK]

Common Mistakes:

• Off-by-one errors in block range
• Starting count from 1 instead of 0
• Choosing blocks after the last block

4. A file stored using contiguous allocation needs to be extended by 5 blocks, but the next 5 blocks after the file are occupied. What is the main problem here?

medium

A. File cannot be extended because contiguous space is not available.

B. File can be extended by linking scattered blocks.

C. File size can be increased without any issue.

D. File can be moved to another location without fragmentation.

Solution

1. Step 1: Understand contiguous allocation extension

   Files must occupy continuous blocks; extension requires free blocks immediately after the file.

2. Step 2: Analyze the problem

   Since the next 5 blocks are occupied, the file cannot be extended contiguously.

3. Final Answer:

   File cannot be extended because contiguous space is not available. -> Option A

4. Quick Check:

   Extension needs free contiguous blocks [OK]

Hint: Extension needs free continuous blocks [OK]

Common Mistakes:

• Assuming scattered blocks can be linked in contiguous allocation
• Ignoring fragmentation issues
• Thinking file can grow without moving

5. You have a disk with free blocks scattered as follows: 5 blocks free at 0-4, 3 blocks free at 10-12, and 7 blocks free at 20-26. You want to store a file of size 6 blocks using contiguous allocation. Which free space can you use and why?

hard

A. Blocks 10-12, because they are in the middle of the disk.

B. Blocks 20-25, because they have enough continuous free blocks.

C. Blocks 0-4, because they are the first free blocks.

D. No space is available because all free blocks are scattered.

Solution

1. Step 1: Identify free block sizes

   Free blocks are 5 at 0-4, 3 at 10-12, and 7 at 20-26.

2. Step 2: Find a continuous free space of at least 6 blocks

   Only blocks 20-26 have 7 continuous free blocks, enough for 6 blocks.

3. Final Answer:

   Blocks 20-25, because they have enough continuous free blocks. -> Option B

4. Quick Check:

   Need ≥6 continuous blocks, only 20-26 fits [OK]

Hint: Choose free space with enough continuous blocks [OK]

Common Mistakes:

• Choosing smaller free blocks that don't fit file size
• Ignoring the need for continuous blocks
• Assuming scattered free blocks can be combined