2012년도 운영체제 1학기 과제 #3

<은행 알고리즘>

1. 목적

은행 알고리즘(Banker’s Algorithm)을 구현해 봄으로써, 데드락을 회피하는 응용 방법을 파악하고 이론에 대한 이해를 향상한다.

2. 입력

사용자에 의한 입력
- 프로세스의 개수 (단, 프로세스의 개수는 5이상 20이하)

- 자원의 이름 (예 : A, B, C ...) (단, 자원의 개수는 2이상 5이하)

- 각 프로세스의 자원 할당량 Random으로 할당

- Random으로 임의의 프로세스가 자원 요청 후 세이프 알고리즘이 있는지 확인

3. 출력
- 시스템이 safety requirement를 만족하는 지 여부와 만족할 경우의 프로세스 순서

-> 시스템은 순서 예) <P1, P3, P4, P2, P0>은 safety requirement를 만족

4. 개발 환경

a. Platform : Windows

b. Dev. Language : C++(MFC 사용 권장-Console도 무방함)

5. 제출 마감 기한
- 05월 29일 (화) 23:59 까지

6. 인원

개인 별로 진행

7. 제출 방식

소스와 실행 파일, 문서 파일을 압축하여 “Homework03_이름_학번.zip”로 파일을 만들고, 파일제목은 “Homework03_이름_학번”으로 하여 ftp://163.180.116.93 (ID :　os, PW : 1111)

8. 프로그램 설명

은행원 알고리즘

- 1단계. If Requesti <= Needi, 2단계로 이동. 그렇지 않으면, 에러 상태.
- 2단계. If Requesti <= availablei, 3단계로 이동. 그렇지 않으면, Process i (Pi)는  wait.
- 3단계. 시스템은 아래와 같이 상태를 바꿔서 Pi가 요청한 자원을 할당했다고 가정한다.

Available := Available – Request;

Allocation := Allocation + Request;

Needi := Needi – Requesti;

Safety Algorithm

- 1단계. Work와 Finish를 벡터 길이 m과 n이라 하자.

Initialize Work := Available and Finish[i] := False for i = 1, 2, ..., n.

- 2단계. i가 다음 a,b 조건을 동시에 만족하는지 찾는다.

a. Finish[i] = False

b. Needi <= Work

이러한 조건을 만족하는 i가 없다면, 4단계로 이동한다

- 3단계. Work := Work + Allocationi

Finish[i] := True

go to step 2.

- 4단계. If Finish[i] = True for all i 이면, 시스템은 안전한 상태이다

동작 예제

- 시스템에 몇 개의 프로세스가 존재하는가? 5 ( 2 <= 프로세스의 개수 <= 99 )

- 자원의 종류? A B C ( 2 <= 자원의 개수 <= 99 )

- 각각의 타입별 자원의 개수: 10 5 7

- 입력

다음을 입력하세요.
할당 가능량 : 3 3 2
Process 0의 할당량 : 0 1 0
Process 0의 최대 할당 가능량 : 7 5 3
Process 1의 할당량 : 2 0 0
Process 1의 최대 할당 가능량 : 3 2 2
...

- 출력

(초기상태)

Allocation	Max	Available

A  B  C	A  B  C	A  B  C

p0	0  1  0	7  5  3	3  3  2

p1	2  0  0	3  2  2

p2	3  0  2	9  0  2

p3	2  1  1	2  2  2

p4	0  0  2	4  3  3

순서 <P1, P3, P4, P2, P0>은 safety requirement를 만족

(알고리즘 동작 후)

Allocation	Max	Need	Available

A  B  C	A  B  C	A  B  C	A  B  C

p0	0  1  0	7  5  3	7  4  3	2  3  0

p1	3  0  2	3  2  2	0  2  0

p2	3  0  2	9  0  2	6  0  0

p3	2  1  1	2  2  2	0  1  1

p4	0  0  2	4  3  3	4  3  1

예) safety requirement <P1, P3, P4, P2, P0> 일때 Random으로 p3이 자원을 요청 해서 할당을 하여도 safety requirement가 만들어 지는 지를 출력