THINK-PRO BLOG

Q. 스케줄러는 무엇이며, 스케줄링을 하는데 있어서 중요한 것은 무엇인가?

스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위를 기반으로 CPU를 할당받게 해주는 역할을 한다. 스케줄러가 스케줄링을 하는데에는 2가지 중요한 요소가 있다. 첫 번째, 스케줄링의 최대 관심사는 무엇인가, 즉, 스케줄링의 기준은 무엇인가? 이다. 스케줄링의 기준이 될 수 있는 대표적인 예로는 대기 시간(waiting time), CPU 할당 시간(allocation time) 등이 있다. 두 번째, 스케줄링을 어떻게 구현할 것인가? 이다. 스케줄링을 구현할 때는 반드시 자료구조의 구현이 따른다. 어떠한 자료구조를 이용하여 스케줄링을 구현할 것인지를 결정하는 것이 스케줄링에 중요한 요소이다. 대표적으로, 링크드 리스트, 해쉬 리스트, 비트 맵, 레드 블랙 트리(리눅스) 등 다양한 자료구조를 사용하지만, 정밀하고 견고한 운영체제일 수록 스케줄링에 사용하는 자료구조의 실행시간을 최대한 줄여나가는 것이 중요하다. 최소한 O(log n) 수준으로 실행 시간을 낮춰야 한다.

Q. 스케줄링의 목표는 무엇인가?

스케줄링의 목표에는 3가지가 있다. CPU 활용을 최대화하자, 평균 대기 시간을 최소화하자. 처리량을 최대화하자. 스케줄링은 멀티 프로세싱 운영 체제를 디자인하는 일과 컴퓨터의 멀티태스킹 작업을 만들어내는 데에 있어서 핵심 개념이다.

Q.  스케줄링 알고리즘에는 무엇이 있나?

FCFS(First Come, First Served), SJF(Shortest Job First), Priority Scheduling, RR(Round Robin) Scheduling 등이 있다.

Q. FCFS(FIrst Come, First Served) 스케줄링은 무엇인가? 그리고 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  FCFS는 First Come, First Served 의 약자이다. 즉, 먼저 온 사람 먼저 대접한다는 뜻으로, CPU를 처음 요구한 프로세스가 CPU를 처음 사용한다는 의미의 스케줄링 알고리즘이다. 구현할 때는 FIFO (First In FIrst Out) 큐 자료구조를 사용한다. FCFS는 스케줄링 특성상 비선점 스케줄링 알고리즘이며, CPU를 사용하고 있는 프로세스 자기 자신이 CPU를 놓아줄 때까지 CPU를 다른 프로세스에게 양보하지 않는다. 이러한 특성은 콘보이 효과를 불러 일으킨다. 콘보이 효과란, CPU를 매우 오래 사용하는 프로세스가 도착하게 되면, 다른 프로세스가 CPU를 사용하는데 기다리는 대기 시간이 매우 커지는 현상을 말한다. 콘보이 효과는 비선점 스케줄링을 사용할 때만 발생한다. FCFS 스케줄링은 콘보이 효과때문에 평균 대기시간이 매우 형편없는 스케줄링 알고리즘이다. FCFS는 비선점 스케줄링 알고리즘의 장점을 그대로 가진다. 비선점 스케줄링 알고리즘은 모든 프로세스가 공평한 조건으로 CPU를 사용할 수 있게 해주며, 반응 시간을 예측할 수 있다.

