[운영체제] Chapter 6. Process Synchronization (1)

[운영체제] Chapter 6. Process Synchronization (1)

2022. 12. 23. 17:00ㆍCS/운영체제

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

데이터의 접근, Race Condition, OS에서의 race condition, The Critical-Section Problem, if you preempt CPU while in kernel mode, 프로그램적 해결법의 충족조건, Peterson's Algorithm, Synchronization Hardware

1. 데이터의 접근

1-1. 데이터의 접근

(1) 데이터가 저장되어 있는 위치에서 → (2) 저장된 데이터를 읽어와서 연산 → (3) 연산한 결과를 가져온 곳에 다시 저장

데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐: process synchronization 문제 발생

1-2. Race Condition(경쟁 상황)

동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 race condition이라고 한다.
- 경쟁 상황으로부터 보호하기 위해 한순간에 하나의 프로세스만이 변수를 조작하도록 해야 한다 = 프로세스들이 동기화되어야
- 일반적인 경우라면 프로세스는 자기 주소만 접근하기 때문에 race condition과 process synchronization 관련 문제가 발생할 일이 없다.
race condition이 발생할 수 있는 상황들
- Multiprocessor system: CPU가 여러 개 있는 시스템에서 메모리를 공유하고 있다면 race condition 발생 가능
- 공유 메모리를 사용하는 프로세스들
- CPU가 1개 이더라도 커널 내부 데이터를 접근하는 루틴들 간(예. 커널모드 수행 중 인터럽트로 커널모드 다른 루틴 수행 시)
  - 프로세스가 직접 관여할 수 없어 OS에게 대행을 맡기기 위해서 시스템 콜을 하면 커널의 코드가 그 프로세스를 대신해 실행하게 된다. = 커널 데이터(프로세스의 입장에서는 공유 데이터) 접근
OS에서 Race condition은 언제 발생할까?
- kernel 수행 중 인터럽트 발생 시
  - 해결: disable interrupt 구간부터 able interrupt까지 작업이 끝날 때까지는 interrupt 처리 불가
- Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
  - 해결: 커널 모드에서 수행 중일 때는 CPU를 preempt 하지 않음, 커널 모드에서 사용자 모드로 돌아갈 때 preempt
    - 할당시간이 정확하게 지켜지지 않으며 약간의 편차는 있겠지만 real-time 시스템이 아니라 시분할 시스템이기 때문에 문제를 쉽게 해결할 수 있다.
- Multiprocessor에서 shared memeory 내의 kernel data
  - 멀티 프로세서의 경우 CPU A에서 데이터를 읽어서 수정할 때 인터럽트를 막는다 해서 CPU B가 데이터를 안 읽어가는 것은 아님 ~ CPU가 여러 개이기 때문(운영체제에 동시에 접근) → interrupt enable/disable로 해결할 수 없음
  - 해결 1) 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 lock을 걸고, 커널을 빠져나올 때 unlock
    - 커널 전체를 하나의 lock으로 걸기 때문에 비효율적이다.
  - 해결 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

1-3. Process Synchronization 문제

공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요
race condition을 막기 위해서는 동시에 실행하는 프로세스(concurrent process) 간에는 동기화(synchronize)되어야 한다.
사용자 프로세스 P1 수행 중 time interrupt가 발생해서 context switch가 일어나서 P2가 CPU를 잡으면 문제가 생길까?
- NO
- P1과 P2가 shared memory를 쓰고 있거나 YES
- P1이 커널에 있는 데이터를 수정하고 있을 때 P2에게 CPU가 넘어가면 YES

2. Critical-Section (임계 구역)

공유 데이터를 접근하는 코드인 critical section이 존재
하나의 프로세스가 critical section에 있을 때 다른 프로세스는 critical section에 들어갈 수 없어야 한다.
- P1 critical section: X = X + 1;
- P2 critical section: X = X - 1;
- P2는 P1이 critical section에 있을 때 P2의 critical section에 들어갈 수 없다.

프로세스들의 일반적 구조

do{ 
  entry section  // 진입 구역 - 임계 구역으로 진입하려면 진입 허가를 요청 lock
  critical section  //공유 데이터를 접근하는 코드
  exit section  //퇴출 구역 unlock
  remainder section  //나머지 구역
} while(1);

