운영체제 8장 Memory Management Stragegies

Chapter 8 Memory Management Strategies

8.1 Background

실행중인 프로그램에 의해 만들어지는 메모리 주소의 sequence만 관심있다. 어떻게 프로그램이 메모리 어드레스를 generate 하는지에 대해서는 관심없음.

 

8.1.1 Basic Hardware

메모리와 CPU의 레지스터만 CPU가 바로 접근할 수 있다. 그러므로 동작을 위해서는 둘 중의 하나에 위치하여야 한다.

레지스터는 CPU안에 있으므로 접근이 매우 빠르지만, 메모리는 메모리 버스를 통하므로 메모리로부터의 데이터를 기다리는 stall라는 것이 생기고 이것은 자원낭비이므로 속도 차를 고려하여 cache라는 메모리 buffer를 둔다.

user프로세스가 OS의 메모리 영역이나 다른 user의 메모리를 접근하는 것을 막아줘야 하는데 여러가지 방법이 있다. 여기서는 한 가지를 소개한다.

base레지스터와 limit레지스터를 가지는데 base는 시작 physical 주소이고 limit는 크기를 나타낸다. 다른 영역을 접근할 경우 trap을 발생시킨다. 이 레지스터들은 OS에서만 접근 가능하고 각 프로세스들이 이들 레지스터를 바꾸는 것을 막는다.

커널모드에서 실행되는 os는 제한 없이 메모리 접근을 할 수 있다.

 

8.1.2 Address Binding

사용중인 memory management에 의존하여 프로세스는 디스크와 메모리사이에서 실행중에 이동될 것이다. 실행을 위해 메모리로 이동되기를 기다리는 디스크에있는 프로세스들은 input queue를 형성한다. 간단하게는 한 프로세스를 선택해서 메모리에 올리고 프로세스가 종료하면 메모리의 공간을 이용가능하도록 한다. 각각의 프로세스의 첫번째 주소는 0000이 될 필요가 없다.

그래서 컴파일러는 각각 프로세스의 symbolic address를 relocatable address로 bind해준다. 그리고 linkage editor나 loader가 relocatable address를 absolute address로 바인드한다.

이 instruction과 데이터가 메모리 어드레스로 바인드 되는 것은 3가지 중에 한 방법으로 발생한다.

(1) Compile time

(2) Load time

(3) Execution time

 

8.1.3 Logical vs Physical address space

CPU는 보통 logical address로 접근한다. 그리고 메모리 유닛에 의해 보여지는 주소는 physical address이다. compile-time/load-time binding은 동일한 물리/가상 주소를 가지지만, execution-time의 경우에는 두 개가 서로 다르다. 가상주소에서 물리주소로의 런타임 맵핑은 MMU에의해 행해진다.

당분간 앞에서 나왔던 base/limit 형태를 쓰기로 하고 base 레지스터를 relocation register라고 한다. 사용자 프로그램은 실제 물리 주소를 절대 보지 못한다.

 

8.1.4 Dynamic Loading

지금까지는 모든 실행되어야 하는 프로세스를 메모리에 다 올렸는데 better memory-space utilization을 위해 이제부터 dynamic loading을 사용한다. 루틴이 호출되면 그때 로드된다. 모든 루틴은 relocatable load format 형태로 디스크에 저장된다. 필요한것만 호출하므로 효율성이 매우 높다. os는 특별한 서포트를 하지 않고 이것은 프로그래머의 설계에 의존한다.

 

8.1.5 Dynamic Linking and Shared Libraries

static linking의 경우에는 시스템 language lib와 다른 모듈들이 하나의 바이너리 이미지로 로더에 의해 결합된다. Dynamic linking은 execution time까지 연기한다. 다이나믹 링킹에서는 stub이 각 라이브러리 루틴 레퍼런스에 들어있다. 스텁이 실행되면 같은 라이브러리가 메모리에 있는지 점검하고 있지 않으면 라이브러리를 메모리에 올린다. 이 방법의 경우에는 메모리에 한 라이브러리만 올라가면 된다. 이러한 시스템을 shared library라고 한다.

 

8.2 Swapping

프로세스는 실행되기 위해 메모리에 있어야 한다 하지만 backing store로 일시적으로 swapped out 되었다가 지속적인 실행을 위해 메모리로 돌아온다. 이상적으로 메모리 매니져는 CPU스케쥴러가 CPU의 리스케쥴을 원할 때 어떠한 프로세스가 메모리에 있어 실행준비가 될수 있도록 가능한 빠르게 프로세스들을 swap해야한다. 이것의 변형이 priority based scheduling algorithm인데 이 것은 roll out, roll in 이라 불린다.

일반적으로 swap out되고 다시 swap in되었을 때 같은 위치로 된다.

