공부하는 개발 블로그

웹 캐슁은 캐슁의 대상이 되는 객체들의 크기와 인출 비용이 일정하지 않으므로 기존의 캐슁과 다른 성격을 가진다.

1)

1) LRU-K: 최근 K번째 참조를 이용

2) LRUF: 각 참조에 가중치를 주어서 계산. 오래될 수록 낮은 가중치를 가짐.

시간 지역성, 객체 인기도(참조 횟수)

노화 기법(aging) : 오래 전에 잉루어진 참조에 대해서 가중치를 줄여나가는 것

캐쉬 오염(cache pollution): 전혀 참조되지 않은 객체가 캐쉬에 유지되는 것.

3. 웹 캐쉬의 일관성 유지 기법

1) pollinv-every-time: 캐쉬 내에 존재하는 객체에 대한 요청이 있을 때마다 근원지 서버에 객체의 변경 여부를 확인하는 방법

2) invalidation: 근원지 서버가 자신의 객체를 캐슁하는 모든 프락시 서버를 기록하고 있다가 객체가 변경된 경우 해당 프락시 서버에 알려주는 방법

3) adaptive TTL(time-to-live): 캐쉬 내에 이미 존재하는 요청이 있을 때 해당 객체에 대한 최종 변경 시각과 최종 변경 확인 시각을 고려해서 변경되었을 가능성이 높다고 판단되는 경우에만 근원지서버에서 변경 여부를 확인한다. 상용 프락시 서버가 사용하는 방식.

변경 가능성 : LMF(Last Modified Facctor)

LMF = (C-V)/(V-M)

C: 현재 시각

V: 최종 확인 시각(validation), M: 최종 변경 시각(modified)

9.1 디스크 구조

디스크에는 데이터가 일정한 크기로 저장됨: 논리 블럭(logical block)

물리적 저장 위치: 섹터(sector)

sector - logical block: 일대일 매핑

디스크는 원판으로 구성.

원판은 트랙으로 구성.

트랙은 섹터로 구성.

섹터에 최소한의 단위 정보가 저장됨.

상대적 위치가 동일한 트랙들의 집합: 실린더.

9.2 디스크 스케줄링

◆디스크 접근 시간(access time) = 탐색 시간 + 회전 지연 시간 + 전송 시간

탐색 시간(seek time) : 디스크 헤드를 해당 실린더로 이동시키는데  걸리는 시간. 원판 안/밖 이동 시간

회전 지연 시간(rotational latency): 디스크가 회전해서 읽고 쓰려는 섹터가 헤드에 도달하는데 걸리는 시간

전송 시간(transfer time): 데이터를 실제로 섹터에 읽고 쓰는 데 소요되는 시간

탐색 시간을 줄이는 것이 핵심

◆

1) FCFS(Fist Come First Served)

2) SSTF(Shorted Seek Time First): 현재위치에서 가장 가까운 위치에 있는 요청. 기아(starvation)발생 가능

3) SCAN(=엘리베이터 스케줄링 알고리즘): 한쪽 끝에서 한쪽 끝으로. 기아, 이동거리에서 효율적이지만 바깥쪽이 안쪽보다 평균 대기 시간이 긺.

4) C-SCAN(Circular SCAN): SCAN과 비슷하나, 한쪽 끝에 도달하면 다시 시작점으로 돌아가서 처리. 돌아가는 길에는 처리 X. 이동거리는 길어지지만 탐색 시간의 편차는 줄일 수 있음..

5) LOOK: 헤드의 진행방향에 더 이상 요청이 없으면 turn.

   C-LOOK: 헤드의 진행방향에 더 이상 요청이 없으면 시작점으로 돌아감.

9.3 다중 디스크 환경에서의 스케줄링

여러 디스크에 데이터가 중복해서 저장된 경우.

어느 디스크에서 작업을 수행할지?에 대한 문제

탐색 시간을 줄이기

디스크간의 부하가 균형을 이루도록

저전력을 원하면 일부 디스크에 요청 집중. -> 디스크에서 요청을 수용할 수 있을 정도에만

9.4 디스크의 저전력 관리

