[스케줄링 알고리듬(Scheduling algorithm)] FCFS 스케줄링(First Come First Served Scheduling) 프로그램 구현

프로세스 상태

비선점 프로세스 스케줄링
FCFS 스케줄링(First Come First Served Scheduling)
SJF 스케줄링(Shortest Job First Scheduling)
HRRN 스케줄링(Highest Response Ratio Next Scheduling)

선점 프로세스 스케줄링
RR 스케줄링(Round Robin Scheduling)
SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
다단계 큐 스케줄링(Multilevel Queue Scheduling)
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
RM 스케줄링(Rate Monotonic Scheduling)
EDF 스케줄링(Earliest Deadline First Scheduling)

이번은 비선점 프로세스 스케줄링 중 FCFS스케줄링을 다뤄봅니다.
정보처리기사 문제에도 많이 출제되고 대학교 운영체제(OS) 전공과목에서도 과제나
시험 문제로 많이 출제 됩니다.

FCFS 스케줄링은 Ready Queue에 들어온 순서대로 CPU에 할당하고 할당받은 프로세스가 작업을 하여
반환할 때까지 CPU를 독점하는 비선점 프로세스 스케줄링입니다.
스케줄링 알고리듬 중에 가장 단순 합니다. 그래서 CPU 사용시간이 길어지면 다음 프로세스들은 
오래 기다려야 하는 단점이 있습니다.

도착시간과 CPU 사용 시간만 주어 졌을 때 대기시간(Wating Time)을 구해 봅시다.

BT = Burst Time(CPU 사용 시간)
AT = Arrival Time(도착시간) Process가 Ready Queue에 들어온 시간
WT = Wating Time(대기시간) Process가 Ready Queue에서 기다리는 총 시간
TAT = Turn Around Time(반환시간) 프로세스가 시작해서 끝날 때까지 걸리는 시간
CT = Completion Time(완료시간)
Pn = Process Number(프로세스 번호) P1, P2...

fcfs.inp 파일에 아래와 같은 데이터가 있습니다. 
4
0 0 40
1 10 25
2 20 30
3 25 5

첫줄은 프로세스의 개수입니다.
두 번째 줄부터 프로세스 정보입니다.
제일 앞줄 0,1,2,3 프로세스 번호(PN)
가운데 줄 0,10,20,25 도착시간(AT)
마지막 줄 40,25,30,5 CPU사용시간(BT)

프로세스 번호(Process Number)	도착시간(Arrival Time)	CPU 사용 시간(Burst Time)
0	0	40
1	10	25
2	20	30
3	25	5

총 4개의 프로세가 사용 신청이 되었고 FCFS이기 때문에 도착시간이(AT) 0인 0번째 프로세스가 먼저
할당이 되고 CPU사용시간(BT)만큼 작업을 하고 AT가 10인 1번째 프로세스가 BT 25만큼 작업을 합니다.

(프로그램 코드로 작성 한다면 도착시간을 기준으로 정렬을 하고 만약 도착 시간이 같다면 프로세스 번호 기준으로

정렬을 하면 됩니다)

이런 식으로 차례대로 진행을 위의 프로세스 정보로 대입해봅니다.

처음 할당받은 프로세스의 CPU 사용 시간은 0 이기 때문에 다음 CPU 사용시간 적용
도착시간(AT) 값이 있으면 그 값을 빼주고 만약 AT값이 없다면 AT값을 0이라 생각하고 계산을 하면 됩니다.

대기시간(WT) = (전전 BT +  전 BT...) - 도착시간(AT)

P0: WT = 0 - P0의 도착시간
P0은 첫 번째로 할당을 받아 작업을 바로 시작하기 때문에 대기 시간이 없겠죠? 

그래서 0으로 두고
P1: WT = P0의 BT - P1의 도착시간
P0에서 CPU가 사용된 시간만큼 기다려야 하기 때문에 40에서 P1의 도착시간을 뺍니다
P2: WT = P0의 BT + P1의 BT - P2의 도착시간
P0, P1의 CPU 사용시간이 있기 때문에 두 프로세스의 합친 시간만큼 기다리는 시간이 발생합니다.
그리고 P2에 도착한 시간 만큼 뺍니다.

P3: WT = P0의 BT + P1의 BT + P1의 BT - P3의 도착시간
위와 같아요.

 

이제 숫자를 넣어 보면 아래와 같이 됩니다.
0
40 - 10 = 30
40 + 25 - 20 = 45
40 + 25 + 30 - 25 = 70

만약 대기시간이 0 이하가 나오면 대기시간을 더하면 안 되겠죠.

그래서 대기시간이 0 이상일 때만 대기시간을 누적하면 되겠습니다.

