운영체제 : 3-기억 장치 관리

1장 기억 장치의 계층 구조

레지스터

   ↕

캐시 메모리

   ↕

주기억 장치(Memory)

  ↕

보조 기억 장치(Disk)

 

CPU가 직접 참조하는 기억 장치는 레지스터, 캐시 메모리, 주기억 장치입니다.

보조 기억 장치는 CPU가 직접 참조 하지 않습니다.

 

기억 장치의 사용 용도

1) 가상 기억 장치(Virtual Memory)

프로그램 전체가 주기억 장치에 상주하면서 실행되는 것보다는 느리겠지만 주기억 장치를 효과적으로 사용할 수 있따는 측면에서는 최고의 기술이며 현재 대부분 이러한 방식을 채택하고 있다.

 

2) 가상 디스크(Virtual Disk)

> 보조 기억 장치인 디스크 기술이 발전되기 전에는 주기억 장치의 일부를 디스크 드라이브로 분리하여 디스크처럼 사용하였던 기술이다.

 

3) 인터리빙(Interleaving)

> 주기억 장치의 액세스 속도를 빠르게 하기 위한 기술이다. 기억 장치의 연속된 위치를 서로 다른 뱅크로 구성하여 하나의 주소로 여러 개의 위치에 해당하는 기억 장치를 접근할 수 있또록 하는 방법이다.

> 하나의 장치가 독립적인 기능을 하는 다른 장치의 상태를 검사할 수 있도록 허가하는 기법을 폴링(Polling)이라고한다.

 

4) DMA(Direct Memory Access)

> 중앙 처리 장치(CPU)를 거치지 않고 직접 주기억 장치와 주변 장치 사이에서 데이터를 주고받는 입출력 제어기로, 입출력에 대한 CPU의 부담을 줄이는 동시에 액세스 속도를 향상시킨다.

> DMA는 사이클 스털링(Cycle Stealing) 기법을 사용한다.

 

사이클 스털링(Cycle Stealing)

> 중앙 처리 장치와 입출력 장치가 동시에 주기억 장치에 접근하려고 하는 경우, 입출력 장치에 우선순위를 부여하는 것으로, 적은 양의 사이클을 필요로 하는 채널에 우선순위를 높여주면 입출력 장비의 효율이 높아진다.

 

2장 기억 장치의 관리 기법

주기억 장치 재사용 기술

다중 프로그래밍 방식에서 주기억 장치를 낭비 없이 사용할 수는 없다. 어떤 분할 방식을 사용하든지 단편화는 발생한다.

이처럼 사용할 수 없는 기억 공간을 하나로 모을 수 있도록 주기억 장치 내의 프로그램을 재구성하면 다시 사용할 수 있는 기억 공간이 생기게 될 것이다.

 

통합(Coalescing) :

인접한 공백(기억 공간)들을 더 큰 하나의 공백으로 만드는 과정으로 차폐 레지스터의 값을 변경하여 분할 영역의 크기를 바꾸게 된다.

 

집약(압축, Compaction, Grabage-collection) :

서로 떨어져 있는 여러 개의 낭비 공간을 모아서 하나의 큰 기억 공간을 만드는 과정으로 사용되지 않은 기억 장치를 주기억 장치의 한쪽 끝으로 옮기는 것이다. 압축 후에는 하나의 커다란 공백이 생기게 된다. Windows 운영체제에서 디스크의 조각 모음 같은 것과 같은 의미이다. 디스크에서 집약은 보통 Garbage-collection이라고한다.

 

가상 기억 장치의 사용 방식

> 보조 기억 장치를 주기억 장치처럼 사용하는 것으로, 주기억 장치보다 용량이 큰 프로그램도 처리가 가능하다.

> 프로그램을 여러 개의 작은 볼록 단위로 나누어서 가상 기억 장치에 보관해 놓고 프로그램 실행 시 요구되는 블록만 주기억 장치에 불연속적으로 할당하여 처리한다.

> 사용자 프로그램이 실제 기억 장치보다 커도 수행이 가능하다.

> 주기억 장치의 물리적 공간보다 큰 프로그램이 실행될 수 있다.

> 프로그램 실행 시 주소 변환 작업이 필요하기 떄문에 설계가 복잡해진다.

> 프로그램 크기를 줄이지 않고 순차적으로 수행하는 기법인 오버레이(Overlay) 문제는 자동적으로 해결된다.

