IT/C

CPU 스케줄링 시뮬레이터 C로 만들기

김효랑이 2018. 10. 31. 14:07
728x90
반응형

 호야의 블로그 

[C] 운영체제-CPU 스케줄링 시뮬레이터 만들기

올해 수행했던 운영체제 short term job에서 일어나는 CPU 스케줄러를 구현하고 확인해보겠습니다. C를 이용하였으며 리눅스 환경에서 구현하였습니다. FCFS, SJF, SRT, Priority, RR(Round-robin) 알고리즘을 구현할 것이며 키보드로 제어가 가능한 UI와 가상의 프로세스 job을 생성하는 기능까지 추가하겠습니다.


개요

글을 읽기에 앞서 이전에 올려드렸던 CPU 스케줄러에 관한 설명을 먼저 보신다면 보다 수월하게 이해할 수 있을 것입니다. 아래 링크를 클릭하시면 됩니다.

2018/10/24 - [IT/OS] - [OS] CPU 스케줄러

 

최종 출력화면은 다음과 같을 것이며 비어있는 entry는 proc.txt에서 프로세스 정보 값을 불러오도록 하겠습니다. 

Process#     CPU_time     Arrival_time     Priority

------------       -------------      ----------------       ----------

<entry>         <entry>         <entry>         <entry>

<entry>         <entry>         <entry>         <entry>

 . . . .                                                                        

. . . .                                                                        


process number와 cpu_time(burst time), Arrival_time, Priority 순으로 다음과 같이 스페이스와 개행으로 구분하는 파일을 만들어 줍니다.

1 6 11 1
2 7 9 2
3 2 6 11
4 1 3 9
5 6 7 0


BT는 0이 될 수 없으며 동시에 발생하는 프로세스, 즉 AT가 같은 프로세스는 없도록 구현하겠습니다. 그리고 RR 알고리즘은 메뉴 선택 시 퀀텀을 입력하도록 할 것이고, Priority 알고리즘은 우선순위 값이 낮은 것이 우선이며 비선점형으로 구현하겠습니다.

디자인한 메뉴의 모습입니다.

 			Main Menu
 			—————-
1 Read processes from proc.txt (Process.txt에서 프로세스 읽기)
2 Generate random processes (랜덤 프로세스 생성)
3 First come first Serve (FCFS)	//첫번째로 온 서비스
4 Shortest Job First (SJF)		//가장 짧은 작업 우선
5 Shortest Remaining time First (SRTF)	//가장 짧은 남은 시간 첫번째
6 Priority
7 Round Robin (RR)
8 Exit
 *** Note: User the arrow keys to choose from the menu		//메뉴에서 선택할 화살표 키 커서 사용


구현

선언

헤더는 다음과 같이 4가지를 선언하겠습니다. windows와 termios는 UI를 위해 필요한 것이므로 알고리즘만 구현하신다면 필요 없을 것입니다.

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <termios.h>


각 프로세스의 정보가 들어가는 process 구조체 입니다. 프로세스 번호와 동작시간, 도착시간, 우선순위, 대기시간, 전체동작시간, 남은 동작시간 순으로 변수를 가집니다.

typedef struct _process{
    int pro_num, cpu_time, arr_t, pri, wait_t, ta_t, rem_t, st, ft;
} process;


방향키 이동 제어 UI를 위한 선언과 메뉴 이동 입력키 변수입니다.

static struct termios old, new;
int select_menu,cur_menu, ent_key;


코드에 기능과 알고리즘을 구현한 함수목록입니다.

void initTermios();
int getkeyboard();
void key_check(int n);
void print(); 

int process_fcfs(process *pro, int n);
int process_srt(process *pro, int n);
int process_pri(process *pro, int n);
int process_rr(process *pro, int n, int Q);
int process_sjf(process *pro, int n);
int process_generate(process *pro, int n);
void at_sort(process *pro, int n);
void resort(process *pro, int n);


메뉴 UI

1. void print()

메뉴는 키이동으로 입력되는 시스템 키 번호에 따라 메뉴를 시시각각 변화시켜 보여줍니다. 아래와 같은 코드로 select_menu 값에 따라 보이는 메뉴가 바뀌게 됩니다.

