[운영체제] 9. 메인 메모리

아래 도서 기반 정리

운영체제 | Abraham Silberschatz - 교보문고

 

목차

• 배경
• 연속 메모리 할당
• 페이징
• 페이지 테이블의 구조
• 스와핑

 

배경

---

메인메모리와 각 처리 코어에 내장된 레지스터들은 CPU가 접근할 수 있는 유일한 범용 저장장치다.
모든 실행되는 명령어와 데이터들은 CPU가 직접적으로 접근 가능한 메인 메모리와 레지스터에 있어야 한다.

기본 하드웨어 (Basic Hadware)

시스템의 올바른 동작을 위해선 사용자 프로그램으로부터 운영체제 영역과 사용자 프로그램 사이를 보호해야 한다.
운영체제가 CPU와 메모리 간의 접근 중에 개입하면 성능이 떨어져, 이런 보호 기법은 반드시 하드웨어가 지원해야 한다.

각 프로세스의 개별적인 메모리 공간을 분리하기 위해 특정 프로세스만 접근할 수 있는 합법적 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만 접근하도록 하는 것이 필요하다.

 

 

• 기준(base) 레지스터 : 가장 작은 합법적인 물리 메모리 주소의 값을 저장한다.
• 상한(limit) 레지스터 : 사용 가능한 영역의 크기를 저장한다.
• 즉, 프로세스가 사용할 수 있는 가장 큰 주소는 base와 limit의 합 만큼이다.
• 사용할 수 있는 주소 범위 외의 주소에 접근하면, 운영체제는 치명적인 오류로 간주하고 트랩(Trap)을 발생시킨다.
• 사용자 프로그램이 운영체제나 다른 사용자 프로그램 코드나 데이터 구조 수정하는 것을 막는다.
• 커널 모드에서 수행되는 운영체제는 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 어떠한 제약도 받지 않는다.

 

주소의 할당 (Address Binding)

운영체제가 프로세스를 실제로 물리 메모리 어디에 적재할지 결정하는 것이다.

원시 프로그램에서 주소는 숫자가 아닌 심볼 형태로 표현된다.
컴파일러는 심볼 주소를 재배치 가능 주소로 바인딩한다.
링커나 로더가 재배치 가능 주소를 절대 주소로 바인딩 시킨다.

주소 할당이 수행되는 시점 크게 3가지

• 컴파일 시간 (compile time) 바인딩
  • 명령어를 컴파일해 실행 파일로 만들 때 주소 결정
  • 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있다면 절대 코드 (absolute code)를 생성할 수 있다.
  • 만일 위치가 변경된다면, 코드는 재컴파일 돼야 한다.
• 적재 시간 (load time) 바인딩
  • 만일 프로세스가 메모리 내 어디로 올라오게 될지 컴파일 시점에 알지 못 하면, 컴파일러는 일단 이진 코드를 재배치 가능 코드(relocatable code)로 만들어야 한다.
  • 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어진다.
  • 이렇게 만들어진 재배치 가능 코드는 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.
• 실행 시간(execution time) 바인딩
  • 명령어 실행하는 순간에 주소 결정
  • 만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다.
  • 우리는 바인딩이 실행 시간까지 허용되었다고 이야기 한다.

 

논리 대 물리 주소 공간 (Logical-Versus Physical-Address Space)

• 논리 주소 (logical address) : CPU가 생성하는 주소
• 물리 주소 (physical address) : 메모리가 취급하게 되는 주소, 메모리 주소 레지스터(MAR)에 주어지는 주소
• 논리 주소 공간 (logical address space) : 모든 논리 주소 집합
• 물리 주소 공간 (physical address space) : 논리 주소와 일치하는 모든 물리 주소 집합

 

가상 주소(virtual address)

컴파일 || 적재 시에 주소를 binding하면 논리 주소와 물리 주소가 같다.
실행 시간 바인딩에서는 논리, 물리 주소가 다르다. 이 경우 논리 주소를 가상 주소(virtual address)라 한다.

 

메모리 관리 장치 (Memory Management Unit, MMU)

논리(가상) 주소를 물리 주소로 바꿔주는 변환(mapping) 작업을 수행하는 하드웨어 장치

 

메모리에 적재할 때 문제점

1. 프로세스 크기가 메모리 크기보다 크면 안 된다.
2. 프로세스가 미리 메모리 전체에 올라가 있는 경우, 메모리에 적재된 코드가 항상 호출되지 않는다.
   -> 효율이 떨어진다.

이러한 문제를 해결하는게 동적 로딩이다.

 

동적 적재 (Dynamic Loading)

필요한 루틴이 호출될 때, 해당 루틴을 메모리에 적재하는 방식이다.

