어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비스하고

#159_단일 분할 할당 기법

- 주기억장치를 운영체제 영역과 사용자 영역으로 나누어 한 순간에는 오직 한명의 사용자만이 주기억장치의 사용자 영역을 사용하는 기법

- 오버레이(Overlay) 기법 : 주기억장치보다 큰 사용자 프로그램을 실행하기 위한 기법으로, 보조기억장치에 저장된 하나의 프로그램을 여러 개의 조각으로 분할한 후 필요한 조각을 차례로 주기억장치에 적재하여 프로그램을 실행함

- 스와핑(Swapping) 기법 : 하나의 프로그램 전체를 주기억장치에 할당하여 사용하다 필요에 따라 다른 프로그램으로 교체하는 기법

#160_다중 분할 할당 기법

- 고정 분할 할당 : 프로그램을 할당하기 전에 운영체제가 주기억장치의 사용자 영역을 여러 개의 고정된 크기로 분할하고, 준비상태 큐에서 준비 중인 프로그램을 각 영역에 할당하여 수행하는 기법

- 가변 분할 할당 : 고정 분할 할당 기법의 단편화를 줄이기 위한 것으로, 미리 주기억장치를 분할해 놓은 것이 아니라 프로그램을 주기억장치에 적재하면서 필요한 만큼의 크기로 영역을 분할하는 기법

#161_단편화(Fragmentation)

- 분할된 주기억장치에 프로그램을 할당하고 반납하는 과정을 반복하면서 사용되지 않고 남는 기억장치의 빈 공간 조각

- 내부(internal) 단편화 : 분할된 영역이 할당될 프로그램의 크기보다 크기 때문에 프로그램이 할당된 후 사용되지 않고 남아 있는 빈 공간

- 외부(External) 단편화 : 분할된 영역이 할당될 프로그램의 크기보다 작기 때문에 프로그램이 할당될 수 없어 사용되지 않고 빈 공간으로 남아 있는 분할된 전체 영역

#162_단편화 해결 방법

- 통합(Coalescing) 기법 : 주기억장치 내에 인접해 있는 단편화된 공간을 하나의 공간으로 통합하는 작업

- 압축(Compaction) 기법, 집약 : 주기억장치 내에 분산되어 있는 단편화된 빈 공간을 결합하여 하느이 큰 가용 공간을 만드는 작업으로, 여러 위치에 분산된 단편화된 빈 공간을 주기억장치의 한쪽 끝느오 옮겨서 큰 기억공간을 만듬

#163_가상기억장치 구현 기법

- 페이징(Paging) 기법

ㆍ가상기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램(페이지)을 동일하게 나눠진 주기억장치의 영역(페이지 프레임)에 적재시켜 실행하는 기법

ㆍ외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있음

- 세그먼테이션(Segmentation) 기법

ㆍ가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행시키는 방법

ㆍ프로그램을 배열이나 함수 등과 같은 논리적인 크기로 나눈 단위를 세그먼트라고 하며, 각 세그먼트는 고유한 이름과 크기를 갖고 있음

ㆍ다른 세그먼트에게 할당된 영역을 침범할 수 없으며, 이를 위해 기억장치 보호키(Storage Protection Key)가 필요함

#164_페이지 교체 알고리즘

- OPT(Optimal Replacement, 최적 교체)

ㆍ앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법

ㆍ각 페이지의 호출 순서와 참조 상황을 미리 예측해야하므로 실현 가능성이 희박함

- FIFO(First in First Out)

ㆍ각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

