Microsoft PowerPoint - StallingsOS6e-Chap06.ppt [호환 모드]

Size: px

Start display at page:

Download "Microsoft PowerPoint - StallingsOS6e-Chap06.ppt [호환 모드]"

상욱 노
5 years ago
Views:

1 6 장병행성 : 교착상태와기아 6 장의강의목표 교착상태 (deadlock) 의원리를이해한다. 교착상태에자원할당그래프가어떻게이용되는지이해한다. 교착상태가발생하기위한필요. 충분조건을이해한다. 교착상태예방기법들을이해한다. 교착상태회피기법들을이해한다. 교착상태의발견과복구기법들을이해한다. 식사하는철학자문제를이해하고해결방법을이해한다. UNIX, LINUX, Solaris, Windows 운영체제에서제공하는병행성기법들을이해한다. 병행성 : 교착상태와기아 2

2 6.1 교착상태원리 6.2 교착상태예방 6.3 교착상태회피 6.4 교착상태발견 통합교착상태전략 6.6 식사하는철학자문제 6.7 유닉스병행성기법 6.8 리눅스커널병행성기법 목차 6.9 솔라리스스레드동기화프리미티브 윈도우즈병행성기법 병행성 : 교착상태와기아 교착상태원리 (deadlock principles) 교착상태예 /* DeadLock example.c */ #include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> int a[4] = {150,100,200,50}; int b[4] = {1, 1, 2, 0}; // account // credit status 상호배제를위해 5 장에서배운기법을사용하면.. 이때발생하는문제는? void *func1() { int tmp1, tmp2; // deposit void *func2() { int tmp1, tmp2; // credit evaluation } // pre processing entercritical(a) t ca tmp1 = a[1]; tmp1 = tmp1 + 10; if (tmp1 > 200) { entercritical(b) tmp2 = b[1]; tmp2 += 1; b[1] = tmp2; exitcritical(b) } a[1] = tmp; exitcritical(a) // post processing } // pre processing entercritical(b) tmp2 = b[1]; if (tmp2 >= 2) { entercritical(a) tmp1 = a[1]; tmp1 = tmp1 * 0.05; 05 a[1] = tmp1; exitcritical(a) } exitcritical(b) // post processing 병행성 : 교착상태와기아 4

3 6.1 교착상태의원리 교착상태의정의 영속적인블록상태 2 개이상의프로세스들이공유자원에대한경쟁이나통신중에발생 사거리에서의교착상태예 병행성 : 교착상태와기아 교착상태의원리 결합진행다이어그램 다음과같이실행하는두프로세스 P 와 Q 가있다면, 둘다자원 A 와 B 에대해배타적사용을원하고있음 단, 자원사용기간은유한함. 병행성 : 교착상태와기아 6

4 6.1 교착상태의원리 결합진행다이어그램 ( 계속 ) 교착상태를쉽게이해하기위한결합진행다이어그램예 병행성 : 교착상태와기아 교착상태의원리결합진행다이어그램 : alternative 교착상태가발생하지않는예 병행성 : 교착상태와기아 8

6.1 교착상태의원리 재사용가능자원 (reusable) 프로세스가사용했다고없어지지는않는자원 사용후반납해야함.

프로세스가한자원을갖고있으면서다른자원을요구하면교착상태가발생할수있음 예 메모리할당 ( 가용메모리크기 = 200Kbytes)

Request 70Kbytes Request 80Kbytes 병행성 : 교착상태와기아 9 6.

시그널, 메시지, I/O 버퍼에있는정보 메시지수신이 blocking 방식으로이루어지면교착상태가발생할수있음 예 :

