Logical address(= virtual memory)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소는 logical address임 => 실행파일 안의 코드는 동일하기 때문에 CPU는 logical address를 봐야할 필요가 있음

Physical address

• 메모리에 실제 올라가는 위치

---

address binding(주소 변환)

• 가상 메모리의 논리적 주소를 메인 메모리의 물리적 주소로 변환하는 것
• 주소 변환은 OS가 관여하는게 아니라 HW적으로 이루어짐
• Symbolic Address -> Logical Address -(이 시점이 언제인가)-> Physical Address
  *Symbolic Adress: 프로그래머가 메모리의 번지 수를 언급하는게 아니라 숫자가 아닌, 이름같은 symbol을 사용해서 메모리에 접근하는데 이를 Symbolic Address라고 함

주소 바인딩의 종류

• Logical Address -> Physical Address가 언제 이뤄지냐에 따라 크게 3가지로 나눠질 수 있음

1. Complie time binding
   • 물리적 메모리 주소가 컴파일 시점에 알려짐
   • 시작 위치 변경시 재컴파일
   • 컴파일러는 절대 코드(absolute address) 생성 => 한번 올라간 메모리 위치는 바꿀 수 없음
2. Load time binding
   • Loader의 책임하에 물리적 메모리 주소를 부여함
   • 컴파일러가 재배치 가능 코드(relocateable code)를 생성한 경우에 가능 => 비어있는 주소면 어디든지 올릴 수 있음
3. Execution time binding (= Run time binding)
   • compile time binding, load time binding 은 이미 메모리에 올라간 주소는 변경할 수 없지만 execution time binding 은 실행중에도 바꿀 수 있음
   • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
   • CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
   • H/W 적인 지원이 필요함 (e.g base and limit registers, MMU)

MMU(Memory-Management Unit)

• logical address를 physical address로 매핑해주는 H/W device
  • MMU는 cpu로부터 logical address를 받으면 메모리의 TTB(Translation Table Base address) 를 통해 Page table에 접근하게 된다.
• base register(= relocation register)와 limit register(프로그램의 크기)를 이용해서 주소를 변환한다
  • base register: 물리적 주소의 최솟값
  • limit register: 논리적 주소의 범위
  • e.g) CPU로부터 p1의 346번지 logical address를 요청하면, MMU는 14000(base)+346(logical)=14346(physical)로 매핑해준다
  • limit를 넘어가는 요청이 들어오면 trap 이 걸리고, 프로그램의 CPU가 OS로 넘어가서 이를 검사함
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되면서 생성해내는 모든 주소값에 대해서 base register(= relocation register)의 값을 더함
• user program
  • logical address만을 다룬다
  • 실제 physical address를 볼 수 없으며 알 필요도 없다

주소 변환의 용어

주소 변환의 용어에는 크게 4가지가 있다.

• Dynamic Loading: 프로세스 전체를 메모리에 미리 다 올리는게 아니라 해당 루틴이 불려질 때마다 메모리에 load하는 것
  • memory utilization이 향상됨
  • 가끔식 사용되는 많은 양의 코드인 경우에 유용햠 (e.g 오류 처리 루틴)
  • OS의 특별한 지원 없이 프로그램 자체에서 구현이 가능, OS가 라이브러리를 지원함(= 프로그래머가 직접 사용하는 방식)
• Dynamic Linking: linking을 실행시간까지 미루는 기법
  • linking: 컴파일된 소스파일들을 하나로 묶어서 실행파일로 만드는 것
  • Static linking
    • 라이브러리가 프로그램 실행 파일 코드에 포함됨
    • 실행 파일 크기가 커짐/ 동일한 라이브러리를 각각의 프로세스가 자신의 메모리 주소 공간에 올리기 때문에 메모리가 낭비됨
  • Dynamic linking
    • 라이브러리가 실행시에 연결됨
    • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 일종의 포인터인 stub이라는 작은 코드를 둠 (= 실행 파일 코드에 포함되지 않음)
    • 라이브러리가 이미 메모리에 있으면 그 루틴 주소로 가고 없으면 디스크에서 읽어옴
    • OS의 도움이 필요
