• 스터디 설명 : 에이블스쿨 교육생들과 CS 공부를 위해 자발적으로 개설 및 참여한 스터디입니다.
• 혼자 공부하는 컴퓨터 구조+운영체제를 교재로 사용하였고, 일부 내용은 별도의 자료로 공부하였습니다.

동기화란

• 동시다발적으로 실행되는 프로세스는 실행 순서와 자원의 일관성을 보장해야하기에 반드시 동기화(synchronization)가 이루어져야 한다.

동기화의 의미

• 정보통신 분야에서 동기화란 ‘작업들 사이의 수행시기를 맞추는 것’을 의미한다. 즉 프로세스 동기화는 프로세스 사이의 수행 시기를 맞추는 것이다. (프로세스 뿐만 아니라 실행의 흐름을 갖는 모든 것이 동기화 대상)
  • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행
  • 상호 배제 : 동시에 접근해서 안되는 자원에 하나의 프로세스만 접근하도록 하기
• 실행 순서 제어를 위한 동기화
  • write가 해당 파일을 생성하기도 전에 read process가 파일을 읽을 수 없다.
  • 즉, write → read 순으로 실행되도록 해야한다.
• 상호 배제를 위한 동기화
  • 동일한 파일에 대해 한 프로세스는 read, 한 프로세스는 write를 할 때, read 프로세스의 실행 중간에 write 프로세스가 새로운 내용을 써버리면, 비일관적 데이터를 사용하게 된다. (생산자와 소비자 문제)
  • 같은 파일에서 값을 읽어와 정해진 연산을 하여 파일에 새로 기록하는 두 프로세스도 마찬가지인데, 원래라면 10 → 12 → 17이 되어야할 파일값에서 두 프로세스가 동시의 10을 읽는다면 10 → 15 → 12와 같이 엉망으로 저장될 수 있다.
  • 이럴 때 상호 배제가 필요하다

공유 자원과 임계 구역

• 동시에 실행되는 서로 다른 프로세스가 같은 자원을 사용할 경우, 이러한 자원을 공유 자원이라고 한다. 공유 자원은 전역 변수, 파일, 보조기억장치든 프로세스가 사용하는 모든것이 될 수 있다.
• 공유 자원 영역 서로 다른 프로세스가 동시에 실행하면 문제가 발생할 수 있는 코드 영역을 임계 구역(critical section)이라고 한다.
  • 운영체제는 임계 구역을 설정함을 통해서 동시에 실행되지 않음을 보장한다.
• 임계 구역에 이미 진입한 프로세스가 있을 경우, 해당 프로세스의 작업이 마무리 된 후에 진입할 수 있어야 한다. 만약 이것이 잘못되어 여러 프로세스가 동시 다발적으로 임계 구역 코드를 실행하게 되는 상황을 레이스 컨디션이라고 한다.
  • 레이스 컨디션이 발생하면 데이터의 일관성이 깨지게 된다.
• 레이스 컨디션이 발생하는 근본적인 이유는, 고급 언어에서 한 줄로 작성된 코드라도, 저급 언어 단계에서는 여러 과정을 거치기 때문이다.
  • 소스코드에서는 한 줄이 수행되고 다음 줄에 수행되는 것처럼 보이는 코드라도, 저급언어로 변환되었을 때는 순서가 꼬일 수 있다.
• 상호 배제 동기화의 원칙은 다음과 같다.
  • 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 진입했다면, 다른 프로세스는 진입할 수 없음
  • 진행(progress) : 빈 임계 구역에는 새 프로세스가 진입할 수 있음
  • 유한 대기(bounded waiting) : 임계 구역에 진입하고자 하는 프로세스는 언젠가는 임계 구역에 진입할 수 있어야 함

동기화 기법

뮤텍스 락(Mutex lock)

• 뮤텍스 락은 상호 배제를 위한 동기화 도구이다.
• 임계 구역에 진입하는 프로세스는 뮤텍스 락을 이용해 일종의 자물쇠를 걸어두어 다른 프로세스의 임계 구역 접근을 막는다.
• 뮤텍스 락의 가장 단순한 형태는 전역 변수 1개와 두 개의 함수로 구현할 수 있다.
  • 전역 변수 lock : True, False로 임계구역의 잠금 여부 표시
  • 함수 acquire : 임계 구역을 잠그는 역할
    • 프로세스가 임계 구역에 진입하기 전에 호출
    • lock이 False가 될 때까지 임계 구역을 반복적으로 확인하고, False임을 확인하면 임계구역으로 진입하면서 lock을 True로 바꾼다.
  • 함수 release : 임계 구역 잠금을 해제하는 역할
    • 작업이 끝났을 때 lock을 False로 바꾼다.
  • 이 경우 프로세스는 lock이 False가 될 때까지 계속 lock 변수를 확인해야한다. 이러한 대기 방식을 바쁜 대기(busy wait)이라 한다.

데커(Dekker) 알고리즘

• 뮤텍스 알고리즘 중 하나로, flag와 turn변수 통해 임계구역에 들어갈 프로세스/스레드를 결정
  • flag: 각 프로세스 별로 현재 진입중인지를 나타내는 변수
  • turn : 현재 어떤 프로세스가 사용중인지를 나타내는 변수 (전역)

1. i 프로세스가 flag[i] = true로 변환하고 진입을 시도
2. if turn == j 라면 flag[i] = false로 변경하여 진입 취소
3. while turn == j 를 통해 turn이 j에서 변경될 때까지 대기
4. 변경이 되면 flag[i] = true로 다시 진입시도
5. 임계 구역 사용
6. 임계 구역 사용 후 turn = j로 j에게 다음 턴이 되었음을 알림
7. flag[i] = false로 사용 완료 표시