Q. SJF 알고리즘은 무엇인가? 그리고 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  SJF는 Shortest Job First 의 약자이다. 가장 시간이 적게 걸리는 작업을 먼저한다는 뜻으로, SJF의 정의는 CPU가 릴리즈되어 있을 때, 가장 시간이 적게 걸리는 프로세스가 선택되어 실행된다는 것이다. SJF는 비선점 스케줄링과 선점 스케줄링 두가지 종류가 있고, 선점형 SJF는 SRTF(Shortest Remaining Time First)라고도 한다. SJF는 스케줄링 알고리즘 중에서 최소의 평균 대기 시간을 위해 최적화된 스케줄링 알고리즘이다. (즉, 스케줄링 알고리즘 중에서 평균 대기 시간을 가장 적게 가지는 스케줄링 알고리즘이다.) 

 SJF의 단점도 있다. SJF에서 최소의 오버헤드로 최적의 성능을 보장하도록 알고리즘을 구현하는 것이 힘들다는 것이 SJF의 단점이다. 선점형 SJF에서는 프로세스들끼리 서로 끼어들기 때문에, 다음 CPU 점유 시간을 예측하는 것이 매우 힘들다. (SJF는 CPU 점유 시간 자체를 예측해야만 구현할 수 있는 스케줄링 알고리즘이다. 즉, 미래를 예측해야 한다는 특성 자체가 SJF 알고리즘을 구현하는 것을 어렵게 만드는 것이다.) 이러한 특성은 제대로 성능을 발휘하는 선점형 SJF를 구현하는 것이 힘들게 한다. 

Q. Priority Scheduling 은 무엇인가? 어떤 특징을 가지고 있고, 어떤 장단점을 가지고 있나?

  높은 우선순위를 가진 프로세스가 항상 먼저 CPU를 사용할 수 있도록 구현한다. 우선순위 기반 스케줄링에는 치명적인 단점 이슈가 있다. 바로 Starvation(굶주림)이다. 우선순위가 낮은 프로세스는 영원히 작동하지 않을 수 있다. (우선순위가 낮은 프로세스의 대기 시간이 무한정 늘어날 수 있다.) Starvation의 해결책은 바로 Aging-method이다.   레디 큐에서 오랜 시간을 기다린 프로세스는 계속해서 우선순위를 높히게 하는 기법이다. 이러한 에이징 메서드 기법을 통해서 우선순위가 낮은 프로세스도 최대 한도의 대기 시간을 가질 수 있다. 참고로, 우선순위 스케줄링은 선점형 SJF와 비슷한 경향을 가지고 있다. 우선순위 스케줄링에서의 각 프로세스의 우선순위가 선점형 SJF 스케줄링에서의 예측 CPU 점유 시간과 동일한 역할을 한다. 우선순위가 높을 수록, 먼저 CPU를 사용할 수 있게 해주듯이, 예측 CPU 점유 시간이 짧을 수록 먼저 CPU를 사용할 수 있게 해준다는  것이 매우 흡사하다.

Q. Round Robin(RR) 스케줄링은 무엇인가? 어떤 특징과 장단점을 가지는가?

  Round Robin 스케줄링은 각각의 프로세스가 공평하게 시간 간격 동안 CPU를 활용할 수 있도록 하는 스케줄링 알고리즘이다. 정해진 시간 간격이 끝나면, CPU를 사용하고 있던 프로세스는 선점적으로 추방당한다. (레디 큐에 다시 들어가게 된다.) 여기서 정해진 시간 간격을 Time Quantum 이라고 한다. 

만약 레디 큐에 n개의 프로세스와 q의 time qunatum을 가지고 있다고 가정하면, 모든 프로세스는 최대한 (n-1)q 시간 안에 CPU 사용을 시작하게 됨을 보장할 수 있다. 따라서, 라운드 로빈은 SJF 스케줄링 보다 반응 시간 최적화에 있어서는 더 탁월한 스케줄링 알고리즘이다. (하지만 대기 시간의 최적화는 SJF가 더 좋은 편이다.)

쓰레드

(프로젝트 개요)

현재 pintos는 시스템 콜 핸들러가 제대로 구현되어 있지 않다. 시스템 콜이 발생해도 system call!! 이라는 출력문 하나만 달랑 뿌리고, 그대로 스레드가 종료된다.(thread_exit()) 따라서, 이번 프로젝트 2는 핀토스의 시스템 콜 핸들러 함수를 구현하고, 간단한 시스템 콜(halt, exit, create, remove)를 구현해본다.

| 시스템 콜?

사용자 모드 수준에서의 프로그램이 커널 기능을 사용할 수 있도록 해주는 인터페이스.

