Front-end Developer

0%

Operating Systems - CPU 스케줄링

Posted on Edited on

CPU: 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리 장치

CPU는 일반적으로 시스템 내에 하나 뿐이기 때문에 여러 프로그램이 동시에 수행되는 시분할 환경에서 매우 효율적으로 관리되어야 한다.

프로그램 실행에는 CPU 내에서 수행되는 기계어 명령은 다음의 세 가지가 있다.

  1. CPU 내에서 수행되는 명령
  2. 메모리 접근을 필요로 하는 명령
  3. 입출력을 동반하는 명령
  • CPU 버스트(CPU burst): 1,2는 사용자 프로그램이 직접 CPU를 가지고 수행하는 비교적 빠른 명령. 프로그램이 I/O를 한 번 수행한 후 다음번 I/O를 수행하기까지 직접 CPU가지고 명령을 수행하는 일련의 작업이다.
  • I/O 버스트: 3은 I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하기 때문에 비교적 느린 명령이다. I/O 작업이 요청된 후 완료되어 다시 CPU 버트스토 돌아가기까지 일어나는 일련의 작업이다.

각 프로그램마다 CPU버스트와 I/O 버스트가 차지하는 비율은 균일하지 않지만 아래와 같이 프로세스를 분류해볼 수 있다.

  • I/O 바운드 프로세스: I/O 요청이 빈번해서 CPU 버스트가 짧게 나타난다. e.g. 대화형 프로그램
  • CPU 바운드 프로세스: I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타난다. e.g. 계산위주 job

CPU는 이와 같이 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내에서 실행되기 때문에 효율적인 스케줄링이 매우 중요하다. CPU 스케줄링 시 CPU 버스터가 짧은 프로세스(I/O 바운드 프로세스)에게 우선적으로 CPU를 사용할 수 있도록 한다. CPU 바운드 프로세스를 먼저 CPU에 할당하면 그 프로세스가 CPU를 다 사용할 때까지 I/O 바운드 프로세스의 응답 시간이 길어지고, 해당 I/O 장치도 그 시간동안 작업을 수행하지 않기 때문이다.

CPU 스케줄러

준비 상태에 있는 프로세스 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영 체제의 코드

스케줄링 방식

  1. 비선점형 방식(nonpreemptive): CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 빼앗기지 않음.
    1. 실행 상태 -> I/O 요청 -> blocked
    2. CPU에서 실행 중이던 프로세스 종료
  2. 선점형 방식(preemptive): 프로세스가 CPU를 계속 사용하기 원하더라도 강제로 빼앗을 수 있음.
    1. 실행 상태 -> 타이머 인터럽트 -> Ready
    2. I/O 요청 -> 봉쇄 -> I/O 작업 완료 -> 인터럽트 -> Ready

디스패치

CPU 스케줄러가 어떤 프로세스에세 CPU를 할당할지 결정하고 나면 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경 설정을 하는 커널 모듈

스케줄링의 성능 평가

  • 시스템 관점: 시스템 입장에서의 성능 척도. CPU 활용도와 처리량
  • 사용자 관점: 프로그램 입장에서의 성능 척도. 소요 시간, 대기 시간, 응답 시간 등 기다린 시간과 관련된 지표
  1. CPU 활용도: 전체 시간 중 CPU가 명령을 수행한 시간의 비율. 휴면(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 중요하다.
  2. 처리량: 주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수. CPU 버스트가 짧은 프로세스에게 우선적으로 할당하는 것이 유리하다.
  3. 소요 시간: 프로세스가 CPU 요청 시점부터 CPU 버스터가 끝날 때까지 걸린 시간. 준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간
  4. 대기 시간: 프로세스가 CPU 버스트 기간 중 준비 큐에서 기다린 시간의 합
  5. 응답 시간: 프로세스가 CPU 요청 시점부터 처음으로 CPU를 얻을 때까지 걸린 시간. 시분할 환경에서 매우 중요함.

스케줄링 알고리즘

1. FCFS (First-Come First-Served)

프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당

비선점형으로 먼저 요청한 프로세스가 자발적으로 CPU를 반납할 때까지 선점하지 않는다. 따라서 먼저 도착한 프로세스가 작업 시간이 길 경우 다수의 프로세스들이 앞 작업이 끝날 때까지 기다려야 해서 평균 대기 시간이 길어질 수 있다. 이렇게 CPU 버스트가 긴 프로세스 다음에 짧은 프로세스가 도착해서 오랜 시간을 기다려야 한다면 이를 콘보이 현상이라고 한다. 이런 경우 I/O 장치의 활용도까지도 떨어지게 된다. 그래서 짧은 프로세스가 도착하면 평균 대기 시간은 짧아지고, 프로세스의 성격에 따라 긴 프로세스가 먼저 도착하면 평균 대기 시간이 길어진다.

2. SJF (Shortest-Job-First)

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당

평균 대기 시간을 가장 짧게 하는 최적을 알고리즘이다.

  • 비선점형 방식: 현재 CPU에서 실행중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 프로세스가 도착하면 CPU를 빼앗긴다. (SRTF: Shortest Remaining Time First)
  • 선점형 방식: 현재 CPU를 점유하고 있는 프로세스가 CPU 버스트를 모두 수행하고 스스로 CPU를 내어놓을 때까지 스케줄링을 하지 않는다.

시분할 환경에서는 중간중간 새로운 프로세스가 도착하는 경우가 발생하기 때문에 선점형 방식이 평균 대기 시간을 가장 많이 줄일 수 있다. 하지만 프로세스의 CPU 버스트 시간을 미리 알 수 없기 때문에 과거의 CPU 버스트 시간을 통해 시간을 예측해서 프로세스에 CPU를 할당한다. 그런데 어떠한 프로세스가 시작되었는데, 그 다음으로 CPU 버스트가 짧은 프로세스가 계속 도착해서 CPU를 빼앗기게 되고, 짧은 프로세스가 계속 도착하게 되면 처음 프로세스는 영원히 CPU를 할당받을 수 없을 수 있고, 이를 기아(starvation) 현상이라 한다.

3. 우선순위 스케줄링

준비 큐에서 기다리는 프로세스들 중에 우선순위가 가장 높은 프로세스에게 제일 먼저 할당

우선순위는 우선순위값을 통해 표시해서 그 값이 작을수록 높은 우선순위를 가지는 것이다. 우선순위 스케줄링도 SJF처럼 기아 현상이 있을 수 있는데, 우선순위가 높은 프로세스가 계속 도착하면 우선순위가 낮은 프로세스는 CPU를 얻지 못하고, 계속 대기해야 하기 때문이다. 이를 해결하기 위해서 노화 기업(aging)을 사용하고, 이는 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 하는 것이다.

4. 라운드 로빈 스케줄링

시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식

각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 제한되며, 시간이 경과한 프로세스가 있으면 CPU를 회수해서 준비 큐에 있는 다른 프로세스에게 CPU를 할당한다. 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대 시간은 할당 시간이라 부른다. 할당시간이 너무 길면 FCFS처럼 콘보이 현상이 발생할 수 있고, 반대로 너무 짧으면 CPU 프로세스 교체가 빈번해서 문맥 교환에 오버헤드가 커진다. 따라서 할당 시간은 수십 밀리세컨드 정도의 규모로 설정한다. 라운드 로빈은 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이고, 대화형 프로세스의 빠른 응답 시간을 보장할 수 있다는 장점이 있다.

References
운영체제
[운영 체제와 정보 기술의 원리] 반효경 지음