운영체제 강의노트 정리 - 주기억장치 관리

Operating System

주기억장치 관리

배경

주소 바인딩

프로그래머는 기호 주소를 사용하여 프로그램을 작성한다. 즉, 변수를 선언하고 변수의 이름을 통해 주소에 접근한다.

프로그램은 실행되기 전 이러한 기호 주소를 실제 주소로 바인딩 해주어야 하며, 다음의 시기에 주소가 바인딩된다.

  • 컴파일 시간 : 프로세스가 메모리의 어느 부분에 적재될지 컴파일러가 알고 있다면, 컴파일할 때 주소를 바인딩할 수 있다.
  • 적재load 시간 : 프로세스가 메모리의 어느 부분에 적재될지 컴파일 타임에 알지 못한다면, 컴파일러는 재배치 가능한 코드relocatble code를 생성한다. 이는 기준 위치 주소를 사용하는 코드를 말한다.
  • 실행 시간 : 실행 도중에 프로세스의 적재 위치가 바뀔 수 있다면 바인딩은 실행될 때 이루어진다. 현재 이 방식을 사용한다.

논리 vs. 물리 주소 공간

CPU에 의해 생성되는 주소를 논리적 주소라고 말하며, 주기억 장치가 접하게 되는 주소(MAR에 적재되는 주소)를 물리적 주소라고 말한다.

컴파일 시간 바인딩이나 적재 시간 바인딩에서, 논리적 주소와 물리적 주소는 같다.

실행 시간 바인딩의 경우, 논리적 주소와 물리적 주소가 다르며, 이 때 논리적 주소를 가상 주소virtual address라고 말한다.

프로그램에 의해 참조될 수 있는 모든 논리적 주소를 논리적 주소 공간logical address space라고 말한다.

모든 논리적 주소에 대응되는 모든 물리적 주소를 물리적 주소 공간이라고 말한다.

실행 시간 바인딩에서, 논리적 주소와 물리적 주소의 바인딩은 메모리 관리 장치MMU : Memory-Management Unit에서 이루어진다.

동적 적재

초창기에는 프로그램이 실행되려면 전체 프로그램이 모두 주기억 장치에 적재되어야 했으나, 프로세스의 크기가 물리적 주기억 장치 크기에 의해 제한되는 문제가 있었다.

이를 해결하기 위해 동적 적재dynamic loading 방식을 사용하며, 이는 루틴이 호출될 때 주기억 장치에 적재하는 방식을 말한다.

모든 루틴은 재배치 가능한 코드의 형태로 디스크에 유지되며, 실행 도중에 다른 루틴을 호출해야 한다면 먼저 이 루틴이 주기억 장치에 있는지 확인하고, 없으면 재배치 가능 연결 적재기relocatable linking loader를 사용하여 루틴을 주기억 장치에 적재한다.

이것으로 사용하지 않는 루틴은 주기억 장치에 적재되지 않게 된다.

동적 연결과 공유 라이브러리

정적 연결static linking은 프로그래밍 언어에서 제공하는 라이브러리를 프로그램과 결합하여 사용하는 방식을 말한다.

하지만 모든 프로그램은 라이브러리의 복사본을 가지고 있으므로, 디스크 공간과 주기억 장치 공간 모두 낭비되는 문제가 있다.

동적 연결dynamic linking은 라이브러리와의 연결이 실행 시간까지 연기되는 방식을 말한다.

각 프로그램에 stub가 포함되며, 이는 주기억 장치에 공유되고 있는 라이브러리 루틴에서 프로그램이 필요로 하는 루틴을 찾아주는 적은 양의 코드다.

따라서 어떠한 루틴을 처음 호출할 때만 stub가 필요하며, 그 루틴을 다시 호출하면 주소 정보를 이용하여 바로 호출할 수 있게 된다.

라이브러리 갱신이 용이하며, 여러 버전의 라이브러리를 사용할 수 있으며, 디스크 공간과 주기억 장치 공간을 절약할 수 있다.

다른 주소 공간을 접근해야 하므로 운영체제의 지원을 필요로 한다.

중첩

Overlay. 프로세스의 크기가 프로세스에게 할당된 공간보다 클 수 있게 해준다.

현재 필요한 명령어와 데이터만 주기억 장치에 유지하는 것으로 실현할 수 있다. 현재는 사용하지 않는다.

스와핑

프로세스는 실행 도중에 일시적으로 주기억 장치에서 디스크로 옮겨진 후, 나중에 다시 주기억 장치에 적재되어 실행을 지속할 수 있으며, 이를 스와핑swapping이라고 한다.