1) 비활성화 기법

활동(active): 헤드가 데이터를 읽거나 쓰는 중

공회전(idle): 디스크가 회전중이지만 읽거나 쓰는 중이 아닌 경우

------ ^ 활성화. 아래: 비활성화

준비(standby): 디스크가 회전하지는 않지만 인터페이스가 활성화

휴면(sleep): 디스크 회전 X 인터페이스 비활성화

비활성 상태가 활성 상태보다 전력 소모가 적으나, 비활성 때 요청을 처리하는 경우 추가 에너지 소모가 든다.

언제 비활성화 할지 결정하는 알고리즘:

시간 기반 : 일정 시간동안 공회전 -> 정지

예측 기반 : 과거 요청을 보고 공회전 구간의 길이 예측

확률 기반: 마르코프 체인 등의 확률 모델 이용

2) 회전 속도 조절 기법

디스크 회전 속도(RPM)

3) 디스크 데이터 배치 기법

디스크 내의 복제본을 만듦. -> 헤드 위치에서 가까운 복제본 이용.

4) 버퍼 캐슁 및 사전 인출(prefetch) 기법

미래에 요청될 데이터를 알거나/예측 가능하다면 prefetch

디스크가 저전력일 때, 최대한 입출력 지연.

5) 쓰기 전략을 통한 저전력 디스크 기법

디스크가 비활성 상태일 때 쓰지 않고 기다렸다가, 활성상태가 되면 씀.

가상 메모리: 각 프로세스는 0번지에서 시작하는 고유의 주소 공간을 가짐.

8.1 요구 페이징

당장 사용할 페이지만 메모리에 올림.

입출력 시간이 단축 -> 응답시간 단축. 더 많은 프로세스 처리.

적은 메모리 필요.

페이지 부재(page fault): 페이지가 메모리에 없다.

1) page fault 처리

(1) MMU(Memory Management Unit)이 page fault trap 발생

(2) CPU으 제어권이 커널모드로 전환. page fault 처리 루틴 호출

(3) 페이지에 대한 접근이 적법한지 체크: 사용되지 않는 주소 영역? 접근 권한이 있는가?

(4) 물리 프레임에서 비어있는 프레임을 할당받아 메모리를 읽어옴

(5) 빈 프레임 없으면 swap out and swap in. 디스크 작업은 오래 걸리므로 page fault가 발생한 프로세스는 CPU를 빼앗기고 봉쇄 상태가 됨. PCB에 CPU 레지스터 상태 및 프로그램 카운터 값 저장.

(6) 디스크 입출력 완료 -> 인터럽트 -> 유효 비트로 설정 -> 봉쇄된 프로세스를 준비큐로 이동.

2) 요구 페이징의 성능

page fault의 발생 빈도에 따라 성능이 결정됨.

EAT(effective access time):

p는 page fulat rate

(1-p) * 메모리 접근 시간 + p*(page fualt 처리 오버헤드 + swap out 오버헤드 + swap in 오버헤드 + 프로세스 재시작 오버헤드)

8.2. 페이지 교체

page fault율을 최소화하는 알고리즘이 목표

1) 빌레디의 오프라인 최적 알고리즘

가장 먼 미래에 참조되는 페이지를 swap out.

페이지가 참조되는 순서를 알고 있다는 가정. 이론적. 알고리즘 성능의 상하선 제공.

2) FIFO

가장 먼저 올라왔던 페이지를 먼저 swap out.

FIFO 이상현상(FIFO anomal): 메모리를 증가시켰음에도 오히려 page fault 증가

3) LRU(Least Recently Used)

시간 지역성(temporal locality) 이용.

가장 오래 전에 참조가 이루어진 페이지를 swap out.

4) LFU(Least Frequently Used)

페이지 참조 횟수가 가장 적은 페이지 swap out.

Incache-LFU: 페이지가 물리 메모리에 올라온 순간부터 1. swap out-in 되면 1부터 다시 시작.

Perfect-LFU: 누적 참조 횟수.

참조 횟수를 저장하는 오버헤드

