9. Synchronization and Mutex

#include <iostream>
#include <thread>

int counter = 0;

int main(){
	std::thread newThread([](){
        for (int i = 0; i < 10000000; i++){
            counter++; 
        }   
    });
	for(int i = 0; i < 10000000; i++){
		counter++;
	}
    newThread.join();
	printf("I counted: %d\n", counting);
	return 0;
}

for(int i = 0; i < 10000000; i++){
// Critical Section starts form here
	counter++;
// To here
}

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

int ticket_amount = 2;

void* ticketAgent(void* arg){
	int t = ticketAmount;
	if (t > 0){
		printf("One ticket sold\n");
		t--;
	}else{
		printf("Ticket sold out\n");
	}
	ticketAmount = t;
	pthread_exit(0);
}

int main(int argc, char const* agrv[]){
	pthread_t ticketAgent_tid[2];
	for(int i = 0; i < 2; i++){
		pthread_create(ticketAgent_tid+i, NULL, ticketAgent, NULL);
	}
	for (int i = 0; i < 2; i++){
		pthread_join(ticketAgent_tid[i], NULL);
	}
	sleep(1);
	printf("The left ticket is %d\n", ticketAmount);
	return 0;
}

#include <pthread.h>
pthread_mutex_t lock;
pthread_mutex_init(&lock,NULL);
pthread_mutex_lock(&lock);
pthread_mutex_unlock(&lock);
pthread_mutex_destroy(&lock);

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

int ticketAmout = 2; // 票的数量: 全局变量
pthread_mutex_t lock; // 定义互斥锁
void* ticketAgent(void* arg){
    pthread_mutex_lock(&lock); // 上锁
	int t = ticketAmout;
	if (t > 0){
		printf("One ticket sold\n");
		t--;
	}else{
		printf("Ticket sold out\n");
	}
	ticketAmout = t;
    pthread_mutex_unlock(&lock); // 解锁
	pthread_exit(0);
}

int main(int argc, char const* agrv[]){
	pthread_t ticketAgent_tid[2];
    pthread_mutex_init(&lock, NULL); // 锁的初始化
	for(int i = 0; i < 2; i++){
		pthread_create(ticketAgent_tid+i, NULL, ticketAgent, NULL);
	}
	for (int i = 0; i < 2; i++){
		pthread_join(ticketAgent_tid[i], NULL);
	}
	sleep(1);
	printf("The left ticket is %d\n", ticketAmout);
	return 0;
}

bool mutex_lock = false;

lock(mutex_lock){
	if(mutex_lock == false){  // test
		mutex_lock = true;    // lock
	}
}
//+--------------------+
//|                    |
//|  critical section  |
//|                    |
//+--------------------+
unlock(mutex_lock){
	mutex = false;
}

bool mutex_lock = false;

lock(mutex_lock){
	while(mutex_lock != true){  // test
		;
	}
	mutex_lock = true;          // lock
}
//+--------------------+
//|                    |
//|  critical section  |
//|                    |
//+--------------------+
unlock(mutex_lock){
	mutex_lock = false;
}

//未上锁:0
//已上锁:1
bool mutex = 0;

lock(mutex){
	while(compare_and_swap(mutex, 0, 1) == false){  //测试+上锁
	//while(test_and_set(mutex, 1) == 1){
		;
	}
}
//+--------------------+
//|                    |
//|  critical section  |
//|                    |
//+--------------------+
unlock(mutex){
	mutex = 0;
}

int pthread_mutex_lock(pthread_mutex_t *mutex){
	//尝试使用CAS操作来获取锁
	if(atomic_compare_and_swap(&mutex->lock,0,1)){  //这是一个快速路径
		//成功获取锁
		return 0;
	}
	//锁已经被其他执行流占有，进入慢速路径(阻塞自己，省略实现)
	return -1;
}

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>

#define NUM_ITERATIONS 100000

pthread_mutex_t mutex;
int counter = 0;