컴파일 시간 또는 적재 시간 바인딩을 사용하는 경우, 스왑 아웃 되었다가 스왑 인 되었을 때 같은 물리 주소로 적재되어야 한다. 실행 시간 바인딩의 경우 다른 위치에 적재될 수 있다.

스와핑을 하려면 보조 기억 장치가 필요하다.

현재는 변형된 형태의 스와핑만을 사용한다.

연속적 공간 할당

주기억 장치는 두 영역으로 분할되어, 한 영역은 운영체제가 사용하고, 다른 영역은 사용자 프로세스가 사용한다. 운영체제는 하위 주소에 위치한다.

연속적 공간 할당에서 각 사용자 프로세스는 연속된 단일 영역을 할당받는다.

주기억장치 보호

운영체제를 사용자 프로세스로부터, 사용자 프로세스를 다른 사용자 프로세스로부터 보호해야 한다.

이를 위해 기저base 레지스터와 한계limit 레지스터를 활용한다.

논리적 주소는 기저 레지스터 값과 한계 레지스터 값의 범위에 있을 수 있다. CPU에 의해 생성된 모든 논리 주소는 사용되기 전 범위 내에 있는지 검사한다.

주기억장치 할당

MFTMultiprogramming with Fixed number of Tasks

주기억 장치를 고정된 크기의 영역으로 분할하여 각 영역을 하나의 프로세스에게 할당한다.

다중 프로그래밍의 정도는 분할 영역의 수에 의해 결정된다.

운영체제는 어떤 영역이 사용 가능한지 관리하기 위해 테이블을 사용한다.

현재 이 방식은 사용되지 않는다.

MVTMultiprogramming with Variable number of Tasks

운영체제는 현재 사용되고 있는 공간과 사용되고 있지 않는 공간을 테이블에 관리한다.

처음에는 운영체제가 적재되어 있는 공간을 제외한 모든 공간을 사용할 수 있다.

프로세스가 도착하면 그것을 수용할 수 있는 크기의 홀hole(사용 가능한 영역)을 찾아 할당한다.

프로세스가 실행되기 위해 도착하면 준비 큐에 할당한다.

스케줄링 알고리즘에 따라 프로세스에게 주기억 장치를 할당하며, 더 이상 할당할 공간이 없으면 프로세스는 대기한다.

홀은 주기억 장치 전반에 걸쳐 흩어져 있게 된다. 이는 단편화 문제를 일으킨다.

동적 기억 장치 할당 문제는, 여러 홀이 있을 때 어떤 홀에 프로세스를 할당하는 것이 적합한지 결정하는 것이다.

  • 최초 적합first-fit : 충분히 큰, 첫 번째로 발견한 홀에 할당한다. 검색 순서는 처음부터일 수도 있고, 이전 검색 종료 위치일수도 있다.
  • 최적 적합best-fit : 프로세스를 수용할 수 있는 가장 작은 홀에 할당한다. 홀이 정렬되어 있지 않다면 모든 홀을 검사해야 한다.
  • 최악 적합worst-fit : 가장 큰 홀에 할당한다. 남는 홀이 가장 크게 되므로 해당 홀을 다시 활용할 확률이 높다.

최초 적합과 최적 적합이 공간 사용 효율 및 할당 시간 측면에서 유리하고, 최초 적합은 최적 적합보다 할당 시간 측면에서 유리하다는 것이 알려져 있다.

하지만 세 알고리즘 모두 외부 단편화external fragmentation를 발생시킬 수 있다. 이는 모든 홀을 합하면 프로세스를 수용할 수 있으나 연속 공간이 아니기 때문에 프로세스를 수용할 수 없는 현상을 의미한다.

이를 해결하기 위해 compactation이라는 방법이 알려져 있다. 이는 할당되어 있는 프로세스의 적재 위치를 재배치하여 하나의 큰 홀을 얻는 방법이다.

어떤 프로세스에게 기억 장치 공간을 할당한 후 아주 작은 홀이 남았다면, 이를 현재 할당받는 프로세스에게 할당된 것으로 간주하고 홀로 유지하지 않아 홀에 관한 정보를 유지하는 비용을 줄이는데, 이와 같은 낭비를 내부 단편화internal fragmentation이라고 한다. 프로세스에게 할당되었으나 사용되지 않는 공간을 말한다.

페이징

페이징 기법에서는 프로세스에게 연속된 공간을 할당해주지 않아도 된다.

현재 가장 널리 사용되고 있는 기법이다.

최근 운영체제와 하드웨어를 밀접하게 연관시켜 구현하고 있다.

기본 개념

물리적 기억 장치는 고정된 크기의 프레임frame으로 나누고, 논리적 주소 공간도 프레임과 같은 크기의 페이지page로 나눈다.