> 연속 할당 방식에서의 기억 장치 단편화 문제를 적극적으로 해결할 수 있다.

> 기억 장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있다.

> 프로세스가 갖는 가상 주소 공간상의 연속적인 주소가 실제 기억 장치엣도 연속적일 필요는 없다.

> 가상 기억 장치의 일반적인 구현 방법은 고정 분할 기법(페이징 기법)과 가변 분할 기법(세그멘테이션 기법)이 있다.

 

고정 분할(정적 분할, Page, Paging)

> 주기억 장치와 프로그램의 크기를 고정으로 분할하는데 그 크기가 모두 같다는 것이다.

> 디스크에 존재하는 분할된 프로그램, 즉 페이지와 주기억 장치에 분할된 영역과 페이지가 교체되면서 프로그램이 실행되는데 이러한 기술을 보통 페이지 기법 혹은 페이징(Pasing)이라고 한다.

> 페이지 기법의 기본적인 이점으로는 프로그램의 크기에 제한이 없으며 주기억 장치를 효율적으로 사용할 수 있따는 것이다.

> 외부 단편화는 존재하지 않지만 내부단편화 발생한다. 사용할 프로그램이 10KB이고, 페이지의 크기가 4라면 4KB, 4KB, 2KB가 된다. 2KB는 페이지 크기보다 적으므로 내부 단편화가 발생된다. 보통 페이지의 개수가 10,000개 정도 된다면 프로그램의 마지막 부분에서 한번 발생하기 때문에 내부 단편화의 발생 빈도는 매우 낮다.

> 외부  단편화는 존재하지 않으며 내부 단편화는 최소화 할 수있다.

 

페이지 부재(Page Fault)

> 가상 기억 장치 시스템에서 가상 페이지 주소를 사용하여 데이터를 접근하는 프로그램이 실행될 때, 프로그램에서 접근하려고 하는 페이지가 주기억 장치에 있지 않은 경우 발생하는 현상이다.

 

스래싱(Thrashing)

> 동시에 여러 개의 작업이 수행되는 다중 프로그래밍 시스템 또는 가상 기억 장치를 사용하는 시스템에서 하나의 프로세스가 작업 수행 과정중 지나치게 페이지 부재(Page Fault)가 발생함으로 인하여 전체 시스템의 성능이 저하되는 현상을 말한다. 즉 페이지 교체가 많아지면 페이지 교체만 하다가 실제 프로그램을 제대로 실행하지 못하게되는 현상이다.

 

스레싱 현상의 방지방법

> 다중 프로그래밍의 정도를 낮춘다(동시에 실행되는 프로그램의 수를 줄인다)

> CPU 이용률을 높인다.

> 페이지 부재(Page Fault)율을 조절하여 대처한다.,

> 자주 사용하는 페이지들을 주기억 장치에 미리 갖다 놓는다(Working Set이용).

 

구역성(Locality)

> Denning 교수에 의해 개념이 증명되었다.

> 프로그램이 실행할 때 기억 장치 내의 모든 정보를 균일하게 참조하는 것이 아니라 어느 한 순간에 특정 부문을 집중적으로 참조하는 프로그램의 순차적인 성질이다. 한번 호출된 자료나 명령은 곧바로 다시 사용될 가능성을 말한다.

> 디스크로부터 주기억 장치에 읽어들일 수 있는 블록(물리적인 레코드)의 크기로 여러 개의 페이지를 주기억 장치에 가져올 수 있다. 그중에 한개의 페이지만이 필요하다면 이왕이면 앞으로 사용할 가능성이 높은 페이지들을 같이 읽어들이는 것이 좋다는 것이다.

> 구역성의 종류에는 시간(Temporal) 구역성과 공간(Spatial) 구역성이 있다.

 

구역성의 종류

시간(Temporal) 구역성 :

> 최근에 참조된 기억 장소가 가까운 장래에도 계속 참조될 가능성이 높음을 의미한다.

> 종류 : 반복(Looping), 부 프로그램(Suboutine, 서브루틴), 스택(Stack), 집계(counting, Totaling) 시 사용되는 변수들

 

공간(Spatial) 구역성 :

> 하나의 기억 장소가 참조되면 그 근처의 기억 장소가 계속 참조될 가능성이 높음을 의미한다.