ㆍ이해하기 쉽고, 프로그래밍 및 설계가 간단하며, 벨레이디의 모순(Belady's Anomaly) 현상이 발생함

- LRU(Least Recently Used)

ㆍ최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

ㆍ각 페이지마다 계수기나 스택을 두어 현 시점에서 가장 오랫동안 사용하지 않은 즉, 가장 오래전에 사용된 페이지를 교체함

- LFU(Least Frequently Used)

ㆍ사용 빈도가 가장 적은 페이지를 교체하는 기법

ㆍ프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우에도 프레임을 계속 차치할 수 있음

- NUR(Not Used Recently)

ㆍ최근에 사용하지 않은 페이지를 교체하는 기법

ㆍ최근의 사용 여부를 확인하기 위해서 각 페이지마다 참조 비트(Reference Bit)와 변형 비트(Modified Bit)가 사용됨

- SCR(Second Chance Replacement)

ㆍ가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법을 단점을 보완하는 기법

#165_페이지 크기

- 페이지가 작을 경우

ㆍ페이지의 단편화가 감소되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 줄어듬

ㆍ프로세스(프로그램) 수행에 필요한 내용만 주기억장치에 적재할 수 있고, 국부성(Locality)에 더 일치할 수 있기 때문에 기억장치 효율이 높아짐

ㆍ페이지 정보를 갖는 페이지 맵 테이블의 크기가 커지고, 맵핑 속도가 늦어짐

ㆍ디스크 접근 횟수가 많아져서 전체적인 입/출력 시간은 늘어남

- 페이지가 클 경우

ㆍ페이지 정보를 갖는 맵 테이블의 크기가 작아지고, 맵핑 속도가 짧아짐

ㆍ디스크 접그 횟수가 줄어들어 전체적인 입/출력의 효율성이 증가됨

ㆍ페이지의 단편화가 증가되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 늘어남

ㆍ프로그램 수행에 불필요한 내용까지도 주기억장치에 적재될 수 있음

#166_국부성(Locality, 구역성)

- 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론

- 스레싱을 방지하기 위한 워킹 셋 이론의 기반이 됨

- 프로세스가 집중적으로 사용하는 페이지를 알아내는 방법 중 하나로, 가상 기억장치 관리의 이론적인 근거가 됨

- Locality 종류

시간 구역성 (Temporal Locality)	ㆍ프로세스가 실행되면서 하나의 페이지를 일정 시간 동안 집중적으로 액세스하는 현상 ㆍ시간 구역성이 이루어지는 기억장소 : Loop(반복, 순환), 스택(Stack), 부프로그램(Sub Routine), Counting(1씩 증감), Totaling(집계)에 사용되는 변수(기억 장소)
공간 구역성 (Spatial Locality)	ㆍ프로세스 실행시 일정 위치의 페이지를 집중적으로 액세스하는 현상 ㆍ공간 구역성이 이루어지는 기억 장소 : 배열 순회, 순차적 코드의 실행, 프로그래머들이 관련된 변수(데이터를 저장할 기억장소)들을 서로 근처에 선언하여 할당되는 기억장소, 같은 영역에 있는 변수를 참조할 때 사용

#167_워킹 셋/페이지 부재 빈도

- 워킹 셋(Working Set) : 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합으로, 자주 참조되는 워킹 셋을 주기억장치에 상주시킴으로써 페이지 부재 및 페이지 교체 현상을 줄임

- 페이지 부재 빈도(PFF, Page Fault Frequecy) : 페이지 부재가 일어나는 횟수

- 페이지 부재 빈도 방식 : 페이지 부재율(Page Fault Rate)에 따라 주기억장치에 있는 페이지 ㅡ레임의 수를 늘리거나 줄여 페이지 부재율을 적정 수준으로 유지하는 방식

#168_스레싱(Thrashing)

- 프로세스의 처리 시간보다 페이지 교체 시간이 더 많아지는 현상

- 다중 프로그래밍 시스템이나 가상기억장치를 사용하는 시스템에서 하나의 프로세스 수행 과정 중 자주 페이지 부재가 발생함으로 인해 나타나는 현상으로 전체 시스템의 성능이 저하됨

- 다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 특정시점까지는 높아지지만 다중 프로그래밍 정도가 더욱 커지면 스레싱이 나타나고, CPU의 이용률은 급격히 떨어짐

- CPU의 이용률을 높이고, 스레싱 현상을 방지하려면 다중 프로그래밍의 정도를 적정 수준으로 유지하고, 페이지 부재 빈도를 조절하여 사용하며, 워킹 셋을 유지해야 함

#169_디스크 스케줄링

- FCFS(First-Come First-Service)

ㆍ가장 간단한 스케줄링으로, 디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 기법