swapping은 backing store를 요구하고 주로 fast disk이다. 많은 메모리 이미지들을 가지고 있을 만큼 충분히 커야 하고 시스템은 ready queue를 가지며 메모리의 이미지가 backing store에 있고 실행을 대기중인 프로세스들로 구성된다.

context switch 시간은 꽤 크다. 이 것의 주요 부분은 transfer time이다. 스왑되는 메모리의 양에 비례한다. 간단하게 얼마만큼 사용될지가 아니라 유저 프로세스가 얼마만큼의 양을 사용하는지 정확히 아는 것이 중요하다. 그러면 우리는 필요한 만큼만 스왑하므로 시간을 줄일 수 있다. 이 정보를 관리하기 위해 메모리에 관해서는 system call을 사용하여 os가 메모리 변화를 알 수 있게 한다.

스와핑을 하기 위해서는 완전히 idle해야 한다.

일반적으로 swap space는 디스크의 chunk 단위로 할당되어 빠르게 사용할 수 있다.

8.3 Contiguous Memory Allocation

메모리는 보통 두부분으로 나뉜다: 첫째는 운영체제용, 둘째는 사용자 프로세스들 용이다. os는 low나 high에 존재하고 interrupt vector의 위치에 따라 결정되며 주로 low메모리에 위치한다.

이제 메모리에 들어가기 위해 대기하는 인풋큐의 프로세스들에게 이용 가능한 메모리를 어떻게 할당하는지 고려할 필요가 있다. 연속적인 메모리 할당에서는 각 프로세스는 연속적인 메모리 섹션을 포함한다.

 

8.3.1 Memory mapping and protection

위 기능들은 relocation 레지스터에 의해 가능하다. 가장 작은 physical address 값을 가진다. 각각의 logical address는 limit레지스터보다 작다. MMU는 동적으로 로지컬 어드레스를 매핑시킨다. 컨텍스트 스위치 발생시, 디스패쳐는 relocation과 limit레지스터를 로드한다. 이를 통해 프로텍션을 달성할 수 있다. 이 메커니즘을 이용해 os의 사이즈를 동적으로 변경할 수 있으며 항상 사용되지 않는 os코드를 transient os 코드라고 한다(ex> device driver)

 

8.3.2 Memory Allocation

메모리 할당중 가장 간단한 방법은 메모리를 고정된 크기의 파티션으로 나누어 할당하는 것이다. variable-partition에서는 이용 가능한 메모리에 대한 정보를 유지하고 할당한다. 이용 가능한 메모리의 공간을 hole이라 한다. 프로세스 시작되면 할당받고 종료하면 반납한다. 공간이 흩어져 있어 사용하지 못하는 경우가 있고 반납된 공간이 크면 쪼개거나 합치거나 하는 식으로 하여 효율적으로 사용한다.

이러한 일반적인 경우를 dynamic storage allocation problem이라 한다. 프리 hole의 리스트들에서 size n의 요ㅕ청을 어떻게 만족시킬 것인지에 대한 것이다. 여러가지 솔루션이 있고 first-fit, best-fit, worst-fit이 일반적이다.

-first fit : 할당 가능할 경우 바로 할당. 빠르다

-best fit : 할당 가능하며 가장 작은 경우

-worst fit : 가장 큰 hole. 할당하고 남는 공간이 제일 많다.

first fit이 제일 빠르고 best fit이 공간 효율은 제일 좋다.

 

8.3.3 Fragmentation

external fragmentation은 first-fit과 best-fit의 경우에 많이 발생하는데 전체 공간은 메모리를 할당하기에 충분한 데 연속적이지 않은 공간일 때를 의미한다.

internal fragmentation은 free block이 매우 작아 해당 공간을 관리하는 데에 드는 메모리가 더 클 경우 그냥 블락 단위로 할당해버리는데 그 경우 해당 프로세스는 해당 사이즈 만큼의 internal fragmentation이 생긴다.

해결법 첫 번째는 compaction으로 한 쪽으로 다 몰아버리는 것인데 비용이 많이 든다. relocation이 dynamic일 때만 사용 가능하며 relocation 레지스터의 값을 변경하여 사용한다.

또다른 해결법은 noncontiguous한 메모리 공간을 사용하는 것이다. 그 예로 paging과 segmentation이 있다.

 

8.4 Paging

Paging은 noncontiguous한 프로세스의 공간을 허용하는 메모리 관리 기법이다. external fragmentation을 해결하기 위한 방법이다. 이것은 backing store의 다양한 사이즈의 메모리 chunk들을 맞추는 문제또한 해결했다. 과거에는 주로 하드웨어에 의해 이루어졌으며 요즘에는 하드웨어와 운영체제가 함게 수행한다.

 