(프로그램 코드 작성시 유의 해서 조건을 주면 되겠죠?)

위 결과 값 총 대기시간을 계산을 해보면 145가 나옵니다.
평균 대기 시간은 전체 대기시간에서 프로세스 개수만큼 나누어 주면 되겠죠.
전체 대기시간 / 프로세스 개수
145 / 4 = 36.25

대기시간을 구했으니 우리는 반환시간을 구할 수 있습니다.

반환시간(TAT) = 대기시간(WT) + CPU 사용 시간(BT)

반환 시간의 경우 대기 시간과 CPU 사용시간을 더하면 구할 수 있습니다.
(0 + 40) + (30 + 25) + (45 +30) = 180 이 되고
이 평균값은
180 / 4 = 45 가 되겠네요

위 데이터 fcfs.inp 파일을 넣으면 FCFS스케줄링 공식을 적용하여 
각각의 프로세스의 대기시간(Waiting Time)을 구하여 그 합을 fcfs.out 파일에 출력을 하는 프로그램을
구현을 해봅니다.
총 반환시간도 화면에 출력을 해보고 대기시간의 평균과 반환시간의 평균도 화면에 출력해봅시다.

 

소스 코드 첨부 하고 이번 포스트를 마칩니다.

 

fcfs.inp 파일 내용

4
0 0 40
1 10 25
2 20 30
3 25 5

 

 

C++ 소스 코드

 

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>

struct ProcessInfo {
	int processNum;
	int arrvalTime;
	int burstTime;
};

class Process {
private:
	ProcessInfo *pinfo;
	int prcessCount;
	int *waitingTime;

public:
	Process(ProcessInfo *pinfo, int prcessCount) { 
		this->prcessCount = prcessCount; 
		this->pinfo = pinfo;
		this->waitingTime = new int[prcessCount];
	};

	~Process() { delete(this->waitingTime); };

	int getTotalWT();   // 대기시간 구하기
	int getTotalTAT();  // 반환시간 구하기
};

// 대기시간 구하기
int Process::getTotalWT() {
	int total_bt = 0;
	int total_wt = 0;

	// 첫번째 대기시간은 0
	waitingTime[0] = 0;
	for (int i = 1; i < prcessCount; i++) {
		total_bt += pinfo[i-1].burstTime;
		waitingTime[i] = total_bt - pinfo[i].arrvalTime;
		// 대기시간이 0 이상 일때만 대기시간 증가
		if (waitingTime[i] >= 0) {
			total_wt += waitingTime[i];
		}
	}

	return total_wt;
}

// Waiting time 이 구해지면 반환시간 구하기
int Process::getTotalTAT() {
	int total_tat = 0;
	for (int i = 0; i < prcessCount; i++) {
		total_tat += waitingTime[i] + pinfo[i].burstTime;
	}

	return total_tat;
}

// 도착시간으로 정렬
bool cmpArrvalTime(const ProcessInfo &p1, const ProcessInfo &p2) {
	if (p1.arrvalTime == p2.arrvalTime) {
		return p1.processNum < p2.processNum;
	} else {
		return p1.arrvalTime < p2.arrvalTime;
	}
	//return p1.processNum < p2.processNum;
}

// 파일에서 프로세스 정보 읽기
ProcessInfo* readInpFile(const char* filename, int &processCnt) {
	std::ifstream fin(filename);
	ProcessInfo *pinfo = NULL;
	if (fin.is_open()) {
		fin >> processCnt;
		pinfo = new ProcessInfo[processCnt];
		for (int i = 0; i < processCnt; i++) {
			fin >> pinfo[i].processNum;
			fin >> pinfo[i].arrvalTime;
			fin >> pinfo[i].burstTime;
		}
	}
	fin.close();
	return pinfo;
}

// 대기시간 합의 결과 파일에 출력
void writeOutFile(const char* filename, int data) {
	std::ofstream fout;
	fout.open(filename);
	fout << data;
	fout.close();
}

void showInfo(int cnt, ProcessInfo *pinfo) {
	printf("프로세스번호\t도착시간\tCPU사용시간\n");
	for (int i = 0; i < cnt; i++) {
		printf("%d\t\t", pinfo[i].processNum);
		printf("%d\t\t", pinfo[i].arrvalTime);
		printf("%d\n", pinfo[i].burstTime);
	}
	printf("\n");
}