5 6.1 교착상태의원리 재사용가능자원 (reusable) 프로세스가사용했다고없어지지는않는자원 사용후반납해야함. 예: 처리기, I/O channels, 주 / 보조메모리, 장치, 커널자료구조 ( 파일, 데이터베이스, 세마포어등 ) 프로세스가한자원을갖고있으면서다른자원을요구하면교착상태가발생할수있음 예 메모리할당 ( 가용메모리크기 = 200Kbytes) 디스크와테이프를이용한백업 P1 // 메모리할당 Request 80Kbytes Request 60Kbytes P2 Request 70Kbytes Request 80Kbytes 병행성 : 교착상태와기아 교착상태의원리 소모성자원 (consumable) 생성되었다가사용된후소멸되는자원 생산자와소비자프로세스 예 : 인터럽트, 시그널, 메시지, I/O 버퍼에있는정보 메시지수신이 blocking 방식으로이루어지면교착상태가발생할수있음 예 : 통신시발생하는교착상태 P1 // 통신 P2 Receive (P2) S d 2 1 Receive (P1) S d 1 2 Send (P2, M1) Send (P1, M2) 병행성 : 교착상태와기아 10

6 6.1 교착상태의원리 자원할당그래프 (Resource Allocation graph) 자원할당그래프예 병행성 : 교착상태와기아 교착상태의원리 자원할당그래프 (Resource Allocation graph) 교차로교착상태의 RAG 표현 Cycle 이발생하고있음 병행성 : 교착상태와기아 12

2 교착상태예방 (deadlock prevention) 교착상태예방 교착상태가발생하기위한 4 가지필요충분조건중하나를설계단계에서배제하는기법 상호배제 운영체제에서반드시보장해주어야함.

7 6.1 교착상태의원리 교착상태조건 교착상태가발생하기위한필요충분조건 4 가지 상호배제 (mutual exclusion) 점유대기 (hold and wait) 비선점 (no preemption) 환형대기 (circular wait) 교착상태가능 vs. 교착상태발생 병행성 : 교착상태와기아 교착상태예방 (deadlock prevention) 교착상태예방 교착상태가발생하기위한 4 가지필요충분조건중하나를설계단계에서배제하는기법 상호배제 운영체제에서반드시보장해주어야함. 점유대기 프로세스가필요한모든자원을한꺼번에요청 비선점 프로세스가새로운자원요청에실패하면기존의자원들을반납한후다시요청 or 운영체제가강제적으로자원을반납시킴 환형대기 자원할당순서 ( 자원유형 ) 를미리정해두면없앨수있음. 병행성 : 교착상태와기아 14

8 6.2 교착상태예방 교착상태예방의예 /* DeadLock example.c */ #include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> int a[4] = {150,100,200,50}; int b[4] = {1, 1, 2, 0}; // account // credit status void *func1() { int tmp1, tmp2; // deposit void *func2() { int tmp1, tmp2; // credit evaluation } // pre processing entercritical(a) tmp1 = a[1]; tmp1 = tmp1 + 10; if (tmp1 > 200) { entercritical(b) tmp2 = b[1]; tmp2 += 1; b[1] = tmp2; exitcritical(b) } a[1] = tmp; exitcritical(a) // post processing } // pre processing entercritical(b) tmp2 = b[1]; if (tmp2 >= 2) { entercritical(a) tmp1 = a[1]; tmp1 = tmp1 * 0.05; a[1] = tmp1; exitcritical(a) } exitcritical(b) // post processing 병행성 : 교착상태와기아 교착상태회피 (deadlock avoidance) 예방과회피의차이점 교착상태예방은자원의사용과프로세스수행에비효율성을야기할수있다. 교착상태회피기법은교착상태발생을위한 4 가지조건중 1, 2, 3을허용 자원할당순서를미리정해놓지도않음 그대신, 자원을할당할때교착상태가발생가능한상황으로진행하지않도록고려한다. 프로세스시작시요구하는자원할당이교착상태를발생시킬가능성이있으면, 프로세스를시작시키지않는다. 수행중인프로세스가요구하는추가적인자원할당이교착상태를유발할수있으면거부한다. 병행성 : 교착상태와기아 16

