8장 Memory-management strategies

Background

CPU는 메인메모리와 레지스터를 통해 명령어와 데이터를 가져온다.
레지스터의 경우엔 한사이클에 가져올 수 있지만 메모리에서 데이터를 가져오려면 여러 사이클이 필요하다.
이 둘의 속도차이를 줄이기 위해 캐쉬가 있다.

각각의 프로세스는 분리된 메모리 공간에 저장된다.
base register와 limit register를 이용해 다른 프로세스 영역에 침입하지 못하게 한다.
이 두 레지스터는 커널이 관리하고 유저모드에서는 변경을 할 수 없다.

Address binding

메모리 주소를 결정할 때 대개 다음과 같은 과정을 거친다.
프로그램 소스는 변수를 이용해 값에 접근 할 수 있다.(symbolic address) 컴파일러를 통해서 이 symbolic address는 relocatable address로 바뀐다. '예를 들면 모듈로 부터 14byte 떨어진 위치에 있다.' 이런식이다. 그리고 linkage editor와 loader는 relocatable address를 absolute address로 바꾼다.

하지만 항상 이 모든 단계를 거치지는 않는다. compile 시간에 메모리 어디에 프로그램이 올라갈 것인지 알수 있다. 하지만 나중에 시작 위치가 바뀌게 되면 재컴파일 해야 된다. 또 다른 경우로 컴파일 시간에 알지 못하면 컴파일러에 의해 relocatable code가 생성되고 메모리로 올라가는 load 시간에 주소가 결정이 된다. 이 때는 시작 위치가 바뀌게 되더라도 변경 된 값을 적용 시켜주면 된다. 그리고 실행 시간에도 프로세스가 변동가능성이 있을 수 있다. 실행 중에 주소가 결정되게 된다.

Logical vs. Physical Address Space

Logical(virtual) address는 cpu가 생성하는 주소이다.
그리고 Physical address는 메모리가 인식하는 주소이다.
실행 중에 주소가 결정될 경우, Virtual address를 Physical address로 바꿔주는 시스템이 필요하다.
이를 memory-management unit( MMU)가 이 일을 한다. CPU가 logical address를 사용하면 MMU의 relocation register가 메모리에 접근할 수 있는 physical address로 바꿔준다.

Dynamic loading

메모리 공간 활용을 잘 하기 위해 사용. 루틴이 실제 호출 될 때까지 디스크에 있는다. 사용될 때, relocatable linking loader가 호출되어 디스크에 있던 루틴을 메모리로 불러들이고 프로그램 주소 테이블을 수정한다.
사용되지 않는 루틴은 절대 호출되지 않아 메모리 공간을 아낄 수 있는 장점이 있다.

Dynamic linking and Shared Libraries

대개 system library에 사용된다.  각 프로그램마다 실행가능한 이미지 만들 때 library가 복사되어 들어간다면 디스크와 메모리 공간을 낭비하는 셈.
stub가 실행가능한 이미지에 library 대신 들어가서 library가 필요할 때, library가 메모리에 없다면 메모리에 불러와주고, 이미 있다면 연결시켜준다. stub는 이러한 일을 할 줄 아는 코드다.
이러한 dynamic linking(실행중 연결)을 통해 프로세스들은 각자의 library를 가질 필요가 없이 library를 공유할 수 있게 된다.

 
Contiguous Allocation

각각의 프로세스가 메모리에서 하나의 연속적인 공간으로 할당되는 것. 

Memory Mapping and Protection

limit register와 relocation register를 이용해서 메모리 매핑과 보호를 한다.
limit register는 logical address의 범위값이고, relocation register는 가장 작은 물리 주소를 가진다.
logical address는 반드시 limit register보다 작아야 한다.
MMU는 relocation register를 통해 동적으로 물리주소로 매핑할 수 있다.

Dynamic Storage-Allocation Problem

여러개 프로세스가 메모리 할당되고 해제되고 하다보면 프로세스 사이에 메모리 공간이 있게 되고 그 공간이 크면 새로운 프로세스를 그 공간에 할당할 수 있다. 작은 공간은 못쓰고 빈 상태로 있다. 운영체제는 할당된 공간과 할당되지 않은 공간에 대한 정보를 가지고 있어야 한다.
빈공간을 활용하여 프로세스를 넣는 방법은 세가지 있다. First-fit, Best-fit, Worst-fit.
First-fit은 처음 발견한 공간이 프로세스를 넣을 만큼 충분하다면 다른 빈공간 안보고 거기다가 넣고
Best-fit은 최대한 아낄려고 모든 빈공간을 다 본 후 가장 알맞은 빈공간에다가 넣고
Worst-fit은 모든 빈공간을 다 보고 가장 큰 공간에다가 넣는 것이다.

Fragmentation

프로세스가 메모리에 계속 들어갔다 나왔다하다 보면 빈공간이 너무 작아 어떤 프로세스라도 들어갈 수 없는 것들이 많이 생기게 된다. 이걸 External Fragmentation이라 하고
Internal Fragmentation은 요청한것보다 약간 크게 할당될 수도 있는데 일부분을 안쓰게 되는 현상이다.
그래서 압축을 하자니 실행중인 프로세스들을 일시중지해야 되므로 현실적으로 어렵다. 그래서 나오게 된것이 Page와 Segmentation 개념이다.

Paging

