CPU 스케줄링
CPU 스케줄링이란 어떤 작업에 CPU를 배정할지 결정하는 것이다. (프로세서 스케줄러processor scheduler 라고도 한다.)
CPU 스케줄링은 규모에 따라 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링으로 구분된다.
고수준 스케줄링
- 가장 큰 틀에서 이루어지는 CPU 스케줄링을 고수준 스케줄링(high level scheduling) 또는 장기 스케줄링(long-term sheduling) 작업 스케줄링(job scheduling)이라고 한다.
- 고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것이다.
- 고수준 스케줄링은 전체 시스템의 부하를 고려하여 작업을 시작할지 말지 결정한다.(이 결정에 따라 전체 프로세스 수가 결정된다. 이를 멀티 프로그래밍 정도 degree of multiprogramming 라고 한다)
- 승인 스케줄링 (admission scheduling) 이라고도 부른다.
저수준 스케줄링
- 고수준 스케줄링과 달리 저수준 스케줄링은 가장 작은 단위의 스케줄링을 저수준 스케줄링(low level scheduling) 이라고 한다.
- 세부적인 일은 하는 단계이다.
- CPU 스케룰러 입장에서 저수준 스케줄링은 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다.
- 단기 스케줄링 (short term scheduling) 이라고도 부른다.
중간 수준 스케줄링
- 중간 수준 스케줄링 (middle level scheduling)은 고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링이다.
- 중간 수준 스케줄링은 고수준 스케줄링에서 활성화된 프로세스가 활성화된 후에도 여러가지 사정으로 시스템에 과부하가 걸릴 때 조절하는 스케줄링이다.
- 중간 수준 스케줄링은 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
- 중지(suspend) : 프로세스의 보류 상태에 해당한다.
스케줄링의 목적
- 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 그 과정에서 특징 프로세스가 배재되어서는 안 된다.
- 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
- 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
- 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
- 반응 시간 보장: 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
- 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.
스케줄링 시 고려 사항
선점형 스케줄링과 비선점형 스케줄링
- 선점형:
- 스케줄링: 빼앗을 수 있음을 뜻한다.
- 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
- 인터럽트 처리를 예로 들 수 있다.
- 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.
- 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생긴다는 단점이 있다.
- 비선점형 스케줄링:
- 빼앗을 수 없음을 뜻한다.
- 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.
- 선점형 스케줄링보다 스케줄러의 작업량이 적고 문맥 교환에 의해 낭비가 적다.
- CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어지는 단점이 있다.
- 과거의 일괄 작업 시스템에서 사용하는 방식이다.
프로세스 우선순위
- 프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉜다. CPU 스케줄러는 각 프로세스에 우선순위를 부여하는데 커널 프로세스의 우선순위가 일반 프로세스보다 높다. (우선순위가 높다는 것을 더 빨리 더 자주 실행된다는 의미이다.)
- 각 프로세스에서 안에서도 중요한 프로세스와 덜 중요한 프로세스로 나뉜다.
- 일반 프로세스는 사용자가 우선순위를 높이거나 낮출 수 있다.
- 유닉스에서는 nice 명령어를 사용하여 관리자만 우선순위를 높일 수 있고 일반 계정은 우선순위를 낮추는 것만 가능하다.
CPU 집중 프로세스와 입출력 집중 프로세스
- 프로세스 상태에서 준비, 실행, 대기, 완료 상태중 CPU를 할당 받아 실제 작업이 일어나는 상태는 실행 상태와 대기 상태이다.
- 프로세스는 CPU를 사용하여 작업하는 실행 또는 입출력을 요청하여 완료되기까지 기다리는 대기 상태에 있다.
- CPU를 할당받아 실행하는 작업을 CPU 버스트(CPU burst)라고 한다.
- 입출력 작업을 입출력 버스트(I/O burst)라고 한다.
CPU 집중 프로세스 (CPU bound process)
CPU 집중 프로세스는 수학 연산과 같이 CPU를 많이 사용하는 프로세스로 CPU 버스트가 많다.
입출력 집중 프로세스 (I/O bound process)
입출력 집중 프로세스는 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스로 입출력 버스트가 많다.
CPU 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. (입출력 요구에 의해 대기 상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있다.)
입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우를 사이클 훔치기(cycle stealing)이라고 한다.
전면 프로세스와 후면 프로세스
- 전면 프로세스: GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스를 말한다.
- 상호작용 프로세스라고도 한다.
- 후면 프로세스: 사용자와 상호작용이 없는 프로세스를 말한다.
- 일괄 작업 프로세스라고도 한다.
전면 프로세스의 우선순위가 후면 프로세스의 우선순위보다 높다.
우선 순위 정리
다중 큐
준비 상태의 다중 큐
프로세스는 저마다 중요도가 다르며 그 중요도는 프로세스 제어 블록에 표시된다.
프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막 tail에 삽입된다. CPU 스케줄러는 우선순위가 가장 높은 큐(0번 큐)의 맨 앞에 있는 프로세스 6에 CPU를 할당한다.
준비 큐를 몇 개로 나눌지, 여러 개의 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 일은 스케줄링 알고리즘에 따라 달라진다.
프로세스의 우선순위를 배정하는 방식에는 고정 우선순위와 변동 우선순위가 있다.
- 고정 우선순위 방식(static priority): 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다.
- 장점: 구현이 쉽다.
- 단점: 시스템의 변화에 대응하기 어려워 작업 효율이 떨어진다.
- 변동 우선순위 방식(dynamic priority): 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 병하는 방식이다.
- 장점: 시스템의 효율성을 높일 수 있다.
- 단점: 구현하기 어렵다.
대기 상태의 다중 큐
대기 상태: 입출력이 완료되기를 기다리는 프로세스가 모여 있는 곳
시스템 내에는 다향한 종류의 입출력 장치가 있기 때문에 대기 상태의 프로세스를 한 곳에 모아 놓으면 관리하기 어려워 다중 큐를 사용한다.
- 같은 장치의 입출력을 기다리는 프로세스의 프로세스 제어 블록은 동일한 입출력 큐에 모여 있다.
- 대기 상태의 다중 큐에 있는 프로세스 제어 블록은 큐에 삽입된 순서대로 처리되지만, 일부는 나중에 들어온 프로세스 제어 블록이 먼저 준비 상태로 옮겨 가기도 한다.
준비 상태 다중 큐와 대기 상태 다중 큐의 차이점:
준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 방면, 대기 큐는 어려 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다.
시스템에는 많은 입출력 장치가 있기 때문에 입출력이 동시에 끝날 경우 여러 개의 인트럽트가 한꺼번에 사용된다. 이렇게 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터(interrupt vector)라는 자료구조를 사용한다.
스케줄링 알고리즘
| 구분 | 종류 |
|---|---|
| 비선점형 알고리즘 | FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링 |
| 선점형 알고리즘 | 라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링 |
| 둘 다 가능 | 우선순위 스케줄링 |
스케줄링 알고리즘의 선택 기준
- CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
- 처치량: 단위 시간당 작업을 마친 프로세스 수(수치가 클수록 좋다.)
- 대기시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간 (짧을수록 좋다.)
- 응답시간: 프로세스 시작 후 첫 번 째 출력 또는 반응이 나올 때까지 걸리는 시간(짧을수록 좋다.)
- 반환시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간 (대기시간과 실행시간을 더한 값)
출처: https://80000coding.oopy.io/fc28d9ac-e072-492c-a390-40ec8ebaac96
스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다. 평균 대기 시간은 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값이다.
FCFS 알고리즘
FCFS(First Come First Served) 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다.(먼저 온 순서대로 서비스 받는 방식) 한번 실행되면 그 프로세스가 끝나야만 비로소 다음 프로세스를 실행할 수 있다.
- 장점:
- FCFS 스케줄링은 알고리즘이 단순하고 공평하다.
- 단점:
- 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리기 때문에 효율성이 떨어진다.(이러한 효과를 콘보이 효과 convoy effect 또는 호위 효과라고 한다.)
- 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율성이 떨어진다.
SJF 알고리즘
SJF(Shortest Job First) 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다. (최단 작업 우선 스케줄링이라고도 한다.)
- 장점:
- 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다.
- 단점:
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
- SJF 알고리즘은 공평성에 위배된다.
- 만약 한 프로세스가 시간이 길어 뒤로 밀린 상태에서 다음에 오는 프로세스들이 계속 짧은 시간을 갖는 프로세스라면 먼저 온 프로세스지만 계속 실행을 못하고 뒤로 밀리게 된다. 이를 아사 (starvation) 현상 또는 무한 봉쇄(infinite blocking) 현상이라고 한다 즉 공평성이 현저히 떨어진다.
SJF 알고리즘 단점은 에이징(aging, 나이 먹기)로 해결할 수 있다. 에이징은 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. (나이로 빗대어 어는 정도에 나이가 들면 실행되는 방식이다.) 하지만 이 방법도 프로세스의 종료 시간을 파악하기 어렵고 아사 현상이 일어날 수 있기 때문에 잘 사용하지 않는다.
HRN 알고리즘
HRN (Hightest Response Ratio Next) 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링하는 방식이다.( SJF 알고리즘을 보안하기 위해 나온 방식, 최고 응답률 우선 스케줄링이라고도 한다.)
- 장점:
- HRN 스케줄링은 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화한다.
- 단점:
- 여전히 공평성이 위배된다.
라운드 로빈 스케줄링
라운드 로빈(RR Round Robin) 스케줄링은 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.(순환 순서 방식) 라운드 로빈 스케줄링은 우선순위가 적용되지 않은 가장 단순한 선점형 스케줄링이다.
- 장점:
- 프로세스가 CPU를 일정 시간 동안 사용한 후 다른 프로세스에 넘겨주어야 하므로 앞의 긴 작업을 무작정 기다리는 콘보이 효과가 줄어든다.
- 단점:
- 라운드 로빈 스케줄링과 FCFS 스케줄링의 평균 대기 시간이 같다면 라운드 로빈 스케줄링이 더 비효율적인 알고리즘이다. (라운드 로빈 스케줄링은 문맥 교환이 추가되기 때문)
SRT 우선 스케줄링
SRT(Shortest Remaining Time) 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로 최소 잔류 시간 우선 스케줄링이라고도 한다. (이 방식은 SJF 스케줄링의 선점형 버전이라고 할 수도 있다.) SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당 받을 프로세스를 선택할 때 남은 작업 시간이 가장 적은 프로세스를 선택한다.
- 단점:
- SJF 스케줄링에 없는 문맥교환이 일어난다.
- 프로세스 종료 시간을 예측하기 어렵다.
- 아사 현상이 일어난다.
우선순위 스케줄링
우선순위 스케줄링은 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당한다.
-
비점선형 방식:
- SJF 스케줄링: 작업 시간이 짧은 프로세스에 높은 우선순위를 부여
- HRN 스케줄링: 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여
-
선점형 방식:
- SRT 스케줄링: 남은 시간이 짧은 프로세스에 높은 우선순위를 부여
-
고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정된다. (단순하게 구현할 수 있지만 시시가각 변하는 시스템 상황을 반영하지 못해 효율성이 떨어진다.)
-
변동 우선순위 알고리즘: 일정 시간마다 번하는 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템 상황을 반영하여 효율적인 운영이 가능하다.
우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성에 위배하고 아사 현상이 일으키는 문제가 있다. 또한 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생한다. 하지만 커널 프로세스와 일반 프로세스는 같은 우선순위에 있으면 안되기 때문에 시스템 효율성 보다 프로세스의 중요도에 따라 정해진다.
다단계 큐 스케줄링
다단계 큐(MLQ Multi-Level Queue) 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식이다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있을뿐더러 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수 있다.
다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스가 작업을 할 수 없다. 1번에 큐가 끝나야 비로소 2번의 큐가 실행될 수 있다.(2번 큐는 끝날 때까지 기다려야 한다.)
다단계 피드백 큐 스케줄링
다단계 피드백 큐(MLFQ Multi-Level Feedback Queue) 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐(MLQ) 스케줄링의 문제점을 보완한 방식이다.
다단계 큐 스케줄링과 다단계 피드백 큐 스케줄링 차이점
다단계 피드백 큐는 다단계 큐와 기본 동작이 같아 우선순위를 가진 여러 개의 큐를 사용한다. 하지만 다단계 큐는 각 단계에 라운드 로빈 방식을 사용하고 우선순위에 변화가 없지만 다단계 피드백 큐 스케줄링은 CPU를 사용한 후 프로세스의 우선순위가 낮아진다. (CPU를 사용한 후의 프로세스의 원래의 큐로 되돌아가지 않고 우선순위가 한 단계 낮아진다.)
우선순위가 낮아진다고 해서 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.
다단계 피드백 큐의 또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기가 다르다. 보통 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스보다 타임 슬라이스가 크다 결국 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는 프로세스는 무한대의 타입 슬라이스를 얻는다. (CPU를 빼앗기지 않고 끝날때 까지 작업한다.)
출처: https://velog.io/@im_lily/%EC%89%BD%EA%B2%8C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Chapter04
인터럽트 처리
인터럽트란 CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치에 예외 상황이 발생하여 처리가 필요할 경우에 CPU에게 알려 처리할 수 있도록 하는 것이다. 우선적으로 처리해야 할 일이 발생하였을 때 그것을 처리하고 원래 동작으로 돌아온다. 크게 하드웨어 인터럽트와 소프트웨어 인터럽트로 나뉜다.
동기적 인터럽트와 비동기적 인터럽트
동기적 인터럽트
- 사용자 인터럽트라고도 한다.
- 프로그램의 문제 때문에 발생하는 인터럽트(예: 다른 사용자의 메모리 영역에 접근하는 경우, 오버플로나 언더 플로에 의해 발생하는 경우)
- 컴퓨터 작업자가 의도적으로 프로세스를 중단하기 위해 발생시킨 경우(예:
Ctrl+C) - 입출력장치 같은 주변 장치의 조작에 의한 인터럽트
- 산술 연산 중 발생하는 인터럽트(예: 어떤 수를 0으로 나눔)
비동기적 인터럽트
- 하드디스크 읽기 오류, 메모리 불량과 같은 하드웨어 오류로 발생하는 인터럽트
- 사용자가 직접 작동하는 키보드 인터럽트, 마우스 인터럽트
인터럽트 처리 과정
인터럽트에는 해당 인터럽트가 발생하면 어떤 일을 할지 정의되어 있다. (인터럽트 번호와 그 번호에 붙어 있는 함수의 쌍으로 이루어져 있다.) 윈도우에서는 인터럽트 번호를 IRQ라고 한다. 인터럽트는 한순간에 여러 개가 동시에 발생하기도 한다 이렇게 동시에 발생하는 인터럽트를 하나로 묶어서 처리하는 개념이 인터럽트 벡터다.
인터럽트 벡터는 인터럽트의 집합이다.
인터럽트 백터
인터럽트가 발생하면 인터럽트 벡터의 번호가 0에서 1로 바뀐다. (동시에 1이 되는 인터럽트 번호가 여러 개일 수도 있다.) 인터럽트 벡터에는 각 인터럽트를 처리하는 함수가 연결되어 있다. 해당 인터럽트가 발생하면 어떤 일을 처리할 것인지가 이 함수에 정의되어 있는데 이를 인터럽트 핸들러(interrupt handler)라고 부른다. (사용자가 정의할 수도 있다.)
인터럽트 처리 과정 설명
- 인터럽트가 발생하면 현재 실행 중인 프로세스는 일시 정지 상태가 되며, 재시작하기 위해 현재 프로세스 관련 정보를 임시로 저장한다.
- 인터럽트 컨트롤러가 실행되어 인터럽트의 처리 순서를 결정한다. 이때 여러 개의 인터럽트가 동시에 발생했다면 우선순위를 고려하여 중요한 인터럽트로부터 처리하도록 순서를 결정한다.
- 먼저 처리할 인터럽트가 결정되면 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행된다. 인터럽트 핸들러는 인터럽트 처리를 위해 미리 정의된 함수이고, 인터럽트 벡터는 인터럽트와 인터럽트 벡터에 등록해 놓으면 해당 인터럽트 발생 시 함수가 실행되러 처리한다.
- 인터럽트 벡터에 연결된 핸들러가 인터럽트 처리를 마치면 일시 정지된 프로세스가 다시 실행되거나 종료된다. 발생한 인터럽트가 입출력 완료라면 일시 정지된 프로세스가 다시 실행되고, 다른 프로세스의 메모리 영역 침범이나 오류라면 종료된다.
인터럽트 이중모드
프로세스는 크게 커널 프로세스 사용자 프로세스로 나뉜다. 운영체제 관련된 커널 프로세스가 실행되는 상태를 커널 모드(kernel mode), 사용자 프로세스가 실행되는 상태를 사용자 모드(user mode)라고 한다. 사용자 프로세스는 하드 디스크 입출력, 프로세스 생성과 같은 커널의 기능을 사용하려면 시스템 호출을 이요하여 커널 프로세스에 작업을 요청해야 한다. 사용자 프로세스는 시스템 호출을 요청한 후 대기 상태로 전환되고 커널 프로세스는 요청받은 작업을 처리한다. 사용자 모드에서 커널 모드로 전환되어 일을 처리하는 것을 이중 모드(dual mode)라고 한다. 이중 모드는 자원을 보호하기 위해 사용하는 기법이다. 즉 사용자 프로세스는 자원을 직접 접근하면 문제가 생길 수 있으므로 커널 모드에서 실행되지 못하고 시스템 호출을 통해서만 자원의 접근 할 수 있다.
사용자가 커널을 사용할 수 있는 방법
- 시스템 호출 (사용자가 자발적으로 커널 모드에 진입)
- 잘못된 명령으로 인한 인터럽트 발생