[OS] Scheduler Simulator 구현 (FCFS, RR, MLFQ, Stride)

운영체제 강의 과제에서 구현한 스케줄러 시뮬레이터이다. C로 작성되었으며 FIFO(FCFS), RR, MLFQ, Stride에 대한 스케줄링 알고리즘을 눈으로 볼 수 있다.

첫 프로젝트 과제가 스케줄러의 구현이라니, 막막했지만 무엇보다 기본에 충실하려 노력했고, 결과만 어떻게 내는 것이 아닌 과정이 실제 스케줄러의 정책과 동일하게 알고리즘을 작성했다.

개발환경은 수업에서는 우분투 VM 환경을 각자 사용하라고 했으나 Toast의 우분투 인스턴스를 사용하여 보다 쾌적하게 개발하였다.

1. 프로그램 구조

1-1. 프로젝트 폴더의 파일 리스트

- include: 스케줄러에 필요한 헤더가 포함된 directory
- lab1_sched.c: 스케줄러 알고리즘을 실질적으로 구현한 c file
- lab1_sched_test.c: 결과를 출력할 main 함수가 포함된 c file
- Makefile: make 커맨드를 사용하기 위해 gcc가 설정된 Makefile

1-2. lab1_sched.c에 작성된 함수

2. 프로그램 설명

2-1. FIFO

FIFO(FCFS)는 먼저 도착하는 순서대로 프로세스를 스케줄링하는 기법이다. 도착한 순서(Arrival Time)대로 single queue에 삽입되고, 스케줄링되는 프로세스의 수행 시간(Service time)이 0이 되면, 다음으로 도착한 프로세스를 수행시킨다.

구현된 모든 스케줄링 알고리즘 (FIFO, RR, MLFQ, STRIDE)는 Queue와 Array(구현 결과가 저장될 이차원 배열)을 초기화시킨 후 시작한다. 프로세스가 도착하면 Queue에 넣고 state(flag)를 RUN 상태로 바꾼다. 시간이 1초씩 증가함에 따라 queue가 비어있지 않으면 FIFO_pop 함수를 호출하여 queue의 가장 앞(head)에 있는 프로세스의 service time의 1초를 수행한다. 이 과정을 반복하다가 해당 프로세스의 service time이 0이 되면 queue의 맨 앞을 플러시(processEnd 함수)하고 queue를 pop한다.

2-2. RR

RR은 도착한 순서대로 single queue에 삽입되고, 시간적 할당(Time slice)를 주어서 time slice만큼 프로세스를 수행하고 service time이 남아있다면 다시 queue에 들어가는 방식이다. queue와 array를 초기화시키고 프로세스의 arrival time에 따라 insertQueue 함수를 통해 queue에 삽입한다. 그 후에 queue에 프로세스가 하나라도 있다면 RR_pop을 호출한다. 또한 프로세스의 상태를 알기 위해 insert_flag를 사용한다. time slice가 지나고 service time이 남아 있는 경우 queue의 가장 뒤(tail)에 삽입한다.

RR_pop 함수에서는 프로세스의 service time이 0이 되면 queue의 인덱스를 초기화시키고 다음 프로세스를 가리킨다. 첫 번째 프로세스의 service time이 남아있는데 두 번째 프로세스가 들어오는 경우 새로운 프로세스를 먼저 수행시킨다. 타임 퀀텀을 1로 고정한다면 queue의 개념 없이도 1초마다의 스케줄링을 할 수 있었는데 유동적인 타임 퀀텀을 사용하기 위해 원형 큐의 개념으로 접근했다.

2-3. MLFQ

MLFQ 본연의 정책에 어긋나지 않으려 노력했다. queue의 개수에 따라 타임 퀀텀()을 자동으로 할당한다. 시간을 증가시키며 도착하는 프로세스를 queue의 Top에 삽입한다. 그리고 queue를 탐색하여 스케줄링 대상을 결정한다. MLFQ의 기본적인 정책은 우선 순위가 가장 높은 queue부터 아래로 내려가며 제일 먼저 탐색된 프로세스를 수행시키는 것이다. 프로세스가 스케줄링되면 수행 완료 후 다음 queue의 위치를 선택해야 하며, queue에 설정된 time slice를 모두 사용하면 lower priority queue에 삽입하고, 그렇지 않다면 priority는 그대로 유지한다. 그리고 lowest priority queue에 도달하면 해당 queue의 time slice만큼 Round Robin의 방식으로 수행하게 된다.

