2011년도 운영체제 1학기 프로그램 과제 #3

<은행 알고리즘>

1. 알고리즘

은행원 알고리즘

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 이면, 시스템은 안전한 상태이다

2. 입력

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

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

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

4) 입력값

Allocation : 0 0 1 0 1 2 0 0 2 3 0 2 3 2 1 1 4 0 0 2

Max	: 0 7 5 3 1 3 2 2 2 9 0 2 3 2 2 2 4 4 3 3

Available  : 3 3 2

5) 입력된 값 출력

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

3. 출력

1) 시스템은 안전한 상태인가?

그렇다. 순서 <P1, P3, P4, P2, P0>은 safety requirement를 만족한다.

2) 프로세스 P1으로부터의 자원 요청이 (1 0 2) 와 같다면 이 요청은 바로 수락이 되는가?

그렇다. 아래와 같은 이유로 가능하다.

a. (1, 0, 2) <= Available = (3, 3, 2)

b. (1, 0, 2) <= Maxi = (3, 2, 2)

c. 할당 후의 변화된 시스템의 상태는 다음과 같다.

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

d. 순서 <P1, P3, P4, P0, P2> safety requirement를 만족한다.

3) “Y”를 누르면 계속하고, 아니면 “N”을 입력한다.

*예제:

Allocation	Max	Available

A  B  C  D	A  B  C  D	A  B  C  D

p0	0  0  1  2	0  0  1  2	1  5  2  0

p1	1  0  0  0	1  7  5  0

p2	1  3  5  4	2  3  5  6

p3	0  6  3  2	0  6  5  2

p4	0  0  1  4	0  6  5  6

1) 시스템은 safe 상태인가?

그렇다. 순서 <P0, P2, P1, P3, P4> 는 safety requirement를 만족한다.

2) 프로세스 P1으로부터의 자원 요청이 (0 4 2 0) 와 같다면 이 요청은 바로 수락이 되는가?

그렇다. 아래와 같은 이유로 가능하다.

a. (0, 4, 2, 0) <= Available = (1, 5, 2, 0)

b. (0, 4, 2, 0) <= Maxi = (1, 7, 5, 0)

c. 할당 후의 변화된 시스템의 상태는 다음과 같다.

Allocation	Max	Need	Available

A  B  C  D	A  B  C  D	A  B  C  D	A  B  C  D

p0	0  0  1  2	0  0  1  2	0  0  0  0	1  1  0  0

p1	1  4  2  0	1  7  5  0	0  3  3  0

p2	1  3  5  4	2  3  5  6	1  0  0  2

p3	0  6  3  2	0  6  5  2	0  0  2  0

p4	0  0  1  4	0  6  5  6	0  6  4  2

d. 순서 <P0, 01, P2, P3, P4> 는 safety requirement를 만족한다.

4. 지침

1) 첫 시작시 메뉴를 이용하여 입력하게 한다,

2) 입력된 데이터가 올바른 것인지 검사해야 한다.

5. 개발 환경

a. Platform : Windows

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

6. 제출 마감 기한

- 6월 7일 (화) 13:00까지

7. 인원

- 개인별

8. 제출 방식

- 소스와 실행 파일, 문서 파일을 압축하여 “Homework3_학번_이름”으로 ftp://163.180.116.80 (ID :　os, PW : ospw)의 "Homework 3" 폴더에 업로드

2011 Spring OS Homework #3

<Implementation for Banker’s algorithm>

1. Algorithm

Banker’s Algorithm:

Step 1. If Requesti <= Needi, go to step 2. Otherwise, raise and error condition.

Step 2. If Requesti <= Available, go to step 3. Otherwise, Process i (Pi) must wait.

Step 3. The system pretends to have allocated the requested resources to process Pi by modifying the state as follows:

Available := Available – Requesti

Allocationi := Allocationi + Requesti

Needi := Needi – Requesti;

Safety Algorithm:

Step 1. Let Work and Finish be vectors of length m and n, respectively.

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

Step 2. Find an i such that both

a. Finish[i] = False

b. Needi <= Work

If no such I exists, go to step 4

Step 3. Work := Work + Allocationi

Finish[i] := True

go to step 2.

Step 4. If Finish[i] = True for all i, then the system is in a safe state.

2. Program inputs

1) How many processes in the system? 5 ( 2 <= number of processes <= 99 )

2) Type of resources? A B C ( 2 <= number of resources <= 99 )

3) Number of resources for each type : 10 5 7

4) Please key in snapshot of the system:

Allocation : 0 0 1 0 1 2 0 0 2 3 0 2 3 2 1 1 4 0 0 2

Max	: 0 7 5 3 1 3 2 2 2 9 0 2 3 2 2 2 4 4 3 3

Available  : 3 3 2

5) Echo print

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

3. Program outputs

1) Is the system in a safe state?

Answer : Yes, the sequence <P1, P3, P4, P2, P0> satisfies the safety requirement.

2) If a request from process P1 arrives for (1 0 2) can the request be granted immediately?

Answer : Yes, Since

a. (1, 0, 2) <= Available = (3, 3, 2)

b. (1, 0, 2) <= Maxi = (3, 2, 2)

c. The new system state after the allocation is made is

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

d. The sequence <P1, P3, P4, P0, P2> satisfies the safety requirement

3) Press “Y” key to continue, otherwise press “N”.

*Example:

Allocation	Max	Available

A  B  C  D	A  B  C  D	A  B  C  D

p0	0  0  1  2	0  0  1  2	1  5  2  0

p1	1  0  0  0	1  7  5  0

p2	1  3  5  4	2  3  5  6

p3	0  6  3  2	0  6  5  2

p4	0  0  1  4	0  6  5  6

1) Is the system in a safe state?

Answer : Yes, the sequence <P0, P2, P1, P3, P4> satisfies the safety requirement

2) If a request from process P1 arrives for (0, 4, 2, 0) can the request be granted immediately?

Answer : Yes. Since

a. (0, 4, 2, 0) <= Available = (1, 5, 2, 0)

b. (0, 4, 2, 0) <= Maxi = (1, 7, 5, 0)

c. The new system state after the allocation is made is

Allocation	Max	Need	Available

A  B  C  D	A  B  C  D	A  B  C  D	A  B  C  D

p0	0  0  1  2	0  0  1  2	0  0  0  0	1  1  0  0

p1	1  4  2  0	1  7  5  0	0  3  3  0

p2	1  3  5  4	2  3  5  6	1  0  0  2

p3	0  6  3  2	0  6  5  2	0  0  2  0

p4	0  0  1  4	0  6  5  6	0  6  4  2

d. The sequence <P0, 01, P2, P3, P4> satisfies the safety requirement

4. Guild Line

1) Try to standard input with menu driven format

2) Your input statement must check data validation

5. Developing environment

a. Platform : Windows

b. Development Language : Java, C/C++(MFC or Console)

6. Due date

- June 7th (THU) 13:00

7. The number of people

- by individual

8. How to submit

- Compress the source file and the execution file like "Homework3_studentID_Name" and upload it to folder “Homework 3” in ftp://163.180.116.80 (ID :　os, PW : ospw)