제 4 장 프로세스 Section 1 프로세스의 개념 Section 2 프로세스 스케줄링

1. 프로세스 정의  고전적 프로세스(classic process) ● 폰 노이만 컴퓨터상에서 실행 중인 프로그램의 개념 Section 1 프로세스의 개념 1. 프로세스 정의  고전적 프로세스(classic process) ● 폰 노이만 컴퓨터상에서 실행 중인 프로그램의 개념 ● 1990년대 이전에 발전했던 운영체제 개념(다중 프로그래밍, 동기화, 교착상태)은 고전적 프로세스 모델 하에서 개발  현대적 프로세스(modern process)와 스레드(thread) ● 윈도우 같은 몇몇 운영체제는 처음부터 현대적 프로세스와 스레드를 지원하도록 설계 프로세스(process) : CPU에 의해 수행되는 사용자 및 시스템 프로그램을 “프로세스”라고 하며 이는 시스템의 작업 단위 ● 시스템 프로세스 - 시스템 코드를 실행 ● 사용자 프로세스 - 사용자 코드를 실행

1. 프로세스 정의 ● 실행중인 프로그램 ● 프로세서에게 할당된 개체 ● 능동적 개체로 순차적 실행 Section 1 프로세스의 개념 1. 프로세스 정의 ● 실행중인 프로그램 ● 프로세서에게 할당된 개체 ● 능동적 개체로 순차적 실행 ● 프로세스 제어 블록에 의해 관리 ● 작업(job), 태스크(task), 활동(activity)이라고도 함

프로세스 제어블록의 구성 포인터 프로세스 상태 프로세스 번호 프로그램 카운터 각종 레지스터 기억장치 관리정보 포인터 프로세스 상태 프로세스 번호 프로그램 카운터 각종 레지스터 기억장치 관리정보 회계 및 입출력 상태 정보 .

2. 순차 프로세스와 병행 프로세스  하나의 프로그램 : 단순히 디스크상에 저장된 파일의 내용으로서  하나의 프로세스 : Section 1 프로세스의 개념 2. 순차 프로세스와 병행 프로세스  하나의 프로그램 : 단순히 디스크상에 저장된 파일의 내용으로서 수동적인(passive) 단위  하나의 프로세스 : 다음 명령어를 수행하도록 지정하는 프로그램 카운터를 가진 능동적(active)인 단위  순차 프로세스 : ● 현재 실행중인 하나의 프로세스를 의미. ● 프로세스의 실행은 순차적인 방식으로 진행되어야 하며, ● 이는 어떤 시점에서든지 하나의 명령어만이 프로세스를 위하여 실행 된다는 의미

2. 순차 프로세스와 병행 프로세스  프로세스 포함 정보 : ● 서브루틴 매개변수, 복귀주소와 임시변수 같은 임시적인 자료를 Section 1 프로세스의 개념 2. 순차 프로세스와 병행 프로세스  프로세스 포함 정보 : ● 서브루틴 매개변수, 복귀주소와 임시변수 같은 임시적인 자료를 가지는 프로세스 스택과 전역변수들을 가지는 데이터 영역 부분  프로세스에 포함되는 내용들 ● 프로세서 문맥(processor context) : 상태 워드나 레지스터들 ● 기억장치 문맥(memory context) : 코드 세그먼트, 데이터 세그먼트, 실행 스택 등 ● 그 프로세스와 연관된 속성들  프로세스 이름 : 프로세스 이름은 프로세스가 생성될 때 할당된 내부적인 번호  우선순위 : 프로세스 우선순위는 CPU를 할당하는 스케줄링에 사용  권한 : 프로세스의 권한은 정보의 보호 목적 및 수행할 연산을 지정

2. 순차 프로세스와 병행 프로세스  병행 프로세스 Section 1 프로세스의 개념 그림 4-1 두 프로세스 쌍 (p, q)의 실행

2. 순차 프로세스와 병행 프로세스  두 병행 프로세스의 3가지 실행 형태 ● 형태 1 : Section 1 프로세스의 개념 2. 순차 프로세스와 병행 프로세스  두 병행 프로세스의 3가지 실행 형태 ● 형태 1 :  먼저 프로세스 P의 명령어 스트림이 완전히 수행되고 나서, 다음에 프로세스 Q의 명령어 스트림이 완전히 수행 종료. ● 형태 2 :  두 프로세스가 종료될 때가지 프로세스 P와 Q가 교대로 수행.  주어진 어느 한 순간마다 단지 하나의 프로세서와 하나의 프로세스 행위만 존재 ● 형태 3 :  프로세스 P의 명령어 스트림과 프로세스 Q의 명령어 스트림이 시간 축에서 중첩되어 동시에 수행.  어느 한 순간에 두 개의 프로세스와 두 가지 프로세스 행위가 존재.  두 개의 분리된 프로세서가 필요. 실제 병렬성(real parallelism)

3. 프로세스 관리자  운영체제의 프로세스 관리자 하드웨어를 사용하여 프로세스, 스레드 자원 추상화를 구현할 책임. Section 1 프로세스의 개념 3. 프로세스 관리자  운영체제의 프로세스 관리자 하드웨어를 사용하여 프로세스, 스레드 자원 추상화를 구현할 책임. 프로세스 관리자는 프로세서와 다른 자원들이 추상기계 함수를 제공할 수 있도록 프로세서와 다른 자원들의 활동을 제어. ● 프로세스/스레드의 생성과 종료 ● 프로세스/스레드 동기화 ● 자원 할당 ● 자원보호 ● 입출력을 구현하는 장치관리자와의 협력 - 연산 초기화하기, 인터럽트 처리하기, 주기억장치와 장치제어기간의 정보 전송하기 등 ● 주소공간의 구현 - 물리적 메모리와 관련 있는 주소 공간 관리의 일정부분을 구현하기 위해 기억장치 관리자와 협력

3. 프로세스 관리자 현대적 프로세스 구성요소 프레임워크(framework) ● 주소 공간(address space) Section 1 프로세스의 개념 3. 프로세스 관리자 현대적 프로세스 구성요소 스레드 기반의 계산이 실행되는 일종의 프레임워크(framework) ● 주소 공간(address space) ● 데이터(data) ● 자원(resource) ● 프로세스 식별자(process identifier): 스레드 구성요소 스레드는 현대적 프로세스 프레임워크 내에서 발생하는 계산의 능동적 요소 ● 환경(environment) ● 데이터(data) ● 스레드 식별자(thread identifier)

프로세스의 상태 현재의 활동에 의해 정의됨 생성, 준비, 실행, 대기, 종료 중의 하나 생성 상태의 작업은 준비상태로 이동 실행상태는 작업이 처리되는 상태 대기 상태는 I/O 완료를 기다리는 상태 작업 스케줄러나 프로세스 스케줄러에 의해 상태전이

4. 프로세스 상태  단일 프로세서 시스템에서의 프로세스 : Section 1 프로세스의 개념 4. 프로세스 상태  단일 프로세서 시스템에서의 프로세스 : => 단지 1개의 프로세스만이 실행 상태에 있고, 준비 상태나 대기 상태의 프로세스들은 여러 개 존재.  프로세스의 상태 ● 보류(pending) 상태 :  작업이 제출되어 스풀 공간인 디스크에 수록되어 있는 상태. ● 준비(ready) 상태 :  CPU를 사용 가능한 상태 즉, CPU를 할당 받을 수 있는 상태.  CPU가 프로세스 자신을 처리해 주기를 기다리고 있는 상태. ● 실행(running) 상태 :  프로세스가 CPU를 차지하고 있는 상태로서, CPU에 의해 프로세스를 수행하고 있는 상태.

4. 프로세스 상태 ● 대기(blocked) 상태 :  프로세스가 CPU를 차지하고 실행되다가 입출력 처리와 같은 Section 1 프로세스의 개념 4. 프로세스 상태 ● 대기(blocked) 상태 :  프로세스가 CPU를 차지하고 실행되다가 입출력 처리와 같은 사건이 발생하게 되면, CPU를 양도하고 입출력 처리가 완료될 때까지 대기 큐에서 대기하고 있는 상태.  대기중인 프로세스는 입출력의 완성 등 외부 신호를 기다리고 있음. ● 교착(deadlock) 상태 :  프로세스가 결코 일어날 수 없는 사건의 발생을 기다리고 있는 상태 ● 완료(terminated) 상태 :  프로세스가 CPU를 할당 받아, 주어진 시간 내에 완전히 수행을 종료한 상태.  종료된 프로세스는 시스템에서 제거되고 관련된 PCB도 삭제.

4. 프로세스 상태  프로세스 상태도(process state diagram) Section 1 프로세스의 개념 그림 4-2 프로세스의 상태 전이도

4. 프로세스 상태  시스템 내의 프로세스 상태 예  프로세스 A, C, D, E는 준비 상태 Section 1 프로세스의 개념 4. 프로세스 상태  시스템 내의 프로세스 상태 예  프로세스 A, C, D, E는 준비 상태  프로세스 B는 실행상태(실행상태는 오직 하나)  프로세스 F, G는 대기 상태. 그림 4-3 프로세스의 상태 예

4. 프로세스 상태 프로세스 상태 전이 시기와 이유 ● 디스패치(dispatch) : 준비 상태 → 실행 상태 Section 1 프로세스의 개념 4. 프로세스 상태 프로세스 상태 전이 시기와 이유 ● 디스패치(dispatch) : 준비 상태 → 실행 상태 준비 상태의 프로세스들 중에서 우선 순위가 가장 높은 프로세스를 선정하여 CPU를 할당. 이때 CPU의 할당 시간(보통 100ms정도) 지정. ● 할당시간 초과(time run out) : 실행 상태 → 준비 상태 지정된 CPU의 할당시간을 모두 사용한 프로세스는 다른 프로세스를 위해 CPU가 선점되고, 그 프로세스는 준비 상태로 전환. ● 대기(block) : 실행 상태 → 대기 상태 실행중인 프로세스가 입출력 명령을 만나면 인터럽트가 발생하여 CPU를 양도하고, 자신은 스스로 대기 상태로 전환. ● 깨움(wake up) : 대기 상태 → 준비 상태 입출력 완료를 기다리다가 입출력 완료 신호가 들어오면, 대기중인 프로세스는 준비 상태로 전환.