void print(){
   switch(select_menu){
      case 1:
	    system("clear");
		printf("\n=================Main Menu====================\n\n▶▶ Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 2:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n▶▶ Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 3:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n▶▶ First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 4:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n▶▶ Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 5:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n▶▶ Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");

         break;
      case 6:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n▶▶ Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 7:
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n▶▶ Round Robin (RR)\n8. Exit\n==============================================\n");
		break;
      case 8:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n▶▶ Exit\n==============================================\n");
        break;
   }
}


2. void key_check()

현재 입력한 키를 확인하는 함수입니다. up 키를 누르면 select_menu의 값을 감소시키고, down 키 입력 시 select_menu 값을 1 증가시켜 메뉴를 이동합니다. 엔터키를 통해 선택된 알고리즘을 호출하여 출력합니다. system("clear") 명령어는 출력 화면을 지우기 위한 용도로 깔끔한 UI를 위해 필수적입니다.

id key_check(int n){
   switch(n){
      case 65: // up -1
         if(select_menu == 1)
         {
            select_menu = 1;
         }
         else
         {
            select_menu--;
         }
		 system("clear");
         print(select_menu);
		 ent_key=0;
         break;
      case 66: // down +1
         if(select_menu == 8)
         {
            select_menu = 8;
         }
         else
         {
            select_menu++;
         }
		 system("clear");
         print(select_menu);
		 ent_key=0;
         break;
      case 10: // enter
		 if(select_menu == 7){
			 cur_menu=select_menu;
		 ent_key=1;
		 }
		 else{
			 print(select_menu);
         cur_menu=select_menu;
		 ent_key=1;
		 }

         break;
   }
}


3. void initTermios(), int getkeyboard()

키를 입력받아 초기화하고, 값을 저장하는 함수들입니다.

void initTermios() {
   tcgetattr(0, &old);
   new = old;
   new.c_lflag &= ~ICANON;
   tcsetattr(0, TCSANOW, &new);
}

int getkeyboard() {
   int ch;
   initTermios();
   ch = getchar();
   return ch;
}


4. void at_sort()

도착한 시간 순으로 프로세스를 정렬합니다. 보다 편리한 알고리즘 구현을 위한 작업입니다. 기존 프로세스 번호 순으로 정렬되어 있어 계속 AT를 비교하며 정렬하는 것 보다 한번에 정렬해놓고 알고리즘만 적용시키면 되므로 보다 편리합니다.

void at_sort(process *pro, int n){
	process temp;
	int i,j;
	for(i=n-1; i>0;i--){
		for(j=0;j<i;j++){
			if(pro[j].arr_t>pro[j+1].arr_t){
				temp=pro[j+1];
				pro[j+1]=pro[j];
				pro[j]=temp;
			
			}
			else if(pro[j].arr_t==pro[j+1].arr_t&&pro[j].pro_num>pro[j+1].pro_num){
				temp=pro[j+1];
				pro[j+1]=pro[j];
				pro[j]=temp;
			}
		}
	}
}


5. void resort()

도착시간 순으로 정렬된 프로세스를 다시 원래대로 프로세스 번호순으로 재정렬 합니다. 알고리즘 통과이후 출력 직전에 적용시켰습니다.

void resort(process *pro, int n){
	process temp;
	int i,j;
	for(i=n-1; i>0;i--){
		for(j=0;j<i;j++){
			if(pro[j].pro_num>pro[j+1].pro_num){
				temp=pro[j+1];
				pro[j+1]=pro[j];
				pro[j]=temp;
			}
		}
	}
}


알고리즘

1. int process_fcfs()

가장 단순한 알고리즘입니다. 도착 순서대로 정렬된 프로세스 구조체를 가져와 cpu_time을 계속 더해주고 대기시간을 구해줍니다.

int process_fcfs(process *pro, int n){
	int temp;
	int wt=0;
	int i,j,k=0;

	for(i=0;i<n;i++){
		temp=0;
		for(j=k;j<i;j++){
			temp=temp+pro[j].cpu_time;
		}
		wt=temp-pro[i].arr_t+pro[k].arr_t;

		if(wt<=0){
			k=i;
			pro[i].wait_t=0;
			pro[i].ta_t=pro[i].cpu_time + pro[i].wait_t;
		}
		else{
			pro[i].wait_t=wt;
			pro[i].ta_t=pro[i].cpu_time + pro[i].wait_t;
		}
	}
}



