[Computer Science] [운영체제] CPU 스케줄링

프로세스 우선순위와 스케줄링 큐

스케줄링

• 여러개의 프로세스가 동시다발적으로 실행된다.
• 모든 프로세스는 실행하기 위해 자원이 필요하다.
• 운영체제가 공정하고 합리적으로 자원을 배분하는 방법이 스케줄링이다.
• 모든 프로세스(및 스레드)는 실행되기 위해 CPU를 필요로 한다

여러 프로세스들이 CPU를 나눠 사용하는 방법?

• 정해진 시간 동안 돌아가면서 CPU를 사용하는 것이 가장 좋지 않을까?
  • 아니다. 프로세스마다 우선 순위가 다르다
• 프로세스 우선순위는 PCB에 명시 된다.
• CPU 우선순위가 높은 프로세스는 더 많이 할당받아 실행이 자중하다.
• PRI, NI : 낮을수록 높은 우선순위, PRI는 운영체제, NI는 사용자

우선순위의 차이를 보이는 대표적인 프로세스 유형

• I/O bound process, CPU bound process
• I/O bound process가 일반적으로 CPU bound process보다 우선순위가 높다.
  • I/O bound process는 CPU보다 연산속도가 느리기 때문에 빠르게 실행하고 대기상태로 접어들게 만든다.. 대기 상태로 전환이 되면 볼일이 자주 없다.

 

 

• CPU burst: CPU 사용하는 구간
• I/O burst: 입출력 완료까지 대기하는 구간

스케줄링 큐

• 자원은한정되어있고 실행중인프로세스는여러개
• 프로세스들의 요구사항을 일목요연하게 관리하는 방법

• 스케줄링 큐는 한마디로 줄이라고 볼 수 있다. 특정 자원을 이용하는 프로세스 들이 서는 줄
• 우선순위에 맞게 CPU를 할당해준다.

큐 (Queue)

자료관점에서 큐는 먼저 삽입된애가 먼저 나오는 FIFO이다.

하지만 운영체제 관점에서는 스케줄링 큐에서 큐는 우선순위에 따라 나가는 것이 달라진다.

우선순위 낮은 프로세스가 먼저 큐에 삽입되었어도 우선순위 높은 프로세스가 먼저 처리될 수 있음

대표적인 스케줄링 큐

• 준비 큐: CPU 이용을 기다리는 프로세스들의 큐, 지금 당장에 이라도 실행할 수 있지만 나의 차례가 아닌 경우
• 대기 큐: 대기상태 프로세스들의큐(입출력요청), 특정 이벤트가 올 때 까지 기다리고 있는 상태

대기 큐의 유형

스케줄링 큐까지 반영한 프로세스 상태 다이어그램

선점형 스케줄링과 비선점형 스케줄링(정말 중요)

• 한 프로세스 실행 도중 다른 급한 프로세스가 실행되어야 한다면?
  1. 현재 실행 중인 프로세스의 자원을 빼앗아 해당 프로세스에게 할당 (선점형 스케줄링)
  2. 현재 실행 중인 프로세스 실행이 끝날때까지 해당 프로세스대기 (비선점형 스케줄링)

선점형 스케줄링 (타임아웃 기반 문맥 교환)

• 프로세스에 자원을 고루 할당 가능
• 문맥 교환 과정의 오버헤드

비선점형 스케줄링

• 고르지 않은 자원분배
• 문맥 교환 과정에서의 오버헤드 적음

CPU 스케줄링 알고리즘

운영체제마다 CPU 스케줄링 알고리즘이 다르다.

전공서 기준 CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소잔여시간우선스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링(FIFO 스케줄링)

• CPU를 먼저 요청한 프로세스부터 CPU 할당
• 준비 큐에 삽입된 순서대로 실행되는 비선점형 스케줄링

최단 작업 우선 스케줄링(SJF 스케줄링)

• 준비큐프로세스중CPU이용시간이짧은프로세스부터실행
• 호위효과 방지 , 평균 대기 시간이 줄어듬

라운드 로빈 스케줄링 (Round Robin 스케줄링)

• 선입 선처리 스케줄링 + 타임 슬라이스
• 준비 큐에 삽입된 순서로 실행하되, 타임 슬라이스(지정된 시간)만큼 실행
• 선점형 스케줄링

최소 잔여 시간 우선 스케줄링 (SRT 스케줄링)

• 최단작업우선스케줄링+라운드로빈스케줄링
• 작업 시간 짧은 프로세스부터 처리하되, 타임 슬라이스만큼 돌아가며