위에서 설명한 알고리즘이 기본이고, 다른 예외 처리를 많이 했다. 모든 queue에서 프로세스가 하나라면 큐의 time slice를 모두 사용해도 lower priority로 내리지 않는다. 또한, 수행한 프로세스가 다시 queue에 삽입됨과 동시에 새롭게 도착한 프로세스가 있다면 새로운 프로세스에 우선 순위를 주었다.

2-4. STRIDE

STRIDE 스케줄링은 프로세스마다 Ticket을 부여하여 Stride를 계산하고, time slice마다 가장 낮은 stride의 프로세스를 수행하고 해당 프로세스의 stride를 누적하는 방식이다. ticket은 프로세스의 service time에 따라 자동으로 할당하고, 각 ticket의 LCM(최소공배수)를 구하여 각 프로세스의 stride를 정한다. 1초마다 스케줄링 대상이 되는 프로세스(schCandidate) 중 수행할 프로세스(schTarget)를 결정하기 위해 각 프로세스의 stride를 탐색하고 가장 낮은 stride를 가진 프로세스를 수행한다. 수행한 프로세스의 service time이 0이 되면 스케줄링 후보에서 삭제한다. 이 과정을 반복하다가 time이 width(프로세스 service time의 합)와 같아지면 구현을 종료한다.

3. 시뮬레이션 구현 결과

3-1. OSTEP 예제의 data로 실행

<input data>

<output data>

3-2. Stride 구현을 확인하기 위해 OSTEP의 Stride 예제의 data로 실행

<input data>

 <output data>

<OSTEP의 Stride 스케줄링 결과와 시뮬레이터 구현 결과가 같음>

4. 배포 자동화 - Makefile 작성

Makefile

# #    DKU Operating System Lab #        Lab1 (Scheduler Algorithm Simulator) #        Student id : 32164959, 32162436 #        Student name : Heo Jeon Jin, Shin Chang Woo # #   Makfeile : #       - Makefile for lab1 compilation. # CC = gcc INC = -I${CURDIR}/include/ CFLAGS = -g $(INC) OBJS_LAB1 = lab1_sched.o lab1_sched_test.o  SRCS = $(OBJS_LAB1:.o=.c) TARGET_LAB1 = lab1_sched .SUFFIXES : .c .o .c.o:     @echo "Compiling lab1 scheduler simulator $< ..."     $(CC) -c $(CFLAGS) -o $@ $< $(TARGET_LAB1) : $(OBJS_LAB1)     $(CC) -o $(TARGET_LAB1) $(OBJS_LAB1) all : $(TARGET_LAB1) dep :      gccmaedep $(INC) $(SRCS) clean :     @echo "Cleaning lab1 scheduler simulator $< ..."     rm -rf $(OBJS_LAB1) $(TARGET_LAB1)  new :     $(MAKE) clean     $(MAKE) Colored by Color Scripter

cs

5. 최종 의견

어떻게 하면 스케줄링 정책의 기본적인 정책을 지키며 코딩할 것인지 많이 고민했다. 평소 프로그램을 만들 때 sudo code(의사 코드)와 mock up(UI 디자인)을 종이에 그려보고 작업하는 편이라 이번에도 그렇게 했고, 실제로 많은 도움이 됐다.

기회가 된다면 스케줄러를 웹에서 만들어서 서비스해보고 싶다. 아마 다음 학기의 수강생이 될 후배 학우들에게도 많은 도움이 될 것이고, 결과물이 정말 괜찮다면 교수님이 만드신 lecture의 ppt에 reference에 기여할 수도 있다는 생각을 했다. c언어로 구현된 알고리즘을 nodejs 문법에 맞게 바꾸고, 프론트엔드에서 사용자가 프로세스 정보를 입력하면 서버에서 구현 결과를 클라이언트에서 볼 수 있게 해보고 싶다. 모든 과정(스케줄링 알고리즘)이 동기적으로 수행되어야 하기에 Promise 문법에 대한 공부를 좀 더 하고 나중에 만들어 볼 예정이다.

프로젝트 전체 폴더는 깃에서 받을 수 있다.

git clone https://github.com/zinirun/lab1_sched.git

cs