프로세스 동기화

컴퓨터 시스템안에서 데이터에 접근하는 경로

1. 데이터가 저장된 위치가 있고
2. 저장된 데이터를 읽어와 연산하고
3. 연산한 결과를
4. 원래위치에 반영

데이터를 그냥 읽어와서 연산을 하면 문제가 되지 않지만, 연산한 결과를 다시 data에 저장을 하게되면 문제가 발생한다.
누가 먼저 데이터를 읽어갔느냐에따라 문제가 발생할수있음

만약 하나의 s-box를 여러 e-box가 공유하는 상황이라면 Race Condition(경쟁상태)의 가능성이 있다.

위의 그림을 보면 각 e-box는 반대되는 행위를 하고있다.

만약 CPU가 하나인 경우에는 위의 상황이 발생하지 않는다. 왜냐하면 한번에 하나의 처리만 가능하기때문에!!

만약 CPU가 여러개 있는 Multiprocessor system에서는 메모리를 공유하고 있다면 위의 상황이 발생할 수 있다!

그리고, 공유메모리를 사용하는 프로세스들의 동시작업이 문제가 될 수 있다.

또,
커널 내부 데이터를 접근하는 루틴들 간 위와 같은 충돌?이 발생할 수 있다.
예를 들면, 한 프로세스의 시스템 콜에 의해 커널모드 수행 중에 다른 프로세스의 인터럽트로 인해 동일한 커널모드의 다른 루틴을 수행시 커널의 데이터에 접근하게 되는 등의 문제가 발생할 수 있음

e-box s-box 예시

OS에서 race condition은 언제 발생하는가?

1. kernel 수행 중 인터럽트 발생시
   
   count변수를 처리하는 중에 인터럽트가 발생
   양쪽 다 커널코드이므로 kernel address space를 공유한다.

2. Process가 system call을 하여 kernel mode로 수행중인데 context switch가 일어나는 경우
   

두 프로세스의 address space간에는 data sharing이 없음

그러나 system call을 하는 동안에는 kernel address space의 data를 access하게됨(share)

이 작업 중간에 cpu를 preempt를 하게되면 race condition!!!

이 문제에 대한 해결책은 커널 모드에서 수행중일 때는 cpu를 preempt하지 않고, 커널모드에서 사용자 모드로 돌아갈 때 preempt하게 하기

3. Multiprocessor에서 shared memory 내의 kernel data

CPU가 여러개있는 환경에서는 어떻게 작동할까?

두가지 방법을 생각해 볼 수있다
1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게하는 방법
2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법

Process Synchronization 문제

• 공유 데이터의 동시접근은 데이터의 불일치 문제를 발생시킬 수 있다.

• 일관성 유지를 위해 협력프로세스간의 실행순서를 정해주는 메커니즘 필요

• Race Condition
  - 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  - 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  

• race condition을 막기 위해서는 concurrent process는 동기화되어야 한다.

The Critical-Section Problem

Critical Section이란?

• 공유데이터에 접근하는 코드

• n개의 프로세스가 공유데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유데이터를 접근하는 코드인 critical section이 존재
• problem
  - 하나의 프로세스가 critical section에 있을때 다른 모든 프로세스는 critical section으로 들어갈 수 없어야 한다.
  

위 문제에 대한 solution

• P0, P1 두 개의 프로세스가 있다고 가정

• 프로세스들의 일반적인 구조를 보면
  

• 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다!(synchronization variable)

critical section 문제를 풀기위해 만족해야할 조건

• 프로그램적 해결법의 충족조건
  - Mutual Exclusion (상호 배제)
  프로세스 p가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
  - Progress (진행)
  아무도 critical section에 있지않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  - Bounded waiting (유한 대기) - 위의 조건과 약간 상반되는조건..
  프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다.

• 가정
  - 모든 프로세스의 수행속도는 0이다.
  - 프로세스들 간의 상대적인 수행속도는 가정하지 않는다.
  

---

위의 조건을 충족하면서 critical section의 문제를 푸는 알고리즘!

Algorithm1

각 프로세스의 turn 값이 다름. 그래서 turn과 일치하는 번호를 가진 프로세스만 critical section에 접근할 수 있고, 이는 위의 첫번째 조건을 만족시킴(한번에 하나의 프로세스만 접근할 수 있기때문에)

하지만 두번째 조건을 만족시키지 못한다.
프로세스는가 한번 critical section에 들어갔다 나와야지만 turn값을 변경해줄 수 있기때문에!!

Algorithm2

앞의 알고리즘과의 차이점은 algorithm2에서는 flag라는 변수를 사용한다.
각 프로세스는 자신의 flag를 가진다.
flag가 true경우 프로세스가 critical section에 들어가고자 하는거임

코드를 보면 자신의 flag를 true로 만들고 그 밑의 코드에서 상대방의 flag를 체크한다! 만약 다른 프로세스의 flag중 true값이 있다면 다른 프로세스가 critical section에 들어가 있겠구나해서 기다린다.

이 알고리즘에도 문제가 있다.

두개의 프로세스가 동시에 flag를 true로 설정하면
상대방의 flag 값이 true이므로 두 프로세스모두 critical section에 못들어가고 계속 대기하게 된다.
즉, 둘다 2행까지 수행하고 끊임없이 양보하는 상황이 발생할 수 있다.

이 알고리즘도 알고리즘1처럼
첫번째 조건은 만족하지만, 두번째 조건을 만족시키지는 않는다.

Algorithm3

