Introduction

Notes during problem solving.

Problem Description

Suppose you are given the following code:

class FooBar {
    public void foo () {
        for (int i = 0; i < n; i++) {
            print("foo");
        }
    }

    public void bar () {
        for (int i = 0; i < n; i++) {
            print("bar");
        }
    }
}

The same instance of FooBar will be passed to two different threads:

  • thread A will call foo(), while
  • thread B will call bar().

Modify the given program to output "foobar" n times.

Code

typedef struct {
    int n;
    sem_t foo_sem;
    sem_t bar_sem;
    sem_t order_sem;
} FooBar;

FooBar *fooBarCreate (int n) {
    FooBar *obj = (FooBar *) malloc(sizeof(FooBar));
    obj->n = n;

    sem_init(&obj->foo_sem, 0, 0x00);
    sem_init(&obj->bar_sem, 0, 0x00);
    sem_init(&obj->order_sem, -1, 0x00);

    return obj;
}

void foo (FooBar *obj) {
    
    for (int i = 0; i < obj->n; i++) {
        
        // printFoo() outputs "foo". Do not change or remove this line.
        sem_post(&obj->foo_sem);
        sem_wait(&obj->bar_sem);
                printFoo();
            sem_post(&obj->order_sem);
    }
}

void bar (FooBar *obj) {
    
    for (int i = 0; i < obj->n; i++) {
        
        // printBar() outputs "bar". Do not change or remove this line.
        sem_post(&obj->bar_sem);
        sem_wait(&obj->foo_sem);
            sem_wait(&obj->order_sem);
                printBar();
    }
}

void fooBarFree (FooBar *obj) {
   sem_destroy(&obj->foo_sem);
   sem_destroy(&obj->bar_sem);
   sem_destroy(&obj->order_sem); 
   
   free(obj);
}

Solution Explanation

Used semaphores to print one at a time & in a certain order.

Code Explanation

Each function (foo(), bar()) waits for each other’s semaphore to be posted.
The post is given before waiting to prevent deadlock. Say bar() calls wait and a context switch happens to foo(), which also waits for bar(). This causes a deadlock.
However, if the environment is not conducted on a single-core CPU, I guess there won’t be a problem.

Conclusion

I originally tried to go for the dining philosophers problem, but leetcode didn’t support C for the problem.
I solved a few other problems that I didn’t post because posting takes a quite of bit of time.
Hopefully I catch up.