Classical Problems of Synchronization

The Bounded-buffer Problem

Buffer

• Shared Memory Block에 위치
• Empty Slot 과 Item Slot으로 나뉨

Producer

• Info를 만드는 Process
• Buffer의 Empty Slot이 Resource
• Buffer의 Empty Slot이 확보되어야 동작
• Buffer가 꽉 차면, 대기 (empty slot : semaphore empty)

Consumer

• Buffer의 Item Slot이 Resource
• Item Slot이 Resource
• Buffer의 Item Slot의 내용이 있어야 동작
• Buffer가 비게 되면, 대기 (item slot : semaphore full)

Code

Semaphores full = 0; // init item size
Semaphores empty = n; // buffer size
Semaphores mutex = 1; // init mutex should be true

Producer

do
{
	Produce an item in nextp
    
    wait(empty);
    wait(mutex); // acquire()
    
    Add nextp to buffer
    
    signal(mutex); // release()
    signal(full);
    
}while(1)

Consumer

do
{
	wait(full);
    wait(mutex); // acquire()
    
    Remove an item from buffer to nextc
    
    signal(mutex); // release()
    signal(empty);
    
    Consume the item in nextc
}while(1)

The Readers-Writers Problem

여러 개의 Readers와 Writers가 Shared data에 접근

• Readers는 Shread Data의 정보를 수정하지 않음
• 따라서 Readers는 Mutual Exclusive 지키지 않아도 됨
• 하지만 Writer는 지켜야 함

semaphore mutex = 1;
semaphore wrt = 1;
int readcount = 0; // Readers in Critical Section

Writer

wait(wrt);

writing is performed

signal(wrt);

• mutex는 readcount에 대한 mutex이므로 writer에는 따로 지정할 필요 없음

Reader

wait(mutex)
readcount++;
if(readcount == 1) wait(wrt); 
// 첫 번째 reader가 진입할 때 writer가 접근하지 못하게 막는 역할
signal(mutex)

reading is performed

wait(mutex);
readcount--;
if(readcount == 0) signal(wrt);
// 마지막 reader가 나갈 때 writer가 접근할 수 있도록 해제하는 역할
signal(mutex)

The dining-philosophers Problem

Reference

monitor diningPhilosophers
{
	int state[5];
    static final int THINKING = 0;
    static final int HUNGRY = 1;
    static final int EATING = 2;
    condition self[5];
    
    void initialization_code
    {
    	for(int i=0; i<5; i++)
        	state[i] = THINKING;
    }
    
    void pickUp(int i)
	{
    	state[i] = HUNGRY;
        test(i);
        
        if(state[i] != EATING)
        	self[i].wait();
    }
    
    void putDown(int i)
    {
    	state[i] = THINKING;
    	test((i+4)%5);
        test((i+1)%5);
    }
    
    void test(int i)
    {
    	if(state[i] == HUNGRY &&
        	state[(i+4)%5] != EATING 
            state[(i+1)%5] != EATING
        )
        state[i] = EATING;
        self[i].signal();
    }	

}

Synchronization within the Kernel

Synchronization in Windows Kernel

• Multithreaded kernel
• Soft Real=time Applications
• Multiple Processors

Accessing global variables

• single processor system : mask interrupt (disable interrupt)
• multi processor system : spinlocks

Dispatcher Objects

• usermode : mutex lock, semaphores, evenets, timers
• signaled state (lock x) / nonsignaled state (lock o)

Critical section Objects

• Usermode에서 Thread Sync를 위해 사용되고, Kernel 개입 없이도 Lock / Unlock 가능

• 대부분의 thread에 대해 spinlock을 걸다가

• thread의 spinlock time이 길어지게 되면, mutex나 semaphore로 전환

Synchronization in Linux Kernel

• Linux Kernel
• atomic_t : interruption 없이 연산 가능

Kernel Code

int mutex_init(mutex_t *mp, int type, void *arg);
int mutex_lock(mutex_t *mp); // acquire
int mutex_trylock(mutex_t *mp);
int mutex_unlock(mutex_t *mp); // release
int mutex_consistent(mutex_t *mp);
int mutex_destroy(mutex_t *mp);

// Multi Processor
spin_lock();
spin_unlock();
// Single Processor
preempt_disable() // switching X
preempt_enable() // switching O

POSIX Synchronization

POSIX Mutex Locks

#include <pthread.h>

pthread_mutext_t mutex;
pthread_mutext_init(&mutex, NULL);

pthread_mutex_lock(&mutex);

/* critical section */

pthread_mutex_unlock(&mutex);

POSIX Semaphores

Named semaphores

• Parent Child Relation이 없는 Process간 사용

#include <semaphore.h>
sem_t *sem;

sem = sem_open("SEM", O_CREATE, 0666, 1);

sem_wait(sem); //acquire
/* critical section */
sem_post(sem); // release

Unnamed Semaphores

int sem_init(sem_t *sem, int pshared, unsigned int value);

sem: 초기화할 세마포어의 포인터
pshared: 0이면 세마포어가 프로세스 내에서만 공유, 
         0이 아닌 값이면 세마포어가 프로세스 간에 공유
value: 세마포어의 초기 값

#include <semaphore.h>
sem_t sem;

sem = sem_open(&sem, 0, 1);

sem_wait(sem); //acquire
/* critical section */
sem_post(sem); // release

POSIX Monitor

• OOP가 아닌 Function Level 이여서 motex lock + condition var으로 구현

// init

phtread_mutex_t mutex;
pthread_cond_t cond_var;

pthread_mutex_init(&mutex, NULL);
phtread_cond_init(&cond_var, NULL);

Thread A

pthread_mutex_lock(&mutex);
while(a != b) // 얼음 얼음 얼음 얼음 얼음
	pthread_cond_wait(&cond_var, &mutex);
pthread_mutex_unlock(&mutex);

Thread B

pthread_mutex_lock(&mutex);
a = b // 땡 
pthread_cond_signal(&cond_var);
pthread_mutex_unlock(&mutex);