# 스케쥴링
- CPU의 시간을 나누어써서 가상화
- 스케줄링의 고려사항
  - 성능저하: 오버헤드를 최소화
  - 제어문제: 통제를 유지하면서 효율적으로 프로세스 실행
# 제한적 직접 실행원리(Limited Direct Execution)
프로세스가 cpu에 제한없이 직접 실행되면 프로세스는 원치않는 기능을 실행하거나 cpu를 독점하는 경우가 발생할 수 있다. 이러한 문제점을 해결하고자 직접 실행방식에 제한을 걸어주게 되었다.
## 권한 분리
프로세스가 무분별하게 자원에 접근하는 것을 막기위해서 커널모드와 사용자 모드를 사용하워 권한을 분리해준다.
- 사용자 모드(User mode): 접근할 수 있는 자원이 제한된 모드
- 커널 모드(Kernel mode): 모든 자원에 접근 가능한 모드
- trap: 사용자 모드에서 trap 시스템 콜을 사용하여 커널 모드의 기능을 사용할 수 있다.
- return-from-trap: trap을 사용한 명령이 완료되면 호출한 사용자 프로그램으로 돌아간다.
- 커널 스택(kernel stack): 프로그램 카운터, 플래그, 레지스터들을 각 프로세스의 커널스택에 저장하여 보관. return-from-trap 명령어가 커널 스택에서 값을 가져와서 사용자 프로그램의 다시 실행.
- 트랩 테이블(trap table): 트랩이 사용될 때 cpu가 점프하여 사용해야할 trap 명령어의 위치 저장
- 트랩 핸들러(grap handler): 트랩을 처리

![제한적 직접 실행 프로토콜](./aseet/제한적%20직접%20실행%20프로토콜-진호.jpeg)
### trap 과정
1. 사용자 모드에서 trap 호출
2. 레지스터를 커널 스택에 저장
3. 하드웨어에서 트랩 테이블의 트랩 위치를 보고 트랩 핸들러로 분기
4. 커널 모드에서 트랩 처리
5. return-from-trap
6. 하드웨어가 커널 스택에서 데이터 복구
7. 사용자 모드로 전환

## 프로스세스 전환
### 협조(cooperative)
- 운영체제가 프로세스들이 합리적으로 행동할 것이라고 신뢰
- 너무 오랫동안 실행할 가능성이 있는 프로세스는 주기적으로 cpu를 포기하여 운영체제가 다른 작업을 실핼할 수 있다고 가정
- 프로세스는 **yield** 시스템 콜을 사용하여 운영체제에게 제어를 넘긴다.
- 악의적으로 만든 프로그램이거나 버그로 인해서 무한 루프에 빠질 경우 제어를 넘길 수 없다.
### 비협조
비협조적인 프로세스로부터 제어를 얻기위해서 **<u>타이머 인터럽트(timer interrupt)</u>** 사용
- 타이머 인터럽트: 수 밀리초 마다 인터럽트를 발생시켜 <u>인터럽트 핸들러(interrupt handler)</u>를 실행시킴
### 문맥의 저장과 복원
- <u>**스케줄러(scheduler)**</u>: 프로세스 전환을 위해 실해중인 프로세스를 중지시키면 해당 프로세스를 실행할 것인지 전환할 것인지 결정을 내리는 역할을 한다.
- **문맥 교환(Context Switching)**: 프로세스를 전환할 때 실행중인 프로세스의 레지스터 값을 저장하고 실핼할 프로세스의 레지스터값을 가져온다. return-from-trap이 실행될 때 다른 프로세스의 값을 가져와서 사용함으로써 문맥교환 가능.
  
![timer interrupt](aseet/타이머%20인터럽트-진호.jpeg)

1. 사용자 모드에서 프로세스 실행
2. 하드웨어에서 타이머 인터럽트 발생
3. 실행중인 프로세스의 레지스터를 커널 스택에 저장
4. 트랩 핸들러로 분기
5. 트랩 처리
6. switch() 루틴 호출
7. 실행중이었던 레지스터를 proc 구조에 저장
8. 전환할 프로세스의 proc 구조에서 레지스터 복원
9. return-from-trap
10. 하드웨어에서 전환할 커널스택을 레지스터로 저장
11. 사용자 모드로 이동

# 스케줄링(Scheduling)
- 워크로드(workload): 프로세스들이 실행하는 상황
## 평가기준
1. 반환시간
   
$T_{turnaround}=T_{completion}-T_{arrival}$

2. 응답시간

