Directory structure (single-level, two-level, tree, acyclic graph) in Operating Systems - Step-by-Step Execution

Concept Flow - Directory structure (single-level, two-level, tree, acyclic graph)

Start: User creates files

↓

Single-level Directory

↓

Two-level Directory

↓

Tree Directory Structure

↓

Acyclic Graph Directory Structure

↓

Files organized with links, no cycles

↓

End: File access and management

Shows how directory structures evolve from simple to complex, organizing files and folders step-by-step.

Execution Sample

Operating Systems

Create root directory
Add subdirectories
Add files to directories
Link files in multiple directories
Access files via paths

This sequence shows how files and directories are created and organized in different directory structures.

Analysis Table

Step	Operation	Directory Structure Type	State Description	Visual Representation
1	Create root directory	Single-level	One directory with files directly inside	Root: [file1, file2, file3]
2	Add subdirectories	Two-level	Root directory with multiple user directories	Root: [User1/, User2/] User1: [file1] User2: [file2]
3	Add nested subdirectories	Tree	Directories nested inside other directories	Root: [DirA/] DirA: [DirB/] DirB: [file1, file2]
4	Link files in multiple directories	Acyclic Graph	Files linked in multiple directories without cycles	Root: [DirA/, DirC/] DirA: [file1] DirC: [link to file1]
5	Access files via paths	All types	Files accessed through directory paths	Path examples: /root/file1 /root/User1/file1 /root/DirA/DirB/file2 /root/DirC/file1 (link)
6	End	N/A	No further changes	Final directory structure stable

💡 All directory types created and files organized; no cycles introduced in acyclic graph

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Directories	None	Root	Root, User1, User2	Root, DirA, DirB	Root, DirA, DirB, DirC	Root, DirA, DirB, DirC
Files	None	file1, file2, file3	file1 (User1), file2 (User2)	file1, file2 (DirB)	file1 (DirA), link to file1 (DirC)	file1, file2, links
Links	None	None	None	None	link to file1 in DirC	link to file1 in DirC

Key Insights - 3 Insights

Why can't files in a single-level directory have the same name?

Because all files are in one directory, names must be unique to avoid confusion, as shown in Step 1 of the execution_table.

How does a two-level directory help organize files better than single-level?

It separates files into user directories, reducing name conflicts and grouping files logically, as seen in Step 2.

Why is the acyclic graph directory structure important?

It allows files to appear in multiple directories via links without creating loops, preventing infinite loops during file access, as shown in Step 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. Which directory contains the files file1 and file2?

A Root directory

B DirA directory

C DirB directory

D DirC directory

💡 Hint

Check the 'State Description' and 'Visual Representation' columns at Step 3.

At which step does the directory structure first include links to files?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for the mention of 'link to file1' in the 'Visual Representation' column.

If we remove the links in Step 4, what type of directory structure would it become?

A Tree directory structure

B Single-level directory

C Two-level directory

D Acyclic graph directory structure

💡 Hint

Refer to the 'Directory Structure Type' column and note the difference between tree and acyclic graph.

Concept Snapshot

Directory structures organize files:
- Single-level: all files in one directory
- Two-level: root with user directories
- Tree: nested directories forming hierarchy
- Acyclic graph: files linked in multiple directories without loops
Each step adds more organization and flexibility.

Full Transcript

This visual execution shows how directory structures evolve from simple to complex. We start with a single-level directory where all files are in one folder. Then, a two-level directory adds user folders to organize files better. Next, a tree structure nests directories inside others, creating a hierarchy. Finally, an acyclic graph allows files to be linked in multiple directories without creating cycles, preventing infinite loops. Each step is shown with operations, directory types, and visual states, helping learners see how files and directories are managed in operating systems.

Practice

1. Which directory structure allows all files to be stored in a single folder without any subfolders?

easy

A. Acyclic graph directory

B. Two-level directory structure

C. Tree-structured directory

D. Single-level directory structure

Solution

1. Step 1: Understand single-level directory

   In a single-level directory, all files are stored in one folder without any subfolders or hierarchy.