5. 디스패치와 문맥 교환  스풀러(SPOOLer) : 제출된 작업들을 스풀 공간인 디스크에 수록하여 Section 1 프로세스의 개념 5. 디스패치와 문맥 교환  스풀러(SPOOLer) : 제출된 작업들을 스풀 공간인 디스크에 수록하여 보류 상태로 만들어 줌.  작업 스케쥴러(job scheduler) : 보류 상태의 작업들 중에서 실행될 작업을 선정하여 대응되는 프로세스로 만들어 보류 상태에서 준비 상태로 전환.  디스패치((dispatch) : 프로세스 스케쥴러(process scheduler)에 의해 준비 상태에 있는 여러 프로세스 중 실행될 한 프로세스를 선정하여 CPU를 할당하며, 프로세스는 준비 상태에서 실행 상태로 전환

5. 디스패치와 문맥 교환  문맥 교환(context switching) 프로세스 스케줄러는 준비 상태의 프로세스 중 Section 1 프로세스의 개념 5. 디스패치와 문맥 교환  문맥 교환(context switching) 프로세스 스케줄러는 준비 상태의 프로세스 중 한 프로세스에게 CPU를 디스패치하여 실행상태로 전환되게 함으로써, 한 프로세스에서 다른 프로세스로 CPU가 할당되는 과정  할당 시간(time slice, time quantum) : 한 프로세스가 CPU를 독점하는 것을 방지하기 위하여 지정된 시간 동안만 프로세스가 CPU를 점유하도록 한 시간. ● 할당시간이 너무 길면 : CPU가 비선점 효과를 갖게 되어 특정 프로세스에게 독점 ● 할당시간이 너무 짧으면 : 문맥 교환이 자주 발생하여 부하가 증가.

6. 프로세스 디스크립터  프로세스 디스크립터(process descriptor) 또는 Section 1 프로세스의 개념 6. 프로세스 디스크립터  프로세스 디스크립터(process descriptor) 또는 프로세스 제어블록(PCB: process control block) : ● 운영 체제에게 프로세스에 대한 중요한 정보를 제공해 주는 자료 구조 테이블. ● 운영 체제가 CPU를 다른 프로세스에 넘겨 주고자 할 때, 프로세스에 관한 모든 정보를 PCB에 저장시키고 나서 다시 실행하고자 할 때에는 PCB에 보관된 정보를 재사용. ● 한 프로세스에 대한 모든 정보를 담고 있는 프로세스 디스크립터의 내용들은 시스템에 따라 다름

6. 프로세스 디스크립터  프로세스 디스크립터의 내용 Section 1 프로세스의 개념 필 드 설 명 프로세스 이름 설  명 프로세스 이름 운영체제 코드에서 사용되는 정수나 테이블 인덱스 같은 프로세스의 내부적 이름 *상태 기본 스레드의 현재 상태 소유자 프로세스 소유자 실행시간 통계 누적시간, 시작시간 등 정보 스레드 이 프로세스와 연관된 스레드의 리스트 관련 프로세스 리스트 이 프로세스의 부모/자식/형제 프로세스 리스트 자식 프로세스 리스트 이 프로세스의 자식 프로세스 리스트 주소 공간 주소공간과 바인딩의 디스크립터 자원 프로세스가 보유한 자원의 리스트, 각 자원 유형은 자원의 개수와 식별자를 기술. *스택 주기억 장치 내의 기본 스레드의 스택 위치

6. 프로세스 디스크립터  프로세스 디스크립터의 관리 Section 1 프로세스의 개념 6. 프로세스 디스크립터  프로세스 디스크립터의 관리 ● PCB = 타스크 제어 블럭(task control block) = 작업 제어 블럭(job control block) = 프로세스 기술자(process descriptor) ● PCB 생성 시기 : 프로세스의 생성시에 만들어 짐. ● PCB 소멸 시기 : 프로세스의 수행이 완료 시 함께 삭제. ● PCB의 내용 관리 : 프로세스의 상태 변화가 일어난 경우 프로세스관리자 의하여 그 내용이 수정되고 변경. ● PCB 구성 : 같은 상태의 프로세스들이 존재하는 준비 완료 리스트나 대기 리스트는 FIFO, 큐, 스택, 우선 순위 큐, 트리 구조, 단순한 연결 리스트들로서 PCB들을 연결.

6. 스레드 추상화  프로세스 관리자의 스레드 관리 주요 내용  스레드 디스크립터의 내용 Section 1 프로세스의 개념 ● 스레드의 생성과 소멸 ● 스레드 특정자원의 할당 ● 스레드 스케줄링 및 문맥교환 관리  스레드 디스크립터의 내용 필 드 설  명 상태 기본 스레드의 현재 상태 실행시간 통계 누적시간, 시작시간 등 정보 프로세스 이 스레드와 연관된 프로세스의 프로세스 디스크립터 참조 관련 스레드 리스트 이 스레드의 부모/자식/형제 스레드 리스트 스택 주 기억장치 내의 기본 스레드의 스택 위치 다른 자원 스레드 특정 자원 참조

스레드의 개념 스레드는 프로세스 내의 다중처리를 위해 제안된 개념 디스패치의 단위를 프로세스에서 스레드로 세분화 프로세스 내의 병렬 수행을 위해 다중 스레딩 이용 하나의 스레드 내에서는 하나의 실행점만이 존재

Section 1 프로세스의 개념 6. 스레드 추상화  스레드의 종류 그림 4-5 스레드와 프로세스 관계

6. 스레드 추상화  단일/다중 스레드형 프로세스 차이 ● 다중 스레드형 프로세스 : Section 1 프로세스의 개념 6. 스레드 추상화  단일/다중 스레드형 프로세스 차이 ● 다중 스레드형 프로세스 : 각각의 스레드는 힙 영역(heap storage), 정적 영역(static storage), 코드(code)를 공유하고, 자기 고유의 레지스터와 스택을 가짐. ● 단일 스레드형 프로세스 : 하나의 스레드가 힙 영역, 정적 영역 그리고 코드를 공유하고 레지스터와 스택도 공유.

6. 스레드 추상화  단일/다중 스레드형 프로세스 차이 Section 1 프로세스의 개념 그림 4-6 단일 스레드형 프로세스와 다중 스레드형 프로세스

6. 스레드 추상화  스레드 상태 ● 대기 상태 : 스레드가 다른 스레드나 또는 외부의 사건과 Section 1 프로세스의 개념 6. 스레드 추상화  스레드 상태 ● 대기 상태 : 스레드가 다른 스레드나 또는 외부의 사건과 동기화 중에 있는 상태로 실행에 부적합한 상태. ● 준비 상태 : 스레드가 프로세서에 의해 실행될 수 있는 상태. ● 실행 상태 : 스레드가 현재 CPU를 가지고 실행 중에 있는 상태. ● 종료 상태 : 스레드가 그의 작업 수행을 완전히 종료한 상태. 그림 4-7 스레드의 상태 변화

 프로세스 스케줄링의 유형 Section 2 프로세스 스케줄링 기능 별 작업 스케줄링 분류 프로세스 스케줄링 방법 별 선점 스케줄링 비선점 스케줄링 알고리즘 별 분류 우선순위 스케줄링 기한부 스케줄링 FIFO 스케줄링 Round Robin 스케줄링 SJF(shortest job first) 스케줄링 SRT(shortest remaining time) 스케줄링 HRN(highest response ratio next) MLQ(multi level queue) 스케줄링 MFQ(multilevel feedback queue) 스케줄링

1. 스케줄링의 목적과 기준  공정한 스케줄링  응답 시간 최소화  처리량 극대화  반환시간 예측 가능 Section 2 프로세스 스케줄링 1. 스케줄링의 목적과 기준  공정한 스케줄링  응답 시간 최소화  처리량 극대화  반환시간 예측 가능  균형 있는 자원 사용  응답 시간과 자원 이용간의 조화  실행의 무한 연기 배제  우선 순위를 실시  바람직한 동작을 보이는 프로세스에게 더 좋은 서비스를 제공

Section 2 프로세스 스케줄링 2. 스케줄링 기법  프로세스 스케줄러 구조 그림 4-8(a) 프로세스 스케줄러

2. 스케줄링 기법  프로세스 스케줄러 구조  순서기(sequencer) Section 2 프로세스 스케줄링 2. 스케줄링 기법  프로세스 스케줄러 구조  순서기(sequencer) CPU를 기다리고 있는 프로세스들의 준비 리스트로 프로세스 디스크립터의 포인터를 위치  문맥 교환기 CPU로부터 제거되는 프로세스/스레드를 위하여 CPU 레지스터에 있는 모든 내용(PC, IR, 조건상태, 프로세스 상태, ALU 상태)를 프로세스 디스크립터에 저장  디스패처 준비리스트에 있는 준비 프로세스/스레드 중 하나를 선택하고 선택된 프로세스/스레드에 대한  문맥교환을 실행함으로써 그 프로세스/스레드에 CPU를 할당

Section 2 프로세스 스케줄링 2. 스케줄링 기법  문맥 교환기 구조 그림 4-8(b) 문맥 교환기

2. 스케줄링 기법  문맥 교환기  문맥 교환은 CPU 레지스터에 저장된 한 프로세스의 Section 2 프로세스 스케줄링 2. 스케줄링 기법  문맥 교환기  문맥 교환은 CPU 레지스터에 저장된 한 프로세스의 상태정보를 저장하고 다른 프로세스를 위한 알맞은 정보를 레지스터로 쓰기 위한 연산  프로세스의 실행이 멈추었을 때 모든 CPU 레지스터의 내용은 그 프로세스 디스크립터에 저장  프로세스가 다시 시작되기 전에 이전에 저장되었던 레지스터의 내용들이 물리적 CPU 레지스터로 다시 복사

3. 선점 및 비선점 스케줄링 1) 선점(preemptive) 스케줄링  한 프로세스가 CPU를 차지하고 있을 때  특징 Section 2 프로세스 스케줄링 3. 선점 및 비선점 스케줄링 1) 선점(preemptive) 스케줄링  한 프로세스가 CPU를 차지하고 있을 때 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우.  높은 우선 순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용.  특징  우선순위가 높은 프로세스가 먼저 수행할 때 유리.  빠른 응답시간을 요구하는 시분할 시스템에 유용.  많은 오버헤드를 초래.