2. int process_srt()

남은 동작시간을 매시간 계산하여 가장 짧은 남은 동작시간을 가진 프로세스를 우선 처리하는 알고리즘입니다. now 변수를 이용해 매시간 카운트하며 남은 계산시간을 계산합니다. 선점형으로 동작합니다. (처음 min 값이 5000인 것은 제일 처음 동작하는 프로세스가 제일 적은 남은 동작시간을 가져야하기 때문입니다)

int process_srt(process *pro, int n){
	int remain, min, now_p, i, temp[150];
	int now, wt=0;

	remain=n;
	now=pro[0].arr_t;
	while(remain>0){
		min=5000;	
		for(i=0; pro[i].arr_t<=now && i<n; i++){	
			if(pro[i].rem_t<min && pro[i].rem_t>0){	
				now_p=i;
				min=pro[i].rem_t;   //가장 적은 남은 동작 시간을 선언
			}
		}
		now++;      //시간 카운트 업
		if(temp[0] !=pro[0].cpu_time){
			for(i=0; i<n; i++){
				temp[i]=pro[i].rem_t;
			}
		}
		
		pro[now_p].rem_t--; //시간이 지날 수록 남은 동작시간 카운트를 감소

		if(pro[now_p].rem_t==0){	//남은 동작시간 0인경우 연산
			pro[now_p].wait_t=now-pro[now_p].arr_t-pro[now_p].cpu_time;
			pro[now_p].ta_t=pro[now_p].cpu_time + pro[now_p].wait_t;
			wt=wt+pro[now_p].wait_t;
			remain--;
		}
	}
	for(i=0; i<n; i++){
		pro[i].rem_t=temp[i];
	}
}


3. int process_pri()

우선순위 알고리즘은 오직 우선순위만 보고 처리합니다. 들어온 순서대로 동작하다가 대기중인 우선순위가 높은 프로세스가 들어오면 다음으로 우선 처리하도록 합니다. 비선점형으로 구현했습니다. 선점형으로 구현하려면 srt 알고리즘을 참고하시면 됩니다.

int process_pri(process *pro, int n){
   int flag = 0;
   int i,time,remain,num, min, temp[150];
   
   for(i=0; i<n; i++){
      pro[i].rem_t = pro[i].cpu_time;
   }
   
   time = pro[0].arr_t;
   remain = n;
   
   	if(temp[0] !=pro[0].cpu_time){
		for(i=0; i<n; i++){
			temp[i]=pro[i].rem_t;
		}
	}

   while(remain>0){
    min = 9999;
   for (i=0; pro[i].arr_t <= time && i<n; i++){
       if(pro[i].rem_t != 0 && pro[i].pri<min && pro[i].cpu_time>0){
          num = i;
          min = pro[i].pri;
          flag = 1;
      }
   }
     
      if(flag ==1){
         pro[num].rem_t = 0;
         pro[num].wait_t = time - pro[num].arr_t;
         remain--;
       time += pro[num].cpu_time;
      }
      
      else{
         time ++;
      }
      flag = 0;
   }
   for(i=0; i<n; i++){
      pro[i].ta_t = pro[i].wait_t + pro[i].cpu_time;
   }
   	for(i=0; i<n; i++){
		pro[i].rem_t=temp[i];
	}
}


4. int process_sjf()

동작시간이 짧은 프로세스를 우선 처리합니다. Priorty 알고리즘에서 우선순위가 작은 프로세스를 우선 처리하는 것과 같은 알고리즘을 사용합니다. 변수만 몇 개 수정하시면 됩니다.