$T_{response}=T_{firstrun}-T_{arrival}$
## 스케줄링 정책
- 선점형: 문맥 교환을 사용하여 실행중인 프로세스를 중단시키고 다른 프로세스를 실행 할 수 있다.
- 비선점형: 각 작업이 종료될 때 까지 계속 실행
### 1. 선입선출
먼저 도착한 작업이 실행되기 때문에 뒤에 실행되는 작업은 앞의 작업이 끝나는 것을 기다려야한다.
### 2. 최단 작업 우선(Shortest Job First, SJF)
모든 작업이 동시해 도착한다면 최적의 알고리즘이라고 할 수 있다.
### 3. 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)
새로운 작업이 도착한 경우 현재 실행중인 작업과 비교하여 작업시간이 적다면 문맥교환을 한다.
### 4. 라운드로빈(Round-Robin, RR)
작업을 단위 기준으로 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum)이라 부른다. 

작업을 단위 기준으로 잘라서 문맥교환을 하게 되면 교환 비용이든다. 라운드 로빈은 공정한 정책으로 사용하기 때문에 반환시간과 같은 평가기준에서는 성능이 나쁘다. 
> 당신은 케익을 먹으면서 동시에 보관할 수는 없다.

# 멀티 레벨 피드백 큐(Multi-level Feedback Queue, MLFQ)
MLFQ가 해결하고자하는 문제
1. 짧은 작업을 먼저 실행시켜 반환 시간을 최적화한다.
2. 응답 시간을 최적화한다.

## 고려사항
1. 기아상태(starvation): cpu를 할당 받지 못하는 상태
2. 독점: 타임슬라이스를 소진하기 전에 입출력 요청을하여 우선순위가 내려가지 않게 할 수 있다.
   
## 기본규칙
1. 여러개의 큐(Queue)로 구성
2. 각각 다른 우선순위(Priority level)가 배정
3. 큐에는 실행준비된 프로세스가 존재
4. 우선순위가 높은 작업이 먼저 실행
5. 우선 순위가 같으면 라운드 로빈 방식으로 실행
6. 작업이 시스템에 진입하면 가장 높은 우선순위의 큐에 저장
7. 주어진 타임 슬라이스를 모두 사용하면 우선순위 강등
   - 해당 규칙의 효과로 SJF에 근접한 성능을 가질 수 있다.
8. 다임 슬라이스를 소진하기전에 cpu를 양도하면 같은 우선순위 유지
   - 입출력을 수행하면 cpu를 자진 반납하기 때문에 우선순위는 유지된다.
9. 주어진 단계에서 시간 할당량을 소진하면 우선순위는 낮아진다.
   - 7,8을 악용하여 독점하는 사례 예방
10.  일정기간이 지나면 시스템의 모든 작업을 최상위 큐로 이동시킨다.
     - 모든 작업을 최상위 큐로 이동시키게 되면 기아상태와 독점을 해결할 수 있다.
     - 해당 일정시간을 부두 상수(voo-doo constants)라고 한다 -> 해당 시간을 정해주는 것에는 흑마술과 같은 미래 예지가 필요하기 때문
  
## MLFQ의 최종 규칙
1. 우선 순위가 높은 작업이 먼저 실행
2. 우선 순위가 같으면 라운드 로빈 방식으로 실행
3. 작업이 시스템에 진입하면 가장 높은 우선순위의 큐에 저장
4. 주어진 단계에서 시간 할당량을 소진하면 우선순위 강등
5. 일정기간이 지나면 시스템의 모든 작업을 최상위 큐로 이동

# 스케줄링: 비례 배분(Proportional Share)
> 비례라는 말을 쓴지 오래돼서 와닿지 않았는데 함수의 비례, 반비례할 때 그 비례다.
- 공정 배분(fair share)라고도 한다.
## 추첨 스케줄링(lottery scheduling)
- 다음 실행될 프로세스를 추첨을 통해 결정
- 더 자주 수행되어야하는 프로세스는 높은 당첨확률을 가진다.
- **추첨권(티켓, ticket)**: 프로세스가 받아야할 자원의 몫을 나타내는데 사용

### 추첨 기법

1. 추첨권 화폐(ticket currency)
   1. 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당
   2. 시스템은 자동적으로 화폐 가치를 변환
   3. 사용자가 할당한 화폐와 시스템의 화폐에는 환율이 있다.
2. 추첨권 양도(ticket transfer)
   1. 양도를 통해서 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다.
   2. 서버/클라이언트 환경에서 클라이언트의 연선을 서버가 대신 더 잘 수행할 수 있도록 본인의 추첨권을 양도한다.
3. 추첨권 팽창(ticket inflation)
   1. 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다.
   2. 프로세스들이 서로를 신뢰할 경우에만 사용
