Linux에서 동작하는 가상의 Operation System
업데이트:
프로젝트 개요
OS에서 동작하는 각각의 요소(Process, Memory, Disk …)들을 활용하여 가상의 OS를 햄버거가게에 대입하여 햄버거가게 운영 프로그램을 구현한다.
구조
메인함수
메인함수 내에서 사용자 선택에 따라 여러 가지 함수가 호출되고 선택된 항목을 동작함. 프로그램 실행 시 메인함수의 매개변수인 입력파일을 입력하여 실행하게 됨.
변수
본 프로그램에서는 연결리스트를 이용한 큐를 중점으로 여러 가지 함수가 동작하도록 구현하였다.
변수에 대해서는 일부 변수만 조건을 지정하는 역할을 하고, 나머지 대부분 변수는 결과 값 출력을 위해 함수의 매개변수에 들어가는 값들이다.
큐
- Order: 주문 큐(FCFS)
- Making: 제조 큐(Round Robin)
- Delibery: 배달 큐(FCFS)
- Result: 결과 큐
- Page: 페이지 큐
- Disk: 디스크 큐
- Abox: 페이지 결과 값 출력 큐
- Bbox: 디스크 결과 값 출력 큐
함수
본 프로그램에서 다루는 함수들의 목록은 다음과 같다.
- PrintMenu: 메뉴 출력
- enQueue: 주문/제조/배달 큐 삽입
- deQueue: 주문/제조/배달 큐 삭제
- Input: 데이터 Read
- PrintGuest: 읽어온 데이터 출력
- PrintResult: 결과 값 저장
- Guest_info: 핵심 동작 함수. 이 함수 내부 while문 안에서 연산과 정의된 함수 호출이 반복됨
- Sort: 번호/도착시간 별로 정렬
- enQueue_IO: 페이지/디스크 큐 삽입
- deQueue_IO: 페이지/디스크 큐 삭제
- Insert_Page: 페이지 삽입
- PageSize_CK: 메인 메모리의 크기가 50을 초과하였는지 체크하여 LRU 동작
- Change: 페이지가 참조되면 LRU 구조에 따라 참조된 순으로 정렬
- PageCK: 재료의 수량이 0인 페이지 체크
- Insert_Dist: 수량이 0인 페이지를 디스크 큐에 삽입
- SSTF: 요구받은 재료들을 현재 head와 가까운 순으로 정렬하고 내보냄
- Bring: 재료를 창고A로 이동
- enQueue_RP: 창고A의 참조 과정 결과 큐 삽입
- enQueue_RD: 창고B의 참조 과정 결과 큐 삽입
- Result_RP: 창고 B에 삽입할 값들을 구함
- Round: 반올림
동작화면
Main
- 메인함수의 매개변수가 입력파일이기 때문에 입력 파일명을 입력하여 프로그램을 실행시킨다.
Print File
- arival_time: 도착한 시간을 1초당 1로 환산한 값
- _burger: 요청받은 햄버거 개수
Open The HamHouse
- C_time: 특정 프로세스의 cpu타임 (주문, 제조, 배달시간의 합)
- Arround_time: 특정 프로세스가 실행되는 시간의 양(I/O 포함)
출력파일 - RR
출력파일 - 창고A
- 시간은 다시 시/분/초 형식으로 환산하여 출력
- 페이지 테이블에 각 재료의 남은 개수를 나타냄
출력파일 - Disk
- 헤드: 현재 헤드의 위치를 나타냄
- 탐색시간: 지난 헤드에서 현재 헤드로 오기까지 걸린 탐색 시간
구현
모델링
가정
- 가게를 오픈하기 전 창고A의 냉장고에는 7가지 재료가 각각 7개씩 존재한다.
- 햄버거를 만들 때 각각의 재료를 사용하여 1개씩 제조한다.
- 운영시간은 00:00 ~ 23:59로 정한다.
- 재료를 모두 소진하였을 경우 새로운 햄버거를 만들 때 확인하고 해당 재료를 ‘bringnum’ 변수에 지정된 개수만큼을 가져온다.
- 주문을 받아도 가게 닫을 시간인 24:00이 되면 모든 서비스를 종료하고 문을 닫는다.
- 초기헤드를 0으로 지정하고 재료별로 1~7번 트랙을 지정함.
- 시간단위를 1초당 1로 지정하고 1루프 동작할 때 마다 1초씩 증가
- 주문은 온 순서대로 받고 배달도 요청받은 순서대로 진행함. 제조는 RR Q에따라 Context Swiching 하면서 동작.
- 메모리 페이지에는 각각의 재료가 지정되어있으며 참조될 때 마다 count를 감소시킴.
- 주문 수는 20 ~ 50으로 가정함.
- 입력파일로 읽어오는 주문에서 하나의 주문에 총 햄버거 수를 약 100개 이상은 가게 사정으로 금하고있음.
- 메모리 사이즈는 50으로 하고, 크기를 넘어서면 LRU 알고리즘이 동작한다.
- 재료 공간이 없을 때, 필요없는 재료를 창고B에 두고 다시 창고B에서 필요한 재료를 냉장고로 가져오는 시간은 재료 갯수당 1초로 정한다. (디스크 head 탐색시간 별개)
동작 원리
동작하기에 앞서서 초기 냉장고(페이지)에 각 재료를 7개씩 삽입
- 입력을 받고 큐에 삽입
- 도착 시간별로 정렬
- 주문 큐 (FCFS) 동작
- 완료되면 제조큐(RR) 삽입 후 동작
4.1 퀀텀시간에 이르면 남은시간을 갖고 맨 뒤로 삽입
4.2 닭고기버거 mod 100, 새우버거 mod 110이 0이되면 페이지 내에 재료를 사용
4.3 재료가 0이면 디스크에 요구하여 디스크 큐에 삽입
4.4 페이지 사이즈를 초과할 경우, LRU 알고리즘 동작아여 가장 오래 사용안된 재료를 1 개씩 감소
4.5 SSTF 알고리즘으로 재료를 가져옴 - 완료되면 배달이면 배달큐(FCFS 삽입 후 동작), 방문이면 종료
- 배달큐 완료시 종료 — terminate 횟수가 처음 입력받은 데이터와 같을 때 까지 반복
Input 함수
입력 파일을 읽어 올 때, 문자를 도착시간과 햄버거 종류, 주문 종류가 문자열로 되어있기 때문에 내장된 string 라이브러리를 이용하여 도착시간은 1분당 60, 1시간당 3600으로 변환하고 햄버거종류는 문자열을 탐색하여 종류별 햄버거 개수*만드는 시간으로 변환한다.
주문 종류는 그대로 읽는다. 이렇게 주문큐로 들어가게 된다.
Guest_info 함수
핵심함수인 Guest_info 함수는 크게 while(1)로 이루어져 있고 그 내부에 모든 큐가 참조되며 연산을 진행하고 making큐에 대해서는 IO도 발생하도록 구현하였다.
전체 while문이 1번 돌면 absoulute_time 이라는 절대시간을 증가시키기 때문에 이 전체 반복문 내부에서 가상의 시간이 존재하며, 각 큐의 상태와 상대시간을 체크하기 위해 relative_time 이라는 상대시간을 각 큐마다 주었다.
입력받은 guest의 수가 모두 terminate되면 while문은 동작을 멈추고 결과 큐들을 읽어오며 출력하게 된다.
프로세스 관리
최초 주문큐로 모든 데이터가 들어오고 다단계 큐의 방식으로 제조큐, 배달큐로 이어짐.
주문큐는 실제 햄버거 주문방식과 같이 FCFS방식으로 구현, 제조큐는 특정 손님이 무한정 기다릴 수 없으므로 RR구현, 배달큐는 배달 도중 되돌아 갈 수 없으므로 FCFS로 구현하였다.
모든 노드가 작업을 완료하면 모든 동작과정이 종료된다.
메모리 관리
메모리 관리에는 우선 페이징 LRU 알고리즘을 사용한다.
초기에 냉장고 상태를 각 7개의 재료가 7개의 수량을 갖도록 하고 재료를 사용할 시기에 각각의 재료를 사용하게 된다. 재료는 수시로 가져오지않고 새로운 햄버거 제조시에만 묶음으로 가져오게 된다.
가장 최근에 사용된 페이지는 맨 앞으로 가고 가장 사용안된 페이지는 맨 뒤로 가게 된다. 실제로 페이지 교체가 일어나야하지만, 재료의 타입이 정해져있고 재료의 수량(bringnum)도 각각 7개씩 49가 최대로 총 사이즈 50을 넘지않기 때문에 일어나지 않는다.
만약 재료의 수량(bringnum) 변수가 8 이상일 경우 상황에따라 LRU 알고리즘이 동작하여 페이지 교체가 발생하게된다.
따라서 메모리 사이즈를 줄이거나 가져오는 재료를 늘리지 않는 이상 메인메모리에 점유중인 프로세스는 교체되지 않는다.
디스크 관리
디스크 관리는 SSTF방식을 사용한다. 페이지를 검사할 때, 재료가 없으면 페이지 참조를 하지못한다.
그 때, 해당 페이지를 디스크 큐로 삽입하여서 큐에 있는 노드들을 현재 head와 가까운 순으로 정렬한 후 가장 가까운 곳으로 이동하여 해당 재료를 가져오고 head값을 갱신시킨다.
댓글남기기