> 종류 : 배열 순회(Array Traversal, 배열순례), 프로그램의 순차적 코드 실행, 프로그램에서 관련된 변수들을 서로 근처에 선언하는 경우

 

작업 집합(Working Set)

> Denning이 제안한 프로그램의 움직임에 관한 모델로 프로세스를 효과적으로 실행하기 위해서는 주기억 장치에 유지되어야 하는 페이지들의 집합을 말한다.

> 자주 참조되는 페이지의 집합은 주기억 장치에 미리 적재해두면 페이지 폴트를 최소화할 수 있고 효율적인 실행이 가능하다.

워킹셋 W(t,w)는 t-w 시간부터 t까지 참조된 page들의 집합으로 표현한다.

즉, 특정 시간의 범위가 있다면 그 시간 동안 참조된 페이지가 워킹셋이며 중복된 것은 하나로 처리하면된다.

예를들어 참조페이지가 1,2,3,5,5,6,3,7,5,6,7,8,9,8,9,8,9 ... 이면

1,2,3 에서의 워킹셋은 {1, 2, 3}

2,3,5,5,6,3,7 에서의 워킹셋은 {2, 3, 5, 6 7} 등 중복X

 

3장 기억장치의 관리 전략

기억장치의 관리 전략의 종류

1) 반입 전략(Strategy) :

> 정의 : 프로그램 / 데이터를 주기억 자잋로 가져오는 시기를 결정하는 전략 -> When

> 종류 : 요구(Demand) 반입, 예상(Anticipatory) 반입

2) 배치 전략(Placement Strategy) : 

> 주기억 장치에 프로그램 / 데이터의 위치를 정하는 전략 -> Where

> 종류 : 최초 적합(First Fit), 최적 접합(Best Fit), 최악 적합(Worst Fit)

3) 교체(재배치) 전략(Replacement Strategy) :

> 정의 : 주기억 장치 내의 빈 공간 확보를 위해 제거할 프로그램/데이터를 선택하는 전략 -> How, What

> 종류 : 최적화(OPT), FIFO(FCFS), LRU, LFU, NUR, Second Chance, PFF

 

배치 전략(Placement Strategy) 

 

1) 최초 적합(First Fit) :

> 입력된 작업을 주기억 장치 내에서 그 작업을 수용할 수 있는 첫 번째 공백에 배치한다.

> 주기억 장치 내의 여러 공백 중 프로세스 배치가 가능한 첫 번쨰 공백을 선택하여 배치한다.

> 주기억 장치의 배치 전략 중 작업의 배치 결정을 가장 빨리 내릴 수 있는 방식이다.

> 내부 단편화의 크기에 상관없이 단편화가 많이 발생한다.

> 초기 결정력이 가장 빠르다.

 

2) 최적 적합(Best Fit) : 

> 입력된 작업을 주기억 장치 내의 공백 중에서 그 작업에 가장 잘 맞는 공백에 배치시킨다.

> 주기억 장치 내의 여러 공백에 대해서 프로세스 크기를 차감하여 그 결과값이 가장 작은 공백에 프로세스를 배치한다.

> 내부 단편화가 가장 적게 발생한다.

> 검색 시간이 길어 결정력이 가장 느리다.

 

3) 최악 적합(Worst Fit) :

> 입력된 작업을 주기억 장치 내에서 가장 잘 맞지 않는 공백, 즉 가장 큰 공백에 배치한다.

> 내부 단편화가 가장 크게 생긴 공간에 배치한다.

> 주기억 장치 내의 여러 공백 각각에 대해서 프로세스 크기를 차감하여 그 결과값이 가장 큰 공백에 프로세스를 배치한다.

 

FIFO(First Input FIrst OutPut) : 

주기억 장치에 들어와 있는 페이지에 타임 스탬프를 찍어 그 시간을 기억하고 있다가 가장 먼저 들어와 있던 페이지를 교체하는 방법이다.

> 주기억 장치 내에 가장 오래된 페이지와 교체한다.

> 알고리즘이 가장 간단하다.

> Page 교체가 가장 많다(Page Fault가 가장 많이 발생한다).

> 프로세스에 할당된 페이지 프레임 수가 증가하면 페이지 부재의 수가 감소하는 것이 당연하지만 페이지 프레임 수가 증가할 때, 현실적으로 페이지 부재가 더 증가하는 모순(Anomaly) 현상이 발생한다(Belady 모순).

 

LRU(Least Recently Used) :

