OS과제 스케쥴러 구현 (SJF구현,SRT구현,MFQ구현)

소개글

숭실대학교 운영체제 2번째 과제
스케쥴러 구현

SJF구현,SRT구현,MFQ구현 입니다.
50점 만점에 45점 받은 과제입니다.

컴파일 실행환경

3.1 운영체제 수행 시뮬레이터 - 스케줄링 알고리즘 시뮬레이터 구현

* 교재 5.3절에 설명된 스케줄링 알고리즘을 시뮬레이션 하는 스케줄링 시뮬레이터를 구현한다.

3.1.1 CPU 스케줄링 시뮬레이터 scheduler_sim 명세

* 스케줄링 시뮬레이터 scheduler_sim 은 두개의 입력을 받는다.

1) 프로세스의 arrival time 과 service time 리스트가 저장되어있는 입력 파일이름

2) 선택된 스케줄링 알고리즘
- Shortest Jop First (SJF)
- Shortest Remaining Time (SRT)
- Multilevel Feedback Queue (MFQ)

* MFQ의 경우 4개의 Queue를 갖는다. 각 queue의 퀀텀(Quantum)값은 각각 2,4,8,∞ 이다.

* 입력파일인 scheduler_times.dat는 다음과 같은 형식으로 구성되어야 한다.

파일 형식)
# cat scheduler_times.dat
P1 5 9
P2 7 3
P3 8 3
P4 9 11


PA 11 15
PB 20 10


- 첫번째 값은 프로세스의 명칭으로 알파벳 또는 숫자로 구성된다. 두번째 값은 프로세스의 arrival time이며, 마지막 값은 service time 이다. 두 값 전부 기본단위는 밀리세컨드라 가정하며, 각각의 값들은 공백으로 구별되야 한다. 세가지의 값이 하나의 프로세스를 의미하며 전체 라인 수는 시뮬레이터에서 동작할 프로세스의 수와 일치한다. 전체 라인수(즉 프로세스의 수)는 최대 1000으로 제한하여 구현을 단순화 한다.

* scheduler_sim은 위의 입력파일을 이용하여 해당 스케줄링 알고리즘으로 프로세스 스케줄링을 계산한다. 스케줄링 이벤트를 출력하는 양식은 다음과 같다. 아래의 출력결과 및 형식은 교재 5.3.2절에서 SRT 부분을 나타낸 것이다.

출력 형식)
$ scheduler_sim scheduler_times.dat SRT

(수행이 끝난 화면)
* Scheduling Chart : Using SRT

P1: -
P2:
P3:
P4: (여기까지 화면은 실시간으로 변한다)
CPU time 26
* Calculated scheduling parameters : Using SRT

P1: arr=0 | run 0-1 | service = 1 | wait = 0 |
P2: arr=1 | run 1-5 | service = 4 | wait = 0 | turn = 4
P4: arr=3 | run 5-10 | service = 5 | wait = 2 | turn = 7
P1: arr=0 | run 10-17 | service = 8 | wait = 9 | turn = 17
P3: arr=2 | run 17-26 | service = 9 | wait = 15 | turn = 24

Average turnaround time = 13
Average waiting time = 6.5

- 처음 출력부분은 해당 스케줄링 알고리즘에 의해 스케줄링된 결과를 교재 5.3.2절에 있는 Gantt 차트와 비슷한 형태로 출력한 것이다. 이 부분은 수행이 완료되기 전까지 clear를 이용하여 CPU 한 텀당 0.5초의 딜레이를 주어 모든 시간이 끝날 때 까지 실시간적으로 표현해 준다. 첨부된 수행 파일을 참고한다. (첨부된 수행파일은 단순히 실시간으로 출력하는 것을 보여주기 위해 간단하게 하였기 때문에 참고만하기 바란다.)
- 프로세스의 수행이 끝났을 경우 표기를 +로 한다.
- CPU time 는 현재까지 진행된 CPU 시간이다.

- arr은 프로세스의 도착 시간, run 은 프로세스가 수행한 시간, service는 서비스를 받았던 시간, wait는 기다린 시간, turn은 프로그램이 수행하는데 걸린 총 시간이다. 예로 time 10에서 완료된 P4를 보면 turnaround time 은 (종료시간 - arrival = 10 - 3 = 7)임을 알 수 있으며 수행이 완료되지 않았을 경우는 표시하지 않는다. waiting time 은 (turnaround - service = 7 - 5 = 2) 임을 알 수 있다. 계산되는 시간 값은 이러한 계산을 정확하게 따라야 하며, 출력 형식도 반드시 위와 같아야 한다. (탭으로 정렬 시킬 필요 없음)

