KOCW.이화여자대학교.반효경.운영체제
위 강의를 바탕으로 학습 및 정리했습니다

---

Process Synchronization

데이터의 접근

• 데이터 읽기 -> 연산 -> 데이터 저장 및 사용

Race Condition

• Shared memory를 써야만 할 때 중간에 CPU가 뺐기더라도 문제가 생기지 않게 코딩해야함
  -> Process Synchronization와 관련된 테크닉

OS에서의 Race Condition

시스템 콜

• 예를 들어, 커널의 데이터를 건드리는 와중에 CPU가 다른 프로세스에 넘어가면 Race Condition 발생할 수도 있음

• 예)

1. 프로세스 A가 커널모드로 count를 1 증가 시키려는 와중에 context Switch가 일어남
2. 공교롭게 프로세스 B도 커널 모드로 같은 동작을 수행 (count + 1)
3. 프로세스 A가 CPU 다시 잡으면서 저장됐던 직전의 상태를 복원
4. 복원하면서 2.에서 커널 모드로 수행했던 count + 1 이전의 상태로 복원됨

-> 프로세스 B가 수행했던 처리가 씹힌거임
-> 결과적으로 프로세스 A가 수행한 커널 모드 count + 1만 반영되는 문제 발생
따라서 커널모드 수행 중일땐 CPU 안뺏음으로써 해결

인터럽트

• 여기서도 count값을 인터럽트 당하기 전의 값을 불러들여서 계산해버려서 원하지 않은 값을 저장

-> 이것도 커널의 공유데이터를 건드리기 전에 인터럽트를 disable 시키고 그 작업이 끝나면 수용하는 방법을 사용

multiprocessor

• 한 CPU가 운영체제를 사용하고 있으면 다른 CPU가 운영체제를 사용하지 못하게 하면 Race condition 해결 가능
  -> 근데 overhead 발생 (여러 CPU가 유저모드/커널모드 를 왔다갔다 해야하는데 커널 모드를 한 CPU만 가야하는 상황)

따라서, 운영체제 전체를 막는 것이 아니라 공유데이터 각각을 막으면 됨 == Lock / Unlock

정리

• OS에서 Race Condition 은 언제 발생하는가?

1. kernel 수행 중 인터럽트 발생시

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

3. Multiprocessor 에서 shared memory 내의 kernel data 동시 사용

Process Synchronization 문제

• chared data의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생 시킴
  -> 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment의 공유데이터를 접근 하는 코드를 Critical Section이라 함

하나의 프로세스가 Critical Section에 있을 때 다른 모든 프로세스는 Critical Section에 들어갈 수 없어야 함!!!

The Critical-Section Problem

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

Initial Attempts to solve Problem

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

• 들어갈 때 / 빠져나갈 때 코드를 추가 해서 동시에 들어가지 못하게 해야함

프로그램적 해결법의 충족 조건

• 기다리는 시간이 유한해야 함

해결 알고리즘 1

• critical section 에 들어가려는 P0(turn = 0)와 P1(turn = 1)이 있다 가정

• turn 이라는 Synchronization Variable으로 누가 누군지 구별

• critical section 에 나갈 때 turn = 1 처럼 상대방이 들어갈 수 있게 바꿔줌

• 둘이 동시에 들어가지 않는건 확실히 보장
  BUT, turn을 내 값으로 바꿔줄 때까지 못들어감 -> 불합리함, 기다리는 P1이 P0보다 더 critical section을 많이 들어가는 프로세스라면?

• 또한 critical section을 원하든 원하지 않든 무조건 번갈아 들어감

• 아무도 안들어가 있을 때도 못들어감

해결 알고리즘 2

• flag 이용
  • 자신이 critical section 에 들어가고 싶다 신호 보냄
  • 다른 프로세스도 flag 들고 있는지 확인
  • critical section 에서 나올 때 flag = False 깃발 내림
• 동시에 들어가는 문제는 이 알고리즘도 해결됨
  • 남의 깃발 들어져 있으면 안들어가니까
• 근데 여기도 아무도 critical section에 있지 않아도 들어가지 못하는 문제 발생
  • 다른 프로세스가 첫줄의 flag[i] = true 한다음에 CPU 뺏기면 계속 flag가 들어져 있는 상태가 되어서 버그 발생
    -> 이 알고리즘도 진행이 안됨

해결 알고리즘 3

• flag == True 면 turn 적용
• 동작은 제대로 하는 데 비효율적임
  • spin lock 라고도 불림
  • 계속 CPU와 memory 쓰면서 wait

Synchronization Hardware

• 이 문제는 하드웨어적 지원이 있으면 매우 쉽게 풀림
  
  • 중간에 CPU 안 뺏기기 + 읽는거랑 데이터 바꾸는걸 한번에 하면 문제 안생김

Semaphore

• 추상 자료형

• Semaphore S

  • 정수 변수
  • 연산은 P / V 두가지
  • P : 자원을 획득하는 과정
  • V : 자원을 반납하는 과정
    

• 공유 자원을 카운팅하고 관리 하기위해 사용

• 어떻게 구현되는지는 몰라도 됨
  

• P연산의 while 문 (spin lock 방식의) -> busy-wait 문제 발생
  -> 따라서 Block & wake up (sleep lock) 방식으로 구현
  

  

그럼 뭐가 더 좋은가

Semaphore 2가지 타입

• Counting semaphore
  • 자원의 수를 세서 1이상의 값을 갖는
• Binary semaphore
  • lock/unlock 표현으로 값을 0/1로 갖는

Monitor