앞선 알고리즘 1, 2에서 사용한 turn과 flag를 모두 사용하고 있다.
자신의 flag를 true로 변경하고, turn을 상대 프로세스의 값으로 변경한다.

while문에서 상대방이 깃발을 들고있는지, 상대방의 turn이 맞는지 체크한다!
만약 조건을 만족시키지 못하면 i는 critical section에 들어가게된다.

이 알고리즘은 3가지 조건을 모두 만족시킨다.

근데 이 알고리즘은 Busy Waiting이라는 문제가 있다.
계속 CPU와 memory를 쓰면서 wait 한다. 비효율적인 방법이긴함!

Synchronization Hardware

하드웨어적으로 하나의 instruction만 주어지면 critical section문제는 해결된다!
즉, 데이터를 읽고+쓰는 행위를 하나의 instruction으로만 처리할 수 있게한다면 적어도 instruction하나가 실행되는 도중에 CPU를 빼앗기지는 않을거임

예를들어, Test_and_set이라는 instruction이 있는데 이 instruction은 a라는 데이터의 현재값을 읽어내고 데이터를 1로 변경하는 하나의 과정을 처리함.

이 코드를 보면 lock이 0인지(lock이 안걸린 상태) test_and_set에서 확인을 하고 1로 변경하는 처리를 해줌(내가 lock을 걸고 critical section으로 들어간다는 의미)

즉, while문에서 lock이 0이면 critical section들어가는거임. lock이 1이었다면 while문을 돌면서 기다린다.

---

Semaphores

추상자료형

• 추상적 자료형은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것이다. 추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다.
• 기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것
• 사용 설명서와 같다.
  선풍기의 사용 설명서를 본다고 가정하자. 사용 설명서에는 정지, 미풍, 약풍, 강풍, 회전, 타이머등의 기능 설명과 사용 방법이 나와있다. 하지만 버튼을 눌렀을 때 선풍기 내부회로에서 어떤 일이 발생하는지에 대해서는 전혀 나와있지 않다. 추상 자료형은 선풍기의 사용 설명서와 같이 기능과 사용 방법을 정의한 것이다.

semaphore도 일종의 추상 자료형임

semaphore에 의해 정의되는 연산은 P연산, V연산이 있다.

• P연산은 semaphore 값(그러니깐 공유데이터..!)을 획득하는 과정이고,
• V연산은 다 사용하고나서 반납하는 과정이라고 생각하면 된다.

위의 두개의 atomic 연산에 의해서 Semaphore자원에 접근이 가능하다.

atomic 연산이란?

• 처리 중간에 다른 것이 끼어들 여지를 주지 않음
• “반쯤 했다.”라는 것은 없고, 단지 “했다”와 “안했다”만 존재하는 연산

Semaphore는 정수값을 가질 수 있는데, 그게 자원의 개수라고 생각하면 됨.

만약 semaphore 자원(예를들면 공유데이터)을 여러개 가지고 있으면,
P연산을 하게 되면 자원을 하나 가져가서 사용하게 된다.
v연산을 하게되면 자원을 다 사용하고 나서 내어놓는것!

위에서 말한 lock을 잠그고 푸는 경우는 semaphore의 자원이 1개일때를 생각하면됨

• 위 방식은 busy-waiting의 방식이고 이는 효율적이지 못하다.

semaphore의 방식은 busy-waiting(=spin lock)뿐 아니라
block & wakeup(= sleep lock) 방식으로 구현 할 수 있다.

block & wakeup implementation

• semaphore를
  
  이렇게 정의할 수 있다.
  semaphore를 기다리는 프로세스들을 L이라는 queue에 담아놓는거임!

• block과 wakeup을 다음과 같이 가정할 수 있음
  - block : 커널은 block을 호출한 프로세스를 suspend 시킨다. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
  - wakeup (P) : block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮긴다.

이런식으로!!

구체적인 구현방식

block & wakeup 방식

P

P연산은 자원을 획득하는 연산인데,
자원의 여분이 있다면 바로 획득하지만, 자원의 여분이없다면 block상태가 된다.

S

자원을 반납하는 연산인데,
반납할 때 이 자원을 기다리면서 잠들어있는 프로세스가 있다면 깨워준다!

여기서 주의할 게 V연산의 IF문을 보면 s.value가 0 이하인 조건을 체크하는 이유가, v연산을 종료하고 s.value++를 해줬는데도 s.value가 0 이하라면 대기중인 프로세스가 있다는 것을 의미함!!

그럼 뭐가더나은가?

• busy waiting과 block & wakeup

보통은 block & wakeup을 쓰는게 더 효율적이다.

critical section의 길이가 긴 경우는 block/wakeup이 적당하고, 길이가 짧은경우에는 block/wakeup의 오버헤드가 busy-waiting오버헤드보다 더 커질수 있다

semaphore를 두가지타입으로 나눌수 있다

• Counting semaphore
  - 도메인이 0 이상인 임의의 정수값
  - 주로 resouce counting에 사용

• Binary semaphore
  - 0또는 1 값만 가질 수 있는 semaphore
  - 주로 lock/unlock에 사용

semaphore를 사용할 때 발생할 수 있는 문제

• Deadlock
  둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 위와 같은 문제를 만나지 않으려면
  프로세스가 semaphore를 얻는 순서를 동일하게 만들어주면됨!
  (S - Q 순서대로 얻게하기!)
  
• Starvation
  프로세스가 suspend된 이후에 semaphore 큐에서 빠져나갈 수 없는 현상