int process_sjf(process *pro, int n){
   int flag = 0;
   int i,time,remain,num, min, temp[150];
   
   for(i=0; i<n; i++){
      pro[i].rem_t = pro[i].cpu_time;
   }
   
   time = pro[0].arr_t;
   remain = n;
   
	if(temp[0] !=pro[0].cpu_time){
		for(i=0; i<n; i++){
			temp[i]=pro[i].rem_t;
		}
	}

   while(remain>0){
    min = 9999;
   for (i=0; pro[i].arr_t <= time && i<n; i++){
       if(pro[i].rem_t != 0 && pro[i].cpu_time<min && pro[i].cpu_time>0){
          num = i;
          min = pro[i].cpu_time;
          flag = 1;
      }
   }
         
      if(flag ==1){
         pro[num].rem_t = 0;
         pro[num].wait_t = time - pro[num].arr_t;
         remain--;
       time += pro[num].cpu_time;
      }
      
      else{
         time ++;
      }
      flag = 0;
   }
   for(i=0; i<n; i++){
      pro[i].ta_t = pro[i].wait_t + pro[i].cpu_time;
   }
   	for(i=0; i<n; i++){
		pro[i].rem_t=temp[i];
	}
}


5. int process_rr()

퀀텀을 정해 모든 프로세스가 들어온 순서대로 퀀텀만큼만 동작하고 다음으로 넘어가는 알고리즘입니다. FCFS에서 퀀텀만 추가되었습니다.

int process_rr(process *pro, int n, int Q){
	int temp, temp2[150];
	int i, count, tt;
	
	if(temp2[0] !=pro[0].cpu_time){
		for(i=0; i<n; i++){
			temp2[i]=pro[i].rem_t;
		}
	}
	
	while(1){   //퀀텀만큼만 동작하는 부분입니다.
		for(i=0,count=0;i<n;i++) {
			temp=Q;
			if(pro[i].rem_t==0){
				count++;
				continue;
			}
			if(pro[i].rem_t>Q)
				pro[i].rem_t=pro[i].rem_t-Q;
			else if(pro[i].rem_t>=0) {
				temp=pro[i].rem_t;
				pro[i].rem_t=0;
				}
				tt=tt+temp;
				pro[i].ta_t=tt;
		}
		if(n==count)
			break;
	}
	for(i=0;i<n;i++){
		pro[i].rem_t=temp2[i];
		pro[i].wait_t=pro[i].ta_t-pro[i].cpu_time;
	}
}


6. int process_generate()

새로운 랜덤 프로세스를 생성하는 함수입니다. proc.txt에 랜덤한 BT와 겹치지 않는 프로세스 우선순위와 도착시간을 설정해주고, 순서에 맞게 프로세스 번호를 설정합니다.

int process_generate(process *pro, int n){
	FILE *fp2;
	int j, found;
	fp2=fopen("proc.txt","a+");
	int i=n;
	int bt =(rand()%25)+1;
	
	pro[i].pro_num=i+1;
	pro[i].cpu_time=bt;
	
	while(1){       //겹치지 않는 프로세스 번호 만들기
		pro[i].pri=rand()%50;
		found=0;
		for(j=0;j<i;++j){
			if(pro[j].pri==pro[i].pri){
				found=1;
				break;
			}
		}
		if(!found) break;
	}
	
	while(1){       //겹치지 않는 프로세스 도착시간 만들기
		pro[i].arr_t=rand()%50;
		found=0;
		for(j=0;j<i;++j){
			if(pro[j].arr_t==pro[i].arr_t){
				found=1;
				break;
			}
		}
		if(!found) break;
	}
	fprintf(fp2,"\r\n%d %d %d %d",pro[i].pro_num, pro[i].cpu_time, pro[i].arr_t, pro[i].pri);
	fclose(fp2);
}


전체 코드

//OS CPU_scheduling.c

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <termios.h>


typedef struct _process{
    int pro_num, cpu_time, arr_t, pri, wait_t, ta_t, rem_t;
} process;

static struct termios old, new;

int select_menu,cur_menu, ent_key;

void initTermios();
int getkeyboard();
void key_check(int n);
void print(); 

int process_fcfs(process *pro, int n);
int process_srt(process *pro, int n);
int process_pri(process *pro, int n);
int process_rr(process *pro, int n, int Q);
int process_sjf(process *pro, int n);
int process_generate(process *pro, int n);
void at_sort(process *pro, int n);
void resort(process *pro, int n);


void print(){
   switch(select_menu){
      case 1:
	    system("clear");
		printf("\n=================Main Menu====================\n\n▶▶ Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 2:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n▶▶ Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 3:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n▶▶ First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 4:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n▶▶ Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 5:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n▶▶ Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");

         break;
      case 6:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n▶▶ Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
        break;
      case 7:
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n▶▶ Round Robin (RR)\n8. Exit\n==============================================\n");
		break;
      case 8:
        system("clear");
		printf("\n=================Main Menu====================\n\n1. Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n▶▶ Exit\n==============================================\n");
        break;
   }
}