시스템 콜의 기능들은 커널 모드에서 실행되고, 처리 후 사용자 모드로 복귀됨.

(프로젝트 해결 방법 개요)

우선, 2가지 함수를 구현해야 함. 

1. 유저 영역은 0x08048000 에서 0xc0000000 사이에 (경계값 제외) 존재하는 주소값이면 유저 영역인 것이다. check_address를 구현할 때 이 바깥 범위의 값이면 exit (-1)을 호출해 프로그램을 종료시켜야 한다. (유저 영역이 아닌 커널 영역을 건드리는 프로그램은 프로그램을 종료시키는 것이 적절한 운영체제의 반응이다.)

2. get_argument 의 함수는 esp 인자에서 인자들을 4바이트씩 긁어온 후, arg라는 변수에 저장하는 행동을 한다. 참고로, arg에 저장하는 값들은 인자의 주소값이다. (이 부분을 정확히 이해하라.) arg에 주소값을 저장하지 않고 인자값 자체를 저장하면 안된다. 왜냐하면, 시스템 콜의 인자들이 전부 4바이트로 표현할 수 있다는 보장이 없기 떄문이다. (가령 문자열이 전달되어 온다면 어떻게 할것인가..? 해결방법은 문자열 자체의 주소값을 저장하는 것이다.)

따라서, arg에는 반드시 인자의 주.소.값이 저장되어야 함을 무한 강조!!

f->esp 의 첫 4바이트는 시스템 콜 넘버이므로, 그 다음 4바이트씩 count 횟수만큼 긁어와서 arg에 저장하면 된다.

============

시스템 콜 핸들러 함수

static void syscall_handler (struct intr_frame *f UNUSED)
{
/* 유저 스택에 저장되어 있는 시스템 콜 넘버를 이용해 시스템 콜 핸들러 구현 */
/* 스택 포인터가 유저 영역인지 확인 */
/* 저장된 인자 값이 포인터일 경우 유저 영역의 주소인지 확인*/
}

f->esp (유저 스택)에는 4바이트씩 인자들이 저장되어 있다. f->esp의 첫 번째 4바이트에는 시스템 콜의 넘버가 저장되어 있고, 그 뒤로 4바이트씩 시스템 콜의 인자가 저장되어 있다.

예를 들어, create 시스템 콜은 인자로 파일 이름과 파일의 첫 크기를 인자로 받는다. 그러면, create 시스템 콜이 발생할 때 유저 스택 포인터는

다음과 같은 구조를 띈다.

f->esp

(4바이트) 4

(4바이트) 0x100

(4바이트) 0x104

....

0x100은 파일 이름 문자열의 주소값이고, 0x104는 파일의 첫 크기의 주소값이다. 물론, 파일의 첫 크기값은 정수일테지만, 정수값 자체를 유저 스택에 저장하지 않는다. 유저 스택에는 '주소값'이 저장되어 있음을 무조건 기억하라. 따라서, 나중에 시스템 콜 핸들러에서 create 시스템 콜을 처리할 때 다음과 같이 처리해야 한다.

    case SYS_CREATE:/* 4 */
      f->eax = create((char *)*(int *)arg[0], (unsigned)*(int *)arg[1]);
    break;

pintos 운영체제에는 자체 내장되어 있는 테스트 프로그램이 있습니다. 

src/userprog/ 디렉토리에서 'make check' 쉘 명령어를 입력하면, 76개의 테스트를 실행하며, 마지막에 테스트의 결과를 알려줍니다.

76개의 테스트 중 (제가 봤을 때) 제일 디버깅이 어려운 테스트는 'multi-oom'테스트입니다.

multi-oom테스트의 목적은 pintos운영체제의 메모리 누수가 존재하는지를 확인합니다.

메모리 누수가 일어나는 곳을 찾아야 하는데 쉽지 않습니다. 

multi-oom 테스트를 해결해나가는 약간의 팁을 제공하자면,

1) malloc - free를 정확하게 사용해라. 