5) clock algorithm(=second chance algorithm, NUR, NRU: Not Used Recently)

LRU를 근사한 알고리즘.

오랫동안 참조되지 않은 페이지 중 하나 swap out.

하드웨어 지원으로 동작 -> 빠름. 대부분 사용

페이지가 참조될때마다 참조 비트 1로 set

참조비트가 1인 경우 0으로 set.(-> 한 바퀴 돌때까지 0인 페이지를 못 발견한 경우를 위함)

참조 비트가 0인 페이지를 발견하면 교체.

8.3 페이지 프레임의 할당

1)균등 할당

2) 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 할당.

3) 우선순위 할당(priority allocation): 당장 CPU에서 실행될 프로세스에 더 많은 페이지 프레임 할당.

프로세스별로 최소한으로 필요한 메모리 양, 반복문 여부 등을 고려해야 더 효율적

8.4 전역 교체와 지역 교체

전역 교체: 교체 범위가 메모리 전체

지역 교체: 같은 프로세스 안의 페이지 중에서 교체

8.5 스레싱(thrashing)

page fault가 크게 상승해 CPU 이용률이 떨어지는 현상

MPD(Multi-Programming Degree): 메모리에 동시에 올라간 프로세스의 수

MPD가 낮은 경우 CPU는 더 많은 프로세스를 메모리에 올림.

그런데 너무 많은 프로세스가 올라가면, page fault 증가 -> 디스크 I/O : 시스템은 page fault 처리에 분주, CPU 이용률 감소.

=> 운영체제는 메모리 상의 프로세스가 적다고 판단하고 프로세스를 더 올림. -> page fault 더 증가. 악순환

1) 워킹셋 알고리즘(working-set algorithm)

지역성이 있는 집합(locality set)을 메모리에 동시에 올라갈 수 있도록 하는 알고리즘.

working-set: 프로세스가 일정 시간 동안 원할히 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합.

working-set의 모든 페이지가 메모리에 올라갈 수 있는 경우에만 적재. 아니면 swap out.

workng-set window: delta

working-set: 시각 t에서 시간간격 [t-delta, t] 사이에 참조된 서로 다른 페이지의 집합. 페이지가 참조된 시점으로부터 delta시간 동안은 메모리에 유지되고, 그 시점이 지나면 swap out.

working-set의 크기의 합이 메모리보다 크면 일부 swap out

working-set window의 크기가 중요.

너무 작으면: 지역성 집합 수용 X

너무 크면: MPD감소 -> CPU 이용률 낮아짐.

working-set의 크기는 시간의 흐름에 따라 변함. 동적 프레임 할당의 기능까지 수행.

2) 페이지 부재 빈도 알고리즘(page-fault frquency algorithm)

프로세스별 page fault 비율을 조사해서,

시스템에서 정한 상한보다 높은 경우, 추가 프레임 할당. 추가할 빈 프레임이 없으면 일부 프로세스 swap out

시스템에서 정한 하한보다 작은 경우, 프레임 수를 줄인다.

◆ 32비트 주소 체계 -> 2^32가지의 서로 다른 메모리 주소.

메모리 주소: 바이트 단위로 부여 -> 2^32 바이트의 메모리 공간에 서로 다른 주소를 할당

◆ 4KB(= 2^12 byte)를 하나로 묶음 : page

한 page내에서 주소를 구별하기 위해서는 12bit가 필요. => 32비트 중 하위 12비트는 내부 주소

7.1 주소 바인딩

◆ 논리적 주소(logical address=가상 주소=virtual address): 프로세스의 독자적인 주소공간.

◆ 물리적 주소(physical address): 물리 메모리에 실제 올라가는 위치. 낮은 영역 - 운영체제. 높은 영역 - 사용자 프로세스

◆ 주소 바인딩(address binding): 논리주소를 물리적 메모리 주소로 연결하는 작업

1) 컴파일 타임 바인딩: 컴파일 시점에 물리 메모리의 어느 곳에 위치할지 결정. 비현실적. 잘 사용 X

