운영체제 강의 정리3

배추·2023년 4월 24일

운영체제

목록 보기

3/4

OS에서 Race condition이 발생하는 경우

kernel 수행 중 interrupt 발생 시
Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

1, 2의 경우, kernel의 값을 register로 읽어와서 변경한 후 memory에 저장하려 할 때 같은 일을 수행하는 interrupt가 발생하면 interrupt된 명령은 반영되지 않는 현상이 발생

해결책: 커널 모드에서 수행 중일 때는 preempt를 하지 않고 커널 모드에서 사용자 모드로 돌아갈 때 preempt를 한다.

Multiprocessor에서 shared memory 내의 kernel data

(방법 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법-비효율적
(방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법

Critical-Section Problem

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우, 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

Critical-Section 해결법의 충족 조건

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

Busy-wait vs Block/Wakeup

Critical section의 길이가 긴 경우 Block/Wakeup이 적당
Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
일반적으로는 Block/Wakeup 방식이 더 좋음

Semaphores

추상 자료형

Counting semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting에 사용
Binary semaphore(=mutex)
- 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion (lock/unlock)에 사용

Monitor

모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 Condition variable 사용
Condition variable은 wait와 signal 연산에 의해서만 접근 가능
등장배경: Semaphore의 문제
- 코딩하기 힘듬
- 정확성(correctness)의 입증이 어려움
- 자발적 협력(voluntary cooperation)이 필요
- 한번의 실수가 모든 시스템에 치명적 영향

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

Deadlock 발생의 4가지 조건

Deadlock이 생기기 위해선 4가지가 모두 만족 되어야 한다.

Mutual exclusion(상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
No preemption(비선점)
- 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
Hold and wait(보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
Circular wait(환형 대기)
- 자원을 기다리는 프로세스간에 사이클이 형성

Deadlock 처리 방법

Deadlock Prevention
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

Utilization 저하, throughput 감소, starvation 문제 발생 가능

Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

ex) Resource-Allocation Graph Scheme, Banker's Algorithm

Deadlock Detection and recovery
- Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

Recovery 방법

Proess termination

Deadlocked된 모든 프로세스 Abort

Deadlock cycle에 연관된 프로세스를 한개씩 Abort

Resource Preemption

비용을 최소화할 victim 선정

Safe state로 rollback하여 process를 restart

Starvation 발생 가능

동일한 프로세스가 계속해서 victim으로 선정되는 경우 cost factor에 rollback 횟수도 같이 고려