void key_check(int n){
   switch(n){
      case 65: // up -1
         if(select_menu == 1)
         {
            select_menu = 1;
         }
         else
         {
            select_menu--;
         }
		 system("clear");
         print(select_menu);
		 ent_key=0;
         break;
      case 66: // down +1
         if(select_menu == 8)
         {
            select_menu = 8;
         }
         else
         {
            select_menu++;
         }
		 system("clear");
         print(select_menu);
		 ent_key=0;
         break;
      case 10: // enter
		 if(select_menu == 7){
			 cur_menu=select_menu;
		 ent_key=1;
		 }
		 else{
			 print(select_menu);
         cur_menu=select_menu;
		 ent_key=1;
		 }

         break;
   }
}

void initTermios() {
   tcgetattr(0, &old);
   new = old;
   new.c_lflag &= ~ICANON;
   tcsetattr(0, TCSANOW, &new);
}

int getkeyboard() {
   int ch;
   initTermios();
   ch = getchar();
   return ch;
}


void at_sort(process *pro, int n){
	process temp;
	int i,j;
	for(i=n-1; i>0;i--){
		for(j=0;j<i;j++){
			if(pro[j].arr_t>pro[j+1].arr_t){
				temp=pro[j+1];
				pro[j+1]=pro[j];
				pro[j]=temp;
			
			}
			else if(pro[j].arr_t==pro[j+1].arr_t&&pro[j].pro_num>pro[j+1].pro_num){
				temp=pro[j+1];
				pro[j+1]=pro[j];
				pro[j]=temp;
			}
		}
	}
}

void resort(process *pro, int n){
	process temp;
	int i,j;
	for(i=n-1; i>0;i--){
		for(j=0;j<i;j++){
			if(pro[j].pro_num>pro[j+1].pro_num){
				temp=pro[j+1];
				pro[j+1]=pro[j];
				pro[j]=temp;
			}
		}
	}
}


int process_fcfs(process *pro, int n){
	int temp;
	int wt=0;
	int i,j,k=0;

	for(i=0;i<n;i++){
		temp=0;
		for(j=k;j<i;j++){
			temp=temp+pro[j].cpu_time;
		}
		wt=temp-pro[i].arr_t+pro[k].arr_t;

		if(wt<=0){
			k=i;
			pro[i].wait_t=0;
			pro[i].ta_t=pro[i].cpu_time + pro[i].wait_t;
		}
		else{
			pro[i].wait_t=wt;
			pro[i].ta_t=pro[i].cpu_time + pro[i].wait_t;
		}
	}
}

int process_srt(process *pro, int n){
	int remain, min, now_p, i, temp[150];
	int now, wt=0;

	remain=n;
	now=pro[0].arr_t;
	while(remain>0){
		min=5000;	
		for(i=0; pro[i].arr_t<=now && i<n; i++){	
			if(pro[i].rem_t<min && pro[i].rem_t>0){	
				now_p=i;
				min=pro[i].rem_t;
			}
		}
		now++;
		if(temp[0] !=pro[0].cpu_time){
			for(i=0; i<n; i++){
				temp[i]=pro[i].rem_t;
			}
		}
		
		pro[now_p].rem_t--;	
		if(pro[now_p].rem_t==0){	
			pro[now_p].wait_t=now-pro[now_p].arr_t-pro[now_p].cpu_time;
			pro[now_p].ta_t=pro[now_p].cpu_time + pro[now_p].wait_t;
			wt=wt+pro[now_p].wait_t;
			remain--;
		}
	}
	for(i=0; i<n; i++){
		pro[i].rem_t=temp[i];
	}
}