문제가 발생하는 이유: critical section에 들어갔다 나오는 것을 CPU를 빼앗기지 않고 한 번에 수행하면 문제가 없다. 그러나 단일 인스트럭션이 끝나면 CPU를 빼앗길 수 있는데 고급 언어의 문장들은 단일 인스트럭션이 아니기 때문에(= 원자적으로 처리되지 않기 때문에) critical section을 수행하는 도중에 CPU를 빼앗긴 수 있어서 문제가 발생한다.

2-1. Critical Section의 프로그램적 해결법의 충족 조건

Mutual Exclusion(상호 배제): 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
Progress(진행): 아무도 critical section에 있지 않은 상태에 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
Bounded Waiting(유한 대기): 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. starvation이 발생하지 않도록

2-2. SW적으로 lock을 걸고 풀 수 있는 방법 - Algorithm 1

프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다: synchronization variable (중간에 끊기지 않는다는 가정)

synchronization variable: int turn - 누가 critical section에 들어갈 차례인지를 알려주는 변수
- Pi can enter its critical section if(turn == i)
Mutual exclusion은 만족하지만 Progress는 만족하지 못한다.
- 과잉 양보: 반드시 한 번씩 교대로 들어가야만 한다(swap-turn). - Mutual exclusion은 만족 O
- 다른 프로세스가 turn을 내 값으로 바꿔줘야만 내가 들어갈 수 있다. → 아무도 critical section에 없어도 들어갈 수가 없다.
  - Progress는 만족 X
- 프로세스가 critical section에 들어가는 빈도는 균일하지 않지만 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면?

2-2. SW적으로 lock을 걸고 풀 수 있는 방법 - Algorithm 2

synchronization variable: bool flag[i] - critical section에 들어가고자 하는 의중을 표시하는 변수
- 프로세스 모두가 자신의 flag를 갖고 있고, 초기값은 flase
Mutual exclusion은 만족하지만 Progress는 만족하지 못한다.
- 프로세스가 flag[i] = true; 로 critical section에 들어가고자 하는 의사만 표시하고 CPU를 빼앗기면 flag로 의사 표시만 해놓은 상태라 모든 프로세스들이 while(flag[i])에 걸려 아무도 critical section에 진입하지 못하고 끊임 없이 양보하는 상황이 발생 가능하다. → Mutual exclusion 만족 O, Progress 만족 X

2-3. SW적으로 lock을 걸고 풀 수 있는 방법 - Algorithm 3 (Peterson’s Algorithm)

synchronization variable: int turn과 bool flag[i] 모두 사용
- critical section에 들어가는 차례를 turn으로 표시하고 상대방으로 turn을 변경해서 progress를 만족
- 프로세스 모두가 자신의 flag를 갖고 있고, 초기값은 flase
Mutual exclusion, Progress, Bounded Waiting 모두 만족
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 프로세스들은 그들의 critical section에 들어가면 안 된다를 만족한다.
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다를 만족한다.
- while(flag[j] && turn == j)와 flag값의 변경으로 Pi가 지난번에 진입했다면 이번에는 자기도 한번은(대기 시간이 한없이 길어지지 않음) 들어갈 수 있어 bounded waiting을 만족한다.
계속 CPU와 메모리를 쓰면서 wait 하는 Busy Waiting(= spin lock) 문제점 발생
- spin lock: while문을 돌면서 lock을 걸어서 상대가 못 들어가게 하는 방법
- 어떤 프로세스가 이미 critical section에 들어가 있는 상태에서 다른 프로세스가 CPU를 잡으면
  → 그 프로세스는 본인이 할당된 시간 동안 계속 while문을 계속 돌면서 체크하지만 본인 스스로 while문을 빠져나갈 수 없다.
  - while문을 빠져나가서 critical section으로 진입하기 위해서는 critical section에 진입해있는 CPU에서 조건을 바꿔줘야(= flag[i] = false;) 한다.
- 비효율적인 방법이다.
- 이러한 문제가 발생하는 이유는 고급 언어의 요청 한 줄은 여러 개의 CPU 인스트럭션으로 구성되어 있고, 고급 언어의 요청을 수행하는 중(= 하나의 인스트럭션을 끝내 면)에 CPU를 빼앗길 수 있기 때문이다.

