Review 운영체제 4 일차

(1)

운영체제 4일차 Review

시형준 jamess90@naver.com 2015. 01. 20

(2)

운영체제(OS)

(3)

프로세스 동기화

• 다중 프로그래밍 시스템에서 여러 프로세스들이 동시에 독 립적으로 진행됨으로 인하여 발생하는 문제점들을 해결하 는 기법

• 이들은 상호 독립적으로 움직임

• 대부분 이러한 문제는 자원에 대한 접근이나 공유 데이터 에 대한 접근 시에 발생

• 커널 내에서 해결하여야 함

(4)

기계어 명령의 특성

• 기계어 명령(machine instruction)

• 원자성(atomicity), 분리불가능 (indivisible)

-> 한 기계어 명령의 실행 도중에 인터럽트 받지 않음

(5)

상호 배제

• 공유 데이터(shared data, critical data)

• 여러 프로세스들에 의해 공동으로 사용되는 데이터

• 임계 지역 (critical section)

• 공유 데이터에 접근하는 프로그램 세그먼트

• 상호 배제 (mutual exclusion)

• 둘 이상 프로세스의 임계 지역 동시 진입을 금지시킴

(6)

상호 배제 프리미티브

• enterCS() 프리미티브

• 임계 지역 진입 전 검사과정

• 다른 프로세스가 임계 지역 내에 존재하는지의 여부 검사

• exitCS() 프리미티브

• 임계 지역 벗어날 경우 처리 과정

• 임계 지역에서 벗어났음을 시스템에 알림

(7)

Dekker의 알고리즘

• 최초의 상호 배제 알고리즘

(8)

Peterson의 알고리즘

• 1981년에 고안된 알고리즘

• 보다 간단한 상호 배제 알고리즘

(9)

N-프로세스 상호배제

• Dijkstra 알고리즘

• 무기한 연기의 가능성이 있음

• Knuth 알고리즘

• 무기한 연기의 가능성을 제거

• 지연 시간이 매우 큼

• Eisenberg 와 McGuire 알고리즘

• 유한 시간 (n-1 번) 내의 시도 후 임계 지역 진입 보장

• Lamport 알고리즘

• 분산 시스템 환경을 위한 상호 배제 기법

(10)

하드웨어적 상호 배제 해결법

• 상호 배제를 위한 소프트웨어적 해결 기법들의 문제

• 실행 시간이 오래 걸림

• 프리미티브 실행중 블록 될 가능성 존재함

• 상호 배제를 위한 하드웨어적 방법의 예

• IBM의 TS(Test and Set) 명령 (기계어 명령)

• 원자성, 분리불가능의 특성 가짐

(11)

TS명령이란?

• TS(a, b)

a  b;

b  true;

• 두 번째 인자인 b의 값을 첫 번째 인자인 a로 복사 하면서

• 동시에 b의 값을 true로 설정함

(12)

• 상기의 각종 상호 배제 기법들의 단점

• busy waiting

• 비효율적임

• busy waiting 방지하는 상호 배제 기법들

• 세마포어(semaphore) 사용 기법

• Sequencer / eventcount 사용 기법

임계 지역에 즉시 진입할 수 없는 프로세스들을 대기 상태로 전이시킴