[week08] KOCW 운영체제(반효경교수님) - Process Synchronization 1

Process Synchronization 1

데이터의 접근

data가 있는 위치에서 읽어와서 연산을 수행하고 다시 그 위치에 연산결과를 저장한다.

data를 읽기만 하면 문제가 없다. 하지만, data를 읽어서 수정을 하고 결과를 저장하는 방식에서는 누가 먼저 읽어갔는지에 따라 결과가 달라질 수 있다.

Race Condition

여러 주체가 하나의 data를 동시에 접근하려고 할 때 race condition이 발생할 수 있다.

→ 조율해주는 방식이 필요하다.

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

프로세스간에서는 자원을 공유하지 않기 때문에 보통 발생하지 않는다(User mode에서는 별로 안생김).

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

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

P(A)가 count를 올리고, P(B)도 count를 올림 →밑에서 증가한count는 무시됨

해결책:

커널 모드에 있을 때는 할당 시간이 끝나도 CPU를 preempt당하지 않도록 함

3. Multiprocessor에서 shared memory 내의 kernel data

Process Synchronization 문제

공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치(inconsistency) 문제를 발생시킬 수 있다.

일관성(consistency) 유지를 위해서는 협력 프로세스간의 실행 순서(orderly execution)를 정의해주는 메커니즘이 필요함

Race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 함

고급언어의 한 문장의 코드는 여러 instruction으로 나뉘어서 실행되기 때문에 발생함을 보여주고 있다.

The Critical-Section Problem

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

critical section: 공유 데이터를 접근하는 코드

Initial Attempts to Solve Problem

critical section을 파란색으로 감싸고(나만 쓰도록 락을 걸고,다 쓰고 풀고) 나머지 수행

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

Mutual Exclusion(상호 배제)

• 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.

Progress

• critical section에 아무도 없으면 들어가게 해줘야 함

Bounded Waiting(유한 대기)

• 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

Semaphores

semaphore가 가지는 정수의 의미는 자원의 개수이다(변수값이 5라면 자원이 5개라는 의미).

변수값을 1로 초기화하면 lock을 걸고(0) lock을 풀고(1)하는데 사용할 수 있다.

atomic 연산에 의해서만 접근 가능

P연산

공유데이터를 획득하는 과정

누군가 자원을 내놓으면 그걸 획득함
자원이 없으면 while문을 돌면서 기다림(busy-wait(spin lock)문제 생김)

V연산

다 사용하고 반납하는 과정

Critical Section of n Process

• busy-wait(=spin lock) → 비효율적
• Block & Wakeup(=sleep lock) → 효율적

Block / Wakeup Implementation

프로세스를 block상태로 바꿔주고 나중에 V연산에서 자원을 반납할 때 block된(잠든) 프로세스중에 하나를 깨우는 형태(block and wakeup)

S.value는 자원의 개수를 세는 의미가 아니다. 상황을 나타낸다.

• S.value가 음수면 누군가가 자원을 기다린다는의미
• S.value가 양수면 누군가 쓰고있다는 의미
• 누군가 깨워야 할지 말지를 확인하려고 사용

일반적으로는 Block/Wakeup 방식이 더 좋다~

Two types of Semaphores

Counting semaphore

• 도메인이 0 이상인 임의의 정수값
• 주로 resource counting에 사용(자원이 여러개)

Binary Semaphore

• 0 or 1값만 가질 수 있는 semaphore
• 주로 mutual exclusion(lock/unlock)에 사용

Deadlock and Starvation

semaphore를 쓸 때 주의점

deadlock해결책 → 순서변경