3. 선점 및 비선점 스케줄링 2) 비선점(non preemptive) 스케줄링 Section 2 프로세스 스케줄링 3. 선점 및 비선점 스케줄링 2) 비선점(non preemptive) 스케줄링  한 프로세스가 CPU를 할당 받으면 CPU는 그 프로세스로부터 빠져 나올 수 없음.  모든 프로세스들에 대한 대우는 짧은 작업이던 긴 작업이던 간에 공정.  응답시간을 쉽게 예측.  특징  모든 프로세스에 대한 요구를 공정히 처리.  응답시간의 예측이 가능.  짧은 작업이 긴 작업을 기다리는 경우가 종종 발생.

4. 스케줄링 알고리즘 1) 우선순위 스케줄링 – non preemptive  우선 순위의 기법 종류 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 1) 우선순위 스케줄링 – non preemptive  각 프로세스에게 우선 순위를 부여하여 순위가 높은 순서대로 처리하는 방법.  우선 순위의 기법 종류  정적 우선 순위 방법  실행이 쉽고 상대적으로 오버헤드는 적으나, 반면 주위 여건의 변화에 적응하지 못하고 우선 순위를 바꾸지 않음.  동적 우선 순위 방법  상황 변화에 잘 적응. 구현하기가 복잡하고 오버헤드가 많으나, 시스템의 응답도를 증가시켜 주므로 효율성.

4. 스케줄링 알고리즘  4개의 우선순위를 갖는 시스템 예. Section 2 프로세스 스케줄링 그림 4-9 4개의 우선순위를 갖는 스케줄링  우선순위 1인 실행 가능한 프로세스가 있는 한, 라운드 로빈 방식으로 주 어진 하나의 프로세스가 할당시간 동안 곧바로 실행.  만약 우선순위 1인 프로세스가 비게 되면, 우선 순위 2인 프로세스가 라운 드 로빈 방식으로 실행되고, 우선순위 1,2가 비게 되면 운선순위 3이 실행.  우선순위가 변하지 않으면 가장 낮은 우선순위 작업은 기아 상태에 빠짐.

4. 스케줄링 알고리즘 1) 우선순위 스케줄링 – non preemptive 도착한 다음의 프로세스들의 집합 고려. Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 1) 우선순위 스케줄링 – non preemptive  예를 들어, 시간 0에 P1, P2, P3, P4, P5 순으로 도착한 다음의 프로세스들의 집합 고려.  우선순위 스케줄링에 대한 Gantt 차트. 프로세스 우선순위 버스트 시간 대기 시간 반환 시간 P1 3 10 6 16 P2 1 P3 19 P4 4 20 P5 2 5 P2 P5 P1 P3 P4 1 6 16 19 20 그림 4-10 우선순위 스케줄링에 대한 Gantt 차트

4. 스케줄링 알고리즘 1) 우선순위 스케줄링 – non preemptive  각 프로세스의 대기시간 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 1) 우선순위 스케줄링 – non preemptive  각 프로세스의 대기시간  P1은 6 ms, P2는 0 ms, P3은 16 ms, P4는 1 ms, P5는 1ms  각 프로세스의 반환시간 = 버스트 시간 + 대기 시간  평균 대기 시간 = (6 + 0 + 16 + 19 + 1)/5 = 8.4 * 10 ms.  평균 반환시간 = (16 + 1 + 19 + 20 + 6)/5 = 12.4 * 10 ms.

4. 스케줄링 알고리즘 2) 기한부 스케줄링 – non preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 2) 기한부 스케줄링 – non preemptive  기한부(deadline)=마감시간 스케줄링은 작업들이 명시된 시 간이나 기한 내에 완료되도록 계획되며, 이들 작업들의 결과가 시간 내에 구해지면 유용하고, 마감 시간이 지난 후에 결과가 구해지면 쓸모가 없게 됨.  시스템은 기한까지 일을 끝내기 위하여 자신의 자원 안배를 주의 깊게 계획.  만약, 많은 기한부 작업들이 동시에 실행된다면 스케줄링이 너무 복잡.  기한부 스케줄링에 의해서 요구되는 집중적인 자원 운영은 많은 오버헤드.

4. 스케줄링 알고리즘 2) 기한부 스케줄링 – non preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 2) 기한부 스케줄링 – non preemptive  두 번째 스케줄링에 대한 Gantt 차트가 가장 빠름. p1 p2 p3 p4 p5 1275 1050 550 200 75 프로세스 버스트 시간 종료시한 대기 시간 반환 시간 P1 350 575 200 550 P2 125 75 P3 475 1050 1025 P4 250 none 1275 P5

4. 스케줄링 알고리즘 3) FCFS 스케줄링 – non preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 3) FCFS 스케줄링 – non preemptive  FCFS(First Come First Service) 스케줄링은 가장 간단한 기법으로써 프로세스들은 대기 큐에 도착한 순서에 따라 CPU를 할당.  일단 프로세스가 CPU를 차지하면 완료될 때까지 수행.  다른 방식에 비하여 작업 완료 시간을 예측하기가 용이.  긴 작업이 짧은 작업을 오래 동안 기다리게 할 수 있고 중요하지 않은 작업이 중요한 작업을 기다리게 하므로 어느 정도 불합리.  대화식 사용자들에게는 부적합. 그림 4-12 FCFS 스케줄링

3) FCFS 스케줄링 – non preemptive Section 2 프로세스 스케줄링 3) FCFS 스케줄링 – non preemptive  예를 들어, 시간 0에 도착한 다음의 프로세스들의 P1, P2, P3 집합을 고려.  FCFS 스케줄링에 대한 Gantt 차트. 프로세스 버스트 시간 대기 시간 반환 시간 P1 24 P2 3 27 P3 30 P4 10 40 P1 P2 P3 P4 24 27 30 40 그림 4-13 FCFS 스케줄링에 대한 Gantt 차트  각 프로세스의 대기시간 : P1은 10ms, P2는 24ms P3은 27ms, P4는 30ms.  평균 대기 시간 = (0 + 24 + 27 + 30)/ 4 = 20.25 * 10ms  평균 반환시간 = (24 + 27 + 30 + 40)/4 = 30.25 * 10 ms.

4. 스케줄링 알고리즘 4) SJF 스케줄링 – non preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 4) SJF 스케줄링 – non preemptive  SJF(Shortest Job First) 스케줄링은 기다리고 있는 작업 중에서 수행 시간이 가장 짧다고 판정된 것을 먼저 수행하는 비선점 스케줄링.  FCFS보다 평균 대기 시간을 감소시키는 반면, 큰 작업에 대해서는 FCFS에 비하여 예측하기 어려움.  긴 작업보다 짧은 작업에게 오버헤드 면에서 볼 때 더 유리.  문제점 수행할 작업이나 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데, 이 정보를 얻기가 어렵다는 점. 최선의 방법은 수행 예측을 사용자에 의존.

4. 스케줄링 알고리즘 4) SJF 스케줄링 – non preemptive  예를 들어, 시간 0에 도착한 다음의 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 4) SJF 스케줄링 – non preemptive 그림 4-14 SJF 스케줄링  예를 들어, 시간 0에 도착한 다음의 프로세스들의 P1, P2, P3, P4 집합을 고려. CPU 버스트 시간의 길이는 10ms.

4. 스케줄링 알고리즘  SJF 스케줄링에 대한 Gantt 차트.  각 프로세스의 대기시간 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘  SJF 스케줄링에 대한 Gantt 차트. 프로세스 버스트 시간 대기 시간 반환 시간 P1 6 3 9 P2 8 16 24 P3 7 P4 P4 P1 P3 P2 3 9 16 24 그림 4-15 SJF 스케줄링에 대한 Gantt 차트  각 프로세스의 대기시간 P1은 3ms, P2는 16ms, P3은 9ms, P4는 0ms.  평균 대기 시간 = (3 + 9 + 16 + 24)/4 = 13 * 10 ms.  평균 반환시간은 (9 + 24 + 16 + 3)/4 = 13 * 10 ms.

4. 스케줄링 알고리즘 5) HRN 스케줄링 – non preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 5) HRN 스케줄링 – non preemptive  HRN(Highest Response ratio Next) 스케줄링은 SJF의 약점, 특히 긴 작업과 짧은 작업간의 지나친 불평들을 어느 정도 보완한 기법.  일단 한 작업이 CPU를 차지하면 그 작업은 완성될 때 까지 실행. 긴 작업과 짧은 작업간의 편향성을 어느 정도 완화.  우선순위 = 대기시간 + 버스트 시간 버스트 시간  시스템 응답(반환)시간 = 대기 시간 + 서비스 시간(버스트 시간)  짧은 작업이나 대기 시간이 큰 작업은 우선순위가 높아짐.

4. 스케줄링 알고리즘 5) HRN 스케줄링 – non preemptive Section 2 프로세스 스케줄링

4. 스케줄링 알고리즘 5) HRN 스케줄링 – non preemptive  예를 들어, 다음과 같은 대기 시간과 버스트 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 5) HRN 스케줄링 – non preemptive  예를 들어, 다음과 같은 대기 시간과 버스트 시간을 가진 프로세스들이 준비 큐에 들어 있다고 가정할 경우, 우선순위에 따라 P1, P4, P2, P3의 순서로 서비스. 프로세스 대기 시간 버스트 시간 P1 12 3 P2 8 4 P3 P4 15 5  각 프로세스의 우선순위 -P1의 우선순위 = (12+ 3)/3 = 5 -P2의 우선순위 = ( 8+ 4)/4 = 3 -P3의 우선순위 = ( 8+ 8)/8 = 2 -P4의 우선순위 = (15+ 5)/5 = 4  우선순위는 P1이 가장 높으며, P4, P2, P3의 순서로 CPU를 할당.

4. 스케줄링 알고리즘 6) 라운드 로빈 스케줄링 - preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 6) 라운드 로빈 스케줄링 - preemptive  라운드 로빈(Round Robin) 스케줄링은 FCFS에 의해서 프로세스 들이 내 보내어 지며 각 프로세스는 같은 크기의 CPU 시간을 할당.  만약, 프로세스가 CPU 시간이 만료 될 때까지 처리를 완료하지 못하면 그 중앙처리 장치는 대기중인 다음 프로세스로 넘어가며 (preemptive), 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내짐.  할당 시간의 크기는 시스템의 동작에 절대적인 영향.(보통 크기는 10∼100 ms)  할당 시간이 크면 FCFS 방식과 동일. 시분할 시스템에 많이 사용  할당 시간이 작으면, 문맥 교환을 위한 오버헤드 증가.