• Overlays: 메모리에 프로세스의 부분 중 실제로 필요한 부분만을 올리는 것
  • 프로세스 크기가 메모리보다 클 때 유용함
  • OS 지원없이 사용자에 의해서 구현
  • OS가 라이브러리를 지원하지 않는다는 점에서 Dynamic loading과 차이가 있음
  • 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현함 (=> 'Manual Overlay' 프로그래밍이 매우 복잡함)
• Swapping: 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
  • backing store(=swap area): 디스크를 말함, 많은 사용자가 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
  • Swap in/Swap out: 일반적으로 중기 스케줄러(swapper)에 의해서 swap out 시킬 프로세스 선정
    • compile time 혹은 load time binding 에서는 원래 메모리 위치로 swap in 해야 함
    • execution time binding 에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
    • swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임 => swapping의 경우 file I/O와 다르게 양이 굉장히 방대함. 양이 워낙 많기 때문에 전송에 들어가는 시간이 상당히 많음.

---

물리적 메모리의 할당

• 메모리는 일반적으로 두 영역으로 나뉘어서 사용됨
  • OS 상주 영역
  • 사용자 프로세스 영역
• 사용자 프로세스 영역의 할당 방법은 크게 두 가지가 있음
  • 1. contiguous allocation(연속적 할당)
    • 각각의 프로세스가 메모리의 연속적인 공간에 적재됨
    • Fixed partition allocation 과 Vairable partition allocation이 있음
  • 2. Noncontiguous allocation(불연속적 할당)
    • 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감
    • paging, segmentation, paged segmentaion 이 있음

---

Contiguous Allocation (연속적 할당)

프로세스를 메모리의 주소 공간에 연속적으로 할당하는 방식에는 크게 고정 분할 방식과 가변 분할 방식이 있음

고정 분할 방식

• 외부 조각(= 외부 단편화): partition이 작아서 프로그램이 올라가지 못해 생기는 메모리 낭비 공간
• 내부 조각(= 내부 단편화): partition이 커서 프로그램이 올라가도 사용되지 않아 생기는 메모리 낭비 공간
• 물리적 메모리를 몇 개의 영구적 분할(partition)으로 나눔
• partition의 크기가 모두 동일한 방식과 서로 다른 방식이 존재함
• partition당 하나의 프로그램 적재
• 융통성 없음
  • 동시에 메모리에 load되는 프로그램 수가 고정됨
  • 최대 수행 가능 프로그램 크기가 제한됨
  • internal fragmentation 발생 (external fragmentation도 발생)

가변 분할 방식

• 연속적으로 할당하다 보니 프로세스의 순서에 따라서 낭비되는 공간이 발생하게 됨
• 프로그램 크기를 고려해서 할당
• 분할의 크기, 개수가 동적으로 변함
• 기술적 관리 기법이 필요함
• external fragmentation 발생
• 가변 분할 방식에는 가장 적절한 hole(= 가용 메모리 공간) 을 찾는 문제가 발생함
  • First-fit: 최초로 찾아지는 hole에 할당
  • Best-fit: 프로세스의 크기와 차이가 가장 적은 hole에 할당
  • Worst-fit: 가장 큰 hole에 할당
• compaction 으로 external fragmentation 문제를 해결할 수도 있음
  • 사용중인 메모리 영역을 한군데로 몰아 넣고 hole들을 다른 한 곳으로 몰아서 매우 큰 block을 만드는 방법
  • 매우 비용이 많이 들고 프로세스의 주소가 실행 시간에 동적으로 재배치(runtime binding)가 가능한 경우에만 수행이 될 수 있음

---

Noncontiguous Allocation(불연속적 할당)

하나의 프로세스를 나누어서 물리 메모리에
물리적 메모리를 불연속적으로 할당하는 방식에는 크게 다음과 같은 세가지 방법이 있음

1. Paging
2. Segmentation
3. Paged Segmentation

1. Paging

• Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
• virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
• 일부는 backing store, 일부는 physical memory에 저장

Basic Method

• physical memory를 동일한 크기의 frame으로 나눔
• virtual memory를 동일한 크기의 page로 나눔(frame과 같은 크기)
• 모든 가용 frame들을 관리함
• page table을 사용해 logical address를 physical address로 변환함
• external fragmentation 발생 안함
• internal fragmentation 발생 가능 => virtual memory를 page로 나누다 보면 자투리 공간이 생길 수 있음

