Concurrent Processes/Threads

Synchronization

어떤 프로세스의 진행이 다른 프로세스의 진행에 의존적인 상황에서, 두 프로세스가 알고있는 정보를 일치시키는 것이다.
synchronization은 critical section에 들어갈 수 있는 인원을 제한하는 것으로, 모든 shared resource(전역변수, 버퍼, 큐, 리스트, 파일..)에 대해 필요하다.

Determinacy(결정성)

같은 input을 넣으면 같은 output이 나오는 것. 수행의 흐름은 다를 수 있지만 결과는 같아야한다.

즉 concurrent 프로그램에서는 가능한 한 동시에 수행되면서, determinacy를 지켜줘야한다.

Mutual Exclusion의 조건

1. critical section에는 혼자만 들어가도록 해줘야한다. (아닌 경우도 있긴 함)
2. Progress
   진행이 되어야한다. 즉 어떤 프로세스가 임계 구역에서 나왔는데 기다리고 있는 프로세스들 중 아무도 들어가지 못하는 상황이 있어서는 안된다. -> tie-breaking rule이 필요
3. Bounded Waiting
   기한이 정해진 기다림이어야한다. (<-> 무기한 연기(Starvation))
4. Performance
   critical section에 들어가고 나오는 작업은 가능한 한 빨리 이루어져야한다.

Mutual Exclusion(Syncronization) 방법

1. Locks
2. Semaphores -> (중요) 모든 유저 프로세스의 싱크로나이제이션 기반이 됨
3. Monitors
4. Messages

=> 세마포, 락 등 싱크로나이제이션 도구들도 사실 그 자체가 크리티컬 섹션이 되는 경우가 많다. 그러나 이런 도구들은 내부적으로 interrupt_disable, spin-lock 등의 방법으로 보호되고 캡슐화되어서 제공된다.

---

Hardware Solution (하드웨어 명령어)

1. test_and_set(&lock)
   임계 구역에 들어가기 위해 비었는지 확인(test)하고, 비었다면 들어가기 위해 flag를 set하는 두 가지 동작을 원자적으로 수행하는 것이다.
   test하고 set하는 사이에 다른 프로세스가 상황을 모르고 끼어드는 것을 막기 위한 방법이다. test & set은 기다리는 동안 busy waiting loop을 돌기 때문에 CPU 낭비를 막기 위해 유저 프로세스에서는 사용하지 않는다.

2. interrupt_disable()
   커널도 사실 크리티컬 섹션 덩어리이기 때문에, 커널 코드에서도 싱크로나이제이션이 필요하다. 예를 들어 스케쥴링 큐를 만지는 과정에서 인터럽트가 들어온다면 망가져버린다. 그러나 인터럽트는 강력해서 mutext lock으로는 막을 수 없기 때문에, 스케쥴링 큐를 건드리는 동안에는 interrupt를 꺼둬야한다(interrupt_disable()).
   그러나 SMP(CPU가 여러개)인 컴퓨터에서 이 코드를 사용할 경우, 다른 CPU가 스케쥴링 큐를 건드리는 것은 막을 수 없기 때문에, Spin-lock과 interrupt_disable()을 함께 사용한다.