• 루틴 : 프로세스의 실행 단위
• 실행할 코드가 많은 경우 유용하다.
• 전체 프로그램 크기는 클 수 있지만, 사용되는 (적재된) 부분은 훨씬 작을 수 있다.

 

동적 연결 및 공유 라이브러리 (Dynamic Linking & Shared Libraries)

• 동적 연결 라이브러리 (Dynamic Linking Library) : 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리
• 추가
• 정적 연결(static linking) : 실행 파일 만들 때(메모리에 적재할 때), 라이브러리를 포함 시켜 만드는 동적 링킹
  • 동일한 라이브러리를 사용하는 프로세스 여러개가 모두 메모리에 적재되면 메모리 낭비다.
• 동적 연결(dynamic linking) : 프로세스가 메모리에 적재된 이후에, 실제 실행하는 시점에 연결 수행

 

연속 메모리 할당 (Contiguous Memory Allocation)

---

연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다.

 

메모리 보호 (Memory Protection)

CPU에 의해 생성되는 모든 주소는 재배치(기준, base)레지스터와 상한(limit) 레지스터 값을 참조해 확인 작업을 거치기 때문에, 운영체제와 다른 사용자 프로그램을 현재 수행중인 사용자 프로그램의 접근으로부터 보호할 수 있다.

 

메모리 할당 (Memory Allocation)

가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션 (variable-partition)에 할당하는 것이다.
가변 파티션 기법에서 운영체제는 사용 가능한 메모리 부분과 사용중인 부분을 나타내는 테이블을 유지한다.

• hole : 하나의 큰 사용 가능한 메모리 블록
• 처음에는 모든 메모리가 사용자 프로세스에 사용 가능하다.
• 프로세스에 공간이 필요할 때 운영체제는 hole의 집합에서 적절한 것을 찾아내야 한다.

 

동적 메모리 할당

• 최초 적합 (First-fit)
  • 첫 번째 사용 가능한 가용 공간을 할당한다.
  • 검색은 집합의 시작에서 부터 || 지난번 검색이 끝났던 곳에서 시작될 수 있다.
  • 충분히 큰 가용 공간을 찾았을 때 검색을 끝낼 수 있다.
• 최적 적합 (Best-fit)
  • 사용 가능한 공간 중에서 가장 작은 것을 택한다.
  • 리스트가 크기 순으로 되어있지 않다면, 전 리스트를 검색해야 한다.
  • 이 방법은 아주 작은 가용 공간을 만들어 낸다.
• 최악 적합 (Worst-fit)
  • 가장 큰 가용 공간을 택한다.
  • 이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위해 유용하게 사용될 수 있다.
  • 가용 공간이 크기 순으로 정렬되어 있지 않으면, 전 리스트를 다 검색해야 한다.

+ 최초 적합과 최적 적합 모두가 시간과 메모리 이용 효율 측면에서 최악보다 좋다.
+ 최초가 일반적으로 최적보 속도가 더 빠르다. 하지만, 보통 이용률 차이가 많지 않다.

 

외부 단편화 (external fragmentation)

프로세스들이 메모리에 적재되고, 제거되는 일이 반복되면 어떤 가용 공간은 너무 작은 조각이 된다.
이처럼 유휴 공간들을 모두 합치면 충분한 공간이 되만, 그것들이 너무 작은 조각으로 여러 공간에 분산되어 있는 것이다.

 

내부 단편화 (internal fragmentation)

일반적으로 메모리를 아주 작은 공간들로 분할하고, 프로세스가 요청하면 분할된 크기의 정수배로 할당을 해준다.
이 때 할당된 공간은 요구된 공간보다 약간 클 수 있는데 이 두 크기 사이에 남는 부분을 내부 단편화라고 한다.

 

외부 단편화 해결 방법

1. 압축 (Compaction)
   • 메모리 모든 내용을 한 군데로 몰고, 모든 가용 공간을 다른 한군데로 몰아 큰 블록을 만드는 것이다.
   • 항상 가능한 방법은 아니다.
   • 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다.
   • 비용이 많이 든다.
2. 페이징

 

페이징 (Paging)

---

프로그램이 여러 곳에 프레임 단위로 분산되어 저장되는 메모리 관리 기법이다.
프로세스의 물리 주소 공간이 연속되지 않아도 메모리 할당이 가능하다.

기본 방법

• 프레임 (Frame) : 물리 메모리에서 같은 크기의 block으로 나누어진 것을 부르는 명칭
• 페이지 (Page) : 논리 메모리에서 같은 크기의 block으로 나누어진 것을 부르는 명칭

프로세스가 실행 될 때 프로세스의 페이지가 메인 메모리 프레임에 적재되는 방식이다.

CPU에서 나오는 모든 주소는 페이지 번호(p, page number)와 페이지 오프셋(d, page offset)으로 나누어진다.
페이지 번호는 페이지 테이블을 액세스할 때 사용된다.