프로세스가 메모리에 연속적으로 저장되지 않아도 된다. 쪼개져서 저장될 수 있다.
paging의 기본방식은 물리주소공간을 frame단위로 쪼개고, 논리주소공간을 frame과 같은 사이즈로 쪼갠다. 논리주소공간의 쪼개진 조각들은 page라고 한다.
메모리 할당이 고정된(page, frame)단위로 이루어 지므로 external fragmentation이 없다. Internal은 마지막 프레임에서 발생할 수 있다.
대신에 주소 변환과정이 좀 복잡해진다.
page가 어느 frame인지 알려주는 page table이 있어야 한다. 프로세스별로 하나씩 있다.
하드웨어가 페이지방식을 지원. -> CPU가 주소를 생성할 때, page number와 page offset으로 나눠서 생성한다. page number로 frame의 시작 위치를 찾고, offset과 시작 위치를 합쳐서 정확한 메모리 주소를 알수 있다.

페이지 테이블은 레지스터에 저장하면 빠르겠지만 요즘 컴퓨터는 페이지개수가 많기 때문에 메모리에 저장한다. (PCB)
하드웨어는 Page-table base register(PTBR)를 제공해서, 페이지테이블이 빨리 바뀔 수 있게 도와준다.
페이지 테이블 참조하느라 한 바이트 읽는데 메모리를 2번 참조하게 된다. 문제다.
하드웨어는 이 문제에 대해 Translation Look-Aside Buffer(TLB)라는 작은 캐쉬를 제공한다.
TLB에 페이지정보가 있으면 메모리에서 읽어오는 것보다 빨리 물리메모리 주소값을 얻을 수 있다.

Protection
page 환경일 경우 memory protection은 각 프레임의 protection bit를 붙여서 수행한다. bit값들은 page table에 저장된다.
이 bit를 이용해서  vaild/invalid를 설정한다. vaild이면 이 페이지가 프로세스의 logical address임을 의미한다. 따라서 사용하지 않는 logical address일 경우엔 invalid로 설정되어 잘못된 메모리에 접근 하는 것을 막아준다.
대개 많은 프로그램들이 자신에게 할당된 logical address를 다 사용하지 않는다. 그래서 모든 logical address를 포함하는 page table은 공간 낭비가 심하다. 그래서 몇몇 시스템은 하드웨어가 page-table length register(PTLR)을 제공하여 페이지 사이즈를 정하게 된다.

Shared Pages
프로세스들이 공통된 page를 따로 메모리에 로드 시킬 필요없이 서로 공유할 수 있다.
page를 read만 할 거면 공유해도 문제없다.(프로세스의 code부분)

Structure of the Page Table

32bit 주소 공간이면, 
페이지 테이블 사이즈게 엄청 커지게 된다.
페이지 크기가 4KB(2^12)이면 페이지 테이블의 엔트리 수는 2^32/2^12 = 2^20 이고 엔트리 하나당 크기가 4byte면 페이지 엔트리 크기는 4MB. 페이지테이블 사이즈가 크면 메인메모리에 한번에 담기 어렵다.

Hierachical Paging
페이지 테이블을 몇단계로 나눈다. 계층화한다.
outer page table들을 통해 page table에서 물리주소를 알아낸다. 

Hashed Page Tables
주소공간이 32bit보다 클 경우 대개 hash를 사용한다.
논리 주소의 페이지숫자를 hash function에 넣어 나온 해쉬값으로 물리 주소공간의 프레임 위치를 알아낸다.

Inverted Page table
프로세스마다 페이지 테이블이 하나씩 있을 경우, 하나의 페이지 테이블은 자신이 사용하는 물리 메모리 이외에도 사용하지 않는 물리 메모리 정보도 가지고 있으므로 많은 공간을 차지할 수 있다. 이런 문제를 해결하는 방법으로 프레임(실제메모리)을 엔트리로 가지고 있는 페이지 테이블을 사용할 수 있다. 테이블이 하나면 된다. 테이블의 하나의 엔트리에는 <process-id, page-number, offset>으로 이뤄져 있어 cpu가 logical address <pid, p, d>를 보내면 이 페이지 table에서 맞는 <pid, p>를 찾고 이 엔트리는 physical address로 정렬되어 있기 때문에 테이블에서의 위치값이 frame의 번호가 된다.
좋은점은 테이블이 하나면 된다느 것이고 문제점은 찾는데 너무 오래 걸린다는 것이다. 그리고 shared page 구현이 어렵다.

Segmentation

유저 관점에서 본 메모리 매핑 기법.
프로그램을 segment들의 집합으로 본다.
segment는 함수, 스택, symbol table(변수이름, 함수이름) 등 사용자가 프로그램을 봤을 때 나눠지는 것들이다.
paging과 구현방식이 비슷하다.
Logical address는 <segment-number, offset>으로 표현되고
Segment table이 있다. table entry에는 base와 limit가 있다. base를 통해 physical 메모리의 어디에 놓일지 알 수 있고, limit를 통해 segment의 사이즈를 알 수 있다. 메모리에 segment별로 저장이 되며, segment끼리 침범하지 않도록 보호할 수도 있고, 프로그램끼리도 보호할 수 있고, code나 data를 공유할 수도 있고, 다른 프로그램이 segment를 공유할 수도 있다. segment가 다양한 사이즈이다 보니 external flagmentation 가능성이 있다.

Segmentation with Paging 
Segmentation과 paging을 둘다 이용한 메모리 매핑 기법.

참고사이트
http://bywords.tistory.com/70