- 위의 스케줄링 이벤트 출력이 완료되면 마지막으로 전체 평균 시간을 출력하도록 한다. 출력해야 할 평균 시간은 (Global) Average turnaround time, (Global) Average waiting time 이다. Average turnaround time은 프로세스들이 종료될 때 까지 걸린 시간의 평균이다.
- 이 출력부분은 스케줄링된 결과를 토대로 계산된 스케줄링 관련 시간 값들이다. 이 부분은 굳이 수행도중에 정보를 보여주지 않아도 되고, 수행이 끝난 다음에 표시해주어도 무관하다.

- 수행이 완료한 뒤에는 scheduler_times.dat 의 정보가 변경되어서는 안 된다.

- 평균 시간은 소수 둘째자리까지 표현한다(셋째자리 반올림).
- idle 상태가 존재한다고 가정하여 실행할 프로세스가 없을 경우 공백상태로 표현.

본문내용

#include<stdio.h>
typedef struct process_line //프로세스 변수들을 저장하기 위한 구조체 선언
{
int num;

int arr_time;
int total_service_time;
int remain_service_time;
int run_service_time;

int start_time;
int end_time;
int wait;
int turn;
int inQueue;
}process;


int processCount = 0;

typedef struct processQueueForMFQ //큐를 위한 구조체 선언
{
int id;
int quantum;
process* p[1000];
int accumulateQuantum;
int rear;
int front;

}pq;

int main(void)
{
FILE *f;
process proQueue[100];
int queueIndex;
process pro[1000];
process *pp;
char temp[20];
int input_num;
int i=1;
int time=0;
int comp_service=0;
int temp_d=0;
int test_num=0;
char print[1000][100];
int ss=0;
int j=0;
int end_test=0;
double avr_turn=0;
double avr_wait=0;
int check=0;
int sort[1000];
int check_sort=0;

for(i=0; i<1000; i++)
for(j=0; j<100; j++)
print[i][j]='0';

for(i=0; i<100; i++)
proQueue[i].num = -1;


for(i=0; i<1000; i++)
sort[i]=0;

system("clear");
printf("select algorithm\n");
printf("1. SJF\n");
printf("2. SRT\n");
printf("3. MFQ\n");
printf("-----------------\n");
printf(": ");
scanf("%d", &input_num);

f=fopen("scheduler_times.dat","r");
int index=0;

processCount = 4;

while(!feof(f)) //파일로 부터 값을 읽어들임. 끝을 알기위해 feof
{

fscanf(f, "%s", temp); //첫번쨰 P1을 읽고

pro[index].num = index+1;
fscanf(f, "%d", &pro[index].arr_time); //arrival time을 읽는다.

pro[index].run_service_time = 0;
pro[index].start_time = -1;
pro[index].end_time = pro[index].arr_time;
pro[index].inQueue = 0;

if(pro[index].arr_time<0) break;

fscanf(f, "%d", &pro[index].total_service_time); //서비스 타임을 읽는다.
end_test+=pro[index].total_service_time;
pro[index].remain_service_time = pro[index].total_service_time;

index++;
test_num++;

}
index--;
test_num--;

fclose(f);

if(input_num==1) //만약 SJF인 경우에
{
int existProcess = 1; //처음 아무것도 가르치지 않는 경우를 위해 NULL로 초기화 해 주었다.
int abab = 0; //abab는 포인터가 가르키는게 있을 경우, 다른걸 선택하지 않게 하기 위해 만들어준 bool 형과 같다.
pp=NULL;


while(1)
{
index=0;

if(pp!=NULL) //pp가 먼가 가르치고 잇으면 abab가 다른걸 선택 못하게 하기 위해
{
abab = 1;

if(pp->remain_service_time==0) //그런데 현재 가르키는게 다 끝낫으면(service time이 계속 감소하므로 0이되면 끝난 것)
{
sort[check_sort]=pp->num; //끝난 게 무엇인지 알기 위해 P1인지 P2인지 숫자를 넣어줬다.(출력 할때 먼저 들어온거 먼저출력하기 위해)
check_sort++;

pp = NULL; //아무것도 안가르치게 만들고
abab = 0; //다른 것을 선택 할 수 있게 한다.

참고 자료

없음