우선순위 스케줄링

범용적인 스케줄링이다. 앞서 말한 스케줄링 방법이 우선순위 스케줄링이라 말할 수 있다.

• 프로세스마다 우선순위 부여, 우선순위 높은 순으로 스케줄링
• 최단작업우선스케줄링–작업시간짧은순으로우선순위부여
• 최소잔여시간스케줄링–남은시간짧은순으로우선순위부여

아사(starvation) 현상

• 모든 우선순위 스케줄링 알고리즘의 근본적인 문제
• 우선순위 낮은 프로세스의 실행이 계속 연기되는 현상
• 우선순위 높은 프로세스 실행하느라 우선순위 낮은 프로세스 실행을 못한다
• 해결책: 에이징(aging) 기법
  • 대기 시간이 길어지면 점차 우선순위를 높이는 방식

다단계 큐 스케줄링

• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링
  • 다음으로 우선순위 높은 프로세스 처리
  • 다음으로 우선순위 높은 프로세스 처리
   

• 프로세스유형별로큐구분가능 e.g.) CPU 바운드, I/O 바운드, 백그라운드, 포그라운드, 실시간 프로세스 ...
• 큐별로다른스케줄링알고리즘적용가능 e.g.) 선입 선처리 큐, 라운드 로빈 큐, ...
• 큐별로다른타임슬라이스적용가능
• 기본적으로 프로세스는 큐 간의 이동 불가능 → 아사 현상 발생

다단계 피드백 큐 스케줄링

• 프로세스가큐간의이동가능

리눅스 스케줄링

실시간 정책 스케줄링 (우선순위 높음): 특수한 프로세스 경우

• SCHED_FIFO
• SCHED_RR

일반 정책 스케줄링 (우선순위 낮음): 일반적인 경우

• SCHED_OTHER/SCHED_NORMAL: 일반적으로 사용하는 경우
• SCHED_BATCH
• SCHED_IDLE

CFS (Completely Fair Scheduler)

비실시간 프로세스를 대상으로 하는 스케줄링 방식 (linux kernel 2.6.23~)†

vruntime (virtual runtime)

• 가상 실행 시간
• 프로세스가 그 동안 실행한 시간을 정규화한 정보
• vruntime이 작은 프로세스를 다음 실행할 프로세스로 삼음
• (vruntime 별 태스크를 고르는 과정에서 RB tree 사용)
• RB(Red-Black) tree는 자가 균형 이진 탐색 트리로 다음과 같은 특징을 가짐:
  • 모든 노드는 빨간색 또는 검은색
  • 루트 노드는 항상 검은색
  • 모든 리프 노드(NIL)는 검은색
  • 빨간색 노드의 자식은 반드시 검은색
  • 임의의 노드에서 리프 노드까지의 경로상 검은색 노드 수가 동일
  • normal task를 관리하기 위해, CFS는 시간 정렬된 run queue structure로 red-black tree를 사용한다. i
  • nsert / delete : 모두 O(log n) time. 빠르고 효율적임
  • 맨 왼쪽 값이 다음 scheduler 값 virtual runtime 값으로 서버를 ordering 한다.
• 이러한 특성으로 인해 트리의 균형을 유지하며, O(log n)의 시간 복잡도로 검색/삽입/삭제 연산이 가능함

타임 슬라이스

• nice 값에 비례해 가중치 할당, 가중치를 바탕으로 타임 슬라이스 할당
• nice : 사용자 영역에서 설정한 프로세스 우선순위
  • 사용자 영역에서의 값은 -20~19
  • 커널 영역에서의 값은 0~139
  • 실시간 스케줄링되는 프로세스: 0~99(값이 작을 수록 우선순위가 높다.)
  • CFS 프로세스: 100~139

nice 명령어

• 새 프로세스를 실행할 때 해당 프로세스의 우선순위 부여
• 기본적으로 설정된 nice 값은 0
• $ nice –n [우선순위] [program]
• $ nice –n 19 uptime

renice 명령어

• 이미 실행 중인 프로세스의 우선순위 부여
• $ renice [우선순위] [PID]
• $ renice +5 1234

결론

리눅스 스케줄링에서는 실시간 정책으로 FIFO, RR 비실시간 프로세스 경우에는 CFS 스케줄러 이용된다.

CFS 스케줄러에서는 virtual runtime과 타임 슬라이스가 있는데

virtual runtime은 작은 프로세스를 다음 프로세스로 삼고 타임슬라이스는 nice를 토대로 연산이 된다.