int process_pri(process *pro, int n){
   int flag = 0;
   int i,time,remain,num, min, temp[150];
   
   for(i=0; i<n; i++){
      pro[i].rem_t = pro[i].cpu_time;
   }
   
   time = pro[0].arr_t;
   remain = n;
   
   	if(temp[0] !=pro[0].cpu_time){
		for(i=0; i<n; i++){
			temp[i]=pro[i].rem_t;
		}
	}

   while(remain>0){
    min = 9999;
   for (i=0; pro[i].arr_t <= time && i<n; i++){
       if(pro[i].rem_t != 0 && pro[i].pri<min && pro[i].cpu_time>0){
          num = i;
          min = pro[i].pri;
          flag = 1;
      }
   }

         
      if(flag ==1){
         pro[num].rem_t = 0;
         pro[num].wait_t = time - pro[num].arr_t;
         remain--;
       time += pro[num].cpu_time;
      }
      
      else{
         time ++;
      }
      flag = 0;
   }
   for(i=0; i<n; i++){
      pro[i].ta_t = pro[i].wait_t + pro[i].cpu_time;
   }
   	for(i=0; i<n; i++){
		pro[i].rem_t=temp[i];
	}
}

int process_sjf(process *pro, int n){
   int flag = 0;
   int i,time,remain,num, min, temp[150];
   
   for(i=0; i<n; i++){
      pro[i].rem_t = pro[i].cpu_time;
   }
   
   time = pro[0].arr_t;
   remain = n;
   
	if(temp[0] !=pro[0].cpu_time){
		for(i=0; i<n; i++){
			temp[i]=pro[i].rem_t;
		}
	}

   while(remain>0){
    min = 9999;
   for (i=0; pro[i].arr_t <= time && i<n; i++){
       if(pro[i].rem_t != 0 && pro[i].cpu_time<min && pro[i].cpu_time>0){
          num = i;
          min = pro[i].cpu_time;
          flag = 1;
      }
   }

         
      if(flag ==1){
         pro[num].rem_t = 0;
         pro[num].wait_t = time - pro[num].arr_t;
         remain--;
       time += pro[num].cpu_time;
      }
      
      else{
         time ++;
      }
      flag = 0;
   }
   for(i=0; i<n; i++){
      pro[i].ta_t = pro[i].wait_t + pro[i].cpu_time;
   }
   	for(i=0; i<n; i++){
		pro[i].rem_t=temp[i];
	}
}

int process_rr(process *pro, int n, int Q){
	int temp, temp2[150];
	int i, count, tt;
	
	if(temp2[0] !=pro[0].cpu_time){
		for(i=0; i<n; i++){
			temp2[i]=pro[i].rem_t;
		}
	}
	
	while(1){
		for(i=0,count=0;i<n;i++) {
			temp=Q;
			if(pro[i].rem_t==0){
				count++;
				continue;
			}
			if(pro[i].rem_t>Q)
				pro[i].rem_t=pro[i].rem_t-Q;
			else if(pro[i].rem_t>=0) {
				temp=pro[i].rem_t;
				pro[i].rem_t=0;
				}
				tt=tt+temp;
				pro[i].ta_t=tt;
		}
		if(n==count)
			break;
	}
	for(i=0;i<n;i++){
		pro[i].rem_t=temp2[i];
		pro[i].wait_t=pro[i].ta_t-pro[i].cpu_time;
	}
}

int process_generate(process *pro, int n){
	FILE *fp2;
	int j, found;
	fp2=fopen("proc.txt","a+");
	int i=n;
	int bt =(rand()%25)+1;
	
	pro[i].pro_num=i+1;
	pro[i].cpu_time=bt;
	
	while(1){
		pro[i].pri=rand()%50;
		found=0;
		for(j=0;j<i;++j){
			if(pro[j].pri==pro[i].pri){
				found=1;
				break;
			}
		}
		if(!found) break;
	}
	
	while(1){
		pro[i].arr_t=rand()%50;
		found=0;
		for(j=0;j<i;++j){
			if(pro[j].arr_t==pro[i].arr_t){
				found=1;
				break;
			}
		}
		if(!found) break;
	}
	fprintf(fp2,"\r\n%d %d %d %d",pro[i].pro_num, pro[i].cpu_time, pro[i].arr_t, pro[i].pri);
	fclose(fp2);
}