malloc함수는 힙영역에 새로운 메모리를 할당하는 함수입니다. 만약에 어떤 함수에서 메모리를 새로 할당한 이후, 그 함수가 종료되기 전까지 할당한 메모리가 사라지지 않는다면, 계속해서 쓸모없는 메모리가 남게 되어 메모리 누수가 발생합니다. 따라서, 함수 루틴 안에서 반드시 malloc을 사용한 경우에는 그에 대응하는 free를 해주기 바랍니다. 참고로, malloc을 한 이후, 그 메모리를 가리키는 포인터를 다음에도 계속 가지고 있다면, 즉시 free를 해줄 필요는 없습니다. 최종적으로 그 메모리가 필요없게 되었을 때 정확히 free를 해주는 것이 관건인 것이지요.

간단히 말하자면, 함수 내에서 임시적으로 사용하기 위해 할당한 메모리는 그 함수가 끝나는 시점에서 즉시 free로 메모리 해제를 해주어야 하고, 스레드 내에서 파일 디스크립터 테이블과 같이 스레드가 죽을 때까지 가지고 있어야 하는 정보에 대한 메모리는 스레드가 죽을 때, 메모리 해제를 해주면 되는 것이지요.

2) 1)과 같은 이유로, palloc_get_page에 대응하는 palloc_free_page를 철저하게 사용하라.

1)과 동일한 이유입니다. palloc_get_page도 메모리를 할당하는 함수이고, palloc_free_page도 메모리를 해제하는 함수입니다.

3) 문자열에 대한 메모리 누수를 정확하게 계산하라.

운영체제를 건축하는 일은 C언어의 메모리 사용을 '정확히' 알아야 합니다.

하지만, 제가 학부생으로서 다른 친구들을 보았을 때 C언어의 메모리(포인터) 사용을 정확하게 아는 사람은 정말 드물어요.

아마 4학년 졸업한 후에도 10명 중 1명이 채 안될 겁니다. 정말 세밀한 부분까지 완벽하게 이해한 사람은 거의 없습니다.

물론 저도 아직 부족한 부분이 많고, 운영체제를 건축해보면서 더더욱 부족한 부분을 알게 되고 수정해나가네요.

그런 부분에서 큰 성장을 하는 것 같아 기분이 좋습니다. :) 

첫 번째 과제의 목표는 프로그램의 이름과 인자를 구분하여 스택에 저장, 인자를 응용 프로그램에 전달하는 기능을 구현하는 것이다.

이를 위해 소규모 목표를 잡아 보면,

1. 응용프로그램의 실행 흐름을 추적하여 파싱 시점을 알아내야 한다.

2. 파싱을 어떻게 할 것인가?

3. 파싱한 인자들을 전달하는 인자 전달 메커니즘을 이해하고, 인자를 전달하는 인터페이스를 구현한다.

| 1. 응용프로그램의 실행 흐름을 추적하여 파싱 시점을 알아내야 한다.

이러한 과정을 지나치며 응용 프로그램이 시작된다. 

run_task에서 start_process 함수까지 진행이 되는 동안 함수들의 인자는 char ** argv 가 전달되는데, 이는 커맨드 라인 전체를 포함하고 있다. (예를 들어, 'ls -a'를 pintos 시작 시 받은 경우, argv 를 'ls -a' 전체를 받는 것이다.)

따라서, 이를 파싱해야 할 시점을 찾을 수 있다. 바로, start_process 에서 load 함수를 호출하는 그 때, 문자열을 파싱하여 넘겨주어야 한다.

| 2. 파싱을 어떻게 할 것인가?

start_process 함수에서 load 함수를 호출하기 전에 문자열을 파싱해야 한다. 문자열 파싱 함수로는 strtok_r 을 쓰도록 하자.

| 3. 파싱한 인자들을 전달하는 인자 전달 메커니즘을 이해하고, 인자를 전달하는 인터페이스를 구현한다.

유저 스택에 파싱된 토큰들을 저장하는 함수를 구현해야 한다.

'핀토스' 운영체제의 몇몇 기능들을 구현해나가며 개선하는 것이 목표입니다.

프로젝트 개요는 다음과 같습니다.