• 페이지 테이블 (page table) : 물리 메모리의 각 프레임의 시작 주소를 저장하고있다.
• 페이지 오프셋 (page offset) : 참조되는 프레임 안에서의 위치
• 프레임의 시작주소와 오프셋이 결합해 물리 메모리 주소가 된다.

논리 주소를 물리 주소로 변환하기 위해 MMU가 취한 단계

1. 페이지 번호 p를 추출해 페이지 테이블 인덱스로 사용한다.
2. 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.

 

• 페이징 기법 사용시 외부 단편화 문제를 예방할 수 있다.
• 프레임의 정수배로 할당되기 때문에 내부 단편화 문제는 해결할 수 없다.
• page 크기가 작을수록 좋다.
• 그러나 너무 작아지면, 그에 반비례하게 페이지 테이블의 크기가 커지고, 이 테이블이 차지하는 공간은 낭비된다.
• 디스크 입장에선 페이지 크기가 클수록 효율적이다.
• CPU 디스패처가 하드웨어 디스패처 테이블을 설정하는데 사용된다.
  따라서 페이징은 문맥 교환 (context switch) 시간을 늘린다.

 

프레임 할당

1. 프로세스가 실행되기 위해 도착 시, 그 프로세스 크기가 페이지 몇개에 해당하는지 조사한다.
   
   • 한 페이지에 프레임 한 개씩 필요하다.
2. n개의 프레임을 사용할 수 있다면, 이 프레임들은 해당 프로세스에 할당된다.
3. 프로세스의 처음 페이지가 할당된 프레임중 하나에 적재된다.
4. 그 프레임 번호가 페이지 테이블에 기록된다.
5. 다음 페이지는 또 다른 프레임에 적재되고, 그 프레임 전호가 페이지 테이블에 기록되는 과정 반복된다.

• 페이지 테이블을 통하지 않고서는 다른 공간에 접근할 방법이 없다.
• 따라서 사용자 프로세스는 자기의 것이 아닌 메모리는 접근조차 할 수 없다.
• 또 페이지 테이블은 그 프로세스가 소유하고 있는 페이지들만 가리키기 때문이다.

 

프레임 테이블 (Frame Table)

운영체제가 물리 메모리를 관리하기 위한 정보들이 저장된 자료구조다.

• 어떤 프레임이 할당되어 있는지
• 어느 프레임이 사용 가능한지
• 총 프레임이 몇 개나 되는지 등이 저장되어 있다.
• 각 프레임당 하나의 항목을 가지고 있다.
  해당 프레임이 비어있는지, 할당 되었는지, 할당 되었다면 어느 프로세스의 어느 페이지에 할당 되었는지 나타낸다.

 

하드웨어 지원 (Hardware Support)

페이지 테이블의 하드웨어 구현

1. 페이지 테이블을 전용 고속 하드웨어 레지스터 세트로 구현
   • 페이지 주소 변환에 효율적
   • 각 레지스터가 문맥 교환중에 교체되어야 하므로, 문맥 교환시간 증가시킨다.
2. 페이지 테이블 기준 레지스터 (page-table base register, PTBR)
   • 페이지 테이블을 메인 메모리에 저장하고, PTBR이 페이지 테이블을 가리키게 한다.
   • 다른 페이지 테이블을 사용하려면 이 레지스터만을 변화시키면 되고, 따라서 문맥 교환 시간을 줄인다.

 

TLB (Translation Look-aside Buffers)

메인 메모리에 페이지 테이블을 저장하면 context switch 속도는 빨라지지만, 메모리 액세스 시간은 느려질 수 있다.
매번 데이터에 접근하려면 한 번은 PTBR 통해 page table에, 한 번은 페이지 오프셋을 결합해 실제 주소에 접근해야 한다.
두 번의 메모리 액세스가 필요한 것이다. 따라서 메모리 접근 시간이 2배로 느려진다. -> 지연 시간 발생

이는 비효율적이기 때문에 캐시를 사용해 해결한다.
TLB는 참조했던 페이지 번호와 그에 상응하는 프레임을 저장하는 캐시 역할을 한다.
CPU는 page table 보다 TLB를 우선 참조한다.

• CPU가 논리 주소를 생성하면, MMU는 해당 페이지 번호가 TLB에 있는지 확인한다.
• 페이지 번호가 발견되면, 해당 프레임 번호를 즉시 알 수 있고 메모리를 접근하는데 사용된다.

 

보호 (Protection)

메모리 할당이 연속적인 경우 limit 레지스터를 통해 메모리를 보호했다.
페이징은 연속적이지 않기 때문에 다른 방법을 사용한다.

valid / invalid bit

