[OS] 정리4

프로세스의 실행은 CPU 실행 사이클과 I/O 대기로 구성된다. 일반적으로 짧은 CPU 버스트가 많고, 적은 수로 긴 CPU 버스트가 발생한다.

CPU 스케줄러

- 메인 메모리에 있는 Ready 상태의 프로세스들 중 하나에게 CPU를 할당시킨다.

- 스케줄링이 발생하는 경우

1. running에서 wait 상태로 변경될 때 (I/O 요청하는 경우)

2. running에서 ready 상태로 변경될 때 (Interrupt 발생)

3. wait 상태에서 ready 상태로 변경될 때 (I/O 요청 완료)

4. 종료될 때

- 1, 4일 경우에만 스케줄링하는 방식이 비선점 스케줄링이다.

- 1~4 모든 경우에 스케줄링하는 방식이 선점형 스케줄링이다.

Dispatcher

- Short-Term 스케줄러에 의해 선택된 프로세스에게 CPU 제어를 넘겨주는 모듈

- Context Switching

- 유저 모드로 전환

- 유저 프로그램을 재시작하기 위해 해당 주소로 이동

Dispatch Latency

- Dispatcher가 한 프로세스를 중지하고 다른 프로세스를 시작하기까지 걸리는 시간

스케줄링의 척도(Scheduling Criteria)

- CPU 사용률 극대화(CPU utilization) : CPU를 최대한으로 놀지 않도록 효율적으로 이용

- 처리 능력 극대화(Throughput) : 주어진 시간에 최대한 많은 작업을 처리 (처리한 프로세스 수 / 시간)

- 경과 시간(반환 시간) 최소화(Turnaround time) : ready_queue에서 대기한 시간 ~ 작업을 마치고 반환하기까지 걸린 시간을 최소화

- 대기 시간(Waiting time) 최소화 : ready_queue에서 대기한 시간의 총합

- 응답 시간(Response time) 최소화 : reqdy_queue에 들어와서 처음으로 CPU를 할당받기까지 대기한 시간

최적화 척도(Optimization Criteria)

- 최대 CPU 사용량

- 최대 처리 시간

- 최소 반환 시간

- 최소 대기 시간

- 최소 응답 시간

스케줄링 알고리즘

- FCFS(First-Come, First-Served)

- SJF(Shortest Job First)

- Priority

- Round Robin(RR)

FCFS : 비선점 / CPU를 먼저 요청한 프로세스가 먼저 처리됨

- ready_queue에 도착한 순서에 따라 CPU 할당

- FIFO Queue로 구현됨

- Convoy Effect : 수행시간이 긴 프로세스가 CPU를 독점하게 되어, 다른 프로세스들이 오랫동안 해당 프로세스가 종료되기를 기다리는 경우 발생

- 평균 대기 시간이 긴 경우가 종종 발생

SJF : 선점 or 비선점 / ready_queue 내의 프로세스 중 수행시간 짧다고 판단되는 것을 먼저 수행

- 각 프로세스의 CPU 버스트 길이를 비교하여 CPU가 이용 가능해지면 가장 작은 CPU 버스트를 가진 프로세스에게 할당해 줌

- 주어진 프로세스들에 대해 평균 대기시간이 최소인 최적 알고리즘

일단 먼저 도착한 프로세스를 실행할 테니, P1로 시작

Timeline

0 P1(6)

1 P1(5)

2 P1(5) > P2(4) 이므로 P2실행. -> P2(3)

3 P2(2)

4 P1(5) > P2(2) > P3(1) 이므로 P3 실행 -> P3(0)

5 P1(5) > P4(4) > P2(2) 이므로 P2 실행 -> P2(1)

6 P2(0)

7 P1(5) > P4(4) 이므로 P4 실행 -> P4(3)

8 P4(2)

9 P4(1)

10 P4(0)

11 P1(4)

12 P1(3)

13 P1(2)

14 P1(1)

15 P1(0)

다음 CPU Burst 길이는

1. 이전 CPU Burst 길이

2. Exponential 평균

을 이용하여 추정한다.

Priority Scheduling : 선점 or 비선점 / 각 프로세스에 우선 순위 번호를 부여하고, 우선 순위가 높은 프로세스부터 CPU를 할당해 줌

- 일반적으로 낮은 번호가 높은 우선순위를 나타냄

- 어떻게 보면 SJF도 다음 CPU 버스트 타임을 이용한 우선 순위 스케줄링이라고 할 수 있음

- Starvation 문제 : 낮은 우선순위의 프로세스가 영원이 수행되지 않는 경우가 생김