4. 스케줄링 알고리즘 6) 라운드 로빈 스케줄링 - preemptive  예를 들어, 시간 0에 도착한 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 6) 라운드 로빈 스케줄링 - preemptive 그림 4-18 RR 스케줄링  예를 들어, 시간 0에 도착한 다음의 프로세스들의 P1, P2, P3 집합을 고려.

4. 스케줄링 알고리즘 6) 라운드 로빈 스케줄링 - preemptive  RR 스케줄링에 대한 Gantt 차트. Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 6) 라운드 로빈 스케줄링 - preemptive  RR 스케줄링에 대한 Gantt 차트. 프로세스 버스트 시간 대기 시간 반환 시간 P1 24 6 30 P2 3 10 13 P3 16 P1 P2 P3 P1 10 13 16 30 그림 4-19 RR 스케줄링에 대한 Gantt 차트  각 프로세스의 대기시간 P1은 6(16-6) ms, P2는 10 ms, P3은 13 ms.  평균 대기 시간= (6 + 10 + 13)/ 3 = 9.67 * 10 ms.  평균 반환시간 = (30 + 13 + 16 )/3 = 19.67 * 10 ms.

4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive  SRT(Short Remaining Time) 스케줄링은 SJF와 마찬가지로 새로 도착한 프로세스를 포함하여 처리가 완료되는데, 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행.  실행중인 프로세스라도 남은 처리 시간이 더 짧다고 판단되는 프로세스가 생기면 언제라도 실행중인 프로세스가 선점. SJF 기법에 선점 방식을 도입한 변형된 방법으로서 시 분할 시스템에 유용.  수행중인 각각의 작업들에 대한 실행시간을 추적 보유 (선점으로 인한 오버헤드).  긴 작업은 SJF보다 대기 시간이 김.

4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive 그림 4-20 SRT 스케쥴링  예를 들어, 시간 0, 1, 2, 3 ms에 차례로 도착한 다음의 프로세스들의 P1, P2, P3, P4 집합을 고려.

4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive  SRT 스케줄링에 대한 Gantt 차트. Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive  SRT 스케줄링에 대한 Gantt 차트. 프로세스 도착 시간 버스트 시간 대기 시간 반환 시간 P1 6 P2 1 8 15 23 P3 2 7 14 P4 3 P1 P4 P3 P2 6 9 16 24 그림 4-21 SRT 스케줄링에 대한 Gantt 차트  프로세스 P1이 도착하여 CPU를 할당 받아 수행하는 도중에 1ms후에 버스트 시간이 8ms인 P2가 도착.  P1의 5ms 남은 버스트 시간이 P2의 버스트 시간보다 크므로 P1이 계속 수행.

4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 7) SRT 스케줄링 - preemptive  2ms후에 버스트 시간이 7ms인 P3이 도착하지만, P1의 4ms남은 버스트 시간이 P3의 버스트 시간보다 크므로 역시 P1이 계속 수행.  3ms후에 버스트 시간이 3ms인 P4이 도착하지만, P1의 3ms 남은 버스트 시간과 P4의 버스트 시간과 같으므로 P1이 마지막 3ms까지 수행이 완료된 후 시스템을 떠남.  큐에는 P1을 제외한 3개의 작업이 남아 있고 그 중에서 가장 작은 P4가 수행되고, 그 다음에는 P3, P2의 순서로 수행.  SRT에서의 각 프로세스의 대기 시간 = 도착시간 - CPU 할당 시간.  각 프로세스의 대기시간 P1은 (0-0)=0ms, P2는 (16-1)=15ms, P3은 (9-2)=7ms, P4는 (6-3)=3ms.  평균 대기 시간 = (0 + 15 + 7 + 3)/4 = 6.25 * 10 ms.  평균 반환시간= (6 + 23 + 14 + 6)/4 = 12.25 * 10 ms.

8) 다단계 큐 알고리즘 - preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 8) 다단계 큐 알고리즘 - preemptive  다단계 큐(multi level queue) 알고리즘은 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 스케줄링 기법, 그룹화된 작업들은 각각의 준비 큐에 넣어두고 각 큐의 독 자적인 스케줄링 알고리즘에 따라서 CPU를 할당 받는 방법.  상위단계에서 하위 단계까지 5개의 큐로 분할. 1. 시스템 작업 2. 대화형 작업 3. 편집 작업 4. 일괄처리 작업 5. 학생 작업  다단계 큐 알고리즘은 준비 상태 큐를 여러 종류로 분할.  각 큐는 자신만의 독자적인 스케줄을 가짐.  각각의 작업들이 다른 묶음으로 분류될 수 있을 때 사용되는 알고리즘.

8) 다단계 큐 알고리즘 - preemptive Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 8) 다단계 큐 알고리즘 - preemptive  일괄 처리 작업이 실행중일 지라도 상위 단계 큐에 작업이 들어오면 일괄 처리 작업은 CPU를 "선점" 당함.  한 큐에서 다른 큐로의 작업 이동불가 그림 4-22 다단계 큐

4. 스케줄링 알고리즘 9) 다단계 피드백 큐 - preemptive  프로세스들은 CPU의 사용시간에 따라 입출력 위주와 Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 9) 다단계 피드백 큐 - preemptive  프로세스들은 CPU의 사용시간에 따라 입출력 위주와 CPU 위주로 구분, 서로 다른 할당시간 부여.  새로운 프로그램이 들어오면 높은 우선 순위를 할당해 주어 단계 1에서 즉시 수행해 주고, 점차 낮은 우선 순위를 부여하며 마지막 단계 n에서는 그 작업이 완료 될 때가지 라운드 로빈으로 순환.  MFQ의 기준  짧은 작업에 유리.  효율적인 IO 장치 이용을 위해 입출력 위주프로세스에 우선권.  가능한 한 빨리 작업의 특성을 알고 그에 맞게 스케줄링.  프로세스가 보다 하위 단계의 큐로 옮겨 갈수록 주어진 할당 시간은 점차 크게 설정. 이는 보다 높은 단계에 있는 큐의 프로세스가 더 높은 우선 순위를 갖기 때문.

4. 스케줄링 알고리즘 9) 다단계 피드백 큐 - preemptive Section 2 프로세스 스케줄링 그림 4-23 다단계 피드백 큐

4. 스케줄링 알고리즘 9) 다단계 피드백 큐 - preemptive 프로세스들을 분류하는데 이상적. Section 2 프로세스 스케줄링 4. 스케줄링 알고리즘 9) 다단계 피드백 큐 - preemptive  이 기법은 CPU에 대한 요구량에 따라 프로세스들을 분류하는데 이상적.  시스템이 제어하는 동작의 변화에 민감하게 반응하도록 하는 적응기법의 일종.  작업이 입력되는 시점에서 한 큐에서 다른 큐로의 작업 이동이 불가능.  다단계 피드백 큐 스케줄링은 아래 요소로 정의.  큐의 수.  각 큐에 대한 스케줄링 알고리즘.  작업을 보다 높은 우선순위의 큐로  격상시키는 시기를 결정하는 방법.  작업을 보다 낮은 우선순위의 큐로  격하시키는 시기를 결정하는 방법.  프로세스들이 어느 큐에 들어갈 것 인가를 결정하는 방법.

1. 상호배제와 임계영역  공유 메모리 함께 동작하는 프로세스들은 종종 메모리를 공유함. Section 3 비 동기 병행 프로세스 1. 상호배제와 임계영역  공유 메모리 함께 동작하는 프로세스들은 종종 메모리를 공유함. 어떤 프로세스는 메모리에 쓰고 또 다른 프로세스는 메모리에서 읽음.  경쟁 조건(race condition) ● 두개 혹은 그 이상의 프로세스들이 공유 기억장치에 읽기/쓰기를 하고, 어떤 프로세스가 언제 실행하느냐에 따라 결과가 달라질 수 있는 상황. ● 경쟁 조건이 있는 프로그램의 결과는 대부분의 경우 올바르나, 이상한 순서로 실행하게 되면 그 결과는 예측할 수 없게 됨.

1. 상호배제와 임계영역  경쟁 조건을 피하려면? 두개 이상의 프로세스들이 동시에 읽기와 쓰기를 못하게, Section 3 비 동기 병행 프로세스 1. 상호배제와 임계영역  경쟁 조건을 피하려면? 두개 이상의 프로세스들이 동시에 읽기와 쓰기를 못하게, 상호 배제(mutual exclusion)가 필요.  상호 배제 : ● 한 프로세스가 공유 기억장치 혹은 공유 파일을 사용하고 있을 때, 다른 프로세스들이 사용하지 못하도록 배제시키는 제어 기법. ● 임계 영역의 개념을 이용하여 두 프로세스가 하나의 공유 자원을 상호 배타적으로 사용할 수 있게 하면서 동시에는 수행할 수 없도록 하는 것.  임계지역(critical region) 또는 임계 영역(critical section) ● 공유 기억장치가 참조되는 프로그램의 부분. ● 어떤 프로세스가 공유 데이터를 접근하는 중일 때, 그 프로세스는 임계영역에 있다고 함.

1. 상호배제와 임계영역  임계영역에 있는 프로세스 ● 가능한 한 빨리 수행되어야 하며, Section 3 비 동기 병행 프로세스 1. 상호배제와 임계영역  임계영역에 있는 프로세스 ● 가능한 한 빨리 수행되어야 하며, ● 프로세스가 임계영역 내에서 블록(blocked)상태가 되면 안되며, ● 무한 루프 상태가 되지 않도록 하여야 함.  상호배제 해결을 위한 4가지 요구 조건 1) 두 개 이상의 프로세스들이 동시에 임계 영역에 있어서는 안됨. (상호 배제 조건) 2) 임계 구역 바깥에 있는 프로세스가, 다른 프로세스의 임계 구역 진입을 막아서는 안됨. (진행 조건) 3) 어떤 프로세스도 임계 구역으로 들어가는 것이 무한정 연기되 면 안됨. (한계 대기 조건) 4) 프로세스들의 상대적인 속도에 대해서는 어떠한 가정도 하지 않음.

1. 상호배제와 임계영역  n개 프로세스들의 상호배제 프리미티브 Section 3 비 동기 병행 프로세스 1. 상호배제와 임계영역  n개 프로세스들의 상호배제 프리미티브 ● 임계 영역에 들어가기 전에 BeginCriticalSection()을 호출, 임계 영역에서 나갈 때 EndCriticalSection()을 호출. ● 다른 프로세스들이 BeginCriticalSection()을 호출할 때, 프로세스 Pi가 이미 임계 영역에 있으면 => 바쁜 대기 (busy waiting) 그림 4-24 상호 배제 프리미티브

