# Operating system
## Producer and Consumer
The three essential problems that need to be addressed in the producer-consumer as following:
1. **Mutual Exclusion**:
This problem ensures that only one thread can access a shared resource(buffer) at a time. It prevents race conditions and ensure data consistency. In this assignment, mutual exclusion ensures that producers and consumers do not simultaneously access or modify the buffer.
3. **Progress**:
It ensures that if a thread(producer or consumer) is not blocked, it can eventually execute its critical section. In this case, progress ensures that if a producer or consumer is ready to produce of consume an item, it will eventually be able to do so without being indefinitely blocked.
5. **Bounded Waiting**:
It ensures that there's a limit on the number of times a thread is allowed to wait to access a shared resource. This prevents a situation where a thread is continually being bypassed by other threads, leading to starvation. In this case, bounded waiting ensures that neither producers nor consumers are indefinitely starved of access to the buffer.

## C Code
In this code, it demonstrates a classic producer-consumer problem using pthreads and semaphores in C. The resource of this code can be accessed from [YouTube](https://www.youtube.com/watch?v=l6zkaJFjUbM&t=5s&ab_channel=CodeVault) provided by [CodeVault](https://www.youtube.com/@CodeVault). The author breaks down the problem step by step and demonstrates how to address the three essential problems

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <semaphore.h>

#define THREAD_NUM 8

sem_t semEmpty;
sem_t semFull;

pthread_mutex_t mutexBuffer;

int buffer[10];
int count = 0;

void* producer(void* args) {
    while (1) {
        // Produce
        int x = rand() % 100;
        sleep(1);

        // Add to the buffer
        sem_wait(&semEmpty);
        pthread_mutex_lock(&mutexBuffer);
        buffer[count] = x;
        count++;
        pthread_mutex_unlock(&mutexBuffer);
        sem_post(&semFull);
    }
}

void* consumer(void* args) {
    while (1) {
        int y;

        // Remove from the buffer
        sem_wait(&semFull);
        pthread_mutex_lock(&mutexBuffer);
        y = buffer[count - 1];
        count--;
        pthread_mutex_unlock(&mutexBuffer);
        sem_post(&semEmpty);

        // Consume
        printf("Got %d\n", y);
        sleep(1);
    }
}

int main(int argc, char* argv[]) {
    srand(time(NULL));
    pthread_t th[THREAD_NUM];
    pthread_mutex_init(&mutexBuffer, NULL);
    sem_init(&semEmpty, 0, 10);
    sem_init(&semFull, 0, 0);
    int i;
    for (i = 0; i < THREAD_NUM; i++) {
        if (i > 0) {
            if (pthread_create(&th[i], NULL, &producer, NULL) != 0) {
                perror("Failed to create thread");
            }
        } else {
            if (pthread_create(&th[i], NULL, &consumer, NULL) != 0) {
                perror("Failed to create thread");
            }
        }
    }
    for (i = 0; i < THREAD_NUM; i++) {
        if (pthread_join(th[i], NULL) != 0) {
            perror("Failed to join thread");
        }
    }
    sem_destroy(&semEmpty);
    sem_destroy(&semFull);
    pthread_mutex_destroy(&mutexBuffer);
    return 0;
}

## Explanation
Firstly, we define the number of threads ```THREAD_NUM``` as 8. Two semaphores ```semEmpty``` and ```smeFull``` are initialized. ```semEmpty``` represents the number of empty slots in the buffer, and ```SemFull``` represents the number of filled slots in the buffer. A mutex ```mutexBuffer``` is also initialized to ensure mutual exclusion when accessing the buffer.

    pthread_t th[THREAD_NUM];
    pthread_mutex_init(&mutexBuffer, NULL);
    sem_init(&semEmpty, 0, 10);
    sem_init(&semFull, 0, 0);

An integer array ```buffer``` is declared to act as the shared buffer between the producer and consumer threads. The counter ```count``` can keep track of the number of elements currently in the buffer.

int buffer[10];
int count = 0;

In this work, we define a Producer Function ```producer``` which generates a random number and adds it to the buffer. It waits until there is space in the buffer ```semEmpty``` and locks the mutex before adding the element. After adding the element, it unlocks the mutex and signals ```sem_post``` that the buffer is no longer empty. ```sem_post(&semFull)``` is used to signal that a slot in the buffer has been consumed by the consumer thread. It increases the count of filled slots in the buffer, allowing other consumer threads to consume more items.

Use to lock the buffer

pthread_mutex_lock(&mutexBuffer);

Use to unlodk the buffer when completing the modification

pthread_mutex_unlock(&mutexBuffer);

void* producer(void* args) {
    while (1) {
        // Produce
        int x = rand() % 100;
        sleep(1);

        // Add to the buffer
        sem_wait(&semEmpty);
        pthread_mutex_lock(&mutexBuffer);
        buffer[count] = x;
        count++;
        pthread_mutex_unlock(&mutexBuffer);
        sem_post(&semFull);
    }
}

For the consumer function, we define a function ```consumer``` which can remove an element from the buffer and print it out. It waits until there is at least one element in the buffer ```semFull```, locks the mutex before removing the element, and then signals ```sem_post``` that the buffer is no longer full. ```sem_post(&semEmpty)``` is used to signal that an empty slot in the buffer has been filled by the producer thread. It increases the count of empty slots in the buffer, allowing other producer threads to add more items. After calling ```sem_post```, if any threads are waiting on the semaphore using ```sem_wait```, one of those threads will be unblocked and allowed to proceed.

void* consumer(void* args) {
    while (1) {
        int y;

        // Remove from the buffer
        sem_wait(&semFull);
        pthread_mutex_lock(&mutexBuffer);
        y = buffer[count - 1];
        count--;
        pthread_mutex_unlock(&mutexBuffer);
        sem_post(&semEmpty);

        // Consume
        printf("Got %d\n", y);
        sleep(1);
    }
}

Notably, in the context of the producer and consumer functions, ```sleep(1)``` is used to simulate some processing time and make the output exhibit slowly. Specifically, after producing or consuming an item, the thread waits for one second before contunuing, simulating the time taken for actual processing.

In the ```main()``` function, threads are created. One thread is designated as the consumer, thile the rest are producers. Each thread runs either the ```producer``` and ```consumer``` function. Then, the main thread waits for all thread to finish ```pthread_join```.

int main(int argc, char* argv[]) {
    srand(time(NULL));
    pthread_t th[THREAD_NUM];
    pthread_mutex_init(&mutexBuffer, NULL);
    sem_init(&semEmpty, 0, 10);
    sem_init(&semFull, 0, 0);
    int i;
    for (i = 0; i < THREAD_NUM; i++) {
        if (i > 0) {
            if (pthread_create(&th[i], NULL, &producer, NULL) != 0) {
                perror("Failed to create thread");
            }
        } else {
            if (pthread_create(&th[i], NULL, &consumer, NULL) != 0) {
                perror("Failed to create thread");
            }
        }
    }
    for (i = 0; i < THREAD_NUM; i++) {
        if (pthread_join(th[i], NULL) != 0) {
            perror("Failed to join thread");
        }
    }
    sem_destroy(&semEmpty);
    sem_destroy(&semFull);
    pthread_mutex_destroy(&mutexBuffer);
    return 0;
}

## Reference
1. [Producer - Consumer Problem in Multi-Threading](https://www.youtube.com/watch?v=l6zkaJFjUbM&t=5s&ab_channel=CodeVault)
2. [ShengYu Talk](https://shengyu7697.github.io/cpp-sem_wait/)
3. [POSIX Semaphores API](https://docs.oracle.com/cd/E19048-01/chorus5/806-6897/architecture-7/index.html)