int main(){
	int  i,n, Q;
	int index=0;
	float tat;
	
	process *ready_queue;
	
	FILE *fp;
	fp=fopen("proc.txt","r");

	while(!feof(fp)) { 
		fscanf(fp, "%d", &ready_queue[i].pro_num);
		fscanf(fp, "%d", &ready_queue[i].cpu_time);
		fscanf(fp, "%d", &ready_queue[i].arr_t);
		fscanf(fp, "%d", &ready_queue[i].pri);
		ready_queue[i].rem_t=ready_queue[i].cpu_time;
		index=index+1;
		i++;
        if(feof(fp)!=0)
            break;
    }
	
	fclose(fp);
	n=index;
	system("clear");
	select_menu = 1;
	cur_menu=select_menu;
	
	
	printf("\n=================Main Menu====================\n\n▶▶ Read processes from proc.txt\n2. Generate random processes\n3. First come first Serve (FCFS)\n4. Shortest Job First (SJF)\n5. Shortest Remaining time First (SRTF)\n6. Priority\n7. Round Robin (RR)\n8. Exit\n==============================================\n");
	while(1){
		key_check(getkeyboard());
		float tat=0.0;
		if(ent_key==1){
			switch(cur_menu){
		case 1: 
		printf("1. Read processes from proc.txt\n====================PROC======================\n");
		printf("P#	BT	AT	Pri\n");
		for(i=0; i<n; i++) {
			printf("%d	%d	%d	%d\n",ready_queue[i].pro_num, ready_queue[i].cpu_time, ready_queue[i].arr_t, ready_queue[i].pri);
		}
		printf("==============================================\n");
		continue;
		break;
		
		case 2:
		printf("2. Generate random processes\n");
		process_generate(ready_queue, n);
		printf("\n\n==================생성완료===================\n");
		n++;
		continue;
		break;
		
		case 3:		//fcfs
		at_sort(ready_queue, n);
		process_fcfs(ready_queue, n);
		resort(ready_queue, n);
		
		printf("3. First come first Serve (FCFS)\n====================FCFS======================\n");
		printf("P#	BT	AT	Pri	WT	TAT\n");
		for(i=0; i<n; i++) {
			tat=tat+ready_queue[i].ta_t;
			printf("%d	%d	%d	%d	%d	%d\n",ready_queue[i].pro_num, ready_queue[i].cpu_time, ready_queue[i].arr_t, ready_queue[i].pri, ready_queue[i].wait_t, ready_queue[i].ta_t);
		}
		printf("average turnaround time: %.2f\n",tat/n);
		printf("==============================================\n");
		continue;
		break;
		
		case 4:		//sjf
		at_sort(ready_queue, n);
		process_sjf(ready_queue, n);
		resort(ready_queue, n);
		
		printf("4. Shortest Job First (SJF)\n====================SJF=======================\n");
		printf("P#	BT	AT	Pri	WT	TAT\n");
		
		for(i=0; i<n; i++) {
			tat=tat+ready_queue[i].ta_t;
			printf("%d	%d	%d	%d	%d	%d\n",ready_queue[i].pro_num, ready_queue[i].cpu_time, ready_queue[i].arr_t, ready_queue[i].pri, ready_queue[i].wait_t, ready_queue[i].ta_t);
		}
		printf("average turnaround time: %.2f\n",tat/n);
		printf("==============================================\n");
		continue;
		break;
		
		case 5:		//srt
		at_sort(ready_queue, n);
		process_srt(ready_queue, n);
		resort(ready_queue, n);
		
		printf("5. Shortest Remaining time First (SRTF)\n====================SRTF======================\n");
		printf("P#	BT	AT	Pri	WT	TAT\n");
		for(i=0; i<n; i++) {
			tat=tat+ready_queue[i].ta_t;
			printf("%d	%d	%d	%d	%d	%d\n",ready_queue[i].pro_num, ready_queue[i].cpu_time, ready_queue[i].arr_t, ready_queue[i].pri, ready_queue[i].wait_t, ready_queue[i].ta_t);
		}
		printf("average turnaround time: %.2f\n",tat/n);
		printf("==============================================\n");
		continue;
		break;
		
		case 6:		//pri
		at_sort(ready_queue, n);
		process_pri(ready_queue, n);
		resort(ready_queue, n);
		
		printf("6. Priority\n====================PRI=======================\n");
		printf("P#	BT	AT	Pri	WT	TAT\n");
		for(i=0; i<n; i++) {
			tat=tat+ready_queue[i].ta_t;
			printf("%d	%d	%d	%d	%d	%d\n",ready_queue[i].pro_num, ready_queue[i].cpu_time, ready_queue[i].arr_t, ready_queue[i].pri, ready_queue[i].wait_t, ready_queue[i].ta_t);
		}
		printf("average turnaround time: %.2f\n",tat/n);
		printf("==============================================\n");
		continue;
		break;
		
		case 7:		//RR
		printf("퀀텀 입력(위, 아래 방향키 입력 시 메뉴 이동)\n");
		scanf("%d",&Q);
		at_sort(ready_queue, n);
		process_rr(ready_queue, n, Q);
		resort(ready_queue, n);
		
		printf("7. Round Robin (RR)\n====================RR========================\n");
		printf("P#	BT	AT	Pri	WT	TAT\n");
		
		for(i=0; i<n; i++) {
			tat=tat+ready_queue[i].ta_t;
			printf("%d	%d	%d	%d	%d	%d\n",ready_queue[i].pro_num, ready_queue[i].cpu_time, ready_queue[i].arr_t, ready_queue[i].pri, ready_queue[i].wait_t, ready_queue[i].ta_t);
		}
		printf("average turnaround time: %.2f\n",tat/n);
		printf("==============================================\n\n");
		ent_key=0;
		continue;
		break;
		
		case 8:
		printf("\n\n====================EXIT======================\n");
		exit(0);
		break;
		}
	}
	else continue;
	break;
	}
}