int main(void) {
	const char* in_file = "fcfs.inp";
	const char* out_file = "fcfs.out";

	int cnt = 0;

	// 파일에서 프로세스 정보 읽기
	ProcessInfo *pinfo = readInpFile(in_file, cnt);
	printf("프로세스 개수: %d\n", cnt);
	
	// Arrval time 기준으로 프로세스 정렬
	std::sort(pinfo, pinfo + cnt, cmpArrvalTime);

	// 파일의 프로세스 정보 출력
	showInfo(cnt, pinfo);

	// FCFS  구하기
	Process p = Process(pinfo, cnt);

	// Waiting time(대기시간) 구하기
	int total_wt = p.getTotalWT();
	printf("총 대기시간: %d\n", total_wt);
	printf("평균 대기시간: %d\n", total_wt/cnt);

	// Turn Around Time(반환 시간) 구하기
	int total_tat = p.getTotalTAT();   // Waiting time 을 구하고 난뒤
	printf("총 반환시간: %d\n", total_tat);
	printf("평균 반환시간: %d\n", total_tat / cnt);

	// 대기시간 합의 결과 파일에 출력
	writeOutFile(out_file, total_wt);

	// 프로세스 정보 메모리 해제
	delete [] pinfo;

	return 0;

}

파이썬 2.7 소스 코드

# -*- coding:utf-8 -*-
# fcfs.inp 내용
# 첫번째 줄 프로세스 총 개수
# 두번재 줄 부터 프로세스 정보
# 프로세스 번호(process num), 도착 시간(arrival time), CPU 사용 시간(burst time)
in_file = 'fcfs.inp'
out_file = 'fcfs.out'

total_wt = 0   # 누적 대기시간
waitng_time = 0.0
proc_queue = []
proc_count = 0

# 입력데이터 로드
with open(in_file) as f:
    lines = f.readlines()

# 프로세스 개수
proc_count = int(lines[0])

# 프로세스 정보 두번째 라인 부터 
for i, line in enumerate(lines[1:]):
    # proc_queue.append([])
    inner_list = [elt.strip() for elt in line.split(' ')]
    inner_list = [x for x in inner_list if x]
    proc_list = map(int, inner_list)
    proc_queue.append(proc_list)
    # total_time += proc_queue[i][1]

proc_queue.sort(key = lambda proc_queue:(proc_queue[1], proc_queue[0]))

# proc_queue 리스트 정보
# 0 - 프로세스 번호(Process Number)
# 1 - 도착시간(Arrival Time)
# 2 - CPU사용시간(Burst Time)

# 출력
for i in proc_queue:
    print i[0], i[1], i[2]

print(proc_queue)

# 계산
total_bt = 0   # 누적 CPU 사용시간
wt = []   # 대기시간
wt.append(0)   # 첫번째 대기시간 0
for i in range(1, proc_count):
    total_bt += proc_queue[i-1][2]  # CPU 사용시간
    wt = total_bt - proc_queue[i][1]
    if 0 <= wt:
        total_wt += wt

# print proc_queue
print 'Total waiting time: ', total_wt
print 'Average waiting time: %.2f' % (total_wt/len(proc_queue))

# 파일 출력
f = open(out_file, 'w')
f.write(str(total_wt))
f.close()

파이썬 3 소스 코드

# fcfs.inp 내용
# 첫번째 줄 프로세스 총 개수
# 두번재 줄 부터 프로세스 정보
# 프로세스 번호(process num), 도착 시간(arrival time), CPU 사용 시간(burst time)
in_file = 'fcfs.inp'
out_file = 'fcfs.out'

total_wt = 0   # 누적 대기시간
waitng_time = 0.0
proc_queue = list()
proc_count = 0

# 입력데이터 로드
with open(in_file) as f:
    lines = f.readlines()

# 프로세스 개수
proc_count = int(lines[0])

# 프로세스 정보 두번째 라인 부터 
for i, line in enumerate(lines[1:]):
    # proc_queue.append([])
    inner_list = [elt.strip() for elt in line.split(' ')]
    inner_list = [x for x in inner_list if x]
    proc_list = list(map(int, inner_list))
    proc_queue.append(proc_list)

proc_queue.sort(key = lambda proc_queue:(proc_queue[1], proc_queue[0]))

# proc_queue 리스트 정보
# 0 - 프로세스 번호(Process Number)
# 1 - 도착시간(Arrival Time)
# 2 - CPU사용시간(Burst Time)

# 출력
for i in proc_queue:
    print(i[0], i[1], i[2])

print(proc_queue)

# 계산
total_bt = 0   # 누적 CPU 사용시간
wt = list()   # 대기시간
wt.append(0)   # 첫번째 대기시간 0
for i in range(1, proc_count):
    total_bt += proc_queue[i-1][2]  # CPU 사용시간
    wt = total_bt - proc_queue[i][1]
    if 0 <= wt:
        total_wt += wt

print('Total waiting time: ', total_wt)
print('Average waiting time: %.2f' % (total_wt/len(proc_queue)))

# 파일 출력
f = open(out_file, 'w')
f.write(str(total_wt))
f.close()