Worksheet 15: File-system

Dream Coding

Niko has a special talent: dream coding. He can write codes with eyes closed, and the quality is better than monkey punching keyboard. One night, he burns the midnight oil to implement the dining philosophers solution from OS lecture, because the demo is next morning.

Niko starts dream coding:

11:53 PM:

$ vim dining_dogs.c
[creates the classic 5 dogs, 5 spoons problem]
[dogs keep deadlocking, all holding left spoon, waiting for right]

$ git add dining_dogs.c
$ git commit -m "add dining dogs deadlock problem"
$ git push origin master
Pushed to master

12:15 AM:

$ vim doghouse_sem.c
[adds doghouse semaphore with limit 4]

$ git add doghouse_sem.c
$ git commit -m "doghouse semaphore for concurrency throttling"
$ git push origin master
Pushed to master

12:40 AM:

$ vim dining_dogs.c
[wiring up sem_wait before entering doghouse]
[adding sem_post after leaving]
[integrating the throttling logic...]

$ git add dining_dogs.c
$ git commit -m "integrate doghouse throttling to prevent deadlock"
$ git push origin master
Pushing... 43%... 67%...

12:41 AM: Niko finally falls asleep after 8-hours non-stop working.

Next Morning - 9:00 AM

Capoo arrives at the office and pulls latest code:

$ git pull origin master

Updating a3f829c..e8b9d12
Fast-forward
 dining_dogs.c    | 67 +++++++++++++++++
 doghouse_sem.c   | 23 ++++++++

Capoo opens dining_dogs.c:

// 5 dogs trying to eat with 5 spoons (forks)
void* dog(void* arg) {
    int id = *(int*)arg;
    int a, b, c;
    
    while(1) {
        drooling(); // Hungry @_@
        
        // Try to pick up spoons
        pthread_mutex_lock(&spoon[id]);           // Pick left spoon
        pthread_mutex_lock(&spoon[(id+1) % 5]);   // Pick right spoon
        
        eat_dogfood(id); // like a king
        
        // Put down spoons
        pthread_mutex_unlock(&spoon[??]);
        pthread_mutex_unlock(&spoon[??]);
}

Capoo opens doghouse_sem.c:

sem_t doghouse;

sem_init(&doghouse, 0, ???);

// 4 dogs can enter doghouse at once
// With 4 dogs and 5 spoons, no deadlock
sem_wait(???)

“WHAT THE …” Capoo’s coffee spills.

“Don’t even compile. What are these random variables int a, b, c? And sem_wait(???)? Wait on WHAT?”

The code is just messy torn writes. (´･ω･`)

Capoo runs into Nini’s office.

Capoo: “Niko pushed the dining dogs code but it’s garbage.”

Nini: “Where’s Niko?”

Capoo: “Still asleep at his desk.””

Nini sigh: “Classic torn write problem. He brain dumped everything but crashed in the middle.”

Nini calls Niko into the office. Niko looks like a zombie.

Nini: “Man. You committed broken code … Do you even remember what you were doing?”

Niko (tired as dog): “Eh .. I… I learned about concurrency throttling in OS lecture. You limit 4 dogs in the doghouse. Then deadlock can’t happen because… uh…”

Nini: “Right! But your code contains garbage like sem_wait(???). Nobody knows what the heck you try to do!”

Nini: “Now LISTEN. Before you write a single line of code, create a pull request (PR) FIRST.”

“If you pass out next time, Capoo could at least throw your PR to Gemini Code. OK?”

### Problem
5 dogs, 5 spoons, classic deadlock when all grab left spoon simultaneously.

### Solution  
Doghouse semaphore with limit 4. Only 4 dogs allowed in the doghouse.
With 4 dogs and 5 spoons, deadlock impossible (always a spare spoon).

### Implementation Steps
1. Create dining_dogs.c with deadlock problem
2. Create doghouse_sem.c with semaphore (init value = 4)
3. Add sem_wait(&doghouse) before dog enters
4. Add sem_post(&doghouse) after dog leaves  
5. Initialize semaphore in main() with value 4

$ vim dining_dogs.c
[creates dog function with mutex locks]
[creates the deadlock scenario]

$ git add dining_dogs.c
$ git commit -m "PR: Step 1 - Create dining dogs deadlock problem"
$ git push origin feature/doghouse-deadlock-prevention

$ vim doghouse_sem.c
[declares sem_t doghouse]
[adds initialization code: sem_init(&doghouse, 0, 4)]

$ git commit -m "PR: Step 2 - Create doghouse semaphore with limit 4"
$ git push origin feature/doghouse-deadlock-prevention

$ git add *.c
$ git commit -m "PR: Complete Steps 3-5 using PR description"
$ git push origin feature/doghouse-deadlock-prevention

Video Lecture

Remember to open the English subtitle on Youtube: eLearn link of the video lecture

(◕ܫ◕) (◕ܫ◕)

!!有繁體中文字幕!!

Readings

• The stories of three file systems
• Textbook: File-system Implementation

Learning Objectives

I understand the following concepts:

• Virtual File-system (VFS)
• What “mounting a file-system” means
• The content of superblock, inode
• ext2 inode structure: the direct pointer / single indirect pointer / double indirect pointer / triple indirect pointer, and how to calculate the maximum supported file size.
• Dentry and dentry cache
• Path resolution
• Torn writes
• The Atomic Rename Trick
• Write Ahead Logging: journal writes, checkpoint, free, journal replay