9 6.3 교착상태회피 시스템상태구분 안전상태 (safe state): 교착상태가발생하지않도록프로세스들에게자원을할당할수있는할당경로가존재 불안전상태 (unsafe state): 경로가없음 자원할당거부 (Resource Allocation Denial) 자원을할당할때교착상태가발생할가능성이있는지여부를동적으로판단 교착상태의가능성이없을때자원할당. 즉, 안전한상태를계속유지할수있을때에만자원할당 각프로세스들이필요한자원들을미리운영체제에게알려야함 프로세스시작거부 (Process Initialization Denial) 교착상태가발생할가능성이있으면프로세스시작거부 병행성 : 교착상태와기아 교착상태회피 Banker s Algorithm 안전상태판별과정 병행성 : 교착상태와기아 18

10 6.3 교착상태회피 Banker s Algorithm ( 계속 ) 병행성 : 교착상태와기아 교착상태회피 Banker s Algorithm ( 계속 ) 불안전상태판별예 자원할당거부 (Banker s algorithm) 프로세스시작거부 병행성 : 교착상태와기아 20

11 6.3 교착상태회피 Banker s Algorithm ( 계속 ) 은행원알고리즘구현예 병행성 : 교착상태와기아 교착상태회피 Banker s Algorithm ( 계속 ) 은행원알고리즘구현예 ( 계속 ) 병행성 : 교착상태와기아 22

12 6.4 교착상태발견 (deadlock detection) 교착상태발견알고리즘 1. 할당행렬 A에서행의값이모두 0인프로세스를우선표시한다. 2. 임시벡터 W 를만든다. 그리고현재사용가능한자원의개수 ( 결국가용벡터 V 의값 ) 를벡터W 의초기값으로설정한다. 3. 표시되지않은프로세스들중에서수행완료가능한것이있으면 ( 요청행렬 Q 에서특정행의값이모두 W 보다작은행에대응되는프로세스 ) 이프로세스를표시한다. 만일완료가능한프로세스가없으면알고리즘을종료한다. 4. 단계 3 의조건을만족하는행을 Q 에서찾으면, 할당행렬 A 에서그행에대응되는값을임시벡터 W 에더한다. 그리고 3 단계를다시수행한다. 병행성 : 교착상태와기아 교착상태발견 교착상태회복 (recovery) 알고리즘 1 교착상태관련모든프로세스종료 2 교착상태에연관된프로세스들을체크포인트시점으로롤백한후다시수행시킴 ( 교착상태가다시발생할가능성존재 ) 3 교착상태가없어질때까지교착상태에포함되어있는프로세스들하나씩종료 4 교착상태가없어질때까지교착상태에포함되어있는자원을하나씩빼앗음 5 종료 ( 또는선점될 ) 프로세스선택기준 지금까지사용한처리기시간이적은프로세스부터 지금까지생산한출력량이적은프로세스부터 이후남은수행시간이가장긴프로세스부터 할당받은자원이가장적은프로세스부터 우선순위가낮은프로세스부터 병행성 : 교착상태와기아 24

13 6.5 통합적인교착상태전략 교착상태예방, 회피, 발견 병행성 : 교착상태와기아 25 문제정의 6.6 식사하는철학자문제 철학자들은반드시포크 2개를사용해야함. 포크는여러철학자들에의해공유될수없음 (mutual exclusion) 어떤철학자도굶어죽어서는안된다. 교착상태도없어야하고, 굶어죽지도않아야한다. 병행성 : 교착상태와기아 26

14 6.6 식사하는철학자문제 세마포어를이용한해결방법 이방법에내재되어있는문제점은? 병행성 : 교착상태와기아 식사하는철학자문제세마포어를이용한다른해결방법 교착상태발생하지않는버전 한번에최대 4 명까지철학자가식탁에앉을수있게제한 병행성 : 교착상태와기아 28