Page Table

• Page table은 main memory에 상주함
  • 페이지를 보통 4KB로 자르면 엔트리가 100만개정도가 필요하게 됨. 거기다 프로세스마다 하나씩 필요하기 때문에 많은 용량이 필요함. => cache memory 나 register에 들어가기에는 용량이 너무 크고, 당연히 disk에도 넣을 수는 없음
• Page table이 main memory에 존재하기 때문에 page table을 가리키는 register가 필요함
  • page-table base register(PTBR): page table의 위치를 가리킴
  • page-table limit register(PTLR): page table의 크기를 보관함
• 모든 메모리 접근 연산에는 2번의 memory access가 필요함
  • page table에 접근하는데 한번
  • data/instruction 접근하는데 한번
• memory access가 두번이 필요하기 때문에 성능을 향상시키기 위해서 associative register 혹은 TLB라고 불리는 고속의 lookup hardware cache를 사용함
  • TLB: main memory와 cpu 사이에서 주소를 변환해주는 캐시메모리
  • 모든 엔트리를 매핑시키는게 아니라 빈번히 참조되는 몇 개의 엔트리만 갖고 있음

Associative Register(TLB)

• parallel search가 가능함 -> TLB에는 page table중 일부만 존재하기 때문
• TLB도 프로세스마다 하나씩 존재해야 함
• 주소 변환
  • page table 중 일부가 associative register에 보관되어 있음
  • 만약 해당 page #가 associative register에 있으면 곧바로 frame #를 얻음
  • 그렇지 않으면, main memory에 있는 page table로 부터 frame #를 얻음
  • TLB는 context switch 시 flush 됨 (remove old entries)

Two-Level Page Table

• inner page table 의 하나의 page table은 memory의 page와 크기가 동일함
• 2단계 page table은 시간은 더 걸리지만, 공간은 더 줄일 수 있음
• 32bit address를 사용하는 경우 logical memory는 최대 2^32B=4GB가 되는데, 현재 컴퓨터는 64bit까지 사용하고 있음.
  • page size가 4KB라면 1M개 이상의 page table entry가 필요함
  • 각 page entry가 4B면 프로세스당 4M의 page table이 필요함
  • 그러나 대부분 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하기 때문에 4G의 주소 공간이 낭비되는 상황이 발생함
    -> page table 자체를 page로 구성함
    -> 사용되지 않는 주소 공간에 대해서 outer page table의 엔트리 값은 NULL(= 대응되는 inner page table이 없음) => logical memory 만큼 outer page table이 만들어지지만, 사용되지 않는 주소 공간에 대해서는 inner page table이 만들어지지 않음 => 공간을 줄일 수 있는 결정적인 이유

Two-Level Paging Example

• local address(on 32bit machine with 4K page size)의 구성
  • 20 bit의 page number
  • 12 bit의 page offset
    • page size = 4KB = 2^12bit 이고, memory에 있는 page의 2^12개의 주소를 구분하기 위해서는 12bit가 필요함
• page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉨(각 page table entry가 4B)
  • 10 bit의 page number
  • 10 bit의 page offset
    • inner page table 에 있는 하나의 page의 크기는 memory의 page와 동일하기 때문에 4K 이고, inner page table에 있는 page 의 하나의 entry의 크기는 4B이므로 4KB/4B = 1K = 2^10B 를 표현하기 위해서는 10bit가 필요함

Multilevel Paging

• Address space가 더 커지면 다단계 페이지 테이블이 필요함
• 각 단계의 페이지 테이블이 메모리에 존재하기 때문에 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하다
• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• e.g) 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns, TLB hit ratio가 98%인 경우
  • effective memory access time = 0.98 x 120 + 0.02 * 520(= 100x4 + 120) = 128ns
    => 결과적으로 주소 변환을 위해서 28ns(= 128ns - 100ns)만 소요됨

Inverted Page Table