실습

아래와 같이 저장된 proc.txt로 테스트 하겠습니다.

1 6 11 1
2 7 9 2
3 2 6 11
4 1 3 9
5 6 7 0


프로그램 실행 시  나타나는 첫 화면입니다. 위아래 방향키로 화면 전환이 가능하며 메뉴 선택이 가능해집니다.


1번 항목 'Read process from proc.txt'를 눌러 현재 프로세스 정보를 확인 합니다.


2번 항목으로 랜덤한 프로세스를 생성합니다. 아래와 같이 프로세스 번호 6, 7, 8, 9 프로세스가 생겼습니다.


3번 항목으로 현재 프로세스들이 FCFS 알고리즘을 수행합니다.


4번 항목으로 SJF 알고리즘을 수행합니다.


5번 항목으로 SRT 알고리즘을 수행합니다.


6번 항목으로 우선순위 알고리즘을 수행합니다.


7번 항목으로 라운드 로빈 알고리즘을 수행합니다. 퀀텀에 따라 값이 바뀝니다.

후기 및 정리

이렇게 프로세스의 스케줄링 시뮬레이터를 구현해봤습니다. 참고하셔서 더 좋은 알고리즘으로 더 나은 프로그램을 구현해보시길 바라겠습니다. 감사합니다.

퍼가실 땐 댓글과 출처 꼭 부탁드리겠습니다.

(소스는 댓글로 요청 시 보내드리겠습니다.)


C 4번째 글: 2018/11/02 - [IT/C] - [C] 운영체제-Page Replacement 알고리즘 만들기

C 3번째 글: 2018/10/31 - [IT/C] - [C] 운영체제-CPU 스케줄링 시뮬레이터 만들기

C 2번째 글: 2018/10/30 - [IT/C] - [C++] 영상처리-이미지 Sobel 경계 검출 및 영상 이진화

C 1번째 글: 2018/10/19 - [IT/C] - [C] 리눅스 환경에서 fork() 함수를 이용한 자식 프로세스 생성하기


조금의 도움이 되셨다면 로그인 없이도 가능한 댓글과

왼쪽 아래 ♥공감 버튼을 꾹 눌러주세요! 



728x90
반응형
저작자표시

'IT > C' 카테고리의 다른 글

Page Replacement 알고리즘 C로 만들기  (1) 2018.11.02
영상처리-C++로 이미지 Sobel 경계 검출 및 영상 이진화  (1) 2018.10.30
리눅스 환경에서 fork() 함수를 이용한 자식 프로세스 생성하기  (0) 2018.10.19

'IT/C'의 다른글

  • 현재글CPU 스케줄링 시뮬레이터 C로 만들기

관련글

티스토리툴바