2) 로드 타임 바인딩: 프로그램이 시작될때 결정. loader에 의해 결정. 컴파일러가 재배치 가능한 코드(reloca-table code)를 생성한 경우만 가능

loader: 사용자프로그램을 메모리에 적재시키는 프로그램.

3) 실행 시간 바인딩(execution time binding, run tmie binding): 프로그램을 실행한 뒤에도 프로그램이 위치한 물리적 메몰 ㅣ상의 주소가 변경될 수 있는 바인딩 방식. CPU가 주소를 참조할때마다 주소 매핑 테이블을 확인. 하드웨어적 지원이 필요(base register, limit register, MMU)

MMU(Memory Management Unit)의 작동 원리

논리주소 = offset from 메모리 시작 주소

논리주소 + 재배치 레지스터(relocation register, 기준 레지스터) -> 물리 주소

프로세스마다 고유한 주소고간을 가지고 있으므로, 같은 논리 주소라도 현재 CPU에서 실행되는 프로세스에 따라 실제 물리 주소는 다름.

MMU는 context swtich 때마다 재배치 레지스터(relocation register)를 프로세스에 알맞게 설정한다.

다중 프로그래밍 환경의 경우, 물리 메모리에 여러 프로세스가 동시에 존재한다. => 프로세스의 메모리 영역을 넘는 곳을 접근할 수 있다. => limit register(한계 레지스터)를 통해 자신의 메모리 영역을 넘는지 확인.

정리

1) CPU가 프로세스의 논리 주소값이 한계 레지스터 값보다 작은지 확인한다.

2) 작다면 논리 주소 + 재배치 레지스터 -> 물리 주소를 구한다.

3) 작지 않다면, 트랩(SW 인터럽트)을 발생시켜 프로세스를 강제종료한다.

7.2 메모리 관리 관련 용어

1) 동적 로딩: 프로세스의 주소공간 전체를 메모리에 올리지 않고 필요할 때마다 루틴 단위로 적재하는 방식. 운영체제의 도움 없이 프로그램 자ㅔ에서 구현 가능. 운영체제가 라이브러리를 통해 지원할 수도 있음.

2) 동적 연결: 컴파일을 통해 생성된 object file과 라이브러리 파일을 연결하는 것을, 프로그램 실행 직전까지 지연시키는 것. 라이브러리 호출시 stub*을 통해 해당 라이브러리가 메모리에 이미 존재하는지 살펴본다. 존재하지 않으면 디스크에서 동적 라이브러리 파일을 찾아 메모리에 적재한 후 수행한다. 여러 프로그램이 공통으로 사용하는 라이브러리를 한 번만 적재하므로 효율적. 운영체제의 지원이 필요하다.

*stub: 동적 연결을 위해서 실행 파일의 라이브러리 호출 부분에 라이브러리 루틴을 찾기 위해 존재하는 작은 코드.

3) 중첩(overlays)

프로세스의 주소 공간을 분할하여 실제 필요한 부분만 적재하는 기법.

동적 로딩과 비슷하나 목적이 다름.

중첩: 프로그램의 크기가 너무 커서 하나의 프로세스조차 메모리에 올리지 못해서 사용

동적 로딩: 다중 프로그래밍 환경에서 메모리 이용률을 향상시키기 위해 그때그때 필요한 부분만 올림.

4) 스왑핑(swapping)

메모리에 올라온 프로세스의 주소 공간 전체를 디스크의 스왑 영역에 일시적으로 내려 놓는 것.

swap area(= 백킹 스토어(backing store): 디스크의 파일 시스템과 별도로 존재하는 일정 영역. 프로세스가 수행중일 때 일시적으로 저장하는 공간. 다수의 사용자 프로세스를 담을 수 있을정도로 충분히 커야함. 일정 접근 속도가 보장되어야함. 특정한 이유로 프로셋를 잠시 내려놓는 것.

swap in: 메모리로 올리기

swap out: 메모리에서 내리기

swapper라고 불리는 중기 스케줄러가 수행.

swapping을 통해 메모리 위의 프로세스 수를 조절할 수 있음. -> 메모리 위의 프로세스에게 충분한 메모리 공간 제공

컴파일 타임 바인딩과 로드 타임 바인딩의 경우 원래의 자리로 돌아가야함.

실행 시간 바인딩의 경우 아무 고간이나 가능.

swapping에 소요되는 시간은 디스크 탐색 시간(seek time)이나 회전 지연 시간(rotational latency)보다는 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송 시간(transfer time)이 대부분.

7.3 물리적 메모리의 할당 방식

운영체제 상주 영역: 인터럽트 벡터 존재. 낮은 주소

사용자 프로세스 영역: 높은 주소

사용자 프로세스 영역의 관리 방법

1) 연속 할당: 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스

