운영체제 공룡책 공부하며 정리한 내용입니다.
Github : https://github.com/orgs/gochu-charmchi/discussions 정리보다는 머리에 넣고, 개념을 체화하는걸 중요하게 생각합니다. 그에 따라 정리가 이상할 수 있습니다.
5.1 기본 개념
CPU - I/O 버스트 사이클
선점 스케줄링, 비선점 스케줄링
- 스케줄링 발생 상황 4가지
- Race condition
디스패처
- 디스패처가 하는 일
- 디스패처 지연
5.2 스케줄링 기준
- CPU 이용률 (CPU utilization)
- 처리량 (throughput)
- 총처리 시간 (turnaround time)
- 대기 시간 (waiting time)
- 응답 시간 (response time)
5.3 스케줄링 알고리즘
CPU 스케줄링이 다루는 문제
선입 선처리 스케줄링 (FCFS)
- 긍정 - 간단
- 부정 - 평균 대기시간의 편차
- 호위 효과 (convey effect)
- 비선점
최단 작업 우선 스케줄링 (SJF)
- 최소 잔여 시간 우선 스케줄링
- 최소 평균 대기시간을 갖는다.
- CPU 버스트 길이를 정확히 알 방법이 없다.
- 예측 - 지수평균
- 선점, 비선점 둘 다 가능
- 선점형 : 최소 잔여 시간 우선 스케줄링
라운드 로빈 스케줄링 (RR)
- Time slice (시간 할당량) 정의
- 10~100ms
- 총처리 시간, 문맥교환 시간에 따라서 정의
- 원형 큐
- 선점
- 문맥 교환은 보통 10 micro second 미만
우선순위 스케줄링
- SJF는 우선순위 알고리즘의 특별한 경우
- 낮은 수가 높은 우선순위라는 특별한 정의는 없다.
- 책에서는 낮은 수 = 높은 우선순위
- 우선순위 결정
- 내부적 - 측정 가능한 양 사용
- 시간제한, 메모리 요구, 열린 파일 수, 버스트 비율 등
- 외부적
- 프로세스 중요성, 비용, 작업 부서 등 운영체제 외적
- 내부적 - 측정 가능한 양 사용
- 선점형, 비선점형
- 선점형 - 높은 우선순위가 있다면 선점
- 비선점형 - readyQ.prepend()
- 무한 봉쇄 (indefinite blocking), 기아 (starvation)
- 문제
- 낮은 우선순위의 프로세스가 무한 대기 → blocking
- 결국 크래시 or 높은 우선순위 다 처리
- 해결
- 노화 (aging)
- 대기중인 프로세스의 우선순위 증가
- 라운드 로빈 + 우선순위
- 우선순위가 같은 프로세스를 라운드 로빈으로 실행
- 노화 (aging)
- 문제
다단계 큐 스케줄링
- 다단계 큐
- 프로세스 큐를 여러 개 사용하는 스케줄링 알고리즘
- 큐 분리 기준
- 우선순위
- 프로세스 유형 - 실시간, 시스템, 대화형, 배치
- 각 프로세스 큐 마다 다른 스케줄링 알고리즘을 적용할 수 있다.
- 각 프로세스 큐에 CPU시간을 할당할 수도 있다.
- 예시
- 포그라운드 CPU 80%, RR
- 백그라운드 CPU 20%, FCFS
- 예시
다단계 피드백 큐 스케줄링
- 다단계 큐 스케줄링 + 프로세스가 큐 사이 이동
- 노화를 적용해 기아 예방
- 8과 16이 없어야 FCFS 실행된다.
- 매개변수
- 큐의 개수
- 각 큐를 위한 스케줄링 알고리즘
- 한 프로세스를 높은 우선순위로 올려주는 시기를 결정하는 방법
- 한 프로세스를 낮은 우선운위로 강등시키는 시기를 결정하는 방법
- 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법
[! question] 기아 (무한 봉쇄) 상태란? 기아란 프로세스가 프로세스 스케줄링 알고리즘으로 인해 CPU자원을 할당받지 못하여, 준비 큐에 계속 남아있는 상태를 말합니다.
[! question] 스케줄링 알고리즘에서 노화란? 노화는 기아를 예방하기 위해, 준비 큐에 남아있는 프로세스의 우선순위를 높이는 것을 말합니다. 계속 준비 큐에 남아있는 프로세스는 우선순위가 높아져 결국 실행할 수 있게 됩니다.
[! question] 시간할당량이란? 시간 할당량이란 RR 방식의 스케줄링 알고리즘에서 사용되는 단위로, 한 프로세스에게 주어진 CPU 시간을 말합니다. Time slice 만큼의 CPU 버스트가 끝나면, 프로세스는 다음 프로세스가 있다면, 다음 프로세스에게 선점당합니다.
5.4 스레드 스케줄링
- 최신 운영체제에서는 프로세스가 아니라 커널 수준 스레드를 스케줄한다.
- 사용자 수준 스레드
- 스레드 라이브러리에 의해서 관리되고, 커널은 그들의 존재를 모른다.
- 간접(LWP)이든 직접이든 커널 스레드에 매핑되어야 한다.
경쟁 범위
- 다대일, 다대다 모델 구현 시스템에서의 스레드 라이브러리는 LWP 상에서 스케줄한다.
- 프로세스 경쟁 스코프 (PCS, process-contention scope)
- 다대일 모델에서 한 개의 커널 스레드에 연결된 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하는 것.
- 우선순위에 따라 스케줄한다.
- 사용자 수준 스레드의 우선순위는 프로그래머에 의해 지정된다.
- 몇몇 스레드 라이브러리는 스레드 우선순위 변경을 허용한다.
- 시스템 경쟁 스코프 (SCS, system-contention scope)
- CPU상에 어떤 커널 스레드를 스케줄 할 것인지 결정한다.
- 일대일 모델 시스템은 오직 SCS 만을 사용하여 스케줄
Pthreads 스케줄링 API
- 다대다 모델 운영체제에서
- PCS 플래그를 사용하여, 다대일 모델 사용 가능
- SCS 플래그를 사용하여, 일대일 모델 사용 가능
5.5 다중 처리기 스케줄링
- 부하 공유 (load sharing)
- 스레드 병렬 실행을 통해 이룰 수 있다.
다중 처리기 스케줄링에 대한 접근 방법
- 비대칭 다중 처리
- master server가 모든 스케줄링, I/O 처리, 다른 시스템의 활동 처리
- 다른 서버들은 사용자 코드만 수행
- master server가 병목이 될 수 있다.
- 대칭 다중 처리 (SMP, symmetric multiprocessing)
- 스케줄 관리 전략
- 공통 준비 큐
- 경쟁 조건이 생길 수 있다.
- 락킹의 경쟁이 심해져 병목이 될 수 있다.
- 각 프로세서의 준비 큐
- 가장 일반적인 접근 방식
- 캐시 메모리 효율적
- 큐마다 부하의 양이 다를 수 있다.
- 균형 알고리즘을 사용하여 해결
- 공통 준비 큐
- 스케줄 관리 전략
다중 코어 프로세서
- 동일한 물리적인 칩 안에 여러 개의 처리 코어
- 각 처리 코어는 개별적인 논리적 CPU 처럼 보이게 된다.
- 메모리 스톨
- 프로세서가 데이터가 가용해지기를 기다리면서 많은 시간을 허비하는 것
- 프로세서가 메모리보다 훨씬 빠르기 때문 혹은 캐시 미스로 일어남
- 메모리 스톨 해결하기 위해 하나의 코어에 2개 이상의 하드웨어 스레드 할당
- 거친 다중 스레딩
- 한 스레드 지연 발생 시, 다른 스레드로 전환
- 스레드 교환 비용이 많다.
- 세밀한 다중 스레딩
- 좀 더 정밀한 스레드 간 교환이 일어나고, 회로를 포함한다.
- 스레드 교환 비용이 적다
- 이중 스레드 처리 코어의 2단계 스케줄링
- 1단계 : 소프트웨어 스레드 결정 스케줄링
- 2단계 : 하드웨어 스레드 스케줄링
- 방법들
- 라운드로빈
- 하드웨어 관리 스레드가 긴급도 측정 - 스케줄
- 방법들
- 2개의 스케줄링 단계가 상호 배타적으로 작동하지 않고, 연관적으로 작동하는 것이 더 좋다.
- 소프트웨어 스레드가 2개 있을 때, 동일한 코어에서 작동하는 것이 프로세서 자원이 공유되어 좋다.
부하 균등화
- load balancing
- 각 프로세서가 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능이다.
- 일반적인 방법 2개
- push migration
- 특정 태스크가 주기적으로 각 처리기의 부하를 검사한다.
- 과부하 스레드에서 덜 바쁘거나, 쉬는 스레드로 push 한다.
- pull migration
- 쉬고 있는 처리기가 바쁜 처리기를 기다리는 프로세스를 pull한다.
- 상호 배타적일 필요는 없다.
- push migration
처리기 선호도
- processor affinity
- warm cache를 이용하기 위해, 운영체제는 스레드를 이주시키지 않으려고 한다.
- 프로세서별 준비 큐는 기본적으로 제공한다.
- 약한 선호도
- 노력하지만 보장하지는 않을 때,
- 강한 선호도
- 시스템 콜을 이용하여 자신이 실행될 처리기 집합을 명시할 수 있다.
- 많은 시스템은 둘 다 지원한다.
- 부하 균등과 처리기 선호도는 서로를 상쇄한다
- 처리기 선호도를 무시하면, 메모리 액세스 시간이 걸림돌이 된다.
이기종 다중 처리
- heterogeneous multiprocessing
- 차이가 나는 코어를 사용한다.
- ARM : big.LITTLE
- big : 성능 코어
- LITTLE : 효율 코어
- 장점
- 고성능이 아니라, 긴 시간의 실행이 필요한 작업을 효율 코어에 할당
- 고성능, 짧은 시간 작업을 성능 코어에 할당
- 절전 모드인 경우 성능 코어 비활성화
5.6 실시간 CPU 스케줄링
- 연성 실시간 시스템 (soft)
- 실시간 프로세스가 스케줄되는 시점에 아무런 보장을 하지 않는다.
- 중요 프로세스가 그렇지 않은 프로세스에 대해 우선권을 가진다는 것만 보장
- 경성 실시간 시스템 (hard)
- 태스크는 반드시 마감시간까지 서비스받아야 한다.
- 마감시간이 지난 것은, 수행하지 않은 것이랑 같다.
지연시간 최소화
- 이벤트 지연시간
- 이벤트 발생과, 실시간 시스템이 이벤트에 반응하는 시간의 간격
- 이벤트 : 타이머 만료같은 소프트웨어적 이벤트 + 방해물 발견 같은 이벤트
- 시스템 마다 크게 차이난다 (ms단위 ~ sec단위)
- 인터럽트 지연시간
- 인터럽트 발생 시점부터 ISR 이 시작하기까지의 시간
- 인터럽트 발생 → 인터럽트 유형 결정 → 문맥 교환 → ISR 시작 전까지
- 디스패치 지연시간
- 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는데 까지의 시간
- 최소화 하려면 선점형 커널을 사용
- 충돌 단계
- 커널에서 동작하는 프로세스에 대한 선점
- 높은 우선순위 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출
- 디스패치 단계
- 우선순위가 높은 프로세스를 사용 가능한 CPU에 스케줄
- 이벤트 발생과, 실시간 시스템이 이벤트에 반응하는 시간의 간격
우선순위 기반 스케줄링
- 실시간 운영체제의 스케줄러는 선점, 우선순위 알고리즘을 지원해야만 한다.
- 연성 실시간 스케줄링
- 실시간 프로세스에게 가장 높은 스케줄링 우선권을 부여한다.
- 선점 및 우선순위 스케줄러는 단지 연성 실시간 기능을 제공하는 것
- 경성 실시간 시스템에는 부가적인 스케줄러가 필요하다.
- 실시간 프로세스의 특성
- 주기적 : 프로세스들은 일정 간격마다 CPU가 필요하다.
- 서비스 받아야 하는 시간이 정해져 있다.
- 주기적 : 프로세스들은 일정 간격마다 CPU가 필요하다.
- 승인 제어 알고리즘
- 프로세스가 마감시간을 스케줄러에게 알린다.
- 마감시간 내에 완수 가능한 것만 승인한다.
- 실시간 프로세스의 특성
Rate-Monotonic 스케줄링
- 주기가 짧은 프로세스에 우선순위를 부여한다.
- 주기가 긴 프로세스는 주기가 짧은 프로세스에게 선점당한다.
Earliest-Deadline-First 스케줄링 (EDF)
- 마감시간에 따라 우선순위를 동적으로 부여한다.
- 마감시간이 빠를수록 우선순위가 높아진다.
- 프로세스가 자신의 마감시간을 스케줄러에서 알려주어야 한다.
- 이론적으로 최적이다.
- 문맥 교환 비용 때문에 100%의 CPU 이용률은 불가능하다.
일정 비율의 몫 스케줄링
- proportional share scheduling
- 프로세스 시간을 프로세스 별로 나누어 할당하는 스케줄 정책
- 프로세스 시간 = 100, A = 50, B = 15, C = 20
- 총 85로 수행 가능
- 승인제어 : 다른 15 초과의 프로세스가 진입하려고 하면 거부해야 한다.
POSIX 실시간 스케줄링
- FIFO, RR, OTHER (시스템마다 다름)
5.7 운영체제 사례들
- Solaris, Windows = 커널 스레드 스케줄링
- Linux = 태스크 스케줄링
Linux 스케줄링
- UNIX → O(1) 스케줄러 → CFS 스케줄러 (Completely Fair Scheduler)
- 다음에 실행될 프로세스는 높은 우선순위 클래스에 속한 가장 높은 우선순위의 태스크를 선택
- 리눅스 스케줄링 클래스
- CFS 스케줄링 알고리즘을 사용하는 디폴트 스케줄링 클래스
- 실시간 스케줄링 클래스
- 각 태스크에 CPU 처리시간의 비율을 할당한다.
- 우선순위를 각 태스크에 할당된 nice 값을 기준으로 계산
- nice 값
- -20 ~ 19 , 값이 적을 수록 높다
- 적은 nice 값의 태스크는 더 큰 비율의 CPU 처리시간을 할당받는다.
- (nice 한 프로세스는 다른 프로세스에게 잘 대해주어, 제일 마지막에 종료된다!)
- CFS는 Time slice 가 아닌, 목적 지연시간(targeted latency)를 찾는다.
- 목적 지연시간
- 다른 모든 수행 가능한 태스크가 적어도 한번씩은 실행할 수 있는 시간 간격
- 디폴트 값과 최솟값을 가진다.
- 활성 태스크의 개수가 일정 임계값보다 많아지면 증가할 수 있다.
- 목적 지연시간
- CPU 시간의 비율은 목적 지연시간 값으로부터 할당된다.
- CFS는 직접 우선순위를 할당하지 않고, vruntime 이라는 변수에 태스크 실행 시간을 기록하여, 가상 실행 시간을 유지한다. 사실상 패스
[! caution] 사실상 패스
Windows 스케줄링
[! caution] 패스
Solaris 스케줄링
[! caution] 패스
알고리즘의 평가
- 알고리즘 선택 기준
- CPU 이용률, 응답 시간, 처리량 등 값의 상대적인 중요성을 반드시 정의해야 한다.
결정론적 모델링
- 특정 작업 부하를 만든 후, 작업 부하에 대한 알고리즘 성능을 정의한다.
- 단순하고 빠르다.
- 예시를 제공하는 데 사용된다.
큐잉 모델
- CPU와 I/O 버스트의 분포는 측정 가능하며, 계산하거나, 추정할 수 있다.
- 프로세스들이 시스템에 도착하는 시간 분포 (도착 시간 분포)도 기술할 수 있다.
- 버스트 분포, 도착 시간 분포를 이용하여 평균 처리량, 이용률, 대기 시간등을 계산할 수 있다.
- Little’s formula
- 평균 큐 길이 = 평균 도착률 * 평균 대기 시간
- 평균 9의 큐 길이 = 평균 1초에 3개 프로세스 도착 * 평균 3초의 대기시간
- 두 개의 값을 알면, 하나의 값을 계산할 수 있다.
- 분석 가능한 알고리즘 분포와 부류가 제한적, 복잡하면 어렵다.
- 근사치이고, 정확성에는 의심 가능하다.
모의 실험
- Simulation
- 컴퓨터 시스템의 모델을 프로그래밍한다.
- 구동 자료는 여러 방법으로 생성할 수 있다.
- 난수 발생기 : 확률 분포(균등, 지수, 푸아송, 경험적 분포) 이용
- 경험적 분포 : 실제 시스템에 대한 측정을 통해 분포를 생성하고, 분포를 이용한다.
- 추적 파일 사용
- 난수 발생기 : 확률 분포(균등, 지수, 푸아송, 경험적 분포) 이용
- 모의 실험기를 프로그래밍 하는 것이 매우 중요한 작업
구현
- 실제 코드로 작성해 운영체제에 넣고 해보는 것
- 제일 비쌈.
- 회귀 테스트를 통해 너 나빠지지 않음을 확인할 수 있다.
- 사용 환경이 변화할 것
- 운영체제에 따라서 사용자의 프로그래밍 방식이 변화할 것이다
- 시스템 관리자 (사용자) 에게 알고리즘이 조정될 수 있도록 하는 것이 융통성 있는 해결책
[! question] 알고리즘의 평가 방법을 간단히 설명하여라. 결정론적 모델링 주어진 작업에 대해 각 알고리즘을 실행해 나온 지표를 이용하여 평가하는 방법 +) 단순하고 빠르다, -) 못써먹을 정도 큐잉 모델 측정 가능한 분포들, 값들을 이용하여 수학적으로 계산해 근사치를 통해 평가하는 방법 +) 수학적으로 분석하기 쉽다. -)다수의 가정이 필요하고, 계산이 어렵고, 근사치이다. 모의 실험 각 알고리즘을 가진 컴퓨터 시스템을 프로그래밍하고, 임의로 생성된 이벤트들로 구동하여 평가하는 방법 이벤트 생성 방법에는 분포(균등, 지수, 푸아송, 경험적)를 이용한 난수 발생기로 생성하는 방법, 실제 시스템을 관찰하여 이벤트들의 순서를 기록해놓은 추적 파일 (trace file)을 사용하는 방법이 있다. +) 상세하게 할 수록 정확한 결과를 얻는다. -) 프로그래밍이 어렵고, 비용이 많이 든다. 구현 실제 운영체제에 실제 스케줄링 알고리즘을 코딩하여 넣고 실행해 측정해보는 방식. +) 제일 정확하다. -)어떻게 설계하느냐에 따라 사용 환경이 바뀐다.