018



CPU Scheduling 왜 하나요?

CPU는 지난 정리에서 살펴봤듯이, 컴퓨터 시스템을 통제하고 프로그램의 연산을 실행하고 처리하는 컴퓨터 시스템의 핵심 장치입니다.

01. CPU Scheduler는 무엇일까요?

CPU 스케줄러는 프로세스가 생성된 후 종료될 때 까지 모든 상태 변화를 조정하는 일을 합니다.

즉 스케줄러가 하는 CPU 스케줄링은 간단히 말해

Ready 상태에 있는 여러 프로세스 중 어떤 프로세스에 CPU를 배정할지 결정하는 일 입니다.

이 작업은 컴퓨터 시스템의 효율에 직결되며 매우 중요한 일 이겠죠.

컴퓨터는 CPU 스케줄링을 통해서 모든 프로세스가 공평하게 작업할 수 있도록 관리합니다.

하지만 때론 안정성, 효율성을 높이기 위해 공평성의 일부분을 희생하는 일도 나타납니다.

01-1. 스케줄링이 추구하는 목적

  • 공평성 : 모든 프로세스가 자원을 공평하게 배정받으며, 특정 프로세스를 배제해서는 안된다.
  • 효율성 : 시스템 자원을 놀리는 시간 없이 스케줄링한다.
  • 안정성 : 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 한다.
  • 반응 시간 보장 : 응답이 없는 경우, 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응한다.
  • 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.



02. 스케줄링의 단계

  1. 고수준 스케줄링(long-term scheduling, job scheduling, admission scheduling)
    1. 가장 큰 틀에서 이루어지는 CPU 스케줄링이며, 시스템 내의 전체 작업 수를 조절합니다.
  2. 중간 수준 스케줄링
    1. 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절합니다. (프로세스를 보류 상태로 보냅니다 = 스왑 영역으로 내립니다.)
    2. 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 합니다.
  3. 저수준 스케줄링(short-term scheduling)
    1. 가장 작은 단위의 스케줄링으로, 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정합니다.

Untitled

보통 우리가 공부하는 스케줄링의 내용은 ‘저수준(단기) 스케줄링’이라 생각하면 되겠네요.



03. 스케줄링 시 고려사항

03-1. preemptive or non-preemptive

  • preemptive(선점형 스케줄링)
    • 프로세스가 CPU를 할당받아 실행 중이더라도, 운영체제가 CPU를 강제로 빼앗을 수 있는 방식입니다.
    • CPU 처리 시간이 매우 긴 프로세스가 CPU 사용을 독점하는 것을 막을 수 있어 효율적인 운영이 가능합니다.
    • 잦은 문맥 교환(Context Switching)으로 오버헤드가 많이 발생합니다.
  • non-preemptive(비선점형 스케줄링)
    • 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식입니다.
    • 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 작습니다.
    • 프로세스 배치에 따라 효율성 차이가 상당합니다.

03-2. CPU bound or I/O bound

두 프로세스가 함께 Ready상태에 있다면, 입출력 집중 프로세스에 먼저 CPU를 할당하는 것이 더 효율적입니다.

→ 입출력 집중 프로세스(I/O bound)는 CPU를 빠르게 쓰고 I/O burst를 하러 나가기 때문에 다른 프로세스가 오래 기다리지 않아도 됩니다.

03-3. 전면 프로세스 or 후면 프로세스

  • 전면 프로세스
    • GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓여 현재의 입출력이 사용되고, 사용자와 상호작용이 가능한 프로세스 (상호 작용 프로세스)
    • 워드 프로세스 등이 있습니다.
  • 후면 프로세스
    • 사용자의 입력 없이 작동합니다. (일괄 프로세스)
    • 압축 프로세스 등이 있습니다.

전면 프로세스는 사용자의 요구에 즉각 반응해야 하기 때문에 먼저 처리해 줘야 합니다.

03-4. 프로세스 우선순위

CPU 스케줄러 대부부은 프로세스에 우선순위를 매겨 우선순위가 높은(우선순위 숫자가 작은) 프로세스를 먼저 처리되도록 합니다.

커널 프로세스 > 일반 프로세스
전면 프로세스 > 후면 프로세스
대화형 프로세스 > 일괄 처리 프로세스
입출력 집중 프로세스 > CPU 집중 프로세스



04. 스케줄링 알고리즘

04-1. Scheduling Criteria(성능 척도)