분할 방법에 따라

(1)고정 분할 방식

물리 메모리를 영구적 분할로 나누고 각 분할에 하나의 프로세스 적재.

분할의 크기는 모두 같을수도, 다를수도

=> 동시에 올릴 수 있는 프로그램의 수, 수행가능한 프로그램의크기 제한.

외부조각(external fragmenation)*, 내부 조각(internal fragmentation)* 발생

(2)가변 분할 방식

프로그램의 크기를 고려하여 메모리 할당. -> 내부조각 발생 X.

하지만 프로그램이 종료되면 중간에 빈 공간이 발생 -> 외부조각 발생할 수 있음.

동적 메모리 할당 문제(dynamic storage-allocation problem): 프로세스를 메모리에 올릴 때 물리 메모리의 어느 공간에 올릴 것인가?

-1) 최초 적합(first-fit): 들어갈 수 있는 공간 중 가장 앞 주소. 시간측면에서 효율적.

-2) 최적 적합(best-fit): 들어갈 수 있는 가장 작은 가용 공간. 가용공간이 크기 순으로 정렬되지 않은 경우 탐색의 오버헤드. 하지만 작은 외부조각으로 효율적.

-3) 최악 적합(worst-fit): 들어갈 수 있는 가장 큰 가용 공간. 최적 적합과 같이 탐색의 오버헤드. 큰 프로그램이 들어갈 수 있는 공간 소진.

=> 최초/최적 적합 주로 사용

컴팩션(compaction): 사용중인 메모리 영역을 한쪽으로 몰아서 가용 공간을 크게 만드는 것. 현재 수행중인 프로세스를 많이 옮겨야해서 비용이 많이 든다. 주소가 바뀌므로 실시간 바인딩의 경우만 적용 가능하다.

* ◆ 외부조각(external fragmenation): 프로그램의 크기가 분할보다 커서 못 들어감. -> 버려지는 공간. but 더 작은 프로그램은 실행 가능.

* ◆ 내부 조각(internal fragmentation): 프로그램의 크기가 분할보다 작아서 남음. -> 낭비되는 공간

2) 불연속 할당: 하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재. 페이징/세그멘테이션/페이지드 세그멘테이션

7.4 페이징 기법

paging: 프로세스의 주소 공간을 동일한 사이즈의 페이즈 단위로 나누어 물리 메모리를 불연ㅅ옥적으로 저장하는 방식.

프로세스 전체를 올릴 필요가 없으므로 일부는 backing store에 일부는 물리 메모리에 혼재시키는 것이 가능.

물리 메모리를 페이지와 동일한 크기의 frame으로 나눔.  -> 빈 프레임만 있다면 어디든 들어갈 수 있으므로 동적 메모리 할당문제가 발생하지 않음.

페이지마다 논리주소를 물리 주소로 바꾸는 작업이 필요하므로 복잡. : 페이지 테이블.

프로세스가 가질 수 있는 페이지 주소만큼의 엔트리를 갖는다.

논리주소와 물리주소가 같은 크기로 나누어지므로 외부 조각 발생 X. 하지만 프로세스의 크기가 페이지 크기의 배수가 아니므로 내부조각 발생 가능.

1) 주소 변환 기법

페이지 테이블[인덱스] = 기준 주소(base address)

2) 페이지 테이블의 구현

페이지 테이블 기준 레지스터: 페이지 테이블의 위치

페이지 테이블 길이 레지스터: 페이지 테이블의 길이