3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정  알고리즘 1 Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정  알고리즘 1 ● 정수형 변수 turn : 두 개 프로세스 , 의 공유 변수. ● i : 프로세스 지역 변수. ● turn, i, j = 0 혹은 1의 값, i = 1 - j. ● 한 순간에 한 프로세스만이 임계 영역에 들어감. 그림 4.25 알고리즘 1에서의 프로세스 의 구조

3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정 ● 알고리즘 1은 임계 영역의 실행 순서를 두 개의 프로세스가 Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정 ● 알고리즘 1은 임계 영역의 실행 순서를 두 개의 프로세스가 교대로 가져야 하므로  두 개 프로세스의 상대적인 시간적 차이를 고려하지 않고  진행 요건을 충족시키지 못하고 있음.  예를 들어, turn=0일 경우 프로세스 가 수행 중이 아니라도 두 번 연속해서 임계 영역에 들어갈 수 없음. ● 1개의 공유변수를 사용하였으므로 락스텝 동기화(lockstep synchronization)문제를 야기

3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정  알고리즘 2 Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정  알고리즘 2 ● turn 대신 bool flag[2]사용 => 배열의 원소는 false로 초기화. ● flag[i]가 true라면 가 임계 영역에 들어갈 준비가 되어 있다는 뜻. ● 프로세스 는 처음에 flag[i]를 true로 지정하여 임계 영역에 진입할 것임을 알림. ● 그 다음에 는 프로세스 가 진입할 의사가 있는지 확인. ● 만일 가 준비되었다면 의 flag[j]가 false가 될 때 까지 대기후, 가 진입. ● 임계 영역을 떠날 때 는 flag[i]를 false로 바꾸어, 더 이상 임계 구역 내에 있지 않음을 알림. ● 이 방식은 진행 조건이 충족되지 않음. ==> 즉, 두 개의 프로세스가 거의 같은 시간에 진입하려고 하면, turn[i],turn[j] 모두 true가 되어 두 프로세스는 내부의 while문에 서 영원히 대기.

3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정  교착상태 : Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 1) 소프트웨어적 해결 과정  교착상태 : - 두 개의 프로세스가 상대방 flag가 false가 되기를 무한히 기다리는 상태. - 교착 상태는 일어날 수 없는 사건을 기다리는 프로세스의 상태. 그림 4.26 알고리즘 2에서의 프로세스 Pi 의 구조

2) 데커 알고리즘 3. 2개 프로세스의 상호배제 두 개의 프로세스를 위한 상호 배제의 최초의 소프트웨어 해결법. Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 2) 데커 알고리즘  데커(dekker)의 알고리즘 : 두 개의 프로세스를 위한 상호 배제의 최초의 소프트웨어 해결법.  프로세스 Pi의 구조 ● 초기값은 flag[0] = flag[1] = false이고, turn = 0 또는 1의 값을 갖음. ● Pi가 임계구역에 들어가려면 flag[i] = true로 설정 후, Pj가 똑같 이 임계 구역에 들어가려 하거나, 임계영역에 이미 있는지를 확인. ● 만일 flag[j] = false이어서 Pj가 임계 구역에 있지 않고, 들어가 려 하지도 않음을 확인하면, Pi가 임계 영역으로 진입. ● 임계 영역에서 나오는 Pi 프로세스는 flag[i] = false로 하여 빠져 나옴을 알리고, turn 은 다음 번에 임계 영역에 들어갈 때 충돌이 생기면 기회를 양보하기 위해서 j 로 함. ● turn 값이 i이면 Pi 가 진입하고 turn값이 j이면 Pj 가 진입함

Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 그림 4.27 데커 알고리즘

3. 2개 프로세스의 상호배제 3) 피터슨 알고리즘  프로세스 Pi의 구조 Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 3) 피터슨 알고리즘  프로세스 Pi의 구조 ● bool flag[2]; // 초기값은 flag[0] = flag[1] = false ● int turn; // turn = 0 또는 1의 값 ● Pi가 임계 영역에 진입하려면 먼저 flag[i] =true로 하여 임계 영역에 들어가고 싶다는 의사 표시. ● 그 다음 turn = j 로 설정하고 내부 while문을 수행. ● 내부 while 문에서, 프로세스 j가 임계구역에 들어갈 의사표시를 하지 않았다면 (false 이므로) 임계 영역에 들어갈 수 있음. ● 만약, 두 개의 프로세스가 동시에 임계구역에 진입하려고 한다 면 둘 중에 하나만을 선택해야 하므로, 변수 turn이 역할을 발휘.

3. 2개 프로세스의 상호배제 ● 조금이라도 turn변수가 늦게 수행된 프로세스가 내부의 while문에서 기회를 양보. Section 3 비 동기 병행 프로세스 3. 2개 프로세스의 상호배제 ● 조금이라도 turn변수가 늦게 수행된 프로세스가 내부의 while문에서 기회를 양보. ● 임계 영역에서 나오는 프로세스는 flag[i]를 false로 함으로써, 다른 프로세스가 임계 영역에 들어가도록 허용. 그림 4.28 피터슨 알고리즘

3. 세마포어(Semaphore)  세마포어 : 세마포어 s는 정수 값을 갖는 변수로서 Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore)  세마포어 : 세마포어 s는 정수 값을 갖는 변수로서 초기화 및 두 개의 연산(P와 V, 혹은 wait와 signal)으로만 접근 가능한 특수한 변수.  wait(혹은 P)와 signal(혹은 V)의 정의. s.wait() : if (s.value > 0) s.value--; else 현재의 프로세스를 s.list에서 기다림. s.signal() : if (1개 이상의 프로세스가 s에서 대기 중이면) 그 중 한 개 프로세스만 진행 s.value++;

3. 세마포어(Semaphore) 1) 세마포어를 이용한 상호 배제의 구현 Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 1) 세마포어를 이용한 상호 배제의 구현  세마포어를 이용한 N개 프로세스의 상호 배제의 구현. ● s는 세마포어 공유 변수이고 초기 값은 1. semaphore s; // 공유 변수 s.init(1); // 초기화 그림 4-29 세마포어를 이용한 상호 배제 (프로세스Pi 의 구조)

3. 세마포어(Semaphore) 2) 세마포어를 이용한 동기화  대기/깨움(block/wakeup) 프로토콜 Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 2) 세마포어를 이용한 동기화  대기/깨움(block/wakeup) 프로토콜 ● 한 프로세스가 입출력을 요구하면 입출력이 끝날 때 까지 그 프로세스는 블록 상태. ● 다른 프로세스는 이 블록된 프로세스를 깨워줌. ● synch는 공유 변수. semaphore synch(0); // 변수 생성 및 초기화 그림 4-30 세마포어를 이용한 동기화

3. 세마포어(Semaphore) 3) 세마포어의 구현 ● wait()를 호출한 프로세스는 CPU 자원을 사용하면서 대기하는 Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 3) 세마포어의 구현 ● wait()를 호출한 프로세스는 CPU 자원을 사용하면서 대기하는 것이 아니고, 자원을 반납하고 대기. 즉 블록 상태로 들어감. ● 다른 프로세스가 signal()을 호출해 주면, 대기하고 있던 프로세스 중 하나는 블록 상태에서 준비 상태로 상태가 변화되고, CPU를 점유하기 위해 기다림(wakeup). ● 각 세마포어는 정수 값과 프로세스 리스트를 가짐. ● 프로세스가 세마포어에서 대기하도록 하려면 프로세스(PCB) 를 list에 추가. ● signal()은 대기 프로세스의 리스트에서 한 프로세스를 꺼내어 실행하도록 함.

3. 세마포어(Semaphore) class semaphore { public: wait(); signal(); Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 3) 세마포어의 구현 ● 세마포어를 다음과 같은 클래스로 정의. class semaphore { public: wait(); signal(); protected: int value; PCB *list; };

Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 3) 세마포어의 구현 그림 4-31 세마포어의 구현

3. 세마포어(Semaphore) 3) 세마포어의 구현  세마포어의 잘못된 사용 Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 3) 세마포어의 구현  세마포어의 잘못된 사용 ● 세마포어는 임계 영역과 관련된 문제를 효과적으로 해결 가능. ● 두 프로세스가 동시에 첫 문장을 수행한다고 할 경우, 두 프로세스는 교착 상태에 빠짐. semaphore s(1), q(1); // 공유 변수 생성 및  초기화 그림 4-32 세마포어의 교착 상태 예