15 6.6 식사하는철학자문제 모니터를이용한해결방법 병행성 : 교착상태와기아 29 유닉스병행성기법 프로세스간통신 (IPC: InterProcess Communication) 시그널 (Signal) 파이프 (Pipe) 메시지전달 (Message passing) 공유메모리 (Shared memory) 세마포어 (Semaphore) sending tasks T T T struct msqid_ds msg msg msg T T receiving tasks kernel stack heap data text shared memory kernel stack heap data text 병행성 : 교착상태와기아 30

16 유닉스병행성기법 시그널 인터럽트와유사점및차이점은? 병행성 : 교착상태와기아 31 유닉스병행성기법지원 원자적연산 리눅스병행성기법 Atomic operations execute without interruption/interference 스핀락 Only one thread at a time can acquire a spinlock. Any other thread will keep trying (spinning) until it can acquire the lock. 세마포어 Binary semaphores, counting semaphores, reader-writer semaphores 장벽 (barrier) To enforce the order in which instructions are executed 병행성 : 교착상태와기아 32

17 원자적연산 (atomic operation) 리눅스커널병행성기법 병행성 : 교착상태와기아 33 리눅스커널병행성기법 스핀락 (Spinlocks) 기본스핀락 (plain, irq, irqsave, bh), 읽기-쓰기스핀락 병행성 : 교착상태와기아 34

18 세마포어 (Semaphores) 기본세마포어 (up, down), 읽기-쓰기세마포어 리눅스커널병행성기법 병행성 : 교착상태와기아 35 장벽 (Barriers) 리눅스커널병행성기법 병행성 : 교착상태와기아 36

Solaris 스레드동기화프리미티브 상호배제 (mutex) 락 A mutex is used to ensure only one thread

The thread that locks the mutex must be the one that unlocks it 세마포어

읽기 - 쓰기락 (readers/writers lock) The readers/writer lock allows multiple

lock. 조건변수 (conditional variables) A condition variable is used to wait until

19 Solaris 스레드동기화프리미티브 상호배제 (mutex) 락 A mutex is used to ensure only one thread at a time can access the resource protected by the mutex. The thread that locks the mutex must be the one that unlocks it 세마포어 (semaphore) Solaris provides classic counting semaphores. 읽기 - 쓰기락 (readers/writers lock) The readers/writer lock allows multiple threads to have simultaneous read-only access to an object protected by the lock. 조건변수 (conditional variables) A condition variable is used to wait until a particular condition is true. Condition variables must be used with a mutex lock 병행성 : 교착상태와기아 37 구조 솔라리스스레드동기화프리미티브 병행성 : 교착상태와기아 38

20 윈도우즈커널병행성기법 객체아키텍처의일부분으로동기화기법제공 Executive 디스패처객체 ( 대기함수 (Wait functions) 사용 ) 임계영역 (Critical Section) Slim 읽기 - 쓰기락 조건변수병행성 : 교착상태와기아 39 윈도우즈커널병행성기법 대기함수 (Wait functions) The wait functions allow a thread to block its own execution. The wait functions do not return until the specified criteria have been met. 임계영역 Similar mechanism to mutex (except that critical sections can be used only by the threads of a single process. ) If the system is a multiprocessor, the code will attempt to acquire a spin-lock. Slim 읽기- 쓰기락 Windows Vista added a user mode reader-writer. Slim as it normally only requires allocation of a single pointer-sized i piece of memory. Condition Variable Windows Vista also added condition variables. Used with either critical sections or SRW locks 병행성 : 교착상태와기아 40

21 윈도우즈리눅스비교 병행성 : 교착상태와기아 41 윈도우즈리눅스비교 병행성 : 교착상태와기아 42

22 교착상태원리 교착상태 4 가지조건 자원할당그래프 교착상태해결 예방 (Prevention) 회피 (Avoidance) 발견 (Detection) 식사하는철학자문제 사례연구 요약 유닉스, 리눅스커널, 솔라리스, 윈도우즈 병행성 : 교착상태와기아 43

6주차.key

6주차.key 6, Process concept A program in execution Program code PCB (process control block) Program counter, registers, etc. Stack Heap Data section => global variable Process in memory Process state New Running