프로세스가 실행될 때, 그것의 페이지는 사용 가능한 어떤 프레임에도 할당될 수 있다.

CPU가 생성하는 주소는 페이지 번호와 페이지 오프셋으로 구성되며, 페이지 번호는 프로세스의 페이지 테이블을 참조하는 색인으로 활용되어 페이지가 할당되어 있는 프레임을 알 수 있게 한다. 메모리 상의 실제 주소는 페이지 번호로 구한 프레임 주소와 페이지 오프셋을 더한 것이 된다.

외부 단편화는 발생하지 않지만 내부 단편화는 발생할 수 있다. 프로세스의 마지막 페이지는 프레임 크기보다 작을 수 있다.

내부 단편화를 줄이기 위해 페이지의 크기를 줄일 수 있으나, 이는 유지해야 하는 페이지 테이블의 크기를 크게 하는 결과를 낳는다.

일반적으로 4KB 또는 8KB의 페이지 크기를 사용한다.

사용자 프로그램은 주기억 장치를 하나의 프로그램만 적재되어 있는 하나의 연속적 공간으로 간주하나, 실제로 사용자 프로그램은 페이지 단위로 나뉘어 주기억 장치 상에 흩어져 있게 된다. 이 차이는 주소 번역 하드웨어가 극복해주며, 사용자는 이 사실을 알 필요가 없다.

운영체제는 주기억 장치를 관리하므로 할당에 대한 자세한 내용을 알고 있어야 하므로, 프레임 테이블을 관리한다.

프레임 테이블에는 프레임의 할당 여부, 할당되어 있는 경우 어떤 프로세스의 몇 번째 페이지가 할당되어 있는지를 관리한다.

운영체제는 각 프로세스마다 페이지 테이블을 관리한다. 이는 보통 PCB에 위치하며, 문맥 전환을 할 때 필요하다. 따라서 페이징은 문맥 전환에 소요되는 시간을 증가시킨다.

하드웨어 지원

다음의 방식으로 하드웨어는 페이지 테이블을 구현한다.

  • 전용 레지스터 집합을 사용할 수 있으며, 페이지 테이블이 작은 경우에만 사용할 수 있다.
  • 주기억 장치의 특정 영역에 페이지 테이블을 저장하고, 이를 가리키는 주소만 레지스터(PTBR : Page Table Base Register)에 저장한다.
    • 항상 두 번 접근해야 하므로 접근 속도가 느리다.
  • 전용 캐시를 사용한다.
    • TLB : Translation Look-asdie Buffer
    • 크기가 제한적이며, 비용이 비싸다.
    • TLB는 페이지 테이블의 일부만 가지고 있으며, 캐시처럼 동작하여 TLB를 먼저 탐색한 후 정보가 없으면 주기억 장치에 있는 페이지 테이블을 참조한다.
    • TLB에 있는 어떠한 정보는 제거될 수 없도록 하며, 일반적으로 커널과 관련된 페이지 정보는 TLB에서 제거되지 않는다.

보호

페이징 기법을 사용하는 환경에서, 주기억 장치 보호를 위해 보호 비트를 사용한다.

보호 비트는 페이지 테이블에 유지된다.

이를 이용하여 페이지가 읽기-쓰기를 모두 허용하는지, 읽기 전용인지 나타낼 수 있다.

페이지 테이블의 각 항마다 유효 비트가 붙어있으며, 이 비트가 설정되어 있으면 이에 해당하는 페이지는 프로세스의 논리 주소 공간에 포함됨을 나타낸다.

페이지 테이블 구조

계층 구조 페이징

현재 시스템은 매우 큰 논리 주소 공간(32bit 또는 64bit)을 제공하므로, 페이지 테이블의 크기가 커지게 되고, 이를 연속적 주소 공간에 저장하는 것이 힘들어지게 된다.

이를 해결하기 위해 페이지 테이블도 페이징하는 페이징 기법이 계층 구조 페이징이다.

논리 주소는 (p1, p2, d)의 순서쌍으로 이루어진다.

  • p1은 첫 레벨 페이지 테이블에 대한 색인이다.
  • p2는 두 번째 레벨 페이지 테이블에 대한 색인이다.
  • d는 실제 페이지 내의 오프셋이다.

이럼에도 64bit 논리 주소 공간을 제공하는 시스템에서는 두 단계 페이징 방식으로는 부족하다. 첫 레벨 페이지 테이블에서만 4TB를 필요로 하게 된다.

단계의 깊이를 높여 다단계 페이징 방식을 사용할 수 있으나, 단계가 깊을 수록 주소를 참조하는 데 많은 시간을 소요하게 된다.