메모리에 대한 모든 접근은 페이지 테이블을 거치기 때문에, 이 때 주소 변환과 함께 이 페이지에 쓰기가 허용되는지 아닌지도 검사할 때 사용하는 비트다.

• valid (유효) : 해당 페이지가 프로세스의 합법적인 페이지임을 나타낸다.
• invalid (무효) : 해당 페이지는 프로세스 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
• 각 페이지에 붙어있는 보호비트에 의해 구현된다.
• 메모리에 대한 모든 접근은 페이지 테이블을 거친다.
  이 때 주소 변환과 함께 해당 페이지에 쓰기 허용 여부를 검사할 수 있다.

 

공유 페이지 (Shared Pages)

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

코드가 재진입 코드(reentrant code)라면 공유가 가능하다.
재진입 코드는 자체 수정을 할 수 없고, 실행 중에는 절대 변하지 않는 코드다.
따라서 여러 프로세스가 동일한 코드를 동시에 실행할 수 있다.

물리 메모리에 하나의 사본만 저장하고, 각 사용자 프로세스의 페이지 테이블은 동일한 물리적 사본으로 매핑시킨다.
따라서 필요한 공간을 절약할 수 있다.

 

페이지 테이블의 구조

---

계층적 페이징 (Hierarchical Paging)

현대 컴퓨터는 매우 큰 주소공간을 가지기 때문에 페이지 테이블도 상당히 커진다.
이 경우 모든 페이지 테이블을 메인 메모리에 연속적으로 할당하기는 어렵다.

2단계 페이징 기법 (two-level paging scheme)을 통해 페이지 테이블 자체를 다시 페이징하여 해결한다.

 

해시 페이지 테이블 (Hashed Page Table)

주소 공간이 32 피트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 사용한다.
해시 페이지 테이블의 각 항목은 연결리스트를 갖는다.
연결리스트의 원소는 가상 페이지 번호, 매핑되는 페이지 프레임 번호, 연결 리스트상의 다음 원소 포인터다.

1. 가상 주소 공간에서 페이지 번호가 오면 그것을 해싱한다.
2. 그것으로 해시 페이지 테이블에서 연결 리스트를 따라가 첫 번재 원소와 가상페이지 원소를 비교한다.
3. 일치하면, 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
   일치하지 않으면, 연결리스트의 다음 원소로 같은 일은 반복한다.

클러스터 페이지 테이블

해시 페이지의 테이블은 각 항목이 한 개의 페이지만 가리키지만, 클러스터 페이지 테이블의 각 항목은 여러개의 페이지를 가리킨다. 따라서 성긴(sparse) 주소 공간에 유용하게 사용된다.

 

역 페이지 테이블 (Inverted Page Tables)

페이징 기법의 단점 중 하나는 각 페이지 테이블 항목의 개수가 수백만개가 될 수 있는것이다.
이러한 테이블은 물리 메모리의 사용을 추적하는데 많은 양의 물리 메모리를 소비한다.

이 문제를 해결하기 위한 방법이 역 페이지 테이블이다.

이러한 방식은 시스템에는 단 하나의 페이지 테이블만이 존재하고, 테이블 내의 각 항목은 메모리 한 프레임씩을 가리키게 된다.

이 방법은 논리 페이지마다 항목을 가지는 대신, 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유한다.

그러나 역 페이지 테이블은 물리 주소에 따라 정렬되어 있고, 탐색은 가상 주소를 기준으로 하므로 테이블 전체를 탐색해야할 수도있다. 따라서 탐색이 오래 걸리게 된다.

+ 공간은 절약하지만, 메모리 접근 시간에선 별로다.

 

스와핑

---

프로세스나 프로세스의 일부분이 실행중에 임시로 백업 저장장치(backing store)로 내보내어 졌다가 실행을 계속하기 위해 다시 메모리로 되돌아오는 방법이다.

(모든 프로세스 물리 주소 공간 크기의 총합) > (시스템의 실제 물리 메모리 크기) 의 경우에 스와핑을 이용하면 동시에 실행하는 것이 가능하다. -> 멀티 프로그래밍 정도를 증가 시킨다.

• swap in : 메모리로 들여보내는 것
• swap out : 디스크로 내보내는 것

• 스와핑의 대부분의 시간은 백업 저장장치에서 I/O하는 시간이다.

 

페이징에서 스와핑

메모리와 백업 저장장치 간에 프로세스 전체를 이동하는데 걸리는 시간이 엄청나기 때문에 최신 운영체제에서는 더는 사용하지 않는다.

대부분의 시스템은 프로세스 전체가 아닌 페이지를 스왑할 수 있는 변형 스와핑을 사용한다.
여전히 물리 메모리를 초과 할당할 수 있지만, 프로세스 전체를 스왑하는 비용은 발생하지 않는다.