스케줄링 알고리즘을 알아보기 전, 이의 효율성을 판단하는 기준이 있습니다.

주의 ) 작업을 마친다는 것 = 하나의 프로세스가 종료된다는 것이 아닌, CPU의 입장에서 프로세스가 들어와 작업을 처리하고 나갔을 때를 말하는 것

CPU의 입장

  • CPU utilization(CPU 사용률)
    • 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
    • 즉 최대한 CPU를 바쁘게 만드는 것
    • 가장 이상적인 수치 : 100%
  • Throughput(처리량)
    • 단위 시간동안 작업을 마친 프로세스의 수
    • CPU burst를 처리한 수

⇒ 일정 시간동안 CPU 하나 가지고 최대한 많은 일을 처리하면 좋다.

프로세스의 입장

  • Turn-around time(반환 시간)
    • 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간.
    • 프로세스의 대기 시간(1번일 수도 있고 여러번일 수도 있음) + 실행 시간
  • Waiting time(대기 시간)
    • 프로세스가 CPU를 할당받아 실행되기 전 대기 상태일때의 시간
    • Ready queue에서 대기를 하는 시간
  • Response time(응답 시간)
    • 프로세스가 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간

⇒ CPU를 빨리 얻어서 나의 작업을 마치면 좋다.

예를 들어,

선점형 스케줄링에서 Ready queue에서 ‘최초’로 CPU를 얻기까지 걸린 시간 → Response time

CPU를 받고 뺏기고 받고 뺏기고를 반복할 때 마다, Ready queue에서 대기한 각각의 시간 → waiting time

CPU 기다리는 시간 + 쓴 시간 + 기다리는 시간 + 쓴 시간… + 나갈 때 까지의 총합 → Turn-around time

💡 응답시간과 대기시간의 정확한 차이
→ 대기 시간은 반환 시간과 마찬가지로 여러 번 있을 수 있지만, 응답 시간은 최초의 1번입니다.
→ 프로세스 입장에서 CPU를 한 번도 못 얻은 것과, 한 번이라도 얻는 것은 사용자 응답에 있어 중요한 차이가 있습니다.

04-2. 알고리즘 종류

FCFS (First Come First Served)

말 그래도 선입 선출 방식으로, Ready queue에 도착한 순서대로 CPU를 할당하는 비선점형 방식입니다.

  • 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리 시간을 따로 고려하지 않기 때문에 매우 단순하고 공평한 방법입니다.
  • 하지만, CPU 처리 시간이 긴 프로세스가 앞에 올 경우, 뒤의 프로세스는 한없이 기다려야 하기 때문에 매우 비효율적입니다. (콘보이 효과)

Untitled 1

SJF (Shortest Job First)

Ready queue에 있는 프로세스 중, 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식입니다.

  • 늦게 도착하더라도 CPU 처리시간이 앞의 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있어 콘보이 효과를 완화할 수 있습니다.
  • 단, 비선점형 방식이기 때문에 CPU를 사용중인 프로세스보다 처리 시간이 짧더라도 CPU를 빼앗지 못합니다.
  • 처리 시간이 긴 프로세스의 경우, 처리 시간이 짧은 프로세스에게 계속 밀려 Ready queue에서 CPU를 영영 할당받지 못할 수 있습니다. (starvation 현상)
  • 중간에 I/O burst가 빈번하게 요구되는 프로세스의 경우, 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵습니다.

Untitled 2

HRN(Highest Response Ratio Next)

SJF 스케줄링에 Aging 기법을 합친 비선점형 알고리즘입니다.

starvation을 해결하기 위해, 대기 시간이 길어지면 우선 순위를 높여주는 방법입니다. (Aging)

  • 공평성이 말끔히 해결되지는 못합니다.

SRTF(Shortest Remaining time First)

SJF의 선점형 방식입니다.

먼저 온 프로세스가 CPU를 할당받고 있더라도, 남은 처리시간이 뒤에 온 프로세스의 처리 시간보다 길면 CPU를 빼앗깁니다.

  • 어떠한 알고리즘보다 평균 대기 시간이 가장 짧습니다.
  • 기본적으로 선점형 방식이기 때문에 잦은 문맥 교환(Context Switching)이 일어나고 그에 따른 오버헤드가 심합니다.
  • starvation 현상이 심화될 수 있습니다.
  • CPU의 예상 시간을 예측하기가 더욱 힘들어 실제로 사용되기 어렵습니다. (exponential averaging을 통해 예측할 수는 있습니다.)

