운영체제 수업을 수강하며 정리한 내용을 작성하려고 합니다.
Priority Scheduling
- 프로세스별 우선순위를 표현하는 정수값을 표기
- 가장 높은 우선순위 프로세스에 CPU 할당 (대개 최소 정수가 가장 높은 우선순위)
- 비선점형: 현재 프로세스가 자발적 양보를 할 때, 우선순위에 따라 다음 프로세스 선택
- 선점형: 매 타임 퀀텀마다(혹은 새 프로세스 생성시) 현재 프로세스보다 높은 priority를 가지고 있는 프로세스 존재 시 수행
- 문제점 - 기아 상태(Starvation)
- 낮은 우선순위를 가진 프로세스는 전혀 수행되지 않을 수 있다.
- 해결 방법 - Aging 기법
- 프로세스별 대기 시간이 증가함에 따라 프로세스 우선순위를 상향
- 우선순위는 어떻게 정할 것인가
- 사용자가 결정(리눅스의 nice값 등)
- 휴리스틱 활용 (과거 기록 → 추론 modeling)
Round robin (RR)
- CPU를 동일한 시간 단위로 쪼개어 프로세스에 배분하는 선점형 스케줄링 방식
- 배분 단위: time quantum
- Time slice: 프로세스별 1회 스케줄링 시 (round) CPU를 점유하는 기간
- e.g., 10ms
- 스케줄러가 Time slice를 감지하는 방법: timer interrupt
- HW timer가 time quantum마다 커널 모드로 진입하고 스케줄링이 수행되도록 함
- Time quantum: CPU 할당의 가장 작은 단위 (e.g., 1ms)
- HW timer가 time quantum마다 커널 모드로 진입하고 스케줄링이 수행되도록 함
- Time slice 동안 수행을 완료한 프로세스:
- Ready 큐의 끝으로 들어감 → 다음 번 할당을 대기
RR 예시
- 장점: response 시간이 짧다
- 특징: time slice가 context switch time보다 큰 것이 적합
- 이유 - time slice가 context switch time보다 작으면 성능이 매우 떨어짐
FCFS와 RR의 비교
- FCFS
- Response time: (0 + 24 + 27) / 3
- wait time : (0 + 24 + 27) / 3
- RR
- Response time (0 + 4 + 7) / 3
- wait time (6 + 4 + 7) / 3
Time slice와 RR의 관계
- Time slice가 큰 경우:
- FCFS와 거의 비슷하게 동작
- Time slice가 작은 경우
- 응답성이 좋아지지만 성능이 매우 떨어짐
Multilevel Queue Scheduling
- Ready 큐를 여러 개 만들어 각각에 대해 상이한 스케줄링 기법을 적용(큐 2개)
- 예시
- Foreground 큐: Interactive한 동작이 필요한 프로세스를 위한 큐
- 큐 동작: Round Robin 기법 적용
- Background 큐: CPU 연산 작업을 주로 수행하는 프로세스를 위한 큐
- 큐 동작: FCFS 기법 사용
- Foreground 큐: Interactive한 동작이 필요한 프로세스를 위한 큐
- 프로세스는 항상 동일한 큐 내에 상주 (큐 간 이동 불가)
- 큐 별로 CPU를 사용할 양을 배분
- e.g., Foreground : Background = 80 : 20
Multilevel Queue Scheduling 예시
- 문제점: starvation problem (기아 현상) - 큐 간 프로세스 이동이 불가능하기 때문에 낮은 큐에 들어간 프로세스는 계속 높은 큐에 프로세스가 들어올 때 기아 현상 발생
Multilevel Feedback Queue (MLFQ)
- 기아 현상을 해결하기 위해 (windows 방식)
- Multilevel Queue에서 프로세스들이 다른 큐로 이동 가능
- Aging의 한 방법
- Downgrade도 가능
- MLFQ design choices
- 큐의 개수
- 각 큐마다 스케줄링 기법
- 언제 프로세스를 한 단계 높은/낮은 큐로 옮길 것인가
MLFQ 예시
- 8ms, 16ms 동안 작업이 완료되지 않은 프로세스는 CPU를 많이 사용하는 프로세스로 간주하고, 낮은 우선순위로 처리하는 프로세스 기법
-
A new job enters Q0
-
The job goes to Q1 after its first-round execution
-
The job goes to Q2 after iss second-round execution
-
CFS scheduling
- 현재 리눅스에서 CPU를 스케줄링하는 방법
- CFS: Completely fair scheduler
- 실행되는 프로세스들이 CPU를 동일한 “비율”로 사용하도록 함
- 실현 가능성?
CFS scheduling의 구현
- 대안
- 프로세스별로 사용한 시간을 트래킹
- 목표에서 어긋난 프로세스를 목표에 가까워지도록 우선순위화
- Next process decision
- “Repair” illusion of complete fairness
- choose a process with minimum CPU time
CFS scheduling의 특성
- 다양한 실행 상황을 고려하기 위해, 아래의 특징을 가짐
- 1) Target latency 보장
- 각 application별로 실행 turn이 돌아오는 데 걸리는 시간을 보장
- 발생가능한 문제점: context switching이 너무 많이 일어날 수 있음
- 2) minimum granularity 보장
- 각 time slice의 최소값 존재
- 3) job간 priority의 고려
- 모든 job에게 항상 동일한 비율의 CPU만 제공할 것인가
- 모든 job에게 항상 동일한 비율의 CPU만 제공할 것인가
- 아이디어: Assign a weight Wi to each process i
CFS의 virtual runtime
- 스케줄링 결정을 simple하게 만들기 위해 weight을 근거로 실제 프로세스의 실제 실행 시간을 정규화(vruntime)
Interprocess communication (IPC) - 프로세스간 통신
- 프로세스가 독립적(고립)이거나 협력해야하는 상황이 있을 수 있다
- Protection domain = 상호 간 메모리 고립
- 협력하는 이유
- Data sharing
- Computation speedup
- Modularity
- Convenience
- Cooperating processes need interprocess communication (IPC)
- 프로세스들 간에 데이터 및 정보를 주고받기 위한 메커니즘
- 커널에서 IPC를 위한 도구를 제공(시스템 콜)
IPC의 두가지 모델
- 공유 메모리 기법(물리 메모리)
- 두 프로세스가 모두 이용할 수 있는 공유 메모리를 설정
- 공유 메모리에 공유할 데이터를 읽고 씀
- 메시지 전달 기법
- 커널을 통해서 데이터를 전달
- 두 프로세스가 직접 공유하는 메모리 영역은 없음
We Need Better UX