-> 주소 변환을 위해서는 2번의 메모리 접근이 필요(테이블 위치 확인 + 테이블에서 페이지 주소 확인)

◆ TLB(Translation Look-aside Buffer): 고속 주소 변환용 캐쉬

병렬 탐색*이 가능한 assosciative register 이용.

*병렬 탐색: 한 번에 TLB내의 모든 항목을 동시에 탐색할 수 있는 기능

EAT(Effective memory access time):

메모리에 접근하는 시간을 1, 연관 레지스터에 접근하는 시간 e, 요청된 페이지가 연관 레지스터에 존재할 확률 a:

(1+e)*a + (2+e)(1-a) = 2 + e - a

3) 계층적 페이징

32 bit 컴퓨터 -> 2^32byte(=4GB)의 주소공간을 갖는 프로그램 지원

페이지의 크기가 4KB라면, 4GB/4KB = 1M개의 페이지 테이블 항목 필요.

각 페이지 테이블 항목이 4byte씩 필요하다면 프로세스당 페이지 테이블을 위해 1M * 4byte = 4MB의 크기의 메모리공간이 필요하다.

◆ 2단계 페이지 테이블에서의 비트 구조

최하위 12 비트: 페이지 내에서의 offset

내부 페이지 테이블 자체도 하나의 프레임에 들어가있으므로 4KB이다.

페이지 테이블의 항목의 크기가 4byte이므로 4KB/4B = 1K개의 항목을 갖게 된다.

=> 중간 10 bit: 두번째 페이지 테이블에서의 인덱스를 위한 비트

=> 32-12-10=10bit: 첫번째 페이지 테이블에서의 인덱스를 위한 비트

EAT:

4단계 페이지 테이블에서 메모리 접근시간이 100ns, TLB 접근 시간이 20ns, 페이지 주소 변환 정보가 TLB에 존재할 확률 98%

0.98* (100+20) + 0.02*(100*5 + 20)  = 128 ns

5번의 메모리 접근: 5*100 ns 보다 훨씬 적음.

4) 역페이지 테이블

물리적 메모리의 페이지 프레임 하나당 하나의 항목을 두는 방식.

물리적 주소에 대한 페이지 테이블. 시스템 전체에 페이지 테이블 하나.

각 엔트리는 프로세스 번호, 논리 페이지 번호를 담음.

요청된 주소가 물리 메모리에 존재하는지 전체적으로 탐색해야하므로 비효율적 -> 연관 레지스터를 통해 병렬 탐색 수행.

5) 공유 페이지

공유 코드를 담은 페이지.

공유 코드(=재진입코드, 순수 코드): 여러 프로세스에서 공통으로 사용될 수 있도록 작성된 코드. read-only. 모든 프로세스에서 동일한 논리 주소를 가져야한다.

<-> 사유 페이지(private page)

6) 메모리 보호

보호 비트(protection bit): 읽기/쓰기/읽기전용

유효-무효 비트(valid-invalid bit): valid이면 물리 프레임에 존재. 무효인 경우 스왑 영역에 존재

7.5 세그멘테이션

의미단위로 나누어서 적재 -> 크기가 균일 X

논리적 주소: <세그먼트 번호, 오프셋> 형태

세그먼트 테이블의 각 항목에는 기준점과 한계점 존재. 크기가 다 다르기 때문.

세그먼트 테이블 기준 레지스터(Segment Table Base Register : STBR)

세그먼트 테이블 길이 레지스터(Segment Table Length Register : STLR): 프로세스의 세그먼트 개수

1) 세그먼트 주소가 세그먼트 테이블의 길이보다 작은가?

2) 작으면 한계점과 오프셋 비교

3) 크다면 예외상황 발생

보호비트, 유효비트 존재.

공유 세그먼트 존재.

장점: 페이징에 비해 공유와 보안 측면에서 효율적.

단점: 크기가 일정하지 않으므로 외부조각, 동적 메모리 할당 문제 발생.

7.6 페이지드 세그멘테이션

세그먼트를 동일한 크기의 페이지로 나눔.

외부의 세그멘트 테이블 + 내부의 페이지 테이블 이용.