8.4.1 Basic Method

Paging은 physical 메모리를 frame단위로 나누고 logical을 page단위로 나눈다. 프로세스가 실행되면 페이지는 그들의 backing store로부터 이용가능한 프레임에 할당된다. backing store는 frame과 같은 크기로 나누어 진다. hardware support로써 page table이 있는데 CPU에서 생성된 모든 주소는 page number(p)와 page offset(d)로 나누어 진다. page number는 page table의 인덱스이다. page table은 각각의 base register주소로 매핑시켜준다.

페이지 사이즈는 하드웨어에 의해 정의되며 2의 제곱수 형태이다. 2의 배수형태로 함으로써 translation이 쉽도록 한다. logical address가 2의 m승 형태이고 page의 사이즈는 2의 n승 형태이면 m-n비트가 페이지 넘버를 구분하는 것이고 나머지 n 비트가 offset이다.

페이징을 사용할 경우 external fragmentation은 없지만 internal이 존재한다. 페이지 사이즈가 고정되어 있어서 꽉 차지 않기 때문인데 이것은 어쩔 수 없다.

프로세스가 실행하게 되어 메모리를 할당받으면 해당 페이지 테이블에 자신의 프레임 넘버가 들어간다.(페이지 테이블은 프로세스마다 있다)

페이징의 중요한 점은 유저가 보는 메모리의 뷰와 실제 physical memory를 완벽하게 분리시켜 준다는 것이다. 이것들을 이어주는 것이 hardware이고 MMU이다. 이렇게 프로세스 단위로 메모리를 관리하고 뷰가 따로 제공되므로 다른 프로세스가 점유하는 프레임을 접근하는 것을 원천적으로 차단할 수 있다.

OS는 별도로 frame table을 가진다. 할당 여부를 확인해야 하기 때문이다.

게다가 OS는 사용자 프로세스가 user space에서 실행하고 모든 로지칼 어드레스가 피지컬 어드레스로 할당된 것을 알아야 한다. 그래서 os는 명령어와 레지스터들을 보관하듯이 각 프로세스의 페이지 테이블의 복사본을 유지한다. 프로세스가 CPU르 할당받아야 할때 dispatcher는 하드웨어 페이지 테이블을 알아야 한다. 그래서 페이징은 context switch시간을 증가시킨다.

 

8.4.2 Hardware support

page table의 하드웨어 구현은 여러가지 방법이 있따.

첫째로 레지스터의 조합으로 구현될 수있다. 좋은 방법이지만, 테이블 엔트리가 많으면 사용하지 못한다. 그래서 page table base register(PTBR)을 사용하여 메모리에 있는 각각의 페이지 테이블의 주소를 레지스터에 보관한다.

이것의 문제는 CPU에서 어느 주소로 접근하려고 할 때 페이지 테이블에 한 번, 실제 주소에 한 번 두번 접근해야 하기 때문에 2배로 속도가 느려진다. 그래서 캐시를 두는데 그것을 Translation Look-aside buffer(TLB)라고 한다. key와 value 값으로 나뉘며 어느 메모리에 접근할 경우 key값을 비교하고 key가 있으면 value를 리턴한다. 이 하드웨어는 빠르지만 비싸다. TLB는 전형적으로 작다. TLB는 몇몇개의 페이지 테이블 엔트리를 가진다.

만약 페이지 넘버가 TLB에 없다면(TLB Miss) 페이지 테이블에 메모리 접근을 해야한다. 메모리 접근 후 TLB에 엔트리를 추가시킨다. 꽉 차있으면 LRU나 Random 알고리즘에 의해 os는 replace를 한다. 그리고 절대 replace가 되지 않는 엔트리를 정할 수도 있으며 wired down되었다고 한다. 보통 커널 코드가 이것으로 설정된다.

어떠한 TLB는 address-space identifiers(ASIDs)를 가진다. 이것은 각각의 프로세스를 식별하고 보호한다. 그리고 ASIDs는 TLB가 여러 메모리를 동시에 엔트리로 가질 수 있게 한다. ASIDs가 없다면, 일반적으로 컨텍스트 스위칭이 일어나면 TLB는 flush된다. 그렇지 않으면 다른 프로세스가 valid하지만 incorrect한 메모리를 접근할 수 있다.

TLB에서 page number가 찾아지는 비율을 hit ratio라고 한다.

 

8.4.3 Protection

메모리 프로텍션은 각각의 프레임들에 대한 프로텍션 비트들에 의해 이루어진다.

첫째로 read/write비트가 있으며 I/O작업을 할 경우 read only로 표시할 수 있다. 잘못된 접근이 이루어졌을 경우 trap이 발생된다.

