#3 - 운영체제 2-2장, CPU 스케줄러
스케줄러의 필요성
- CPU-I/O Burst Cycle : CPU가 동작하는 시간과 I/O가 실행되는 시간의 사이클
- I/O 상태에서는 CPU가 동작하지 않기 때문에 좀더 효율적인 CPU 연산을 위해 스케줄링이 필수적이다.
- 아래에서는 CPU 스케줄링에 대하여 다룬다.
## CPU 스케줄러
- 다음과 프로세스 하나에 대하여 다음과 같은 상황에 스케줄러가 위치를 지정한다.
- Running 상태에서 Waiting 상태로 전환된 프로세스
- Running 상태에서 Ready 상태로 전환된 프로세스
- Waiting 상태에서 Ready 상태로 전환된 프로세스
- 완전히 종료된 프로세스
- 작업들은 우선순위를 가지고 있으며 선점이 될 수도 있다.
- 우선순위가 1에서 4인 작업은 비선점으로 항상 우선적으로 동작한다.
- 나머지 작업들은 선점될수 있으며 우선순위에 따라 다시 평가된다.
- 이런 우선순위 작업은 Ready Queue에서 주로 발생한다.
Dispatcher
- 디스패처는 Short-term 스케줄러에 의해 선택된 프로세스를 CPU에 할당하는 동작을 한다.
- 디스패처는 커널 환경에서 동작한다.
- 프로세스의 문맥을 교환하거나 유저모드로 변경시키고, 적절한 위치로 프로그램을 이동한다.
- 문맥이 교환되거나 새로운 프로세스를 CPU에 할당할 때 발생하는 시간을 디스패치 레이턴시라고 한다.
## 스캐줄링 정책
- 스케줄러는 정책에 따라 동작을 수행하며 다음의 특징을 가진다.
- CPU 유틸리제이션 : CPU는 항상 바쁘게 동작해야한다.
- 처리량(Throughput): 단위 시간단 처리하는 갯수를 정해야 한다.
- 스케줄러는 3가지 시간적 특징을 가진다.
- Turnaround Time : 작업이 전체 동작하는 시간
- Ready - Run - Terminate - Ready 되는 전체 시간을 의미한다.
- Waiting Time : 작업의 대기시간
- Ready Queue 에서 대기하는 시간을 의미한다.
- 짧은 작업을 우선하여 동작하면 최적의 정책이 된다.
- Response Time : 전체 동작 중 가장 첫번째 결과가 나올 때 까지의 시간
- 여러 작업들 중 가장 먼저 실행되는 결과 까지의 시간을 의미한다.
- Turnaround Time : 작업이 전체 동작하는 시간
- 은행 비유를 통해 위 시간들의 특징을 알아보자
- 은행 입장 후 번호표 뽑기 (Ready Queue)
- 번호가 될때 까지 대기 (Waiting Time)
- 만약 다른 손님이 우선권을 가진 작업이 들어오면 선점당함
- 통장정리를 시작하고 한줄이 찍혔음 (Response Time)
- 모든 작업이 완료되고 은행을 나왔음 (Turn Around Time)
- 스캐줄러는 상황에 따라서 conflict가 발생한다.
- 상호작용이 중요한 시스템에서 Response Time을 중요시 했다면
- Response Time이 강화되고 -> 문맥교환이 증가되며 -> 처리량이 감소된다.
- 따라서 상호아에 맞는 적절한 스케줄링 정책이 요구된다.
- CPU의 동작시간과 처리량을 극대화 하고 시간적 특징들을 최소로 하는 스케줄링 정책이 필요하다.
First-Come, First-Served(FCFS) 방식
- 거의 FIFO 방식과 동일하다.
- 먼저 들어온 작업은 우선적으로 처리된다.
- 따라서 비선점이고, 반드시 순서에 따라 처리된다.
- 상당히 비효율적이고 최근에는 거의 사용되지 않는다.
- 간트 차트를 참고해보자
- 작업들의 순서에 따라 평균 대기시간이 달라지는 것을 확인 할 수 있다.
- 이른 호위효과(Convoy Effect)라고 하며 FCFS가 비효율 적인 이유이다.
Shortest-Job-First (SJF) 방식
- 가장 짧은 작업을 우선적으로 처리한다.
- 선점이나 비선점으로 동작될 수 있는데, 기본적으로 선점이다.
- 비선점일 때 : 한번 CPU Burst 상태가 되면 해당 작업이 끝날때까지는 선점되지 못한다.
- 사진
- 선점일 때 : CPU Burst 상태에서 더 짧은 실행시간의 작업이 선점되며, Burst 중이던 동작은 그대로 대기한다.
- 이를 Shortest-Remaining-Time-First(SRTF)라고 한다.
- 사진
- 비선점일 때 : 한번 CPU Burst 상태가 되면 해당 작업이 끝날때까지는 선점되지 못한다.
- 그렇다면 실제로 Burst되는 시간은 어떻게 알 수있을까?
- 동작해보지 않고서 Burst Time은 정확하게 알 수 없다.
- 그러나 이전 CPU Burst Time을 기반으로 예측이 가능하다.
- 다음 CPU Burst 예측하는 방법
- 다음 CPU Burst = 가중치 상수 x 현재 실재로 실행된 Burst Time + (1 - 가중치 상수) x 앞에서 예측했던 현재 실행중인 작업의 Burst Time 예측값
- τ next = α*T real + (1 - α) τ now
- 가중치 상수 α는 0에 가까울 수록 실제 시간을 고려하지 않고, 1에 가까울수록 실제 실행시간만을 고려한다.
- 따라서 0.5의 값을 가지면 실제 시간과 예측했던 시간을 적절히 사용가능하다.
Priority Scheduling
- 각 프로세스에 우선순위를 부여하여 스케줄링 하는 것을 의미한다.
- 선점형과 비선점형 둘다 사용가능하며 가장 높은 우선순위의 프로세스가 할당된다.
- SJF는 Priority Scheduling으로 볼 수 있다.
- Priority Scheduling의 가장 큰 단점은 Starvation이다.
- 낮은 우선순위를 가진 프로세스가 영원히 실행되지 않을 수도 있다.
- Starvation을 해결하기 위하여 Aging 기법을 도입한다.
- Aging : 말그대로 나이를 먹는것, 오래 기다린 프로세스의 우선순위를 높여 준다.
- 비선점형 Priority Scheduling의 가장 큰 단점은 우선순위 역전 현상이다.
Highest Response Ratio Next(HRRN) 방식
- 응답률이 높은 프로세스를 우선적으로 사용하는 방식의 스케줄링 기법이다.
- 응답률을 계산하는 방법은 다음과 같다.
- 응답률 = (기다린시간 + 필요한 CPU Burst) / 필요한 CPU Burst
- 기다린 시간이 길수록 응답률이 높아진다.
- Aging을 사용한 대표적인 사례이다.
Round Robin (RR) 방식
- FIFO 방식에 기초하여 제작 되었지만 FCFS와는 다르게 선점이 가능하다.
- 정해진 타임 퀀텀만큼 프로세스가 동작되고 다음 프로세스로 넘어간다.
- 따라서 여러 프로세스가 대기할 수 있는 시스템 메모리가 요구된다.
- 단독으로 쓰이는 상황은 드물고, 대부분의 어려운 스케줄링 알고리즘의 기반이된다.
- 각 프로세스는 q만큼 동작하고 대기하는데, 최대 (n-1)q만큼 대기한다.
- q의 크기에 따라 두가지 현상이 발생한다.
- q가 너무 크다 : FIFO처럼 먼저 들어온 프로세스가 먼저 일을 끝낸다.
- q가 너무 작다 : 문맥 교환이 많이 발생하여 오버해드가 커진다.
- 즉 적절한 q를 찾아야 효과적인 RR방식이 된다.
- 사진
- 윈도우에서 RR방식
- 우선순위에 따른 선점형 방식을 사용
- 0에서 31 사이의 우선순위중 15를 기준으로 구분하여 정책 결정
- 15보다 큰 우선순위 : 완전한 타임 퀀텀을 제공
- 15보다 낮은 우선순위 : 남은시간만큼만 타임 퀀텀을 제공
Multilevel Queue 방식
- 우선순위를 기반으로 여러 개의 Background와 Foreground를 사용하는 방식이다.
- 우선순위가 낮은 프로세스들은 대체로 Background로 가고 FCFS를 사용한다.
- 우선순위가 높은 프로세스들은 Foreground로 가며 RR방식이 사용된다.
Multilevel Feedback 방식
- 계속해서 다른 Ready Queue로 넘어가는 방식이다.
- 다음 예시를 바탕으로 이해해보자.
- Q0 : RR방식으로 8초의 타임퀀텀 제공
- Q1 : RR방식으로 16초의 타임퀀텀 제공
- Q2 : FCFS방식으로 동작
- 새로운 작업이 Q0에 FCFS방식으로 할당되었다.
- CPU로 들어가 작업중인데 8초의 타임 퀀텀을 제공받았다.
- 8초안에 작업이 끝나지 안았고, Q1에 다시 할당된다.
- 다시 Q1에 있던 작업이 FCFS방식으로 할당되었다.
- 16초의 타임 퀀텀을 제공받았지만 또 끝나지 않았다.
- Q2로 할당된다.
- 이번에는 FCFS방식으로 동작하기 때문에 완전히 작업을 끝낼 때까지 사용가능하다.
- 따라서 Que의 갯수나 정책, 다른 Que로 이동하는 타이밍 등을 정해야 한다.
Fair Share Scheduling(FSS) 방식
- 여러명의 사람이 동시에 접근 할때 사용하는 CPU 스케줄링 방식이다.
- 하나의 CPU 리소스에 여러명이 접근하면 불공평하게 사용할 수도 있다.
- 따라서 모든 사람이 공평하게 CPU를 사용할 수 있도록 하는 스케줄링 방식이다.
- 사용한 리소스량이나 필요로 하는 리소스의 크기를 바탕으로 시스템 리소스를 할당한다.
Thread Scheduling
- 유저 스레드(언어에서 제공)와 커널 스레드(시스템이 요구)에서 각각 다르게 동작함
- 유저 스레드는 프로세스 내부에서만 경쟁한다. (PCS)
- 커널 스레드는 존재하는 모든 스레드들과 경쟁한다.
- 자바에서의 스레드 관리(유저 스레드)
- 선점형 Priority 방식의 스케줄링 기법을 사용한다.
- FIFO Queue는 같은 우선순위를 가진 스레드가 많을 때 사용한다.
- 여러개의 스레드를 동시에 생성하고, 빠른속도로 스와핑 한다.
- 이때 Runnaing 중인 스레드가 종료되면 바로 Running가능한 스레드를 실행시킨다.
Multiple-Processor Scheduling
- 여러개의 CPU에서 프로세서를 스케줄링 하는 것을 의미한다.
- 스케줄링하는 척도는 크게 두가지 정도가 있다.
- Processor Affinity (프로세스 친화도)
- 시간 친화도 : 특정 CPU에서 더 효과적으로 동작하는 프로세서가 있다.
- 공간 친화도 : NUMA 시스템에서는 메모리들이 물리적으로 분산되어 있기 때문에 이를 고려해야한다.
- NUMA : 각 CPU는 각자의 메모리 영역을 가진다.
- 자신의 메모리 영역에서는 빠른 접근을, 다른 CPU의 메모리 영역에서는 접근이 느리다.
- Soft affinity : 가능한 같은 프로세서에 동작하려고 하지만 강제하지 않는다.
- Hard affinity : 강제로 다른 프로세서에 특정 프로세스를 할당한다.
- Load Balancing (로드 균형)
- CPU간의 부하정도가 일정하도록 유지하는 것이 좋다.
- PUSH Migration : 특정 프로세스의 로드 밸런스를 감시하고, 비어있는 프로세서에 할당해준다.
- PULL Migration : 비어있는 프로세서가 직접 대기중인 프로세스를 가지고 온다.
Multicore Processors
- 이번엔 CPU가 여러개의 코어를 가질 때의 스케줄링 방법이다.
- 최근 CPU들은 하나의 프로세서 안에 여러개의 코어로 나누어져있다.
- 보통 하나의 코어에는 하나의 스레드만 동작가능하다.
- 각 스레드들이 코어에서 연산이 될때, 메모리 콜이 자주 발생한다.
- 메모리 콜 상태에서는 해당 코어는 Idle상태가 되며 이것이 반복되면 큰 오버해드가 된다.
- 이때 해당 코어에서 다른 스레드를 동작하면 각 코어들은 쉬지않고 동작이 가능하다.
- 하나의 코어에 여러개의 스레드가 동작하는 것처럼 보이는 것을 하이퍼 스레딩이라 한다.
- 하이퍼 스레딩을 쓰면 하나의 코어에서 여러개의 스레드가 빠르게 교체되며 동작하므로 더 효과적이다.
Real-Time Scheduling
- 실시간 선점형 시스템 스케줄링 방법을 이야기하며 실시간에서 오차를 줄인 스케줄링 기법이다.
Hard real-time computing
- 아주 약간의 오차도 허용하지 않는다. 따라서 방산이나 의료분야에서 주로 사용된다.
- GUI가 없으며 상황에 따라서 필요없는 시스템을 모두 포기한다.
- 데드라인을 넘어간 이후의 데이터는 모두 버린다.
Soft real-time computing
- 오차는 허용하지만 최소화 하기 위해 노력한다.
- 실시간 스트리밍이나 약간의 지연이 발생해도 상관없는 시스템에서 사용한다.
- 데드라인을 넘어간 이후의 데이터는 신뢰도가 서서히 떨어진다.
펌웨어 real-time computing
- 소프트 리얼 타임 컴퓨팅과 하드 리얼 타임 컴퓨팅의 중간쯤 된다.
- 데드라인을 넘어간 이후의 데이터는 사용은 가능하나 의미가 없다.
- 날시 예보와 같은 분야에 사용된다.
Real-time scheduling의 특징
- 운영체제를 선점할 수 도 있는 강한 선점형 스케줄링 기법이다.
- 우선순위 역전현상을 막을 수 있다.
- 더 빠른 응답을 받을 수 있다.
Deadline Based Scheduling
- Real-time 시스템들은 주기가 있는 작업이 대부분이다.
- 다음의 두가 대표적인 알고리즘이 있다.
- Rate Monotonic Scheduling(RMS) algorithm
- 주기가 더 빨리 끝나는 작업을 우선적으로 처리한다.
- 데드라인을 우선시 하지 않기 때문에 작업에 실패할 수도 있다.
- Earliest Deadline First(EDF) algorithm
- 작업마다 데드라인이 존재하고, 데드라인이 가장 짧은 일부터 처리한다.
- 무조건 남은 데드라인까지가 우선이라 주기는 고려하지 않는다.
- 다음의 상황을 만족해야한다.
- 다른 프로세스를 의존하지 않는다.
- 주기적이지 않으면 데드라인은 없다.
- 선점 이후의 오버헤드는 고려하지 않는다.
- 주기가 있는 프로세스는 반드시 그 안에 작업을 끝내야한다.
😺 오타나 논리적 오류 지적은 언제든지 환영합니다!😺
항상 읽어주셔서 감사합니다~ 🙏
Leave a comment