2-4. 동기화를 위한 하드웨어 지원 - Test & Set: Synchronization Hardware

하드웨어적으로 Test & modifiy를 atomic(원자적으로) 하게 수행할 수 있도록 지원하는 경우 앞의 문제(= 수행 중에 커널에서 CPU를 빼앗기는 )는 간단히 해결할 수 있다.
- 원자적으로 수행: 만일 두 개의 test_and_set() 명령어 가 동시에 실행된다면(각각 다른 코어에서), 이들은 어떤 임의의 순서로 순차적으로 실행될 것이다.
synchronization 문제가 발생하는 이유는
- 데이터를 읽고 쓰는 것을 하나의 인스트럭션으로 처리할 수 없기 때문에 문제가 발생한다.
- 데이터를 메모리에서 읽으면서 동시에 쓰는 것을 하나의 인스트럭션으로 실행이 가능하다면
  → 적어도 인스트럭션 하나가 실행되는 도중 CPU를 빼앗기진 않는다.

bool lock = false; //Synchronization variable

//Process Pi
do{
	while(Test_and_Set(lock));    
	//누가 이미 lock을 걸었는지 확인하고, 걸지 않았다면 내가 lock을 걸고 critical section에 진입
	critical section
	lock = false;    //lock 풀기
	remainder section
}

Test_and_Set(lock);
1. 누가 이미 lock을 걸었는지를 check 하고(값을 읽고)
2. lock을 걸지 않았다면 내가 lock을 걸고 critical section에 들어가는 작업(값을 세팅)
- 을 Test_and_Set 인스트럭션으로 (값을 읽고, 세팅을) 동시에 확인할 수 있음
- lock == 0 이면 while을 벗어나 critical section에 바로 들어가고
- lock == 1 이면 누군가가 이미 critical section에 들어가 있다는 것이고, 이는 Test_and_Set을 통해 읽으면 1이 읽혀 while문을 계속 돌고 있음

[복습]

Race Condition(경쟁 상황): 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
- Multiprocessor system
- 공유 메모리를 사용하는 프로세스들
- 커널 내부 데이터를 접근하는 루틴들 간
OS에서 Race condition 발생
- kernel 수행 중 인터럽트 발생 시 : disable interrupt 구간부터 able interrupt까지 작업이 끝날 때까지는 interrupt 처리 불가
- Process가 시스템 콜하여 kernel mode로 수행 중일 때 context switch가 일어나는 경우: 커널 모드에서 수행 중일 때는 CPU를 선점하지 않음
- Multiprocessor에서 shared memory 내의 kernel data: 커널 내부의 공유 데이터에 접근할 때마다 그 데이터에 대한 lock을 거는 방법
Process Synchronization 문제: 공유 데이터에 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다. 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하다.
Critical Section: 공유 데이터를 접근하는 코드, 하나의 프로세스가 critical section에 있을 때 다른 프로세스는 critical section에 들어갈 수 없어야 한다. critical section을 수행하는 도중에 CPU를 빼앗긴다면 문제가 발생한다.
Critical Section의 프로그램적 해결법의 충족 조건
- Mutual Exclusion
- Progress
- Bounded Waiting
Peterson's Algorithm: critical section에 들어갈 차례인 turn 변수와 critical section에 들어가고자 하는 의사인 flag를 모두사용하고, turn = j; while(flag[j] && turn == j)를 통해 Mutual exclusion, progress, bounded waiting 모두 만족한다.
1. 그러나 while문을 돌며 critical section 진입 여부를 확인하기 때문에 계속 CPU와 메모리를 사용하며 wait: Busy Waiting 발생
Test & Set: 데이터를 메모리에 읽으면서 동시에 쓰는 것을 하나의 인스트럭션으로 실행하여 하드웨어적으로 Test & modify를 atomic 하게 수행할 수 있도록 지원한다.

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

[Operation System Comcepts] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f

반효경 [운영체제] 11. CPU Scheduling 2 / Process Synchronization 1

설명이 없습니다.

core.ewha.ac.kr

https://core.ewha.ac.kr/publicview/C0101020140404144354492628?vmode=f

반효경 [운영체제] 12. Process Synchronization 1