그리고 valid-invalid비트가 있는데 이것은 해당 어드레스가 해당 프로세스의 logical address인지 나타내 주며 잘못된 접근이 있을 경우 트랩이 발생된다. valid 비트만으로 판단할 경우 사이즈를 넘어가는 경우에 잘못된 접근이 이루어 질 수 있어서 어떠한 시스템들은 page-teable length register(PTLR)를 제공하여 잘못된 접근에 대해 트랩을 발생시킴으로써 프로텍션을 제공한다.

 

8.4.4 Shared Pages

중복 코드가 있을 경우 sharing 하는 것이 가능하다. 그리고 그 코드를 reentrant code(or pure code)라고 한다. re-entrant code는 non-self-modifying code이므로 실행 중에 변하지 않는다. 그러므로 2개 이상의 프로세스가 같은 코드에서 동시에 실행된다. 하지만 data 프레임은 공유하지 않는다. 다른 무거운 프로그램들도 공유될수 있다. 이 메커니즘은 스레드들이 메모리 공유하는 메커니즘과 유사하다. 실제로도 공유 페이지를 어떠한 os들은 shared memory로 구현한다.

 

 

8.5 Structure of the Page Table

8.5.1 Hierachical Paging

페이지 테이블이 너무 커지면 그것 자체로도 크기가 엄청 커지기 때문에 그 경우에는 페이지 테이블을 또 페이지 한다. 이러한 메커니즘을 forward-mapped page table이라고 하며 메모리 주소의 수가 늘어날 경우 level을 더욱 늘릴수도 있다.(ex>64bit CPU).

 

8.5.2 Hashed Page Tables

 

8.5.3 Inverted Page Tables

각각의 프로세스마다 페이지 테이블이 만들어지기 때문에 실제로는 다른 프로세스에서 해당 메모리에 접근하고 있음에도 불구하고 페이지 테이블 엔트리에 데이터를 가지고 있어야 하는 경우가 있다.

그래서 inverted page table을 사용한다. 시스템에 페이지 테이블이 한개만 존재한다. 그리고 각 피지컬 메모리에 하나의 페이지를 가진다. 여기에서는 ASID가 필요하다. ASID는 논리주소가 상응하는 물리주소에 대응되는 것을 보장한다. 이것의 단점은 서치시 걸리는 시간이며 해시를 이용하여 시간을 감소시킨다.

 

 

8.6 Segmentation

8.6.1 Basic Method

Segmentation은 메모리 관리 기법이며 논리 주소 영역은 세그먼트의 집합이다. 각 주소는 세그먼트 이름과 오프셋으로 표현된다. 세그먼트 이름은 숫자로 표현되어 segment-number와 offset으로 표현한다.

 

8.6.2 Hardware

세그멘테이션에서 이차원의 주소형태를 띄지만 이것을 일차원의 물리주소로 표현해야 한다. 이 맵핑은 Segment table에 의해 표현되며 각각 segmentation base와 limit를 가진다. 오프셋이 limit를 넘으면 trap이다.

 

 

<Summary>
CPU에 의해 생성되는 메모리 주소는 적법성을 검사해야 하며 그것은 하드웨어적으로 이루어진다. 다양한 메모리 관리 알고리즘이 많은 측면에서 다르다. 다른 메모리 관리 전략을 비교할 때 우리는 아래의 고려사항들을 사용한다.

-Hardware Support : 1~여러개 파티션 구조에서는 base-limit 레지스터 쌍이 충분하며 address map을 정의하기 위해서는 페이징과 세그멘테이션은 맵핑 테이블을 필요로 한다.

-Performance : 간단한 시스템에서는 빠르고 페이징과 세그멘테이션도 빠르지만 테이블이 메모리에 있게 되면 속도가 저하된다. TLB는 퍼포먼스 감소를 어느정도 막아준다.

-Fragmentation : fixed size에서는 internal fragmentation이 생기며 variable-size에서는 external fragmentation이 생긴다.

-Relocation : external fragmentaiton의 하나의 해결법은 compactoin이다. 프로그램을 쉬프트 시킨다. 이것은 논리 주소가 동적으로 relocate될 것을 요구사항을 ㅗ한다.

-Swapping : 스와핑은 어느 알고리즘에든지 더해질 수 있다. 더 많은 프로세스가 특정 시간에 더 적합하게 실행되도록 한다.

-Sharing : 사용자들간에 코드와 데이터를 공유하여 멀티프로그램이 레벨을 증가시킨다. 페이지나 세그먼트가 공유될수 있다.

-Protection : 페이징이나 세그먼테이셔이 제공되면 다른 섹션은 ex only, read only, read-write 형태로 선언될 수 있다.