3. 세마포어(Semaphore) 3) 세마포어의 구현  다른 교착 상태의 예 ● 상호배제에서 초기 값을 0으로 주었을 때, Section 3 비 동기 병행 프로세스 3. 세마포어(Semaphore) 3) 세마포어의 구현  다른 교착 상태의 예 ● 상호배제에서 초기 값을 0으로 주었을 때, ● mutex.wait()를 수행하면 교착 상태에 빠짐. semaphore mutex(0); while (1) { ... mutex.wait(); // 임계 영역 (critical section) mutex.signal(); }

4. 모니터(Monitor)  모니터 : 순차적으로만 사용할 수 있는 공유자원 또는, Section 3 비 동기 병행 프로세스 4. 모니터(Monitor)  모니터 : 순차적으로만 사용할 수 있는 공유자원 또는, 공유자원 그룹을 할당하는데 사용되는 데이터, 프로시저를 포함하는 병행성 구조. ● 자원관리기능을 수행하려는 프로세스는 반드시 해당 모니터 진입부를 호출. ● 여러 개의 프로세스들이 동시에 모니터에 들어가려 할 경우, 모니터 자체는 상호 배제가 엄격하게 실시. ● 즉, 한 순간에 단 한 개만의 프로세스만이 모니터 내부에 있을 수 있음. ● 모니터가 이미 사용 중이면 프로세스는 대기. ● 모니터 내부의 변수는 모니터 내부에서만 접근 가능 : "정보의 은폐 기법". ● 만일 프로세스가 모니터에 들어가서 수행 중에 자원이 이미 할당되어서 대기해야 하면, 조건 변수의 wait()를 호출.

Section 3 비 동기 병행 프로세스 4. 모니터(Monitor)  모니터 구조 그림 4-33 모니터 구조

4. 모니터(Monitor)  모니터 동기화 기법 ● 동기화 기법이 필요하다면 프로그래머는 조건 변수를 Section 3 비 동기 병행 프로세스 4. 모니터(Monitor)  모니터 동기화 기법 ● 동기화 기법이 필요하다면 프로그래머는 조건 변수를 여러 개 선언. condition x, y; ● 연산 wait와 signal.==>동기화  연산 x.wait(); ● 이 wait연산을 호출하는 프로세스는 다른 프로세스가 다음 연산을 호출할 때 까지 중단. ● 중단된 프로세스는 조건 변수 x에서 대기. ● 기타 조건 변수 큐 => 이러한 프로세스들이 대기하는 블록된 큐.  연산 x.signal(); ● x.signal()은 중단된 프로세스만 재개. ● 만약 중단된 프로세스가 없다면, signal연산은 아무런 변화 없음.

1. 교착 상태의 정의와 사용 예  교착 상태 시스템 자원을 사용하기 위해 경쟁하거나 상호간에 Section 4 교착상태 1. 교착 상태의 정의와 사용 예  교착 상태 시스템 자원을 사용하기 위해 경쟁하거나 상호간에 통신하는 프로세스들이 영구적으로 블록킹 된 상태.  일반적인 교착 상태의 정의. ● 하나 또는 둘 이상의 프로세스가 더 이상 계속할 수 없는 어떤 특정 사건을 기다리고 있는 상태. 여기서 특정 사건이란, 자원의 할당과 해제를 의미. ● 둘 이상의 서로 다른 프로세스가 자신이 요구한 자원을 할당받아 점유하고 있으면서, 상호간에 상대방 프로세스에 할당되어 있는 자원을 요구하는 경우.  비교 - 노화(aging) 기법 어떤 자원을 기다린 시간에 비례하여 프로세스에게 우선 순위를 부여하는 기법을 적용하는 방법으로서 무한 연기를 해결.

1. 교착 상태의 정의와 사용 예 그림 4-34 자원의 간단한 교착 상태 Section 4 교착상태 1. 교착 상태의 정의와 사용 예  각 프로세스는 자신에게 할당된 자원을 점유하고 있으면서, 상대방 프로세스의 자원을 요구하는 상태.  환형 대기(circular wait) 치명적인 포옹(deadly embrace). B 그림 4-34 자원의 간단한 교착 상태

2. 무한 연기와 에이징  무한 연기(indefinite postponement) Section 4 교착상태 2. 무한 연기와 에이징  무한 연기(indefinite postponement) ▶ 다중 프로그래밍 시스템에서 자원할당 및 CPU 스케줄링에 의해 하나의 프로세스를 선택하는 동안 다른 프로세스들을 기다리게 하는데, ▶ 이러한 상황에서 여러 다른 프로세스들이 시스템에서 스케줄링되어 처리되는 동안, 한 프로세스의 스케줄링이 무한 연기될 수 있는 현상. ● 무한 연기의 발생 원인 운영체제의 편중된 자원 할당정책 때문. ▶ 만약, 자원 할당정책이 우선순위에 의해 수행된다면, ▶ 자신보다 높은 우선순위의 프로세스가 계속 도착하여 자원을 할당 받게 되므로, 우선순위가 낮은 프로세스는 그 자원을 무기한으로 기다림.

2. 무한 연기와 에이징 ● 무한 연기 문제 방지 : 노화(aging) 기법 사용 Section 4 교착상태 2. 무한 연기와 에이징 ● 무한 연기 문제 방지 : 노화(aging) 기법 사용 ▶ 오랫동안 대기한 프로세스의 우선 순위가, 새로 도착하는 다른 모든 프로세스 보다 높아져서 먼저 자원을 할당 받게 함. 무한 연기 교착 상태 ∙어떤 특정 프로세스가 자원을 할당 받기 위해 무한정 기다리는 상태. ∙자원의 편중된 분배 정책 때문에 발생하며 노화 기법 (aging)에 의해 해결. ∙시스템에 있는 여러 개 또는 모든 프로세스가 아무 일도 못하고 어떤 특정 사건을 기다리며, 무기한 연기되어 있는 상태. ∙상호배제, 점유와 대기, 비 선점, 환형대기와 같은 조건에 의해 발생하며 이를 부정함으로써 해결.

3. 교착 상태 발생의 4가지 필요조건 1) 상호 배제 조건 (mutual exclusion) Section 4 교착상태 3. 교착 상태 발생의 4가지 필요조건 1) 상호 배제 조건 (mutual exclusion) 프로세스들이 자원을 배타적으로 점유하고 있어, 다른 프로세스들이 자원을 사용할 수 없도록 만듬. ● 프로세스들이 그들이 필요한 자원에 대해 배타적인 제어권을 요구. ● 최소한 한 번에 한 프로세스만이 자원을 사용할 수 있으며, ● 다른 프로세스가 그 자원을 요구하면, 자원을 요구한 다른 프로세스는 자원이 해제될 때까지 임계구역 바깥에서 대기.

3. 교착 상태 발생의 4가지 필요조건 2) 점유와 대기조건 (hold and wait) Section 4 교착상태 3. 교착 상태 발생의 4가지 필요조건 2) 점유와 대기조건 (hold and wait) 부분 할당이라 고도 하는데, 프로세스들은 동일한 자원이나 다른 종류의 자원을 부가적으로 요구하면서, 이미 어떤 자원을 점유하고 있음. ● 프로세스가 자신에게 이미 할당된 자원들을 점유하고 있으면서, 다른 자원을 추가로 요구하여 기다리고 있음. ● 최소한 하나의 자원을 점유하고 있는 프로세스가 존재해야 하며, ● 이 프로세스는 다른 프로세스에 할당된 자원을 추가로 점유하기 위해 대기.

3. 교착 상태 발생의 4가지 필요조건 3) 비 선점 조건 (non-preemption) Section 4 교착상태 3. 교착 상태 발생의 4가지 필요조건 3) 비 선점 조건 (non-preemption) 자원들은 그들을 점유하고 있는 프로세스로부터 도중에 해제되지 않음. 단지 프로세스들 자신이 점유한 자원을 해제할 수 있음. ● 프로세스에게 일단 할당된 자원을 모두 사용하기 전에는, 그 프로세스로부터 도중에 회수할 수 없음. ● 자원들은 선점하지 못하며, 점유하고 있는 프로세스에 의해 타스크를 종료한 후에 해제할 수 있음.

3. 교착 상태 발생의 4가지 필요조건 4) 환형 대기 조건 (circular wait) Section 4 교착상태 3. 교착 상태 발생의 4가지 필요조건 4) 환형 대기 조건 (circular wait) 프로세스와 자원들이 원형을 이루며, 각 프로세스는 자신에게 할당된 자원을 가지면서, 상대방 프로세스의 자원을 상호요청하는 경우. ● 대기하고 있는 프로세스 집합 P0, P1, ..... Pn에서 P0는 P1이 점유한 자원을 대기하고 있고, P1은 P2를 대기하고, Pn-1은 Pn을 대기하며, Pn은 P0가 점유한 자원을 대기. ● 사이클 형성

4. 교착상태의 연구분야 1) 교착 상태의 예방  교착 상태의 예방(deadlock prevention) Section 4 교착상태 4. 교착상태의 연구분야 1) 교착 상태의 예방  교착 상태의 예방(deadlock prevention) ● 교착 상태의 발생 가능성을 사전에 모두 제거하도록 시스템을 조절  교착 상태 예방은 교착 상태 발생 필요조건의 4가지중 하나를 부정함으로써 수행.  Havender가 제시한 방안 ● 사전에 교착 상태의 가능성을 없애는 것으로, ● 4가지 교착 상태 발생 필요 조건을 만족하지 않게 하는 것.

4. 교착상태의 연구분야 1) 교착 상태의 예방 (1) 점유와 대기조건의 부정 Section 4 교착상태 4. 교착상태의 연구분야 1) 교착 상태의 예방 (1) 점유와 대기조건의 부정  각 프로세스는 필요한 자원들을 모두 한꺼번에 요청하고 ● 시스템은 요청된 자원들을 분석하여 한 프로세스가 요구한 자원을 전부 할당하여 주든지, ● 또는, 하나라도 부족하면 전혀 할당하지 않든지 하는 방식으로 자원을 할당하는 방법.  프로세스는 일시에 요구한 모든 자원 중에서 ● 원하는 자원이 사용가능하지 않아 할당되지 않을 때는, ● 그 프로세스는 자원이 사용가능 해질 때 까지 기다려야 하며, ● 이때, 기다리는 동안 아무 자원도 가지고 있을 수 없음.

4. 교착상태의 연구분야 1) 교착 상태의 예방 (1) 점유와 대기조건의 부정 ● 장점 ● 단점 Section 4 교착상태 ▶ 프로세스들이 자원을 기다리고 있는 동안은, ▶ 아무 자원도 점유하고 있지 않으므로, ▶ 점유와 대기 조건이 부정되며, 교착 상태도 발생하지 않음. ● 단점 ▶ 자원 낭비와 비용 증가를 초래. ▶ 자원 공유 불가. ▶ 자원이 부족한 상태에서 필요한 자원 모두가 동시에 사용 가능하지 않을 수도 있기 때문에, 어떤 프로세스는 끝내 필요로 하는 자원을 모두 얻지 못하는 문제가 발생(무한 연기 문제).

4. 교착상태의 연구분야 1) 교착 상태의 예방 (2) 비선점 조건의 부정  만일, 어떤 자원을 갖고 있는 프로세스가 Section 4 교착상태 4. 교착상태의 연구분야 1) 교착 상태의 예방 (2) 비선점 조건의 부정  만일, 어떤 자원을 갖고 있는 프로세스가 ● 더 이상의 자원 할당 요구가 받아 들여지지 않으면, ● 원래 가지고 있던 자원을 일단 반납하고, ● 필요하다면 다시 그 자원이나 다른 자원을 요구하도록 함.  이미 자원을 가지고 있으면서 추가 자원 요구를 거절당한 프로세스로 하여금, ● 가지고 있는 모든 자원을 내놓고, ● 필요한 경우 다시 추가 자원까지를 요구하도록 함으로써 ● 비선점 조건을 방지하는 방법.