- Aging : Starvation 문제를 해결하는 방법으로, 시간이 지날수록 우선 순위를 높이는 방식

Round Robin(RR) : 선점 / 각 프로세스는 동일한 크기의 Time Slice(CPU 시간 : 일반적으로 10 ~ 100ms로 설정한다)을 할당받음

- Time Slice동안 처리하고 완료하지 못했다면 ready_queue의 맨 뒤로 들어간다. CPU 제어는 다음 프로세스로 넘어간다.

- 할당 시간이 크면 FCFS 스케줄링과 같아지고, 할당 시간 너무 작으면 Context Switching이 자주 발생하여 성능저하가 큼

일반적으로 평균 처리시간이 길지만 응답 시간은 짧다. 

Multiple Processor Scheduling

- 스케줄링은 CPU를 여러 개 사용할 수 있을 때 복잡해진다.

Symmetric Multiprocessing(SMP)

- 둘 이상의 프로세서

- 모든 프로세서는 운영체제에서 실행되며, 관리된다.

- 모든 프로세서는 공유 메모리를 사용하여 통신한다.

- 모든 프로세서가 메인 메모리, 네트워크, I/O 장치 등 하드웨어에 대한 엑세스 권한을 가진다.

- 프로세서는 동일한 프로세스를 실행하지 않는다.

- 각 프로세서는 각각 ready_queue를 가지거나, 하나의 ready_queue를 공유하여 사용할 수 있다.

Asymmetric Multiprocessing

- SMP가 가능했던 시기 이전의 방식이다.

- Master 프로세서만이 운영체제에서 실행되며, 관리된다.

- 프로세서들은 Master-Slave 관계

- Master 프로세서는 Slave 프로세서들에게 프로세스를 할당한다.

- Master 프로세서가 자료구조를 다룬다.

- Master 프로세서만이 프로세스 스케줄링, I/O, 등의 처리를 한다.

Load Balancing

- SMP 시스템의 모든 프로세서가 작업 부하를 고르게 받도록 분산시킨다.

- 각 프로세서가 개별적으로 ready_queue를 가지는 시스템에서만 필요한 기법

- Push Migration : 특정 Task가 프로세서들의 부하를 주기적으로 체크하고, 고르게 분배한다.

- Pull Migration : 프로세서가 스스로 작업이 많은 프로세서로부터 프로세스를 가져온다.

Process Affinity (친화성) : CPU Cache와 프로세스간의 관계를 고려해서 성능 향상

- 만약 시스템에서 Process Migration을 허용해서 새로 스케줄링이 되어 다른 프로세스가 해당 CPU를 할당받게 되면, Cache 메모리의 내용도 비우고 새로운 프로세스의 정보로 채워야 한다. 이런 Migration에 대한 Cost가 높기 때문에 대부분의 SMP 시스템들은 프로세스의 Migration을 피하려 한다.

- 한 마디로 프로세스가 같은 프로세서에서 실행되도록 하는 방식이다.

- Soft Affinity(Migration 허용) : 동일한 프로세서에서 현재 실행중인 프로세슬르 유지하려고 하지만, 이를 100% 보장하지는 않음

- Hard Affinity(Migration 불가) : Migration될 수 없는 프로세서를 지정하는 System Call 제공

Symmetric Multithreading (SMT)

- Memory Stall : 메모리에 엑세스할 때 CPU와 직접 연결된 메모리는 자신의 register와 RAM이다. register는 CPU 내부에 존재하며, 접근이 빠르지만, RAM으로의 접근은 조금 느리다. 그 이유는 Memory Bus를 통해 데이터가 전달되기 때문에, 메모리로부터 데이터를 기다리는 현상이 생기게 되는데, 이를 Memory Stall이라고 한다. 

 예를 들면, Cache Miss가 발생할 경우, 데이터가 사용가능한 상태로 될 때까지 기다리는 데에 많은 시간을 들인다. 이 문제를 해결하기 위해 HW 설계자는 2개 이상의 HW Thread가 각 Core에 할당되는 멀티 프로세서 코어를 개발했다. intel에서는 Hyper Threading이라는 이름으로 다룬다.

- OS 관점에서, 각 HW Thread는 SW Thread를 실행할 수 있는 논리적 프로세서로 정의한다.

Memory Stall 문제

SMT

MultiCore Processor

- 최근 경향은 동일한 물리적 칩에 여러 개의 코어를 배치하는 것이다. 이를 MultiCore Processor라고 한다.

- 2 단계의 스케줄링이 필요하다.

Level 1. SW Thread를 HW Thread로 매핑

Level 2. 각 코어가 실행할 HW Thread를 결정