> 참조된지 가장 오래된 페이지를 대체 대상으로 선정한다.

> 현시점에서 가장 오랫동안 사용하지 않은 페이지와 교체한다.

> 각 페이지마다 계수기(시간 기억 영역)를 두어 사용하는 기법이다.

 

NUR(Not Used Recently) :

페이지당 두 개의 정보 비트(참조 비트, 변형 비트)를 이용하여 교체하는 방법이다.

> 최근에 사용(참조)하지 않은 페이지를 제거한다.

> 하드웨어 비트 - 참조 비트(Refernced Bit)와 변형 비트(Modified Bit)를 사용한다.

 

4장 디스크 관리

디스크 스케줄링의 전략과 목적 :

> 처리량을 최대화한다.

> 응답 시간을 최소화한다.

> 응답 시간의 편차를 최소화한다.

 

디스크 스케줄링 종류 및 특징

1) FCFS(First Come First Served, FIFO)

가장 간단한 스케줄링 형태로 대기 큐에 들어온 작업에 CPU를 할당하는 기법이다 (I/O 요청 순으로 대기 큐에 기억시킨다).

> 도착 순서에 따라 실행 순서가 고정된다는 점에서 공평하다.

> 요청한 순서대로 진행하기 때문에 순서가 바뀌는 일이 없다.

> 디스크의 부하가 적을 때 유리하다.

> 디스크의 부하가 커지면 응답 시간이 길어진다.

> 탐색 시간(Seek Time)을 최적화하려는 시도가 없다.

 

2) SSTF(Shortest Seek Time First) :

현재의 헤드 위치에서 가장 가까운 입출력 요청을 먼저 서비스한다. 즉, 헤드의 탐색 거리 (Seek Distance)가 가장 짧은 요청을 먼저 서비스하게 된다.

> 현재 헤드 위치에서 가장 짧은 탐색 거리의 요청을 먼저 서비스한다.

> 가운데 트랙이 안쪽이나 바깥쪽보다 서비스받을 확률이 높다.

> 헤드에서 멀리 떨어진 요청은 기아 상태(Staravation State)가 발생할 수 있다.

> FCFS보다 처리량이 많고 평균 응답 시간이 짧다.

> 처리량이 많기 때문에 일괄 처리에 유용하다.

> 응답 시간의 편차가 크기 때문에 대화형 시스템에는 부적합하다.

 

3) SCAN :

SSTF의 문제점인 응답 시간의 편차를 극복하기 위해 Denning이 개발한 방법으로 헤드가 디스크 표면을 양방향(안쪽/바깥쪽)으로 이동하면서 I/O 요청을 서비스한다. 이 때, 헤드는 이동하는 방향의 앞쪽에 I/O 요청이 없을 경우에만 후퇴가 가능하다. 진행 방향이 정해지면 같은 방향에 있는 가장 짧은 탐색 시간을 갖는 요청을 우선 서비스하게 된다.

> SSTF의 문제점인 응답 시간의 편차를 개선하는 기법이다.

> 진행 방향상의 가장 짧은 거리에 있는 요청을 먼저 수행한다.

> 진행 방향으로 끝까지 간다.

> SSTF에 발생하는 안쪽과 바깥쪽의 차별 대우를 최소화하고 응답 시간의 편차를 줄인다.

> 대부분의 디스크 스케줄링 전략의 기본이 된다.

> 부하가 적은 경우에는 SCAN 기법이 가장 좋은 결과를 가진다.

 

4) C-SCAN :

SCAN의 문제점인 안쪽과 바깥쪽의 차별 대우를 모두 없애기 위해 항상 바깥쪽 실린더(트랙)에서 안쪽으로 움직이면서 가장 짧은 탐색 시간을 가진 요청을 우선 서비스한다. 헤드는 트랙의 안쪽으로 한방향으로만 움직이며 안쪽에 더 이상 I/O 요청이 없으면 다시 바깥쪽에서 안쪽으로 이동하면서 I/O 요청을 서비스하게된다.

> 안쪽과 바깥쪽의 차별 대우를 모두 없앴다.

> 항상 바깥쪽에서 안쪽으로 움직이면서 서비스한다(반대는 서비스하지 않는다).

> 안쪽 방향으로 끝가지 진행한다.

> 응답 시간의 편차가 매우작다.

> 부하가 많은 경우에는 C-SCAN 기법이 가장 좋은 결과를 가진다.