## 결정론적(Deterministic) 방법을 사용하지 않는 이유
결정론적 방법음 새로운 작업이 생기지 않을 경우에만 이상적이다. 새로운 작업이 도착했을 경우 그 작업이 없는 경우에 형성된 결정론적 방법은 새로운 작업을 추가하여 새롭게 설정되어야한다. 이렇게 되면 더 이상 결정론적이지 않다는 모순이있다.

# 멀티 프로세서 스케줄링(Multiprocessor scheduling)
## 캐시(cache)
- 지역성
  - 시간 지역성(temporal locality): 한번 접근된 데이터는 다시 접근될 가능성이 높다.
  - 공간 지역성(spatial locality): 접근된 데이터의 주변 데이터는 접근될 가능성이 높다.
- 캐시 일관성 문제(cache coherence): 멀티 프로세서가 캐시의 데이터를 사용할때 변경된 데이터가 아닌 변경 이전의 데이터를 사용하게 되는 문제
  - 버스 스누핑(bus snooping): 버스 기반 시스템에서는 버스를 통해서 캐시를 통해 복사된 데이터의 원본이 변경되면 복사된 데이터를 갱신해주는 기법

여러 스레드에서 특정 데이터에 동시에 접근할 경우 **락(lock)** 을 사용하는 방법으로 데이터 일관성을 유지할 수 있다.
## 캐시 친화성(cache affinity)
하나의 프로세스를 여러 cpu에서 실행하게 할 경우 여러 cpu의 캐시에 해당 프로세스의 데이터를 저장해야한다. 그렇기 때문에 가능한 한 프로세스를 동일한 cpu에서 실행해야한다.

## 단일 큐 스케줄링(Single Queue Multiprocessor Scheduling, SQMS)
단일 큐를 사용하여 큐에 포함된 작업들을 멀티 프로세서에 할당해주는 방식으로 사용한다. 타임 슬라이스 단위로 하여 여러 cpu에서 작업을 돌아가면서 실행하게 할 경우 캐시 친화성이 떨어져서 작업 효율이 하락하게 된다. 그렇기 때문에 각 cpu에서 최대한 캐시 친화성을 유지해주기 위해 할당된 프로세스는 해당 cpu에서 완료하도록 해주는 것이 좋다.
하지만 동기화 오버헤드가 발생하기 때문에 확장성이 좋지 안혹 캐시 친화성이 낮다.

## 멀티 큐 스케줄링(multi-queue multiprocessor scheduing, MQMS)
SQMS와 달리 스케줄링을 위한 큐를 여러개 가지고 있다. cpu 개수가 증가할 수록, 큐의 개수도 증가하기 때문에 락과 캐시 일관성은 더 이상 문제가 되지 않는다. 
하지만 MQMS는 **워크로드 불균형(load imbalance)** 를 가진다. 지나치게 캐시 친화성을 가지기 때문에 한쪽의 cpu에서 먼저 작업이 끝나게되면 멀티 프로세서의 장점을 활용하지 못한다는 단점이 있다.

![mqms](./aseet/mqms-jinho.jpeg)

위와 같이 한쪽에서 작업이 먼저 끝나게되면 싱글 프로세서와 동일하게 동작한다.

이를 해결하기 위해서 **이주(migration)** 기법을 사용할 수 있다. 

이주 기법을 사용하면 여러 스레드에서 할당된 작업의 수가 불균형을 이루게 된 경우, 보다 여유있는 cpu로 작업을 옮겨주오 균형을 이루도록 한다.

![migration](./aseet/migration-jinho.jpeg)

위의 그림처럼 cpu0에는 작업A만이 할당되어있고 cpu1에는 작업 B,D가 할당되어 있다면 몇번의 타임 슬라이스동안 작업 B를 이주시켜서 균형을 맞춰줄 수 있다.

하지만 큐를 너무 자주 검사하게 되면 높은 오버헤드로 확장성에문제가 생긴다. 하지만 너무 자주 검사하지 않게 되면 워크로드의 불균형을 초래한다.

## O(1) 스케줄러
해당 스케줄러는 아직 타임 퀀텀이 남아있는 active 배열과 타임 퀀텀을 모두 소비한 expired 배열이 존재한다. active 배열의 작업이 타임 퀀텀을 소비하게 되면 expired 배열로 옮기게 되고 active 배열이 모두 비게 되면 두 배열에 대한 포인터를 바꿔서 실행하게 된다. 스케줄링의 성능이 O(1)이기 때문에 O(1)스케줄러라고 불린다. acitve 배열에 우선순위를 부여하여 사용할 수 도 있다.