2. Step 2: Compare with other structures

   Two-level and tree structures have multiple folders or subfolders, and acyclic graph allows shared folders, so they are not single-level.

3. Final Answer:

   Single-level directory structure -> Option D

4. Quick Check:

   Single-level = all files in one folder [OK]

Hint: Single-level means one folder only, no subfolders [OK]

Common Mistakes:

• Confusing single-level with two-level structure
• Thinking tree structure is single-level
• Assuming acyclic graph is single-level

2. Which of the following correctly describes a two-level directory structure?

easy

A. All files are stored in one directory without subdirectories

B. Directories form a hierarchy with multiple levels

C. Each user has a separate directory under the root directory

D. Directories can share subdirectories forming cycles

Solution

1. Step 1: Recall two-level directory structure

   In two-level structure, each user has their own directory under a common root directory.

2. Step 2: Eliminate incorrect options

   All files are stored in one directory without subdirectories describes single-level, B describes tree structure, and D describes cyclic graphs which are not allowed.

3. Final Answer:

   Each user has a separate directory under the root directory -> Option C

4. Quick Check:

   Two-level = user directories under root [OK]

Hint: Two-level means root plus user folders only [OK]

Common Mistakes:

• Mixing two-level with single-level structure
• Thinking two-level allows deep folder trees
• Confusing acyclic graph with two-level

3. Consider a tree-structured directory where the root has two subdirectories: Docs and Images. Docs contains files a.txt and b.txt. Images contains pic1.jpg. How many total files are in the directory tree?

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Count files in Docs directory

   Docs contains two files: a.txt and b.txt, so count is 2.

2. Step 2: Count files in Images directory

   Images contains one file: pic1.jpg, so count is 1.

3. Step 3: Add all files

   Total files = 2 (Docs) + 1 (Images) = 3 files.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   2 + 1 = 3 files [OK]

Hint: Add files in all subdirectories for total count [OK]

Common Mistakes:

• Counting directories as files
• Forgetting to add files from all subdirectories
• Miscounting number of files in Docs

4. A directory structure is supposed to be a tree, but a user accidentally creates a cycle by linking a subdirectory back to its ancestor. What problem does this cause?

medium

A. The directory structure is no longer acyclic, causing infinite loops

B. Files become inaccessible due to missing links

C. The directory becomes single-level

D. The directory structure automatically corrects itself

Solution

1. Step 1: Understand tree and cycle concepts

   A tree directory must not have cycles; linking back creates a cycle.

2. Step 2: Identify consequences of cycle

   Cycle causes infinite loops when traversing directories, breaking acyclic property.

3. Final Answer:

   The directory structure is no longer acyclic, causing infinite loops -> Option A

4. Quick Check:

   Cycle breaks acyclic tree causing infinite loops [OK]

Hint: Cycles cause infinite loops in directory traversal [OK]

Common Mistakes:

• Thinking files become inaccessible immediately
• Assuming directory fixes cycle automatically
• Confusing cycle with single-level structure

5. In an acyclic graph directory structure, a file can appear in multiple directories by sharing links. Which advantage does this provide compared to a tree structure?

hard

A. It prevents any file from being deleted accidentally

B. It reduces disk space by storing one copy with multiple references

C. It forces all files to be stored in a single directory

D. It creates cycles to speed up file access

Solution

1. Step 1: Understand acyclic graph directory

   Acyclic graph allows multiple directories to share the same file via links, avoiding duplicates.

2. Step 2: Identify advantage over tree structure

   This sharing reduces disk space since only one copy of the file is stored with multiple references.

3. Step 3: Eliminate incorrect options

   Files can still be deleted, it does not force single directory storage, and cycles are not allowed.

4. Final Answer:

   It reduces disk space by storing one copy with multiple references -> Option B

5. Quick Check:

   Shared links save space in acyclic graph [OK]

Hint: Shared links save space by avoiding duplicate files [OK]

Common Mistakes:

• Thinking acyclic graph creates cycles
• Assuming files cannot be deleted
• Confusing with single-level directory