[운영체제] 프로세스 스케줄링 2 (process scheduling)

이전 글에서 공부했던 것은 클래식한 스케줄링 방법이고, 이번 글에서는 조금 더 복잡한 스케줄러에 대해 공부한다.

Priority Scheduling

우선순위 스케줄링, 사실 SJF, STCF 스케줄러도 우선순위 스케줄러이다. 앞서 공부했던 이 스케줄러들의 문제점은 무엇일까?

• startvation
  굶주림 문제가 있다. 계속해서 높은 우선순위의 프로세스가 들어온다면 우선순위가 낮은 프로세스는 오랫동안 실행되지 않는다. 이러한 문제를 해결해 보자!

EDF Eariest Deadline First

데드라인이 빠른 프로세스를 먼저 실행하는 것이다. 당연한 얘기지만 preemtive 한 스케줄러이다. 이 스케줄러가 유명한 이유는 데드라인에 대해서 최적이기 때문이다. 이 스케줄러로 데드라인을 맞출 수 없다면 어떤 스케줄러를 가져와서 데드라인을 맞출 수 없다. 이 스케줄러는 데드라인을 안다고 가정하고 있다. 주로 RTOS 에서 사용한다. (Real Time Operation System)

MLQ MultiLevel Queue

1. 우선순위가 높은 큐와 낮은 큐를 만든다.
2. 높은 큐에 CPU 시간을 더 많이 분배한다.
   우선순위가 높은 큐는 interactive 한 프로세스이고, 우선순위가 낮은 큐는 주로 background 에서 돌아가는 CPU bound process 일 것이다. 따라서 우선순위가 높은 큐는 같은 우선순위 프로세스에 대해 RR 스케줄링을, 낮은 큐는 FCFS 스케줄링을 적용한다. 이 스케줄러는 어떤 프로세스가 interactive process 인지 알고 있다고 가정한다. 만약 정확히 안다고 하더라도 CPU bound 에서 foreground process 로 바뀌거나 그 반대의 경우에 대해서는 처리하지 못 한다.
   우리는 어떠한 가정을 하지 않고도 interactive process 는 높은 우선순위를, CPU bound process 는 낮은 우선순위를 주고 싶다. 즉, 일반화 시키고 싶다.

MLFQ MulitLevel Feedback Queue

이 스케줄러는 더 많은 수의 큐를 가지고 있다. (보통 4개) 각각의 큐는 우선순위가 다르다. 다음과 같은 규칙을 따른다.

1. 우선순위가 높은 큐를 먼저 실행한다.
2. 우선순위가 같다면 RR 스케줄링한다.
3. 처음 진입한 프로세스는 가장 높은 우선순위 큐에 넣는다.
4. a) time slice 를 다 사용하면 한 단계 낮은 큐로 이동시킨다.
   b) time slice 를 다 사용하지 않으면 우선순위를 유지한다.

• 우선순위가 낮을수록 time slice 가 크다. (유사 STCF)

interactive process
interactive process 가 들어오면 timeslice 를 다 사용하기 전에 I/O 요청으로 waiting queue 로 빠진다. 따라서 계속해서 높은 우선순위를 유지할 수 있다.

CPU bound
CPU bound process 가 들어오면 오랫동안 실행되기 때문에 처음엔 실행하다가 점점 낮은 순위로 이동하게 된다.

STCF approximation
CPU bound process 의 경우 여러 개가 들어올 경우 근사적으로 STCF 를 따라한다.

아주 좋은 스케줄링 방법처럼 보이지만 여전히 문제점이 존재한다.

• starvation 문제가 존재한다.
• timeslice 를 악용할 경우 cheating 문제가 존재한다.

stavation 문제 해결

다섯 번째 규칙 : 일정 시간마다 모든 프로세스를 높은 우선순위 큐로 boost 시켜준다.

• starvation 문제 해결
• 동적으로 중요도가 바뀌는 프로세스의 우선순위 해결

cheating 문제 해결

규칙 4.b. 변경. 지금까지 프로세스가 사용한 time slice 시간을 유지하고, 다 사용하면 우선순위를 낮춰 준다.

구현시 고려사항

1. 몇 개의 큐를 만들 것인가?
2. 각 큐에 CPU 시간을 얼마나 할당할 것인가?
3. 각 큐의 time slice 는 얼마나 줄 것인가? 그리고 꼭 RR 을 사용하지 않을 수도 있다.
4. priority boost 시간을 얼마로 할 것인가?

상용 OS 에서 많이 사용하고 있다. 윈도우에서도 작업관리자에서 사용자가 프로세스의 우선순위를 높여줄 수 있다.

fairness

fairness 를 고려한 스케줄링

lottery scheduling

로또 스케줄링

1. 각 프로세스에 다른 수의 티켓을 분배한다.
2. 난수를 생성해 당첨된 프로세스를 실행한다.

장점 : 구현이 쉽다. MLFQ 처럼 많은 정보를 유지하지 않아도 된다. 새 프로세스가 들어오면 티켓 수만 조절하면 되고 수정도 쉽다.
문제점 : 완벽한 난수를 생성하기 어렵다. 짧은 시간 수행할 경우 공정하지 않을 가능성이 있다.

stride scheduling

1. 위 스케줄러처럼 티켓을 분배한다.
2. 티켓들의 최소공배수를 구한다.
3. stride = (최소공배수) / (티켓수)
4. pass += stride
5. pass 값이 작은 프로세스를 우선적으로 실행시켜 준다.
   각 프로세스는 한 번 실행할 때마다 pass 값을 stride 만큼 더해준다. 티켓 수가 많을 수록 stride 값이 작으므로 더 많이 수행할 수 있다. 일정 시간(모든 프로세스의 pass 가 최소공배수가 되는 시점)마다 정확히 티켓만큼의 비율로 CPU 시간을 분배할 수 있다.

lottery scheduling 보다 구현하기 어렵다. 새 프로세스가 들어올 경우 전체 티켓수가 바뀌고, 새 프로세스의 pass 값을 어떻게 설정할 것인가의 문제가 생긴다. pass 값도 유지해야 한다.

두 스케줄링 모두 티켓을 얼마나 줘야하는 지에 대한 문제가 있다. 이 문제는 아직도 풀리지 않은 문제이다.

• 인천대학교 컴퓨터공학부 3학년 전공필수 과목인 박문주 교수님의 운영체제 강의를 듣고 작성한 글입니다.