void* mutex_thread_func(void* arg){
	for (int i = 0; i < NUM_ITERATIONS; ++i)
	{
		pthread_mutex_lock(&mutex);			//Get mutex lock
		counter++;
		for (int j = 0; j < 10000; ++j);	//Increase system load
		pthread_mutex_unlock(&mutex);		//Release the lock
	}
	return NULL;
}

int main(int argc, char const *argv[])
{
	pthread_t t1,t2;
	struct timespec start, end;

	pthread_mutex_init(&mutex, NULL);		//Initialize the lock

	clock_gettime(CLOCK_MONOTONIC, &start);	//Start time counting

	pthread_create(&t1, NULL, mutex_thread_func, NULL);
	pthread_create(&t2, NULL, mutex_thread_func, NULL);

	pthread_join(t2, NULL);
	pthread_join(t1, NULL);

	clock_gettime(CLOCK_MONOTONIC, &end);	//Finish time counting

	pthread_mutex_destroy(&mutex);			//Destroy the lock

	double elapsed = (end.tv_sec - start.tv_sec) 
				   + (end.tv_nsec - start.tv_nsec) / 1e9;

	printf("Final counter value with pthread_mutex_t: %d\n",counter);
	printf("Elapsed time with pthread_mutex_t: %f\n",elapsed);

	return 0;
}

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>

#define NUM_ITERATIONS 100000

pthread_spinlock_t spinlock;
int counter = 0;

void* mutex_thread_func(void* arg){
	for (int i = 0; i < NUM_ITERATIONS; ++i)
	{
		pthread_spin_lock(&spinlock);		//Get spin lock
		counter++;
		for (int j = 0; j < 10000; ++j);	//Increase system load
		pthread_spin_unlock(&spinlock);		//Release the lock
	}
	return NULL;
}

int main(int argc, char const *argv[])
{
	pthread_t t1,t2;
	struct timespec start, end;

	pthread_spin_init(&spinlock, PTHREAD_PROCESS_PRIVATE);		//Initialize the lock

	clock_gettime(CLOCK_MONOTONIC, &start);	//Start time counting

	pthread_create(&t1, NULL, mutex_thread_func, NULL);
	pthread_create(&t2, NULL, mutex_thread_func, NULL);

	pthread_join(t2, NULL);
	pthread_join(t1, NULL);

	clock_gettime(CLOCK_MONOTONIC, &end);	//Finish time counting

	pthread_spin_destroy(&spinlock);		//Destroy the lock

	double elapsed = (end.tv_sec - start.tv_sec) 
				   + (end.tv_nsec - start.tv_nsec) / 1e9;

	printf("Final counter value with pthread_spinlock_t: %d\n",counter);
	printf("Elapsed time with pthread_spinlock_t: %f\n",elapsed);

	return 0;
}

semaphore sem;
wait(sem){
	while(s <= 0){
		//busy waiting
	}
	s--;
}
post(sem){
	s++;
}

typedef struct{
	int value;
	struct process* L;
}semaphore;
semaphore sem;
wait(sem){
	s.value
	if(s.value < 0){
		block(s.L);
	}
}

post(sem){
	s.value++;
	if(s.value <= 0){
		wakeup(P);
	}
}

semaphore mutex = 1;

Thread n:
	//其他代码
	wait(mutex);    //相当于lock
	//+--------------------+
	//|                    |
	//|  critical section  |
	//|                    |
	//+--------------------+
	post(mutex);    //相当于unlock
	//其他代码

semaphore sync = 0;    //初始化为0，表示P2需要等待

P1:
	//其他代码
	//执行P2需要等待的操作
	post(sync);
	//其他代码
P2:
	//其他代码
	wait(sync);    //等待P1相关操作执行完毕
	//继续执行
	//其他代码

semaphore printer = 3;

Process n:
	//其他代码
	wait(printer);
	//+-----------------+
	//|                 |
	//|  using printer  |
	//|                 |
	//+-----------------+
	post(printer);
	//其他代码

#include <semaphore.h>