4. 교착상태의 연구분야 1) 교착 상태의 예방 (2) 비선점 조건의 부정 Section 4 교착상태 4. 교착상태의 연구분야 1) 교착 상태의 예방 (2) 비선점 조건의 부정  어느 시점에서 어떤 자원을 사용하고 있던 프로세스가 ● 일단 이 자원들을 반납하게 되면, 더 이상 진행할 수가 없으므로 ● 현 시점까지 수행한 모든 작업이 수포로 돌아갈 수도 있음.  문제점 ● "얼마나 자주 이러한 자원 반납을 행해야 하는가"하는 점(비용 증가의 원인). ● 무한 연기가 발생할 가능성이 있다는 점(시간 낭비의 원인). ● 자원을 모두 얻지 못하는 상태가 발생할 수 있으며, 특수한 자원을 사용할 때만 적용가능.

4. 교착상태의 연구분야 1) 교착 상태의 예방 (3) 환형대기 조건의 부정 Section 4 교착상태 4. 교착상태의 연구분야 1) 교착 상태의 예방 (3) 환형대기 조건의 부정  모든 프로세스에게 각 자원의 유형별로 할당순서를 부여.  만일, 한 프로세스가 주어진 유형의 모든 자원을 할당 받았으면, 그 프로세스는 자원의 할당 순서에 따라 나중에 위치하는 유형의 자원만을 요구할 수 있게 함. ● 시스템 설치 시 모든 자원에게 고유번호를 부여 ● 프로세스들이 자원을 요청할 때에는 번호가 증가하는 순으로 요청. ● 추가로 요청하는 경우에도, 현재 가지고 있는 자원보다 더 큰 번호를 가진 자원만을 요청하도록 제한하는 방법.

Section 4 교착상태 1) 교착 상태의 예방 (3) 환형대기 조건의 부정 그림 4-35 순서화에 의한 자원의 요구

● 급한 프로그램이 발생시 자원 할당에 어려움이 발생. Section 4 교착상태 1) 교착 상태의 예방 (3) 환형대기 조건의 부정  문제점 ● 자원에 번호를 부여할 때 실제로 프로세스가 실행 중에 자원을 사용하는 순서를 반영할 수 있어야 함. ● 새로운 자원이 시스템에 추가되면, 현존하는 프로그램과 시스템을 재 구성해야 함. ● 급한 프로그램이 발생시 자원 할당에 어려움이 발생.

4. 교착상태의 연구분야 1) 교착 상태의 예방 (4) 상호 배제 조건 부정  상호 배제 조건은 비 공유를 전제. Section 4 교착상태 4. 교착상태의 연구분야 1) 교착 상태의 예방 (4) 상호 배제 조건 부정  상호 배제 조건은 비 공유를 전제.  공유 가능한 자원들은 배타적인 접근을 요구하지 않으므로 교착 상태로 될 수 없음.  상호 배제 조건은 공유할 수 없는 자원들의 사용시에 이루어 져야 함. ● 프린터 등은 이에 해당하지만 기억 장치나 CPU는 공유할 수 있는 자원이며 상호 배제 조건을 따르지 않아도 됨. ● 이 방법은 공유가능 자원 할당 시에만 가능

은행가 알고리즘(banker's algorithm). Section 4 교착상태 4. 교착상태의 연구분야 2) 교착 상태의 회피  시스템의 운영 중 상황을 보아가면서 교착 상태 가능성을 피해가는 것. 은행가 알고리즘(banker's algorithm). (1) 안전 상태와 불안전 상태  안전(safe) 상태 ● 시스템이 특정한 순서대로 각 프로세스에게 자원을 할당할 수 있고, ● 교착 상태를 방지할 수 있으면 안전한(safe) 상태. ● 결국 모든 작업이 완료될 수 있는 상태.  불안전(unsafe) 상태 ● 교착 상태가 발생할 수 있는 상태. ● 불 안전 상태라고 해서 모두가 교착 상태는 아니며, ● 불 안전 상태는 교착 상태로 될 수 있음.

2) 교착 상태의 회피 (1) 안전 상태와 불안전 상태  시스템의 3가지 상태 공간 Section 4 교착상태 그림 4-36 안전, 불안전, 교착 상태의 공간

a는 t 개에서 각 사용자 프로세스의 총 할당량을 뺀 값. Section 4 교착상태 2) 교착 상태의 회피 (2) 안전 상태와 불안전 상태 예  t개의 동일 유형의 테이프 구동기 자원을, u개의 사용자 프로세스들 사이에 공유. ● a : 할당할 수 있는 잔여량. a는 t 개에서 각 사용자 프로세스의 총 할당량을 뺀 값.  l(i) : 사용자 i의 현재 할당량. ● 사용자 2가 4대의 테이프 구동기를 할당 받았다면 l(2) = 4.  m(i) : 사용자 i의 최대 요구량. ● 사용자 2가 최대 8대의 테이프 구동기를 요구했다면 m(2) = 8.  c(i) : 사용자 i의 추가 요구량 ● 총 12대의 테이프 구동기에서, 사용자 2가 최대 8대의 테이프 구동기를 요구하여, 현재 4대를 할당 받았다면, ● 사용자 2의 추가 요구량 c(2) = m(2) - l(2) = 8 - 4 = 2 ● 잔여량 a = t - 총 할당량 = 12 - 4 = 8.

요구량 > 잔여량 -→ 대기 : 할당량 = 할당량 + 요구량 Section 4 교착상태 2) 교착 상태의 회피 (2) 안전 상태와 불안전 상태 예  안전 상태의 예 ● 요구량 > 필요량 -→ error : 잔여량 = 잔여량 - 요구량 요구량 > 잔여량 -→ 대기 : 할당량 = 할당량 + 요구량 요구량 < 잔여량 -→ 할당: 필요량 = 필요량 - 요구량 ● 3개의 프로세스, 총 자원이 12개. 현재 할당량은 10개, 잔여량은 2개. 프로세스 현재 할당량 최대 요구량 추가 요구량 프로세스 1 2 5 3 프로세스 2 4 6 프로세스 3 8 그림 4-37 시스템의 안전 상태 예

2) 교착 상태의 회피 (2) 안전 상태와 불안전 상태 예  불 안전 상태의 예 현재 할당량은 11개, 잔여량은 1개. Section 4 교착상태 2) 교착 상태의 회피 (2) 안전 상태와 불안전 상태 예  불 안전 상태의 예 ● 3개의 프로세스, 총 자원이 12개. 현재 할당량은 11개, 잔여량은 1개. 프로세스 현재 할당량 최대 요구량 추가 요구량 프로세스 1 6 9 3 프로세스 2 5 프로세스 3 2 4 그림 4-38 시스템의 불안전 상태 예

2) 교착 상태의 회피 (2) 안전 상태와 불안전 상태 예  안전 상태에서 불안전 상태로의 전이 Section 4 교착상태 2) 교착 상태의 회피 (2) 안전 상태와 불안전 상태 예  안전 상태에서 불안전 상태로의 전이 ● 3개 프로세스, 총 자원 12개. 현재 할당량 10개, 잔여량 2개. ● [그림 4-39] 시스템의 상태는 프로세스2에 추가 요구량을 할당할 수 있으므로 안전 상태. ● 프로세스 3에 추가 요구량 4대 중 잔여량 2대를 할당한다면, 어떤 프로세스도 종료할 수 없게 되어 다음과 같이 불안전 상태로 전이. 프로세스 현재 할당량 최대 요구량 추가 요구량 프로세스 1 2 5 3 프로세스 2 4 6 프로세스 3 8 그림 4-40 안전 상태에서 불안전 상태로의 전이 예

Section 4 교착상태 2) 교착 상태의 회피 (3) 은행가 알고리즘 ● n : 시스템의 프로세스 수, m : 자원 형태의 수 (1) Available : 각 자원 별로 사용 가능한 자원의 수 표시, m인 벡터. Available[j] = k라면, 자원 형태 R j이 k개 있다는 의미.(잔여량) (2) Max : 각 프로세스의 최대 자원의 요구량 표시, n x m 행렬. Max[i,j] = k라면, 프로세스 P i 는 자원 형태 R j 를 최대 k개까지 요구할 수 있다는 의미.(최대 요구량) (3) Allocation : 현재 각 프로세스에게 할당되어 있는 자원의 수를 정의하는 n x m 행렬. Allocation[i,j] = k.(현재 할당량) (4) Need : 각 프로세스의 자원의 추가 요구를 표시, n x m 행렬. Need[i,j] = k라면, 프로세스 P i 는 자원형태 R j 를 추가로 k개 더 필요로 한다는 의미.(추가요구량, 필요량)

(1) Request i ≤ Need i 라면 (2)단계로 감. 그렇지 않으면 최대 요구량을 초과하기 때문에 오류 상태 Section 4 교착상태 2) 교착 상태의 회피 (3) 은행가 알고리즘 ● Request i : 프로세스 Pi를 위한 요청 벡터. ● 만약, Request i[j] = k라면 프로세스 P i 는 Rj형 자원을 k개 요구. ● 프로세스 P i 가 자원을 요청하면 다음 조치를 취함. (1) Request i ≤ Need i 라면 (2)단계로 감. 그렇지 않으면 최대 요구량을 초과하기 때문에 오류 상태 (요구량 > 필요량--→ error) (2) Request i ≤ Available 라면 (3)단계로 감. 그렇지 않으면 자원이 부족하기 때문에 대기 (요구량 > 잔여량(남은 자원)--→ 대기 ) (3) 시스템은 다음과 같이 요구된 자원들을 프로세스에게 할당함. 잔여량 = 잔여량 - 요구량 (Available = Available - Request i) 할당량 = 할당량 + 요구량 (Allocation i = Allocation i + Request i) 필요량 = 필요량 - 요구량 (Need i = Need i - Request i)

(1) Work, Finish를 각각 길이가 m, n인 벡터라고 하면, Section 4 교착상태 2) 교착 상태의 회피 (3) 은행가 알고리즘  안전 알고리즘 ● 시스템이 안전 상태인지를 발견하는 알고리즘 (1) Work, Finish를 각각 길이가 m, n인 벡터라고 하면, 초기화: Work = Available로 Finish[i] = false, i = 1, 2, 3,....n Work는 남아 있는 자원수인 Available의 임시변수. (2) 다음과 같이 되는 i값을 찾음. a. Finish[i] = false b. Need i < Work 만약, 이러한 i 값이 있으면 (3)단계로 가고, 없으면 (4)단계로 감. (3) 자원을 할당한 후 해제. Work = Work + Allocation i Finish[i] = true, (2)단계로 감. (4) 모든 i에 대하여 Finish[i] = true이면 시스템은 안전 상태.

