비 선점형 알고리즘: FCFS스케줄링, SJF스케줄링, HRN스케줄링
선점형 알고리즘: 라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
둘 다 가능: 우선순위 스케줄링
스케줄링 알고리즘의 선택 기준
- CPU사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법이다.
- 처리량: 시스템이 정상적으로 작용한다면 일정 시간 후 작업이 끝난다. 처리량은 단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클수록 좋은 알고리즘이다.
- 대기 시간: 작업을 요청하더라도 실제 작업이 이루어지기 전까지는 대기 시간이 필요하다. 대기 시간은 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간으로, 이 시간이 짧을수록 좋다.
- 응답 시간: 대화형 시스템에서는 사용자의 요구에 얼마 만에 반응하는지가 중요하다. 응답 시간은 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간으로, 이 시간 역시 짧을수록 좋다.
- 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반호나하는 데까지 걸리는 시간이다. 반환 시간은 대기 시간과 실행 시간을 더한 값이다.
대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
응답 시간: 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지 걸리는 시간
실행 시간: 프로세스 작업이 시작된 후 종료되기까지 걸리는 시간
반환 시간: 대기 시간을 포함하여 실행이 종료될 때까지 걸리는 시간
스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다.
FCFS스케줄링
first come first served스케줄링은 준비 큐에 도착한 순서대로 cpu를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다.
프로세스 P1은 도착하자마자 실행되므로 대기시간이 0밀리초, 작업 시간이 30밀리초다. 프로세스 P2는 3밀리초 뒤에 도착하여 27밀리초(30-3)를 기다린 후 18밀리초 동안 실행된다. 프로세스 P3은 밀리포 뒤에 도착하여 42밀리초를 기다린 후 9밀리초 동안 실행된다. 3개의 프로세스의 평균 대기 시간은(0+27+42)/3 = 23밀리초다.
FCFS스케줄링 알고리즘은 단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리느라 시스템의 효율성이 떨어진다. 이러한 문제를 콘보이 효과 convoy effect 또는 호위 효과라고 한다. 컨베이어 벨트에 작업물이 한 줄로 늘어서 있을 때 앞의 작업이 오래 걸려서 뒤의 작업이 지연되는 현상과 같다.
SJF스케줄링
shortest job first스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다.
FCFS스케줄링의 콘보이 효과를 완화하여 시스템의 효율성을 높이는 것이다.
시작 시점에는 프로세스 P1뿐이므로 P1은 대기하지 않고 바로 실행된다. P1이 30밀리초 동안 작업을 하면 큐에 프로세스 P2와 P3이 기다리고 있다. 두 프로세스 중 P3의 작업이 짧기 때문에 P3이 먼저 시작한다. 따라서 프로세스 P3이 24밀리초(30-6밀리초)를 기다린 후 9밀리초 동안 실행된다. 마지막으로 P2가 36밀리초(39-3밀리초)를 기다린 후 18밀리초 동안 실행된다. 3개 프로세스의 평균 대기 시간은(0+24+36) / 3 = 20밀리초다.
평가
1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
2. SJF알고리즘은 공평성에 위배된다.
- 계속 연기되는데 이를아사 starvation현상 또는 무한 봉쇄 infinite blocking 현상이라고 한다. 작업 시간이 길다는 이유만으로 계속 뒤로 밀린다면 공평성이 현저히 떨어진다. 그런 공평성이 위배 문제는 에이징(나이 먹기) aging으로 완화할 수 있다. 에이징은 최대 몇 살까지만 양보하도록 규정하는 방식이다.
라운드 로빈 스케줄링
동작 방식
'순환 순서 방식'으로 번역되는 라운드 로빈(RR Round Robin) 스케줄링은 한 프로세스가 할당받은 시간 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 선점형 알고리즘 중 가장 단순하고 대표적인 방식으로, 프로세스들이 작업을 완료할 때까지 순환하면서 실행된다.
라운드 로빈 스케줄링 FCFS스케줄링과 유사한데, 차이점은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, 즉 타임 슬라이스가 있다는 것이다.
SRT우선 스케줄링
SRT스케줄링은 SJF스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로 최소 잔류 시간 우선 스케줄링이라고도 한다.
이 방식은 SJF스케줄링의 선점형 버전이라고 할 수 있다.
SRT스케줄링은 SJF스케줄링과 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음
우선순위 스케줄링
프로세스는 중요도에 따라 우선순위 priority를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다.
다단계 큐 스케줄링
다단계 큐(MLQ: multi-level Queue) 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 프로세스는 운영체제로부터 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다.
다단계 큐 스케줄링에서는 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수 없다. 우선순위가 1번인 큐에 CPU할당을 기다리는 프로세스가 있다면 우선순위가 2번인 큐의 프로세스는 1번 큐의 프로세스의 작업이 끝날 때까지 기다려야 한다. 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는 데, 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다.
다단계 피드백 큐 스케줄링
다단계 피드백 큐(MFLQ: multi - level feedback Queue) 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐(MLG) 스케줄링의 문제점을 보완한 방식이다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 기본 형태가 같아 우선순위를 가진 여러 개의 큐를 사용한다.
다단계 피드백 큐 스케줄링에서는 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서는 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다.
결국 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻는다. 무한대의 타임 슬라이스를 얻는다는 것은 프로세스가 실행상태에 들어가면 CPU를 빼앗기지 않고 끝까지 작업을 마친다는 의미다. 그러므로 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS방식으로 작동한다.
인터럽트 처리
개념은 인터럽트 처리는 입출력뿐 아니라 시스템 보호에 매우 중요한 역할을 한다. 인터럽트의 작동원리를 프로그래밍 방식과 역관 지어 이해해 보자.
윈도우에는기본적으로 3개의 버튼이 있다. 최소화, 최대화, 종료가 있는데 이 버튼이 눌렀는지 안 눌렀는지 주기적으로 확인하는 대신 버튼이 눌리면 프로세스에 알려주는데 이를 이벤트 드리븐(event driven)이라고 한다.
운영체제의 입출력 처리도 이와 똑같다. 과거에는 입출력장치가 거의 없었기 때문에 입출력을 요청하면 운영체제가 주기적으로 입출력장치를 직업 확인해서 처리했는데, 이러한 방식을 폴링이라고 한다. 하지만 다양한 입출력장치가 개발되어 운영체제가 모든 입출력을 관리하기 어려워지자 이벤트 드리븐 방식과 마찬가지로 입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 이 사실을 알리게 되었는데, 이를 인터럽트라고 한다.
인터럽트와 이중모드
운영체제와 관련된 커널 프로세스가 실행되는 상태를 커널모드 kernel mode, 사용자 프로세스가 실행되는 상태를 사용자 모드 user mode라고 한다. 사용자 프로세스가 하드디스크 입출력, 프로세스 생성과 같은 커널의 기능을 사용하려면 시스템 호출을 이용하여 커널 프로세스에 작업을 요청해야 한다. 사용자 프로세스는 시스템 호출을 이용하여 커널 프로세스에 작업을 요청해야 한다. 사용자 프로세스는 시스템 호출을 요청한 후 대기 상태로 전환되고 커널 프로세스는 요청받은 작업을 처리한다. 즉 사용자 모드에서 커널 모드로 전환되는데, 이와 같이 운영체제가 두 모드를 전환하며 일 처리를 하는 것을 이중모드 dual mode라고 한다.
