정보처리기사 제3과목 운영체제 – 제3장 기억장치 관리
요약 정리
Ⅰ. 주기억장치 관리 기법
1. 주기억장치(Main Memory) 관리 기법
가. 연속 할당(Continuous Allocation)
파일들을 보조 기억 장치 내의 연속적으로 인접된 장소에 할당하는 것. 사용자는 생성될 파일을 저장하기 위한 장소의 크기를 미리 명시해야 하는데, 만약 원하는 만큼의 기억 공간이 확보되지 못하면 그 파일은 생성되지 못한다. 또한 연속 할당 함으로써 액세스 시간은 줄어드나 파일이 디스크에서 제거된 후에는 단편화(Fragmentation) 문제가 발생할 수 있다.
① 단일 프로그래밍
시스템 내에 항상 하나의 프로세스만 존재하며 현재의 프로세스가 종료된 후에 다른 프로세스가 실행되는 가장 단순한 기법.
② 고정 분할 다중 프로그래밍(Fixed Partition Multi Programming)
주기억장치를 여러 개의 고정된 크기들로 분할하여 실행 중인 여러 프로세스에게 할당하는 기법.
③ 가변 분할 다중 프로그래밍(Dynamic Partition Multi Programming)
프로그램이 적재될 때마다 그 크기에 맞게 주기억장치의 공간을 할당해주는 기법.
나. 불연속 할당(Non-Continuous Allocation) = 가상기억장치(Virtual Memory)
① 페이징(Paging) 기법: 가상기억장치에서 설명.
② 세그먼테이션(Segmentation) 기법: 상동.
2. 주기억장치(Main Memory) 관리 전략
가. 반입 전략(Fetch Strategy) → 언제(When)
주기억장치에 적재할 프로그램이나 데이터를 언제 보조기억장치에서 주기억장치로 가져올 것인가를 결정하는 전략.
- 요구 반입(Demand Fetch) 전략
- 예상 반입(Anticipatory Fetch) 전략
나. 배치 전략(Placement Strategy) → 어디에(Where)
새로 가져오는 프로그램이나 데이터를 주기억장치의 어디에 위치시킬 것인가를 결정하는 전략.
- 최초 적합(First Fit): 입력된 작업을 주기억장치에 적재 시 그 작업을 수용할 수 있는 최초 공백에 배치.
- 최적 적합(Best Fit): 입력된 작업을 주기억장치에 적재 시 단편화(Fragmentation) 공간이 가장 적게 발생하는 공백에 배치.
- 최악 적합(Worst Fit): 입력된 작업을 주기억장치에 적재 시 단편화(Fragmentation) 공간이 가장 크게 발생하는 공백에 배치.
다. 교체 전략(Replacement Strategy) → 무엇을(What)
새로운 프로그램을 배치할 주기억장치의 위치를 정할 때, 주기억장치의 공간이 부족하여 현재 주기억장치에 적재되어 있는 프로그램 중에서 어떤 프로그램이나 데이터를 제거할 것인지를 결정하는 전략.
3. 단편화(Fragmentation)
가. 단편화(Fragmentation)의 정의
주기억장치 상에서 빈번하게 기억 장소가 할당되고 반납됨에 따라 기억 장소들이 조각들로 나뉘어지는 현상.
나. 단편화(Fragmentation)의 종류
- 내부 단편화(Internal Fragmentation): 이미 정해진 크기에 프로그램을 할당하고 남은 기억 공간으로 사용되지 못하는 공간이다.(기억공간 > 작업량)
- 외부 단편화(External Fragmentation): 이미 정해진 크기에 프로그램의 크기가 커서 기억할 수 없게 된 공간이다.(기억공간 < 작업량)
| 분할 크기 | 작업 크기 | 단편화 크기 | 단편화 종류 |
|---|---|---|---|
| 25K | 24K | 1K | 내부 단편화 |
| 15K | 14K | 1K | 내부 단편화 |
| 10K | 12K | 10K | 외부 단편화 |
| 10K | 6K | 4K | 내부 단편화 |
다. 단편화(Fragmentation)의 해결 방안
- 통합(Coalescing): 인접한 기억공간들을 더 큰 하나의 공백으로 만든다.
- 압축(Compaction or Garbage Collection): 서로 떨어져 있는 여러 개의 낭비 공간을 모은다.
4. 기억장치 보호(Storage Protection, Memory Protection)
– 기억장치 보호(Storage Protection) 개념
기억장치로의 접근에 일정한 제한을 두는 것으로, 특히 다중 프로그래밍(Multi Programming) 시스템에서 여러 프로세스가 동시에 수행되면서 자신이 사용하도록 허가 받은 기억장치 영역 외의 다른 곳을 함부로 읽거나 쓰는 것을 방지하는 것을 말한다. 보호를 실현하는 방법은 여러 가지가 있으나 주로 경계 레지스터(Fence Register), 한계 레지스터(Bound Register), 기억장치 보호키(Storage Protection Key)에 의한 방법 및 접근 권한에 의한 방법 등이 있다.
– 기억장치 보호(Storage Protection) 방법
- 베이스 레지스터(Base Register): 주기억장치가 분할된 영역으로 나뉘어 관리될 때, 프로그램이 한 영역에서 다른 영역으로 옮겨지더라도 명령의 주소 부분을 바꾸지 않고 정상적으로 수행될 수 있도록 한다.
- 경계 레지스터(Fence Register): 분할된 영역을 다른 프로그램이 사용하지 못하도록 분할 영역의 주소를 기억한다.
- 한계 레지스터(Bound Register): 사용자 영역에 존재하는 프로그램은 운영체제 영역을 침범하지 못하도록 한다.
- 기억장치 보호키(Storage Protection Key): 세그먼테이션(Segmentation) 기법은 블록의 크기가 가변적이기 때문에 주기억장치에 배치될 때 다른 프로그램과 같이 섞여서 배치되게 된다. 따라서 동일한 프로그램의 세그먼트에 대해서는 구분이 필요한데 이 구분을 하기 위한 키이다.
Ⅱ. 가상기억장치
1. 가상기억장치(Virtual Memory) 관리 기법
가. 페이징(Paging) 기법
– 페이징(Paging) 기법의 개념
블록의 크기가 동일한 고정된 크기로 가상기억장치를 구성하는 방법.
– 페이징(Paging) 기법의 특징
- 페이지 기법은 블록이 고정적이다.
- 페이지 크기가 작을수록 더 많은 페이지 사상(Mapping) 테이블이 존재한다.
- 페이지 크기가 작을수록 내부 단편화(Internal Fragmentation)는 줄어들게 된다.
- 페이지 크기가 작을수록 자주 사용하는 페이지 집합 – 작업 집합(Working Set) – 을 효율적으로 운영할 수 있다.
- 페이지 크기가 작을수록 특정한 참조 지역성만을 포함하기 때문에 기억장치 효율이 좋을 수 있다.
- 페이지 크기가 클수록 페이지 테이블(Page Table)의 크기가 작아지므로 주기억장치의 공간이 절약된다.
- 페이지 크기가 클수록 참조되는 정보와는 무관한 많은 양의 정보가 주기억장치에 남게 된다.
- 페이지 크기가 클수록 페이지 테이블(Page Table)이 복잡하지 않으므로 관리가 용이하다.
- 하나의 페이지 크기가 크면 디스크로부터 I/O 전송에 소모되는 시간은 커지게 된다.
- 페이지 크기가 작으면 입출력 시간은 늘어난다.
- 내부 단편화(Internal Fragmentation)만 발생한다.
– 페이지 주소 변환 기법
- 직접 사상(Direct Mapping): 페이지 사상표(Page Mapping Table)에서 구한 실 주소와 가상주소 상의 변위(d)로 실제 주소를 구함.
- 연관 사상(Associative Mapping): 고속의 연관 메모리에 자주 사용하는 페이지나 현재 적재된 페이지만을 기억시켜 속도를 향상시키는 방법.
- 연관/직접 사상(Set Associative Mapping): 연관 사상과 직접 사상을 같이 사용.
나. 세그먼테이션(Segmentation) 기법
– 세그먼테이션(Segmentation) 기법의 개념
블록의 크기가 다른 가변적인 크기로 가상기억장소를 구성하는 방법.
– 세그먼테이션(Segmentation) 기법의 특징
- 세그먼테이션(Segmentation) 기법은 블록이 가변적이다.
- 프로그램을 세그먼트화(Segmented) 하는 근본적인 이유는 메모리 절약을 위해 사용한다.
- 세그먼테이션(Segmentation) 기법에서는 기억장치 보호키(Storage Protection Key)가 필요하다.
- 외부 단편화(External Fragmentation)만 발생한다.
- 세그먼테이션(Segmentation) 기법에서 빈 공간들이 생기는 현상을 체커 보딩(Checker-Boarding) – 외부 단편화(External Fragmentation) – 이라고 한다.
용어 설명
– 오버레이(Overlay)
하나의 프로그램을 몇 개의 영역으로 분할하여 보조기억장치에 수용하고, 처리의 흐름에 필요한 영역을 주기억장치에 순차적으로 불러내어 실행하는 방식. 각 영역을 호출하는 루트 영역은 늘 주기억장치에 존재한다. 프로그램이 커서 주기억장치에 수용할 수 없을 때 유효한 방법.– 페이지 부재(Page Fault)
가상기억장치 시스템에서, 가상 페이지 주소를 사용하여 데이터를 접근하는 프로그램이 실행될 때, 프로그램에서 접근하려고 하는 페이지가 주기억장치에 있지 않은 경우에 발생하는 현상.– 스와핑(Swapping)
시분할 시스템(Time-Sharing System)에서 현재 진행 중인 프로그램을 시스템의 주기억장치로부터 보조기억장치로 전달하고, 순위가 높은 프로그램으로 대체하는 것. 순위가 높은 프로그램이 수행을 마치면 다시 원래 프로그램으로 환원.– 쓰레싱(Thrashing)
가상기억장치 시스템에서, 프로그램이 접근한 페이지(Page)나 세그먼트를 디스크에서 주기억장치로 올려놓기(Load)를 위한 페이지 부재(Page Fault)가 너무 자주 일어나 프로그램의 처리 속도가 급격히 저하되는 상태. 시스템이 처리할 수 있는 것보다 더 많은 작업을 무리하게 실행시키려 할 때 발생.
2. 가상기억장치(Virtual Memory) 관리 전략
가. 반입 기법(Fetch Strategy)
페이지나 세그먼트를 언제 보조기억장치에서 주기억장치로 옮길 것인가를 결정하는 기법
- 요구 반입 기법(Demand Fetch Strategy)
- 예상 반입 기법(Anticipatory Fetch Sttategy)
나. 배치 기법(Placement Strategy)
페이지나 세그먼트를 주기억장치의 어디로 옮길 것인가를 결정하는 기법.
다. 교체 기법(Replacement Strategy)
주기억장치에 적재되어 있는 페이지 또는 세그먼트들 중에서 어느 것을 교체할 것인가를 결정하는 기법.
① 최적 페이지 교체(OPR, Optimal Page Replacement)
– 최적 페이지 교체(OPR)의 개념
페이지 교체 방법에서 최적의 실행을 얻기 위하여 앞으로 오랫동안 사용되지 않을 페이지를 대치시키는 것으로, 최소의 페이지 부재(Page Fault)율을 갖는 알고리즘.
– 최적 페이지 교체(OPR)의 특징
- 페이지 사용 횟수를 정확히 예측하여 교체하는 방법.
- 앞으로 가장 오랫동안 사용되지 않을 페이지와 교체.
- Belady의 알고리즘으로 가장 이상적이지만 실현 가능성이 희박.
- 페이지 부재(Page Fault) 횟수가 가장 적으므로 Hit율이 가장 큼.
② 선입 선출(FIFO, First Input First Output)
– 선입 선출(FIFO)의 개념
각 페이지가 주기억장치로 들어올 때마다 타임스탬프(Time Stamp)를 찍어 그 시간을 기억하고 있다가 페이지가 교체될 필요가 있을 때 가장 먼저 주기억장치에 들어와 있는 페이지를 교체하는 방법.
– 선입 선출(FIFO)의 특징
- 주기억장치 내에 가장 오래 있던 페이지와 교체.
- 알고리즘이 간단.
- 페이지 교체(Page Replacement)가 가장 많음. 따라서 페이지 부재(Page Fault)가 가장 많이 발생.
- 프로세스(Process)에 할당된 페이지 프레임 수가 증가하면 페이지 부재(Page Fault)가 더 증가하는 모순(Anomaly) 현상이 발생. → Belady 모순.
③ 가장 최근의 사용 횟수 방식(LRU, Latest Recently Used System)
– 가장 최근의 사용 횟수 방식(LRU)의 개념
페이지가 호출되면 페이지 테이블에 복사되어 있는 사용 횟수 레지스터의 값은 가장 최근에 호출된 시간을 나타내므로, 모든 페이지의 사용 횟수 레지스터 값을 탐색하여 가장 적은 값을 가진 페이지와 교체하는 방식.
– 가장 최근의 사용 횟수 방식(LRU)의 특징
- 사용한지 가장 오래된 페이지를 대체 대상으로 선정.
- 현시점에서 가장 오랫동안 사용하지 않은 페이지와 교체.
- 각 페이지마다 계수기를 두어 사용하는 기법.
④ 최소 사용 빈도(LFU, Least Frequently Used)
– 최소 사용 빈도(LFU)의 개념
각 페이지의 사용이 얼마나 집중적으로 되었는가에 관심을 갖고, 가장 적게 사용되거나 집중적이 아닌 페이지로 대체하는 방법.
– 최소 사용 빈도(LFU)의 특징
- 사용한 횟수가 가장 적은 페이지와 교체.
- 사용한 횟수를 기억할 참조 변수를 각 페이지에 두어 사용.
⑤ NUR(Not Used Recently)
– NUR의 개념
적은 오버헤드(Overhead)로 가장 최근의 사용 횟수 방식(LRU)와 유사하며 실제로 자주 쓰이는 기법이다. 근래에 쓰이지 않은 페이지는 가까운 미래에도 쓰이지 않을 가능성이 많기 때문에 이러한 페이지를 호출되는 페이지와 교체하는 방법.
– NUR의 특징
- 최근에 사용하지 않은 페이지와 교체.
- 하드웨어 비트인 참조 비트(Referenced bit)와 변형 비트(Modified bit)를 사용.
- 근래에 쓰이지 않은 페이지들은 가까운 미래에도 쓰이지 않은 가능성이 높음.
⑥ 2차 기회(Second Change)
선입 선출(FIFO)의 변형된 기법으로 가장 오래된 페이지의 참조 비트를 조사하여 그 비트가 ‘0’일 경우는 페이지를 교체시키고, 만약 ‘1’이라면 참조 비트를 ‘0’으로 만든 다음 선입 선출(FIFO) 리스트의 꼬리부분으로 옮겨 놓아 마치 새로운 페이지가 도착한 것처럼 취급하는 기법.
⑦ PFF(Page Fault Frequency)
작업 집합(Working Set)에 존재하는 페이지들을 관찰하여 최근에 자주 사용되고 있지 않은 페이지와 작업 집합(Working Set)에 속하지 않은 페이지 중에서 최근에 자주 사용하는 페이지와 교체하는 기법.
3. 구역성(Locality)
가. 구역성(Locality)의 개념
프로그램이 수행 도중 기억 장치를 참조하는 패턴이 기억 장치의 전 부분에 걸쳐 고루 나타나는 것이 아니라, 어느 순간에는 일정한 한두 곳의 기억 장치 부분에 집중적으로 접근하는 성질. 예를 들면, 순차적인 명령 수행, 루프(Loop), 배열 접근, 스택(Stack) 등에 관련된 프로그램은 구역성(Locality)을 잘 나타낸다. 이에 비해 포인터 참조, 해시표(hash table) 등은 구역성(Locality)이 잘 나타나지 않는 예이다. 구역성(Locality)은 가상 기억 장치나 캐시 기억 장치를 설계하는 데 중요한 역할을 한다.
나. 구역성(Locality)의 종류
- 시간 구역성(Temporal Locality): 먼저 참조된 기억 장소의 일정 부분이 그 후에도 계속 참조될 가능성이 높음을 의미. 루프(Loop), 서브루틴(Subroutine), 스택(Stack) 등.
- 공간 구역성(Spatial Locality): 일단 어느 기억 장소가 참조되면 그 기억 장소 부근이 계속 참조될 가능성이 높음을 의미. 배열 순례(Array Traversal), 순차적 코드, 관련된 변수 등.
4. 작업 집합(Working Set)
자주 참조되는 페이지의 집합으로, 주기억장치에 고정 배치하여 교체 대상에서 제외함으로써 교체 성능을 높이는 방법.
Ⅲ. 보조기억장치
1. 디스크 스케줄링(Disk Scheduling)
가. FCFS(First-Come First-Served)
– 도착 순서에 따라 실행 순서가 고정된다는 점에서 공평하다.
– 요청한 순서대로 진행하기 때문에 순서가 바뀌는 일이 없다.
– 디스크의 부하가 적을 때 유리하다.
– 디스크의 부하가 커지면 응답 시간이 길어진다.
– 탐색 시간(Seek Time)을 최적화하려는 시도가 없다.
예) 대기 큐(Queue): 98, 183, 37, 122, 14, 124, 65, 67.
디스크 헤드(Head)의 위치: 53(단, 가장 안쪽이 1번 트랙 가장 바깥쪽이 200번 트랙으로 가정)
진행 방향: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67.
총 이동량: 638.
나. SSTF(Shortest Seek Time First)
– FCFS의 단점을 보완하기 위한 기법이다.
– 대기 큐(Queue) – 대기열 – 에 먼저 들어와 있지 않더라도 탐색 거리가 짧으면 먼저 서비스 받는다.
– 가운데 트랙(Track)이 안쪽이나 바깥쪽보다 서비스 받을 확률이 높다.
– 헤드(Head)에서 멀리 떨어진 요청은 기아 상태(Starvation State)가 발생할 수 있다.
– FCFS보다 처리량이 많고 평균 응답 시간이 짧다.
– 처리량이 많기 때문에 일괄 처리에는 유용하다.
– 응답 시간의 편차가 크기 때문에 대화형 시스템에는 부적합하다.
예) 대기 큐(Queue): 98, 183, 37, 122, 14, 124, 65, 67.
디스크 헤드(Head)의 위치: 53(단, 가장 안쪽이 1번 트랙 가장 바깥쪽이 200번 트랙으로 가정)
진행 방향: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183.
총 이동량: 236.
다. SCAN
– SSTF의 응답 시간의 편차를 개선한 기법이다.
– 진행 방향 상의 가장 짧은 거리에 있는 요청을 먼저 수행한다.
– 진행 방향으로 끝까지 진행한다.
– SSTF에 발생하는 안쪽과 바깥쪽의 차별 대우를 최소화하고 응답 시간의 편차를 줄인다.
– 대부분의 디스크 스케줄링(Disk Scheduling) 전략의 기본이 된다.
– 부하가 적은 경우에는 SCAN 기법이 가장 좋은 결과를 가진다.
예) 대기 큐(Queue): 98, 183, 37, 122, 14, 124, 65, 67.
디스크 헤드(Head)의 위치: 53(단, 가장 안쪽이 1번 트랙 가장 바깥쪽이 200번 트랙으로 가정)
진행 방향(안쪽): 53 → 37 → 14 → 1 → 65 → 67 → 98 → 122 → 124 → 183.
총 이동량: 235.
라. C-SCAN
– 안쪽과 바깥쪽의 차별 대우를 모두 없앴다.
– 항상 바깥쪽에서 안쪽으로 움직이면서 서비스한다. (단, 반대로는 서비스 하지 않는다)
– 안쪽 방향 끝까지 진행한다.
– 응답 시간의 편차가 매우 작다.
– 부하가 많은 경우에는 C-SCAN 기법이 가장 좋은 결과를 가진다.
예) 대기 큐(Queue): 98, 183, 37, 122, 14, 124, 65, 67.
디스크 헤드(Head)의 위치: 53(단, 가장 안쪽이 1번 트랙 가장 바깥쪽이 200번 트랙으로 가정)
진행 방향: 53 → 37 → 14 → 1 → 200 → 183 → 124 → 122 → 98 → 67 → 65.
총 이동량: 386.
마. LOOK과 C-LOOK
SCAN과 C-SCAN에서 헤드(Head)를 끝까지 이동하지 않는 방법.
바. N-Step SCAN
어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비스하고, 진행 도중 도착한 요청들은 한데 모아져서 다음에 서비스 할 수 있도록 배치된다.
사. 에센바흐 기법(Eshenbach Scheme)
탐색 시간(Seek Time), 회전 지연 시간(Latency Time, Rotational Delay, RPM 지연 시간), 전송 시간(Transmission Time)을 모두 고려해서 개발된 스케줄링.
Ⅳ. 기억장치 계층
1. 기억장치 계층(Memory Hierarchy)의 개념
크기, 속도, 가격당 성능에 따라 분류된 기억장치의 계층. 이 계층은 고속/소형의 반도체 기억장치, 중속(中速)의 디스크 기억장치, 대형/저속의 테이프 기억장치 등으로 구분된다. 또는 캐시(Cache), 주기억장치, 보조기억장치 등으로 구분될 수 있다.
끝.
참고 자료
正益社 – 전산학 개론
한올출판사 – C언어로 구성한 자료구조
가메출판사 – 정보처리기사 필기 7년간 기출문제 총정리
정보통신용어사전