그림 4-41 시간 t0에 시스템의 상태 2) 교착 상태의 회피 (4) 은행가 알고리즘 예제 Section 4 교착상태 상태 ● P0부터 P4까지 5개의 프로세스 P0, P1,...P4와, 3개의 자원 형태 A, B, C를 가진 시스템. ● 자원 형태는 A =10개, B = 5개, C = 7개. ● 시간 t0에 시스템의 상태가 다음 그림과 같다고 가정. 상태 프로세스 Allocation Max Available A     B     C A     B     C  P0 P1 P2 P3 P4 0     1     0 1     0     0 3     0     2 3     1     1 0     0     2 6     5     3 2     2     2 9     0     2 3     2     2 3     2     3 3     3     2 그림 4-41 시간 t0에 시스템의 상태

그림 4-42 Need 행렬 2) 교착 상태의 회피 (4) 은행가 알고리즘 예제 Max - Allocation으로 정의, Section 4 교착상태 2) 교착 상태의 회피 (4) 은행가 알고리즘 예제 ● 행렬 Need의 내용은 다음 그림과 같이 Max - Allocation으로 정의, ● 이 시스템은 <P1, P3, P4, P2, P0> 순서가 안전 조건을 충족하므로 현재 안전 상태.          상태 프로세스 Need A B C P0 P1 P2 P3 P4 6 1 3 4 2 그림 4-42 Need 행렬

그림 4-43 새로운 시스템 상태 (4) 은행가 알고리즘 예제 Section 4 교착상태 상태 프로세스 Allocation ● 프로세스 P1은 자원형태 A의 자원을 1개, C의 자원을 2개 더 요청하여 Request i = (1, 0, 2)라고 가정. ● 이 요청이 즉시 허용될 수 있는지 여부를 결정하기 위하여, 먼저 Request i ≤ Available 즉, (1, 0, 2)≤(3, 3, 2)인지를 검사. (TRUE) , 이 요청이 충족되어 다음과 같은 새로운 상태에 도달. ● 안전알고리즘 실행, <P1, P3, P4, P2, P0> 순서가 안전 조건을 충족하므로 현재 안전 상태.          상태 프로세스 Allocation Max Available A     B     C A     B     C  P0 P1 P2 P3 P4 0     1     0 2     0     2 3     0     2 3     1     1 0     0     2 6     4     3 0     2     0 6     0     0 0     1     1 3     2     1 2     3     0 그림 4-43 새로운 시스템 상태

2) 교착 상태의 회피 (4) 은행가 알고리즘 예제  은행가 알고리즘의 단점 Section 4 교착상태 ● 이제, 새로운 시스템의 상태가 안전한지를 결정해야 함. ● 안전 알고리즘을 실행하여 <P1, P3, P4, P0, P2> 순서가 안전 요구를 충족하는 것을 발견할 수 있음. ● 따라서, 즉시 프로세스 P1의 요구를 허락. ● 그러나, 시스템이 이 상태에 있을 때는 P4가 (3, 3, 0)을 요청하면 자원이 부족하기 때문에 허용할 수 없다는 것을 알 수 있음. ● P0가 (0, 2, 0)을 요청하면 자원이 충분하더라도 결과로 얻어지는 상태가 불 안전하기 때문에 허용할 수 없음.  은행가 알고리즘의 단점 ● 할당할 자원이 일정량 존재해야 함. ● 각 프로세스의 최대 자원 요구량을 미리 알아야 함. ● 일정한 수의 사용자 프로세스가 있을 때만 적용할 수 있음. ● 프로세스들은 유한한 시간 내에 할당된 자원을 반납해야 함.

4. 교착상태의 연구분야 3) 교착 상태의 발견 Section 4 교착상태 ● 시스템의 운영 중에 교착 상태가 일어났는지를 결정하고 교착 상태에 관련된 프로세스와 자원을 발견하는 것. ● 프로세스와 자원간에 순환적 "요구"와 "할당" 관계에 있는 것을 규명하는 것. ● 자원 할당 그래프의 소거와 교착 상태 발견 알고리즘이 있음.

4. 교착상태의 연구분야 4) 교착 상태의 회복  교착 상태를 회복하는 2가지 방법. Section 4 교착상태 ● 시스템이 교착 상태에 빠지면, 교착 상태는 하나 또는 그 이상의 교착 상태 필요조건을 제거함으로써 회복. ● 보통 하나 또는 그 이상의 프로세스를 시스템으로부터 제거하여 그들의 자원을 빼앗아 다른 프로세스가 사용할 수 있도록 함. ● 회복은 몇 개의 프로세스들이 수행한 작업의 일부 또는 전부를 잃게 됨.  교착 상태를 회복하는 2가지 방법. ● 환형 대기를 없애기 위하여 단순하게 한 개 이상의 프로세스를 중지. ● 교착 상태의 프로세스로 부터 자원을 선점.

(1) 교착 상태 프로세스들을 모두 중지 하는 방법 Section 4 교착상태 4) 교착 상태의 회복 (1) 프로세스 중지 (1) 교착 상태 프로세스들을 모두 중지 하는 방법 ● 이 방식은 교착 상태에 빠진 모든 프로세스를 중지하는 방식. ● 확실하게 교착 상태의 사이클을 제거하지만 비용이 많이 듬. ▶ 그 이유: 우선 이들은 오랜 시간동안 연산했을 가능성이 있으며, 현재까지 수행한 부분 결과들을 모두 잃어 버리며, 나중에 다시 재 연산을 해야 하기 때문. (2) 교착 상태가 해결될 때까지 한 프로세스씩 중지 ● 이 방식은 교착 상태에 빠진 프로세스들 중에서 한 프로세스씩 차례로 중지시켜 가면서 해결하는 방식. ● 매번 각 프로세스가 중지될 때 마다 교착상태 발견 알고리즘을 호출하여 프로세스들이 아직도 교착 상태에 있는지 확인하므로 부담이 큼.

(1) 프로세스 중지 (3) 희생자 선택의 원칙 최소의 비용으로 중지시키는 방법을 찾아야 함.  희생자 선정 시 고려사항 Section 4 교착상태 (1) 프로세스 중지 (3) 희생자 선택의 원칙 ● 프로세스를 중지시키는데 있어서 기본적으로 최소의 비용으로 중지시키는 방법을 찾아야 함. ● 최소 비용의 원칙으로 희생자(victim) 프로세스를 선정.  희생자 선정 시 고려사항 ● 프로세스들의 우선순위 ● 얼마나 오래 동안 프로세스를 수행할 것인가(지금까지 프로세스가 수행된 시간과 작업을 종료하는데 필요한 시간) ● 프로세스가 어느 종류의 자원을 얼마나 많이 사용할 것인가(프로세스가 사용한 자원 유형과 자원의 수) ● 프로세스가 작업종료 위하여 얼마나 더 많은 자원을 필요로 하는가(더 필요한 자원의 수) ● 복귀하는데 얼마나 많은 프로세스가 포함되어 있는가(종료하는데 필요한 프로세스 수) ● 프로세스가 대화 식인지 일괄처리 식인지의 여부

4. 교착상태의 연구분야 4) 교착 상태의 회복 (2) 자원 선점  자원의 선점 시 해결해야 할 3가지 사항 Section 4 교착상태 4. 교착상태의 연구분야 4) 교착 상태의 회복 (2) 자원 선점 ● 프로세스로부터 자원들을 선점하여,이들 자원을 교착 상태가 해결될 때까지 다른 프로세스들에게 할당.  자원의 선점 시 해결해야 할 3가지 사항 1) 희생자 선정 2) 복귀(rollback) 문제 3) 기아 상태 문제

4) 교착 상태의 회복 (2) 자원 선점 Section 4 교착상태  희생자 선정 ● 교착 상태에 놓인 프로세스들을 회복시키기 위하여, 어느 자 원을 선점시키고, 어느 프로세스를 희생시킬 것인가를 결정. ● 프로세스 중지에서와 같이 비용을 최소화하기 위하여, 자원 선점의 순서 결정. ● 비용 요인으로는 교착 상태 프로세스가 점유하고 있는 자원의 수나, 교착 상태 프로세스가 지금까지 실행하는데 소요한 시간 등의 매개변수

4) 교착 상태의 회복 (2) 자원 선점  복귀(rollback) 문제 Section 4 교착상태 ● 시스템의 안전 상태가 어떤 것인지를 결정하기 어렵기 때문에, 가장 단순한 방법은 완전 복귀(total rollback) 방법 즉, 그 프로세스를 완전히 취소한 후 중지시키고 처음부터 다시 재시작하는 방법. ● 맨 처음으로 완전 복귀시키는 것은 대가가 크므로, 보다 효과적인 방법은 시스템이 실행하는 모든 프로세스에 대한 정보를 유지하여, 단지 교착 상태를 벗어날 정도로 프로세스를 복귀시킴.

4) 교착 상태의 회복 (2) 자원 선점  기아 상태 문제 Section 4 교착상태 ● 자원들이 항상 동일한 프로세스로 부터 선점된다면, 기아 상태(starvation)가 발생할 수 있음. ● 희생자의 선택을 기본적으로 비용의 감소에만 국한하여 선정할 경우, 같은 프로세스가 반복적으로 희생자로 선정될 수 있는 가능성. ● 그 결과 이 프로세스는 결코 자신의 타스크를 완료하지 못하는 기아 상태에 있게 됨. ● 이러한 사항에 대한 해결 방안으로 희생자 반복 선택 횟수의 상한선을 정하여 프로세스를 복귀하도록 하여 해결.

▶ 숙련된 조작자의 주의를 요하는 것이 대부분이나, ▶ 그러한 조작자가 항상 있는 것은 아님. Section 4 교착상태 4) 교착 상태의 회복 (3) 교착 상태 회복의 문제점 ● 시스템이 교착 상태인지를 알기가 어려움. ● 대부분의 시스템은 프로세스를 무기한 정지시키고, 이를 시스템에서 제거한 후, 다음에 다시 계속하도록 하는 기능이 거의 없음. ● 설사 효율적인 중단/재시작 기능이 있다 하더라도, ▶ 그것들은 상당한 추가 부담이 필요하며, ▶ 숙련된 조작자의 주의를 요하는 것이 대부분이나, ▶ 그러한 조작자가 항상 있는 것은 아님. ● 소규모의 교착 상태로부터 회복도 많은 일을 필요로 하며, ▶ 대규모의 교착 상태로 일 경우에는 더 많은 양의 일이 필요. ● 최적의 프로세스를 선택하여 제거하기 위한 결정이 현실적으 로 어려움.