Untitled 3

Priority Scheduling

프로세스의 중요도에 따라 매긴 우선순위를 반영한 알고리즘으로

SJF, HRN, SRTF도 우선순위 알고리즘의 일종입니다.

  • 위의 알고리즘들의 문제점과 마찬가지로 starvation, 공평성 문제가 존재합니다.

RR (Round Robin)

프로세스에게 각각 동일한 CPU 할당시간(타임 슬라이스, quantum)을 부여해서 해당 시간 동안만 CPU를 이용하게 하는 선점형 알고리즘입니다.

만약 할당 시간동안 처리를 완료하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘깁니다.

빼앗긴 프로세스는 Ready queue의 맨 뒤로 가게 됩니다.

  • 따로 CPU 처리 시간을 계산하지 않아도 되어, 선점형 방식의 가장 단순하고 대표적인 방법입니다.
  • 우선 순위가 없어 매우 공평합니다.

RR 알고리즘의 경우, 할당 시간이 q고 대기 중인 프로세스의 개수가 n개라면, 어떤 프로세스도 (n-1)q 이상을 기다리지 않아도 됩니다.

→ 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있는 큰 장점을 가집니다.

Untitled 4

위의 그림은 time quantum = 5인 경우

RR 방식에서 가장 중요한 부분은 타임 슬라이스(time quantum)의 크기 결정입니다.

  • 타임 슬라이스가 큰 경우
    • 처리 시간이 긴 프로세스에 의해 CPU의 효율성이 떨어질 수 있습니다.
    • 타임 슬라이스가 크면 클수록 FCFS(선입 선출)알고리즘과 다를바가 없습니다.
  • 타임슬라이스가 작은 경우
    • 여러 프로그램이 동시에 실행되는 효과를 볼 수 있지만 너무 잦으면 오버헤드가 상당히 커질 수 있습니다.

보통의 타임 슬라이스는 10-100ms 범위로 설정합니다.

Multilevel Queue

다단계 큐 스케줄링은 우선순위에 따라 Ready queue를 여러개 사용하는 방식입니다.

당연히 우선순위가 높은 큐에 먼저 CPU가 할당되고, 해당 큐에 속한 프로세스가 모두 처리되야 다음 우선순위 큐가 실행될 수 있습니다.

한번 우선순위가 매겨져 Ready queue에 들어가면 해당 우선순위는 바뀌지 않습니다.

  • 각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있습니다.
  • 전면 프로세스들이 속해있는 큐는 우선순위가 높으며, RR 알고리즘을 이용하여 타임 슬라이스를 작게 합니다.
  • 후면 프로세스들이 속해있는 큐는 사용자와의 상호작용이 없으므로 FCFS 알고리즘을 사용합니다.
  • 보통 CPU 총 시간의 80%가 전면 프로세스, 20%는 후면 프로세스 처리에 할당됩니다.
  • starvation과 공평성 문제가 존재합니다.

Untitled 5

Multilevel Feedback Queue

다단계 큐의 공평성 문제를 완화하기 위해 신분 하락(우선순위 조정)이 가능한 알고리즘입니다.

  • 한번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아집니다. → 낮은 큐로 이동
  • 우선순위가 높아져 상위 큐로 이동할 수도 있습니다. → 일정 기간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동시킨다. → 부두 상수 S(voo-doo constants)의 값을 적절하게 조정해야 합니다.
  • 우선순위가 높은 큐보다 우선순위가 낮은 큐에 타임 슬라이스 크기를 크게 줍니다. → 어렵게 얻은 CPU를 조금 더 오랫동안 사용하게 해주기 위함 → 주로 상위 큐의 배수로 제공 (상위 큐가 8이라면 하단의 큐는 16)

Untitled 6

고려해야 할 사항

  1. 몇개의 큐가 존재하는가?
  2. 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가?
  3. starvation을 피하고 변환된 행동을 반영하기 위해서 얼마나 자주 우선순위가 상향 조정되어야 하는가? (부두 상수 S로 결정)


출처

https://jhnyang.tistory.com/25

https://bnzn2426.tistory.com/65

https://velog.io/@ssseungzz7/OS-CPU-Scheduling

반효경 교수님 운영체제 강의

카테고리: ,

업데이트:

댓글남기기

다른 게시글