[4주차] - CPU 스케줄링
1. 시스템 콜의 4가지 종류
fork()
- fork() 시스템 호출을 하면 PCB를 포함한 부모 프로세스 영역의 대부분이 자식 프로세스에 복사되어 똑같은 프로세스가 만들어진다
- fork()의 장점
- 프로세스 생성 속도가 빠름
- 추가 작업없이 자원을 상속할 수 있음
- 시스템 관리를 효율적으로 할 수 있다
exec()
- exec() 시스템 호출은 기존의 프로세스를 새로운 프로세스로 전환하는 함수이다
- 프로세스는 그대로 둔 채 내용만 바꾸는 시스템 호출이다
- exec() 시스템 호출을 사용하는 목적은 프로세스의 구조체를 재활용하기 위함이다
- exec() 시스템 호출을 하면 코드 영역에 있는 기존의 내용을 지우고 새로운 코드로 바꿔버린다
- exec() 시스템 호출 시 남아있는 정보는 프로세스 구분자(PID, PPID, CPID)이다
wait()
- 운영체제는 부모 프로세스가 먼저 종료됨으로써 고아 프로세스가 생기는 것을 방지하기 위해 wait() 시스템 호출을 사용한다
- wait() 시스템 호출은 자식 프로세스가 끝나기를 기다렸다가 자식 프로세스가 종료되면 다음 문장을 실행한다
- wait() 시스템 호출을 잘 사용하면 부모 프로세스가 자식 프로세스보다 먼저 끝나는 경우가 없기 때문에 부모 프로세스, 자식 프로세스간 동기화에도 사용된다
exit()
- exit() 시스템 호출은 작업의 종료를 알려준다
- exit() 시스템 호출을 사용함으로써 부모 프로세스는 자식 프로세스가 사용하던 자원을 빨리 거둬 갈 수 있다
- exit() 시스템 호출은 전달하는 인자를 통해 정상종료(0), 비정상종료(-1)를 알려줄 수 있다
2. 프로세스간 협력
독립적 프로세스
- 프로세스는 각자의 주소 공간을 갖고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세서의 수행에 영향을 미치지 못함
협력 프로세스
- 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음
3. 메시지 패싱
4. CPU 버스트와 I/O 버스트
I/O-bound process
- cpu를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- many short CPU bursts
CPU-bound process
- 계산 위주의 job
- few very long CPU bursts
5. CPU 스케줄러 & 디스패쳐
6. 스케줄링 기준
- 다음 항목들은 CPU 스케줄링의 성능 평가의 기준이 된다
- CPU utilization(이용률)
- 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
- Throughput(처리량)
- 단위 시간 당 작업을 마친 프로세스의 수
- Turnaround time(소요시간, 반환시간)
- Waiting time(대기 시간)
- 대기한 시간의 총합
- Response time(응답 시간)
- 처음 cpu를 사용하러 들어와서 처음 응답을 받은 시간
- CPU utilization(이용률)
7. 스케줄링의 단계
오늘날의 CPU 스케줄러는 대부분 중간수준 스케줄링과 저수준 스케줄링으로 구성되어 있다
고수준 스케줄링
- 장기 스케줄링 또는 작업 스케줄링, 승인스케줄링이라고도 함
- 고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것을 말한다
- 여기서 작업은 운영체제에서 다루는 일의 가장 큰 단위로, 1개 또는 여러개의 프로세스로 이루어진다
- 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다
- 고수준 스케줄링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총개수가 정해진다
저수준 스케줄링
- 단기 스케줄링이라고도 부른다
- 가장 작은 단위의 스케줄링으로 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다
- 프로세스 상태에 관한 내용(run, ready, block)은 대부분 저수준 스케줄링에 해당
중간수준 스케줄링
- 고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링이다
- 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다
- 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 원만하게 작동하도록 지원한다
- 프로세스의 상태 중 보류 상태에 해당하며, 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 한다
8. 스케줄링의 목적
공평성
- 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안 된다
효율성
- 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다
안정성
- 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다
확장성
- 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다
반응 시간 보장
- 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다
무한 연기 방지
- 특정 프로세스의 작업이 무한히 연기되어서는 안 된다
9. 선점형 스케줄링과 비선점형 스케줄링
선점형 스케줄링
- 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다
- 문맥교환 같은 부가적인 작업으로 인해 낭비가 생기는 것이 단점이다
- 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다
- 대부분 저수준 스케줄러는 선점형 스케줄링 방식을 사용한다
비선점형 스케줄링
- 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다
- CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여려 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다
- 과거의 일괄 작업 시스템에서 사용하던 방식이다
10. FCFS(First Come First Served)
FCFS 스케줄링의 동작 방식
- 준비큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다
- 초기의 일괄 작업 시스템에서 사용되었던 FCFS 스케줄링은 프로세스가 큐에 도착한 순서대로 실행되며, 비선점형 방식이기 때문에 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다
- 큐가 하나라 모든 프로세스는 우선순위가 동일하다
FCFS 스케줄링의 성능
- 평균 대기 시간으로 평가해보면 시스템의 모든 프로세스가 작업을 요청하여 실제로 작업이 시작할 때까지 기다린 시간을 합한 후 프로세스의 수로 나누어 구한다
FCFS 스케줄링의 평가
- FCFS 스케줄링 알고리즘은 단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어진다
- 콘보이 효과 : 컨베이어 벨트에 작업물이 한 줄로 늘어서 있을 때 앞의 작업이 오래 걸려서 뒤의 작업이 지연되는 현상과 같다
- 다른 단점은 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다는 점이다
11. SJF(Shortest Job First)
SJF 스케줄링의 동작 방식
- 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다
SJF 스케줄링의 평가
- SJF 스케줄링은 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다
SJF 스케줄링의 단점
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다
- 현대의 운영체제는 프로세스의 작업 길이를 추정하는 것이 어렵기 때문에 SJF 스케줄링을 사용하기가 힘들다
- 공평하지 못하다
- SJF 스케줄링은 공평성을 위배한다
- 작업시간이 긴 프로세스가 Starvation 현상에 빠질 가능성이 있다
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다
12. Priority Scheduling
우선순위 스케줄링의 동작 방식
- 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다
우선순위 스케줄링의 적용
- 선점형과 비선점형 방식에 모두 적용 가능하다
- SJF 스케줄링(비선점형) : 작업 시간이 짧은 프로세스에 높은 우선순위를 부여
- HRN 스케줄링(비선점형) : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여
- SRT 스케줄링(선점형) : 남은 시간이 짧은 프로세스에 높은 우선순위를 부여
- 선점형과 비선점형 방식에 모두 적용 가능하다
고정 우선순위 알고리즘
- 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정
- 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다
변동 우선순위 알고리즘
- 일정 시간마다 우선순위가 변한다
- 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반영하여 효율적인 운영이 가능하다
우선순위 스케줄링의 평가
- 우선순위 스케줄링은 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 Starvation 현상을 일으킨다는 점이 문제
- 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생해 시스템의 효율성이 떨어진다
13. Round Robin
라운드 로빈 스케줄링의 동작 방식
- 한 프로세스가 할당받은 시간 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
- 선점형 알고리즘 중 가장 단순하고 대표적인 방식으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
- FCFS 스케줄링과 유사하지만 각 프로세스마다 CPU를 사용할 수 있는 최대시간이 정해져있다는 점이 다르다
타임 슬라이스 크기와 문맥 교환
- 타임 슬라이스가 큰 경우
- 타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다
- 실제로 라운드 로빈 스케줄링에서 타임 슬라이스가 무한대이면 FCFS 스케줄링이 된다
- 타임 슬라이스가 작은 경우
- 타임 슬라이스를 1밀리초와 같이 매우 작은 값으로 설정하면 사용자는 여러 프로그램이 동시에 실행되는 것처럼 느낄 수 있따
- 하지만 타임 슬라이스가 너무 작다면 문맥 교환이 너무 자주 일어나서 성능에 악영향이 생긴다
- 참고로 유닉스 운영체제에서는 타임 슬라이스가 대략 100밀리초이다. 대략인 이유는 100~200밀리초 사이에서 조정할 수 있도록 했기 때문이다
- 타임 슬라이스가 큰 경우
14. 다단계 큐 스케줄링(Multilevel Queue)
다단계 큐 스케줄링의 동작 방식
- 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
- 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입
- 라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정
- 우선순위는 고정형 우선순위를 사용하며, 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다
다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식
다단계 큐 스케줄링의 단점
- 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다
- 즉 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다
15. 다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링의 동작 방식
- 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
- CPU를 사용하고 난 프로세스의 우선순위가 낮아진다
- CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다
다단계 피드백 큐 스케줄링의 특징
- 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
- 우선순위에 따라 타임 슬라이스의 크기가 다르다는 것
- 프로세스의 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다(어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록)
- 마지막 큐에 있는(우선순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻는다
- 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식
본 포스팅은 반효경 교수님의 2017 운영체제 강의를 바탕으로 제작되었습니다.
하루하루 성장하는 개발자