해시된 페이지 테이블

해시 테이블hash table의 각 항은, 같은 위치로 해시되는 페이지 번호의 연결 리스트로 구성되며, 각 요소는 다음의 필드로 구성된다.

  • 가상 페이지 번호
  • 페이지 프레임의 값
  • 다음 요소를 가리키는 포인터

주소에 있는 가상 페이지 번호를 해시하여 해당하는 해시 테이블의 위치를 계산한 후, 해당 위치에 있는 연결 리스트를 검색하여 페이지 프레임 값을 얻는다.

다단계 페이징 방식보다는 주소를 참조하는데 소요되는 시간이 적다.

역 페이지 테이블

지금까지의 페이징 기법이 프로세스마다 별도의 페이지 테이블을 사용하며, 이는 프로세스가 사용하는 각 페이지에 대한 항으로 구성되어 있거나, 전체 주소 공간에 대한 항으로 구성되어 있다.

위의 방법은 매우 큰 공간을 필요로 하므로, 역 페이지 테이블 기법으로 이 문제를 해결할 수 있다.

역 페이지 테이블은 주기억 장치의 각 프레임에 대한 항만을 가지고 있으며, 이는 프레임에 저장되어 있는 가상 주소와 이를 사용하는 프로세스 식별자로 구성되어 있다.

각 가상 주소는 프로세스 식별자, 페이지 번호, 오프셋으로 구성되어 있으며, 프로세스 식별자와 페이지 번호를 이용하여 페이지 테이블을 검색한다. 일치하는 항의 위치가 프레임의 위치가 된다.

페이지 테이블을 검색하는 비용이 크며, 이를 극복하기 위해 해시 테이블을 사용할 수 있다.

공유 페이지

페이징 기법은 공통 코드를 공유할 수 있다는 장점이 있다.

여러 사용자가 공통으로 사용하는 메모리 공간에 재진입 코드를 위치시킨다. 이는 자체 수정이 되지 않아야 하며, 코드를 공유하기 위해서는 반드시 재진입 가능해야 한다.

역 페이지 테이블 방식을 사용하면 코드를 공유하기 어려운데, 개별 프로세스의 페이지 테이블을 유지하지 않아 모든 프로세스가 하나의 큰 단일 논리 주소 공간을 사용하기 때문이다.

두 프로세스가 페이지를 공유하기 위해서는 그 페이지에 대한 같은 가상 주소를 사용해야 하므로 공유가 쉽지 않다.

세그먼테이션

기본 방법

사용자들은 주기억 장치를 연속적 선형 공간으로 생각하지 않고, 순서가 없는 다양한 크기의 세그먼트 집합으로 생각한다.

세그먼테이션은 이러한 사용자 관점을 지원해주는 주기억 장치 관리 기법이다.

세그먼테이션에서 논리 주소 공간은 세그먼트의 집합으로 구성되며, 각 세그먼트는 이름과 길이를 갖는다.

사용자는 세그먼트 이름과 오프셋을 이용하여 주소를 지정한다.

컴파일러가 사용자 프로그램을 번역할 때 자동으로 세그먼트를 구성해준다.

하드웨어

세그먼트 주소와 물리 주소 간 매핑을 수행한다.

이 때 세그먼트 테이블을 사용하며, 각 항은 세그먼트의 기저와 한계로 구성되어 있다.

기저에는 세그먼트의 물리 시작 주소, 한계에는 세그먼트의 길이가 기록되어 있다.

보호와 공유

세그먼트는 논리적 구성 단위임과 동시에 물리적 구성 단위다. 따라서 세그먼트는 프로그램의 의미적으로 정의된 일부분이다.

세그먼트는 데이터 부분과 명령어 부분으로 구분될 수 있으며, 명령어 부분은 읽기 전용 또는 실행 전용으로 지정하여 보호할 수 있다.

보호 비트를 각 세그먼트와 연관시켜 세그먼트를 보호할 수 있다.

배열을 하나의 세그먼트로 관리하면 자동으로 배열의 경계를 검사할 수 있다.

페이지와 마찬가지로 코드와 데이터의 공유가 가능하며, 세그먼트 단위로 이루어질 수 있다.

단편화

페이징 기법은 고정된 크기의 페이지를 사용하므로 외부 단편화가 발생하지 않지만, 세그먼트는 가변 길이를 가지므로 외부 단편화가 발생할 수 있다.

페이징과 세그먼테이션의 결합

프로세스가 가질 수 있는 세그먼테이션의 개수와, 각 세그먼트를 페이징하기 위한 페이지 크기를 지정한다.