int sem_init(sem_t *sem, int pshared, unsigned int value);
/* 
Parameters:
	1. sem: Pointer to the semaphore to initialize.
	2. pshared: If non-zero, the semaphore is shared between processes; if zero, it is shared between threads of the same process.
	3. value: Initial value of the semaphore.

Return value: Returns 0 on success, -1 on failure and sets errno appropriately.
*/

int sem_destroy(sem_t *sem);
/* 
Parameters:
	1. sem: Pointer to the semaphore to destroy.

Return value: Returns 0 on success, -1 on failure and sets errno appropriately.
*/

int sem_wait(sem_t *sem);
/* 
Parameters:
	1. sem: Pointer to the semaphore to decrement (wait).

Return value: Returns 0 on success, -1 on failure and sets errno appropriately.
*/

int sem_trywait(sem_t *sem);
/* 
Parameters:
	1. sem: Pointer to the semaphore to decrement (try to wait).

Return value: Returns 0 on success, -1 on failure and sets errno appropriately.
*/

int sem_post(sem_t *sem);
/* 
Parameters:
	1. sem: Pointer to the semaphore to increment (signal).

Return value: Returns 0 on success, -1 on failure and sets errno appropriately.
*/

int sem_getvalue(sem_t *sem, int *sval);
/* 
Parameters:
	1. sem: Pointer to the semaphore.
	2. sval: Pointer to an integer to store the current value of the semaphore.

Return value: Returns 0 on success, -1 on failure and sets errno appropriately.
*/

Statement A1;
post(sem);

wait(sem);
Statement B1;

wait(mutex)
count++
post(mutex)
if count == n
    for i from 1 to n
	post(barrier)
	end for
end if
wait(barrier)

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

#define BUFFER_SIZE 20
#define PRODUCER_NUMBER 10
#define CONSUMER_NUMBER 10

int* buffer;
int pindex = 0;
int cindex = 0;
sem_t spaces;
sem_t items;
pthread_mutex_t mutex;
unsigned int seed = 252;

int produce(int id){
    int r = rand_r(&seed); // rand_r for thread safe.
    printf("Producer: %d\tproduced: %d.\n", id, r);
    return r;
}

void consume(int id, int value){
    printf("Consumer: %d\tconsumed %d.\n", id, value);
}

void* producer(void* arg){
    int* id = (int*) arg;
    for(int counter = 0; counter < 100; ++counter){
        int num = produce(*id);
        sem_wait(&spaces);
        pthread_mutex_lock(&mutex);
        buffer[pindex] = num;
        pindex = (pindex + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&items);
    }
    free(arg);
    pthread_exit(NULL);
}

void* consumer(void* arg){
    int* id = (int*) arg;
    for(int counter = 0; counter < 100; ++counter){
        sem_wait(&items);
        pthread_mutex_lock(&mutex);
        int num = buffer[cindex];
        buffer[cindex] = -1;
        cindex = (cindex + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&spaces);
        consume(*id, num);
    }
    free(id);
    pthread_exit(NULL);
}

int main(int argc, char** argv){
    buffer = malloc(BUFFER_SIZE * sizeof(int));
    for(int i = 0; i < BUFFER_SIZE; i++){
        buffer[i] = -1;
    }
    sem_init(&spaces, 0, BUFFER_SIZE);
    sem_init(&items, 0, 0);
    pthread_mutex_init(&mutex, NULL);

    pthread_t producer_thread[PRODUCER_NUMBER];
    pthread_t consumer_thread[CONSUMER_NUMBER];

    for(int i = 0; i < PRODUCER_NUMBER; i++){
        int* id = malloc(sizeof(int));
        *id = i;
        pthread_create(&producer_thread[i], NULL, producer, id);
    }
    for(int j = 0; j < CONSUMER_NUMBER; j++){
        int* id = malloc(sizeof(int));
        *id = j;
        pthread_create(&consumer_thread[j], NULL, consumer, id);
    }
    for(int k = 0; k < PRODUCER_NUMBER; k++){
        pthread_join(producer_thread[k], NULL);
    }
    for(int k = 0; k < CONSUMER_NUMBER; k++){
        pthread_join(consumer_thread[k], NULL);
    }

    free(buffer);
    sem_destroy(&spaces);
    sem_destroy(&items);
    pthread_mutex_destroy(&mutex);
    pthread_exit(0);
}