• page table은 프로세스마다 page table이 존재해야 하면서 주소 변환을 위한 page table 자체에만 공간을 너무 많이 할당해야 한다는 단점이 있었고 이를 보완하기 위한 방법 중 하나임
• 사실 이 방법은 logical address 를 보고 physical address 로 변환하기 위한 것이 아니라, physical address 를 보고 logical address 로 변환하기 위한 page table임
• logical address를 physical address에 매핑하는 방법
  • 1. inverted page table의 모든 entry 를 확인함
  • 2. [pid, p]와 일치하는 entry를 찾으면 page frame의 base인 f번째에 존재한다는 것을 알게 되고, 이를 physical address로 매핑할 수 있음
• page table이 프로세스마다 하나씩 존재하는게 아니라 시스템 안에 page table 이 딱 하나만 존재함
  • page table 의 entry가 memory의 page frame 갯수만큼 존재함
    => page table을 하나만 사용하기 때문에 공간적인 장점은 있지만, overhead의 단점과 p가 여러개 있을 수도 있어서 pid를 갖고 있어야 한다는 단점이 있음
    => TLB를 사용해 병렬적으로 entry를 탐색시키는 방법으로 시간적 단점을 줄일 수 있음

Shared Page

• 공유할 수 있는 code에 대해서는 같은 memory frame을 사용함으로써 page table의 공간을 줄인다
• read-only로 하여 프로세스 간 하나의 code만 메모리에 올림(e.g text editors, compilers, window systems)
• Shared code(= Re-entrant code)는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
• private code and data는 각 프로세스마다 독자적으로 메모리에 올림

2. Segmentation

• 프로그램을 의미 단위인 여러 개의 segment로 구성함
  • 작게는 프로그램을 구성하는 함수 하나하나를 segment로 정의
  • 크게는 프로그램 전체를 하나의 segment로 정의
  • 일반적으로는 code,data,stack 부분이 하나씩의 segment로 정의됨
• logical address를 <segment-number, offset> 으로 구성함
• Segment table 사용
  • 엔트리마다 base와 limit를 갖고 있음
  • base: segment의 physical memory 시작 주소
  • limit: segment의 길이 => Paging과 다른 부분임, <s,d> 에서 d <= limit 여야 함
• Segment-table base register(STBR)
  • 물리적 메모리에서의 segment table의 위치
• Segment-table length register(STLR)
  • 프로그램이 사용하는 segment의 수 ( <s,d> 에서 s < STLR.length 여야 함)

Segmentation Architecture

Protection

• 각 세그먼트 별로 protection bit가 있음 (read/write/read-only 권한 bit)
• Valid bit = 0 => illegal segment

Sharing

• 
• segment는 의미 단위이기 때문에 Protection 과 Sharing에 있어서 paging보다 더 효과적임

Allocation

• first fit/ best fit
• external fragmentation 발생 => segment의 길이가 동일하지 않기 때문에 가변 분할 방식에서와 동일한 문제점들이 발생함

Example of Segmentation

3. Paged Sementation

• 메모리에 올릴 때 segment를 page로 쪼개서 메모리에 올리는 방식 => external fragmentation 문제 해결
  • 즉 segment 하나 당 하나의 page table을 가지게 됨
• sharing, protection은 page로 쪼개기 전 segment 단위로 이루어짐
• pure segmentation 과의 차이점
  • segment-table entry가 segment의 base address를 가지고 있는 것이 아니라, segment를 구성하는 page table의 base address를 갖고 있음
  • logical address -> segment table -> page table -> physical address
  • <s, d> -> (segment table) -> <p, d'> -> (page table) -> <f, d'> -> memory

---

Memory Protection

Pabe table의 각 entry마다 아래의 bit를 둔다.

Protection bit

• page에 대한 접근 권한(read/write/read-only) => 어떤 연산에 대한 권한을 나타냄
• page마다 code를 담고 있는 부분, stack 부분을 담고 있는 부분, data를 담고 있는 부분이 있고, 담고 있는 내용마다 변하지 않아야 하는 page도 있기 때문에 사용한다.

Valid/Invalid bit

• valid: 해당 주소의 frame에 그 프로세스를 구헝하는 유효한 내용이 있음 => 접근 허용
• invalid: 해당 주소의 frame에 그 유효한 내용이 없음 => 접근 불허
  • 1. 프로세스가 그 주소 부분을 사용하지 않음
  • 2. 해당 페이지가 메모리에 올라와 있지 않고, swap area(= backing store)에 있는 경우

---

출처: http://www.kocw.net/home/search/kemView.do?kemId=1046323