티스토리 뷰

728x90

1. 개요

  

   Operating System Concepts 9th Edition(8th==공룡책)의 7장 프로그래밍 문제로 은행원 알고리즘을 다중스레드 프로그램을 작성한다. 이번 과제에서는 은행원 알고리즘 중 자원 요청 알고리즘(Resource-Request Algorithm)으로 구현한다.

 


2. 개념 및 용어정리

  

 1. 은행원 알고리즘 : 프로세스가 자원들을 요청하면 시스템은 그것을 들어주었을 때 시스템이 계속 안전 상태에 머무르게 되는지 판단하고 안전하게 된다면 그 요청을 들어준다.

 
2. 자원 요청 알고리즘 : 은행원 알고리즘을 구현하는 방식 중 하나로 프로세스가 자원을 요청하면 우선적으로 남아있는 자원보다 같거나 작게 요청했는지 확인한 후 가상으로 자원을 할당해 준다. 이후 남은 자원을 가지고 시스템의 상태를 확인한 후 안전하면 가상으로 할당 했던 자원을 실제 프로세스에게 주고 불안전하다면 시스템으로 다시 반환한다.

 

3. 알리리즘 상의 용어

a. Available : 시스템에서 각 종류별로 가용한 자원의 개수이다.

b. Max : 각 프로세스가 최대로 필요로 하는 자원의 개수이다.

c. Allocation : 각 프로세스가 현재 할당 받은 자원의 개수이다.

d. Need : 각 프로세스가 향후 요청할 수 있는 자원의 개수이다.


 


3. 프로그램 시나리오 및 조건

  


1. 프로그램은 각각의 자원의 수와 동작 시간에 대한 값을 파라메터로 입력받는다.

2. 프로그램은 정해진 수만큼 Customer(프로세스)를 생성하며 Customer의 Max값은 maximum.txt 파일을 읽어 초기화 한다.

3. 각각의 Customer(프로세스)는 자원 요청과 자원 반환을 반복한다. 반복시 한번의 행위에 대해 프로그램에 정의해둔 시간이 증가한다. 

4. 자원 요청은 Customer(프로세스)의 필요한 자원 전체를 요청하는 것이 아니라 Random으로 값을 요청한다. 값은 현재 필요한 자원의 수를 넘을 수 없다.  

5. 요구한 자원의 수보다 사용 가능한 자원의 수가 작을 시 요구한 자원의 수를 남아 있는 자원의 수로 대체한다.

6. 정의된 시간이 입력받은 시간보다 커질 시 프로그램은 종료한다.

7. 책(문제)에는 0과 -1로 하라고 되어있지만, 함수에 대해 긍정적인 결과는 1, 부정적인 결과는 0으로 통일한다.



4. 프로그램 실행 결과

  


4. Source Code(1) - 전역변수, 메크로, 라이브러리 참조

  

1. limitTime : main함수의 입력 파라메터 중 이 프로그램이 돌아가는 총 시간(runtime)이 저장된다.
2. systemTime : 
Customer(프로세스)가 자원을 요청할 때마다 증가한다.

3. processNum : thread를 생성시 파라메터로 프로세스 번호를 넘기기 위해 추가하였다.

4. emptyResources : 가용할 자원의 수가 없는 자원의 개수를 저장한다. 

 


5. Source Code(2) - int main(int argc, char *argv[])

  

1. 메인 함수가 받은 파라메터인 3개의 자원의 각각의 자원량과 총 실행 시간을 저장한다.
2. Customer(프로세스)가 가지는 최대 자원 요구량 세팅한다.

3. Critical section인 자원에 대한 접근을 제한할 mutex를 설정한다.

4. Thread를 생성한다.

 


6. Source Code(3) - int init_ProcessSet(FILE* fp)

  

 Customer(프로세스)가 가지는 최대 자원 요구량이 저장되어 있는 파일(maximum.txt)을 읽고 각각의 프로세스의 Allocation, Max, Need값을 초기화 한다.

   maximum.txt


7. Source Code(4) - void *customer(void *processNum)

  

 Customer Thread를 구성하는 코드이다. 전역 변수인 systemTime의 수가 limitTime의 수보다 같거나 커질 때까지 sleep과 (release_resources)와 (request_resources) 중 조건에 맞는 것을 무한 반복한다. 조건은 모든 Resource의 필요량이 가득찼는지 아닌지로 결정된다.


8. Source Code(5) - request_resources(int pNum)

  

  Customer(프로세스)가 System에게 자원을 요구하는 함수이다. 

1. Critical Section인 자원에 접근을 하기 때문에 mutex를 걸어준다.  

2. SystemTime을 증가시킨다. 이후 요청할 각각의 자원의 크기를 Random으로 정한다. 

3. 실질적으로 system의 자원을 할당 받는 것이 아니라 가상의 자원을 만들어 안전한지 아닌지 확인한다. 

4. 확인 결과 안전하면 자원을 할당하고 불안전하면 회피한다.

5. mutex를 해제한다.



9. Source Code(6) - int checking_safety(int tmp_Allocation......)

  

  자원을 할당하였을 떄 시스템에 안전한지 아닌지 확인하는 함수이다. 함수의 주요 부분은 3중 for문으로 되어 있는 곳이다. 바깥쪽 2개의 for문은 하나의 Customer에 대해 모든 Customer를 확인하며 가장 안쪽 for문은 특정 Customer의 자원들을 확인한다.

1. 특정 Customer(프로세스)에 대해 남아있는 자원으로 일을 끝낼 수 있는지 확인한다.

2. 일을 끝낼 수 있으면 해당 프로세스의 현재 자원을 반환한다.

3. 반복문으로 다른 모든 프로세스가 끝낼 수 있는지 확인한다.



10. Source Code(7) - release_resources(int pNum)

  

  Customer(프로세스)가 System에게 자원을 반환하는 함수이다. 

1. Critical Section인 자원에 접근을 하기 때문에 mutex를 걸어준다.  

2. SystemTime을 증가시킨다. 

3. 자원을 반환한다.

4. mutex를 해제한다.



11. Full Source Code

  

   maximum.txt

'SoftWare > OS' 카테고리의 다른 글

OS - 8. Memory Management  (0) 2016.06.01
OS - 7. Deadlocks  (0) 2016.05.30
식사하는 철학자 문제(C언어)  (0) 2016.05.07
OS - 6. Process Synchronization (1)  (0) 2016.04.25
OS - 5. CPU Scheduling (2)  (0) 2016.04.23
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함