[⚙️ OS] 프로세스 동기화

프로세스 동기화

여러 프로세스가 공유자원에 접근한다면 race condition(경합조건)이 발생한다.

이러한 상황을 막기 위해서 필요한 mechanism이 있다. 

 

 

🔹 Locking Mechanism 

• 어떤 작업이 수행되는 것을 막는다
  • 👉 before entering critical section 
  • 👉 before accessing shared data

 

• critical section(임계영역)은 최대한 짧게 설정해야한다 
• multi-processors에서 interrupt-based locks을 구현하기 어려움 👉 read-write instructions 으로 해결

 

---

🔹 Semaphore 

• Synchronization tool
• Counting semaphore
• Binary semaphore ➔ 0 또는 1 값만 가짐. mutex lock 
  • 여러 개의 프로세스들이 자원(메모리)을 공유할 때 하나의 프로세스만 접근 가능하도록 함 = mutual exclusion = mutex
• wait() = P()
  • waits for semaphore to become positive, then decrements it by 1
  • 자원 획득하지 못하면 block()
• signal() = V()
  • increments the semaphore by 1, waking up a waiting P
  • 자원 반납하면 wakeup()
• Semaphore Implementation with no busy waiting
  • Block() : put the process on the waiting queue
    ➔ 커널은 block을 호출한 프로세스를 suspend시키고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
    ➔ context switching 일어나서 다음 프로세스에게 CPU 사용권 넘어가게 함으로써 CPU가 놀지 않도록 만듦.
     
  • Wakeup() : remove one of processes in the waiting queue and put it in the ready queue
    ➔ block된 프로세스를 wake up 시키고 이 프로세스의 PCB를 ready queue로 옮김

typedef struct{
	int value;
    struct process *list; /* process wait queue */
} semaphore;

P(semaphore *S){
	S->value--;
    if(S->value < 0){
    	add this process to S->list;
        block();
    }
}

V(semaphore *S){
	S->value++;
    if(S->value <= 0){
    	remove a process P from S->list;
        wakeup(P);
    }
}

 

---

 

 

🔹 Java Synchronization 

public class SynchronizedQueue {
    public LinkedList<Integer> q = new LinkedList<Integer>();
    
    public synchronized void enqueue (int item) {
        q.add(item);
        notify();
   }
   
    public synchronized int dequeue () {
        try {
        	while (q.size() == 0) {
        		wait();
        	}
        	return q.removeFirst();
        } catch (InterruptedException e) {
        	return 0;
        }
    }
}

 

 

 

동기화의 문제 

 

🔹 Producer-Consumer with Bounded Buffer 

• 버퍼는 오직 하나의 스레드만 조작할 수 있음 ➔ mutual exclusion (mutex)
• 버퍼가 가득 차있다면 producer는 consumer가 버퍼에서 가져갈 때 동안 wait
• 버퍼가 비어있다면 consumer는 producer가 버퍼를 채울 때 동안 wait 

 

 

🔹 Readers-Writers Problem 

• 한 프로세스가 DB에 write중일 때 다른 프로세스가 접근하면 안됨
• read는 여럿이 동시에 해도 됨
• Solution
  • writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 reader들을 다 DB에 접근하게 해줌
  • writer는 대기 중인 reader가 하나도 없을 때 DB 접근 허용
  • 일단 writer가 DB에 접근 중이면 reader들은 접근 금지
  • writer가 DB에서 빠져나가야만 reader 접근 허용
• Shared Data
  • readCount ➔ 현재 DB에 접근 중인 reader 수
  • DB
• Synchronization variables
  • mutex : readcount를 접근하는 코드(critical section)의 mutual exclusion 보장
  • db : reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

• 여럿이 읽을 수 있도록 readcount 설정
• 누군가 이미 읽고 있다면 readcount++는 readcount>1일 것임
  👉 lock을 따로 걸 필요가 없다. 이미 최초에 와서 읽고 있는 것이 db에 lock을 걸어놓았기 때문=P(db)
  
  
• 마지막으로 읽고 나가는 프로세스인 경우 readcount-- == 0
  👉 db에 걸어놓은 lock을 푼다 = V(db)
  
  
• reader가 이미 lock을 걸어놓았을 때 writer보다 reader가 늦게 왔어도 reader를 먼저 처리 
  👉 Starvation 발생 가능 ➔ 우선순위를 부여해서 해결 가능 

 

 

🔹Dining Philosophers Problem 

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 
• Starvation : 영원히 자원을 얻지 못하고 무한히 기다림 

 

 

 

Concurrency Problem

 

🔹 Monitors 

• mutual exclusion ➔ lock
  • always acquire before accessing shared data structure
  • always release after finishing with shared data
• conditional synchronization ➔ condition variables 
  • a queue of threads waiting for something inside a critical section
  • 특정 조건이 충족될 때까지 스레드 기다리게 함