wait(roomEmpty);
// Write something
post(roomEmpty);

wait(mutex);
readers++;
if(readers == 1){
	wait(roomEmpty);
}
post(mutex);
// Read data.
wait(mutex);
readers--;
if(readers == 0){
	post(roomEmpty);
}
post(mutex);

wait(turnstile);
wait(roomEmpty);
// Write data.
post(roomEmpty);
post(trunstile);

wait(turnstile);
post(turnstile);
wait(mutex);
readers++;
if(readers == 1){
	wait(roomEmpty);
}
post(mutex);
// Read data.
wait(mutex);
readers--;
if(readers == 0){
	post(roomEmpty);
}
post(mutex);

wait(writeMutex);
writers++;
if(writers == 1){
	wait(noReaders)
}
post(writeMutex);
wait(noWriters);
// Write data.
post(noWriters);
wait(writeMutex);
writers--;
if(writers == 0){
	post(noReaders)
}

wait(noReaders);
wait(readMutex);
readers++;
if(readers == 1){
	wait(noWriters);
}
post(readMutex);
post(noReaders);
// Read data.
wait(readMutex);
readers--;
if(readers == 0){
	post(noWriters);
}
post(readMutex);

void foo(){
	pthread_mutex_lock(&lock);
	/* Read some data. */
	if(condition_is_true){
		printf("Cannot continue due to reasons.\n");
		// Missing something here~
		return;
	}
	/* Do something more. */
	pthread_mutex_unlock(&lock);
}

#include <pthread.h>
#include <stdio.h>

typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    int count;
} Monitor;

void init(Monitor *m) {
    pthread_mutex_init(&m->mutex, NULL);
    pthread_cond_init(&m->cond, NULL);
    m->count = 0;
}

void increment(Monitor *m) {
    pthread_mutex_lock(&m->mutex);
    m->count++;
    pthread_cond_signal(&m->cond);
    pthread_mutex_unlock(&m->mutex);
}

void wait_for_count(Monitor *m, int target) {
    pthread_mutex_lock(&m->mutex);
    while (m->count < target) {
        pthread_cond_wait(&m->cond, &m->mutex);
    }
    pthread_mutex_unlock(&m->mutex);
}

void destroy(Monitor *m) {
    pthread_mutex_destroy(&m->mutex);
    pthread_cond_destroy(&m->cond);
}

int main() {
    Monitor m;
    init(&m);

    pthread_t t1, t2;
    pthread_create(&t1, NULL, (void *(*)(void *))increment, &m);
    pthread_create(&t2, NULL, (void *(*)(void *))wait_for_count, &m);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Final count: %d\n", m.count);

    destroy(&m);
    return 0;
}

#include <iostream>
#include <mutex>
#include <condition_variable>
#include <thread>

class Monitor {
private:
    std::mutex mtx;
    std::condition_variable cond;
    int count = 0;
public:
    void increment() {
        std::unique_lock<std::mutex> lock(mtx);
        count++;
        cond.notify_one();
    }
    void wait_for_count(int target) {
        std::unique_lock<std::mutex> lock(mtx);
        cond.wait(lock, [this, target] { return count >= target; });
    }
    int get_count() const {
        return count;
    }
};

int main() {
    Monitor monitor;

    std::thread t1(&Monitor::increment, &monitor);
    std::thread t2(&Monitor::wait_for_count, &monitor, 1);

    t1.join();
    t2.join();

    std::cout << "Final count: " << monitor.get_count() << std::endl;

    return 0;
}

#include <pthread.h>

pthread_mutex_lock();   // system call * 1
shared_var++;
pthread_mutex_unlock(); // system call * 2

#include <atomic>

std::atomic<int> shared_var(0);

shared_var++; // Operations to shared_var is unbreakable.