피터슨(Peterson) 알고리즘

• 데커와 유사하지만 다른 프로세스/스레드에게 진입 기회를 먼저 양보한다는 차이가 있다.

1. i 프로세스가 flag[i] = true로 변환하고 진입을 시도
2. turn = j 로 j에게 턴을 먼저 양보
3. if flag[j] && turn==j : j 프로세스가 진입해있다면 풀릴때까지 대기
4. 임계 구역 사용
5. flag[i] = false로 사용완료 표시

제과점(Bakery) 알고리즘

• 2개 이상의 여러 프로세스에 대해 적용할 수 있는 알고리즘으로, 일종의 번호표를 사용한다.
  • 번호표(number[i])는 임계 구역을 사용하지 않는다면 0(false 역할)이고, 번호표를 받는다면 양수가 된다.

1. isReady[i] = true : 번호표 수령 대기
2. number[i] = max(number[0:n]) + 1 : 현재 받을 수 있는 번호표 중 가장 큰 번호를 받음
3. 모든 프로세스 번호에 대해 반복문을 돔 (for j = 0; j < n; j++)
   1. while isReady[j] : j가 번호표를 받지 않은 상태라면 받을때까지 확인

세마포(semaphore)

• 공유 자원이 2개 이상 있을 경우 여러 개의 프로세스가 각각 공유 자원에 접근이 가능해야 한다. (각 공유 자원에 하나의 프로세스만 진입 가능한 경우도 마찬가지)
  • 그 중에서도 공유 자원이 2개이면서, 각 공유 자원에 하나의 프로세스에만 진입 가능한 경우를 ‘이진 세마포’라고 하는데, 뮤텍스 락도 이진 세마포 기법 중 하나이다.
• 세마포도 뮤텍스 락과 비슷하게 전역 변수 1개, 함수 2개로 구현이 가능하다.
  • 전역 변수 S : 현재 접근 가능한 프로세스 수 명시
  • 함수 wait : 임계 구역에 진입할 수 있는지, 기다려야 하는지 명시하는 함수
    • S의 값이 0이라면 S가 1 이상이 될 떄까지 반복적으로 확인한다.
    • S가 1 이상이라면 S를 1 감소 시키고 임계 구역에 진입한다.
  • 함수 signal : 대기 중인 프로세스에 임계 구역에 진입해도 된다는 signal을 주는 함수
    • 작업을 종료할 때 호출하여 S를 1 증가시킨다.
  • 앞서 뮤텍스 락과 마찬가지로 바쁜 대기를 해야하는데, 이를 해소하기 위해 wait 함수에서 S == 0일 경우 프로세스의 PCB를 대기 큐에 넣고, 다른 프로세스가 signal 함수를 호출할 때, signal 함수에서 대기 큐의 PCB를 꺼내서 준비 큐로 옮겨주는 작업을 한다.

# wait 예제
wait() {
	S--; # 우선 S를 1 감소시킴
	if (S < 0) {
		add this process to Queue; # 대기 큐에 프로세스 추가
		sleep(); # 대기 상태 진입
	}
}

# signal 예제
signal() {
	S++;
	# 현재 대기중인 프로세스가 있다는 것을 S 값을 통해 확인 (1이상이면 wait없이 진입하므로)
	if (S<=0) {
		remove a process p from Queue # 대기 큐에 있는 프로세스를 꺼냄
		wakeup(p) # 꺼낸 프로세스를 준비상태로 변경
	}
}

• 지금까지는 상호 배제를 위한 동기화였지만, 세마포를 통해 실행 순서 제어를 위한 동기화 역시 가능하다.
  • 세마포의 변수를 0으로 두고, 먼저 실행할 프로세스 뒤에 signal 함수를, 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 된다.
  • 먼저 실행된 프로세스가 종료되면 signal 함수를 통해 대기 중인 프로세스가 있다는 것을 확인(S=0)하고 대기 큐에있는 다음 프로세스를 꺼내 준비상태로 변경한다.
  • 만약 다음 프로세스가 먼저 실행되더라도 S=-1이 되어 실행되지 않고 대기 큐에 들어가게 된다.

모니터 (monitor)

• 세마포의 단점은 매번 임계 구역 앞 뒤로 wait과 signal 함수를 명시해야 하며, 코드가 방대해지는 과정에서 순서가 잘못되거나 중복 실행될 경우 예기치 못한 결과가 발생할 수 있다.
• 이를 보완하기 위해 사용자 기준에서 훨씬 편리한 방법인 모니터 동기화 도구를 사용하게 되었다.

• 모니터는 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리한다.
  • 프로세스는 오직 인터페이스를 통해서만 공유 자원에 접근할 수 있다.
  • 모니터는 공유 자원 인터페이스에 접근하기 위한 큐를 이용하여 모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 위한 동기화를 제공한다.
• 모니터도 실행 순서 제어를 위한 동기화를 제공하는데, 이를 위해 조건 변수라는 특별한 변수를 사용한다. (프로세스 수행이나 일시 중단 등을 판단)
  • 조건 변수를 통해 wait과 signal 연산을 수행할 수 있다.
    • wait : 호출한 프로세스의 상태를 대기 상태로 전환하고, 조건 변수에 대한 대기 큐에 삽입 (상호 배제를 위한 큐와 다른 큐 → 실행 조건이 만족될 때 까지 일시 대기)
    • signal : wait 연산으로 일시 중지된 프로세스를 재개하는 연산 (중단된 프로세스와 다른 프로세스에 의해 실행 됨)
      하나의 모니터 안에는 하나의 프로세스만 있을 수 있으므로, signal을 호출한 프로세스가 모니터를 떠난 뒤 실행되거나, 일시 중단 된 후 실행된다.