각 entry는 segment | page index | offset 의 구조로 이루어져있다.

segment에는 page table의 주소가 들어있다.

CPU 스케줄
선점형 : CPU를 빼앗길 수 있다
비선점형 : CPU를 빼앗기지 않는다.
1)FCFS(First Come First Served)
프로세스가 하나씩 끝나므로 평균 대기시간/소요시간은 짧음.
프로세스별로 CPU 버스트/ I/O버스트 시간이 다른 경우 프로세스마다 편차가 심함.
대표적 단점
convoy effect(콘보이 현상): CPU 버스트가 짧은 프로세스가 나중에 도착해서 오랜 시간을 기다려야하는 것.
2.SJF(Shortest-Job First) : CPU 버스트가 짧은 순. 평균 대기시간이 가장 짧음(선점형/비선점형 중 비선점형이 더 짧음)
SRTF(shorted Remaining Time First): 도중에 CPU 버스트가 더 짧은 프로세스가 오면 CPU를 빼앗아서 할당함.
기아(starvation) 현상: CPU 버스트가 짧은 프로세스가 계속 도착하면, CPU 버스트가 긴 프로세스는 계속 처리되지 못함.
CPU 버스트 시간은 실제로 알 수 없으므로, 예측.
T_n+1 = alhpa * t_n + (1-alpha)*T_n
T_n: 예측시간, t_n: 실제 CPU 버스트 시간

3) 우선순위 스케줄링
aging(노화): 대기 시간이 길어지면 우선순위를 조금씩 높임.

4) 라운드 로빈
할당시간이 너무 긺: FCFS와 차이가 없음
할당시간이 너무 짧음: context switch 오버헤드가 크다.
-> 수십 ms: 대화형 프로세스의 대기시간이 너무 길지 않을 정도.
여러 이질적인 프로세스를 처리할때 유용
SJF보다 평균 대기시간은 길지만 응답시간은 짧음.
할당시간 초과: 타이머 인터럽트를 통해 CPU회수
중간 산출물이 없으므로 평균 대기시간/소요시간은 길지만, 응답시간은 짧음.


5) 멀티레벨 큐
준비큐를 여러개로 분할하여 관리하는 스케줄링 기법
성격이 다른 프로세스를 관리하기 위함.
전위 큐 : 빠른 응답이 필요한 대화형 프로세스. 라운드 로빈
후위 큐: 응답 속도가 주요하지 않은 계산 프로세스. FCFS

어떤 큐를 먼저 사용할것인가?
고정 우선순위 방식 : 전위 큐 > 후위 큐
타임 슬라이스 : 전위 큐 80%, 후위 큐 20%. 기아 현상 해결

6) 멀티레벨 피드백 큐
멀티레벨 큐 + 하나의 프로세스가 다른 큐로 이동 가능.
노화(aging) 등 구현 가능

7) 다중처리기 스케줄링(multi-processor scheduling)
CPU가 여러 개인 환경
-1) 대칭형 다중처리: 각 CPU가 알아서 스케줄링 결정
-2) 비대칭형 다중처리 : 하나의 CPU가 스케줄링 담당.

8) 실시간 스케줄링
경성 실시간 시스템(hard real-time system) : 정해진 시간 내에 완료되야하는 시스템
연성 실시간 시스템(soft real-time system) : 데드라인이 존재하지만 지키지 않는다고 위험 상황이 발생하지 않는 시스템
EDF(Earliest Deadline First): 데드라인이 얼마 남지 않은 요청 먼저
연성 실시간 + 일반 작업의 경우: 데드라인이 존재하는 프로세스에 우선순위 할당

5.스케줄링 알고리즘의 평가
큐잉 모델: 확률 분포를 통해 프로세스의 도착률과 CPU의 처리율을 바탕으로 CPU의 처리량(throughput). 프로세스의 평균 대기 시간 계산.
시뮬레이션
구현 및 실측
트레이스(trace): 실제 시스템에서 추출한 CPU 입력값. 몇 초에 어떤 프로세스가 도착하고 CPU 버스트 시간이 얼마이다.