7장 메모리 관리

Logical Address vs Physical Address

• Logical address(=virtual address)
  - 프로세스마다 독립적으로 가지는 주소 공간
  - 각 프로세스마다 0번지부터 시작
  - CPU가 보는 주소는 logical address임

• Physical address
  - 메모리에 실제 올라가는 위치
  - 하위 주소에는 운영체제 커널이 올라가 있고, 상위 주소에는 여러 프로그램들이 섞여서 올라가 있음

프로그램마다 0번지부터 시작하는 독자적인 주소가 있지만 프로그램이 실행이 되려면 물리적인 메모리 어딘가로 올라가야 하고, 그러면 주소가 바뀌게 된다.
이 때, 어떤 프로그램dl 물리적인 메모리의 어느 곳으로 올라갈지 주소를 결정하는 것을 주소 바인딩(Address binding) 이라고 한다.

• 주소 바인딩
  Symbolic Address -> Logical Address -> Physical address

Q. Symbolic Address 란?
프로그래밍을 하면서 값을 저장할 때, 변수를 선언하고 변수에 값을 저장하지 특정 메모리 위치를 지정하여 값을 저장하지는 않는다. 함수 호출시에도, '몇 번지 주소로 점프해라' 하지 않고, 함수 이름을 주어 해당 함수를 호출한다. 즉, 프로그래머는 프로그래밍 시 Symbol로 된 주소 (Symbolic address)를 사용한다.

주소 바인딩(Address Binding) : 주소 변환이 이루어지는 시점에 따라

• Compile time binding
  - 물리적인 메모리 주소(physical address)가 컴파일 시 알려짐
  - 시작 위치 변경시 재컴파일
  - 컴파일러는 절대코드 (absolute code) 생성 -> (logical address == physical address)
  - 현대의 컴퓨터 시스템에서는 사용하지 않음. 과거 컴퓨터 시스템에서 프로그램이 하나만 실행되는 환경의 경우, 다른 프로그램이 동시에 메모리에 올라가는 일이 없기 때문에 컴파일시 미리 물리적인 메모리 주소를 결정해서 올리는 compile time binding 이 사용되기도 했음

• Load time binding
  - 실행이 시작될 때 주소 변환이 이루어짐
  - Loader의 책임 하에 물리적 메모리 주소 부여
  - 컴파일러가 재배치가능코드(relocate code) 를 생성한 경우 가능

• Execution time binding(=Run time binding)
  - 실행시에 주소가 결정된다는 점은 Load tiem binding과 같음
  - 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  - CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
  - 하드웨어적인 지원이 필요(e.g. base and limit registers, MMU)

CPU가 바라보는 주소는 logical address 이다.
컴파일된 코드 안에는 logical address가 포함되어 있음. 실행이 되어 메모리에 올라가더라도 instruction code 안에 있는 address 자체는 바뀌지 않는다.

Memory-Management Unit(MMU)

• MMU (Memory-Management Unit)
  logical address를 physical address로 매핑해주는 Hardware device

• MMU scheme
  사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=recolation register)의 값을 더한다.

• user program
  - logical address만을 다룬다
  - 실제 physical address를 볼 수 없으며 알 필요가 없다.
  
  

Hardware Support for Address Translation

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터

• Relocation register(=base register) : 접근할 수 있는 물리적 메모리 주소의 최소값
• Limit register : 논리적 주소의 범위

CPU가 메모리 몇 번지를 달라고 logical address를 주게되면, 먼저 해당 논리주소가 프로그램 크기보다 더 큰 것인지 아닌지 확인한다 : limit register 값과 요청된 logical address 값을 비교

if) logical address >= limit register
trap!! : addressing error
CPU 제어권이 운영체제에게 넘어가게 되고, 운영체제는 상황에 알맞은 처리를 수행한다.

else) 요청된 logical address에 base register 값을 더해서 physical address로 주소변환을 한 다음, 물리적인 메모리 어딘가에 있는 내용을 읽어다가 CPU에게 전달해준다.

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load 하는 것

• memory uilization의 향상
• 가끔식 사용되는 많은 양의 코드의 경우 유용( 예 : 오류 처리 루틴 )
• 운영체제의 특별한 지원없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)

• Dynamic Loading != Paging System

현대의 컴퓨터 시스템도 프로그램을 실행시키면 메모리에 통째로 올라가지 않고, 당장 필요한 부분만 메모리에 올라가고, 필요가 없어지면 메모리에서 쫓겨난다. 하지만, 이것이 본래의 Dynamic Loading의 개념은 아니다.

엄밀히 말해서, 현대의 컴퓨터 시스템은 운영체제가 관리해주는 paging system에 의해서 이루어지는 것이고, 원래의 Dynamic Loading은 '프로그래머의 코딩 + OS 라이브러리 지원' 을 통해 이루어지는 것을 의미한다.

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림

• 프로세스의 크기가 메모리보다 클 때 유용 (프로세스 크기 > 메모리 크기)
• 운영체제의 지원 없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
  - "Manual Overlay"
  - 프로그래밍이 매우 복잡

Swapping

프로세스를 일시적으로 메모리에서 backing store(=swap area)로 쫓아내는 것

• Swap in / Swap out
  - 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
  - priority-based CPU scheduling algorithm
  => priority가 낮은 프로세스를 swapped out 시킴
  => priority가 높은 프로세스를 메모리에 올려 놓음
  - Compile time 혹은 load time binding 에서는 원래 메모리 위치로 swap in해야함
  - Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
  - swap time은 대부분 transfer time (swap 되는 양에 비례하는 시간)임 <= swap하는 용량이 방대하기 때문

Dynamic Linking

Linking(여러군데 존재하던 compile된 파일들을 묶어서 실행파일을 만드는 과정)을 실행 시간(execution time) 까지 미루는 기법

• Static linking
  - 라이브러리가 프로그램의 실행파일 코드에 포함됨
  - 실행 파일의 크기가 커짐
  - 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
  (eg. printf 함수의 라이브러리 코드)

• Dynamic linking
  - 라이브러리가 실행시 연결(link)됨
  - 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub 이라는 작은 코드를 둠
  - 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 디스크에서 읽어옴
  - 운영체제의 도움이 필요

Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용

• OS 상주 영역 : interrupt vector 와 함께 낮은 주소 영역 사용
• *사용자 프로세스 영역 : 높은 주소 영역 사용

*사용자 프로세스 영역의 할당 방법

• Contiguous allocation(연속할당)
  각각의 프로세스가 메모리의 연속적인 공간에 (통째로) 적재되도록 하는 것
  - Fixed partition allocation
  - Variable partition allocation

• Noncontiguous allocation(불연속할당)
  하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
  - Paging
  - Segmentation
  - Paged Segmentation

Contiguous Allocation

* External fragmentation(외부 조각)
  - 프로그램 크기보다 분할의 크기가 작은 경우
  - 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

* Internal fragmentation(내부 조각)
  - 프로그램 크기보다 분할의 크기가 큰 경우
  - 하나의 분할 내부에서 발생하는 사용되지 않은 메모리 조각
  - 특정 프로그램에 배정되었지만 사용되지 않는 공간

• 고정분할(Fixed partition) 방식
  - 물리적 메모리를 몇 개의 영구적 분할(partition) 로 나눔
  - 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
  - 분할당 하나의 프로그램 적재
  - (-) 융통성이 없음
  => 동시에 메모리에 load되는 프로그램의 수가 고정됨
  => 최대 수행 가능 프로그램 크기 제한
  - Internal fragmentation 발생 (external fragmentation도 발생)

• 가변분할(Variable partition) 방식
  - 프로그램의 크기를 고려해서 할당(프로그램을 차곡차곡 쌓아서 메모리에 올림)
  (하지만 프로그램 수행이 완료되는 시점이 각기 다르기 때문에 메모리 중간중간에 Hole*이 생김)
  - 분할의 크기, 개수가 동적으로 할당
  - 기술적 관리 기법 필요
  - External fragmentation 발생

	Hole
	- 가용 메모리 공간
	- 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
	- 프로세스가 도착하면 수용가능한 hole을 할당
	- 운영체제는 다음의 정보를 유지 a)할당 공간 b)가용 공간 (hole)

Dynamic Storage-Allocation Problem

: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

• First-fit : Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit : Size가 n 이상인 가장 작은 hole을 찾아서 할당
  - Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함
  - 많은 수의 아주 작은 hole들이 생성됨
• Worst-fit : 가장 큰 hole에 할당
  - 역시 모든 리스트를 탐색해야 함
  - 상대적으로 아주 큰 hole들이 생성됨

• compaction
  - external fragmentation을 해결하는 한가지 방법
  - 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
  - 매우 비용이 많이 드는 방법..
  - 최소한의 메모리 이동으로 compaction하는 방법 (매우 복잡한 문제)
  - Compaction은 일단 프로세스의 주소가 실행 시칸에 동적으로 재배치 가능한 Run time binding이 보장되는 경우에만 수행될 수 있다.

Noncontiguous allocation

• Paging 기법
  하나의 프로그램을 구성하는 주소공간을 같은 크기의 page로 자른다.
  page 단위로 물리적인 메모리에 올려놓거나, backing store에 내려놓거나 한다.

프로그램을 구성하는 주소공간을 같은 크기의 page로 자르는 것처럼, 물리적인 메모리 상에 사용자 프로그램이 들어갈 수 있는 공간들도 page 하나가 들어갈 수 있는 크기로 미리 잘라놓는다. = Page frame

불연속할당 기법을 사용하면 앞서 살펴본 hole과 관련된 문제들이 사라지지만,
주소 변환이 복잡해진다. 잘려진 각각의 page가 물리적인 메모리의 어디에 올라가있는지를 확인해봐야한다.
즉, 주소 변환을 page별로 해야하기 때문에 address binding이 더 복잡해진다.

• Segmentation 기법
  프로그램의 주소 공간을 의미 있는 단위 로 자르는 기법이다.
  프로그램의 주소 공간은 code, data, stack으로 구성되는데, segmentation 기법은 code segment, data segment, stack segment 로 잘라서 각각의 segment를 필요시에 물리적인 메모리에 다른 위치에 올려놓을 수 있게 하는 방법이다. (segment의 단위는 꼭 code, data, stack이 아닐 수 있다)

Segment는 의미 단위로 자른 것이기 때문에 크기가 균일하지는 않다. 따라서 앞서 이야기한 Dynamic Storage-Allocation Problem이 Segmentation 기법 사용시에도 발생한다.

Paging

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

즉, 프로그램을 구성하는 논리적인 메모리를 동일한 크기의 페이지로 잘라서 각각의 페이지별로 물리적인 메모리의 적당한&비어있는 위치에 올라갈 수 있게 하는 기법

<기본 방법>
- physical meory를 동일한 크기의 frame으로 나눔
- logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
- 모든 가용 frame들을 관리
- page table을 사용하여 logical address를 physical address로 변환
- External fragmentation 발생 안함
- Internal fragmentation 발생 가능

• paging table
  페이지 테이블은 논리적인 페이지 N이 물리적인 메모리의 몇 번째 frame에 올라가 있는지 알려준다. 논리적인 메모리의 페이지 개수만큼 엔트리(entry)가 존재한다.
  

- page table을 통한 주소 변환은 엔트리를 전부 서치할 필요는 없다. 페이지 번호 p가 주어지면 배열(페이지 테이블)의 인덱스, 즉 위에서부터 p번째 엔트리로 가면 주소 변환이 바로 이루어지기 때문이다.

그런데, 프로그램 하나의 주소 공간이 약 백 만개의 페이지로 잘린다. 그렇다면 100만 개의 엔트리가 CPU의 레지스터 안에 들어갈 수 있는가? 없다. 결국, 주소 변환에 사용되는 paging table도 메모리에 저장해야 한다.

Implementation of Page Table

• Page table은 main memory에 상주한다
• Page-table base register(PTBR) 가 page table을 가리킴
• Page-table length register(PTLR) 가 테이블 크기를 보관
• 모든 메모리 접근 연산에는 2번의 memory access가 필요
  • page table 접근 1번
  • 실제 data/instruction 접근 1번
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB) 라 불리는 고속의 lookup hardware cache 사용. TLB는 page table에서 빈번히 참조되는 일부 엔트리를 caching 하고 있다.

TLB 는 page table의 정보 전체가 아닌 일부만을 담고 있다.
- parallel search 가 가능하다.
- TLB는 context switch 때 flush (remove old entries) (왜냐, 프로세스마다 주소 변환 정보가 다르기 때문에)

CPU가 논리적인 주소(page #)를 주게되면, 메모리 상에 있는 page table에 접근하기 전에 TLB를 먼저 검색해봐서, 혹시 TLB에 저장된 정보를 이용하여 주소 변환이 가능한지 체크한다.
i) 해당 page # 가 TLB에 저장되어 있다면
frame # 를 바로 얻어서 주소 변환이 이루어져 물리적인 메모리에 접근 (memory access 1회)
ii) TBL에 저장되어 있지 않다면, (TLB miss)
page table로부터 frame # 을 얻어 주소 변환을 하고, 메모리에 접근 (memory access 2회)

Effective Access Time

• Associative register lookup time = ε
• memory cycle time = 1
• Hit ratio = α
  - associative register(TLB)에서 찾아지는 비율

Effective Access Time(EAT)
		<hit>        <miss>	
EAT = (1 + ε)α + (2 + ε)(1 - α)
	= 2 + ε - α

- TLB에서 주소 변환 정보가 찾아지는 비율(α)만큼은 TLB 접근시간(ε)과 실제 데이터를 접근하는 메모리 접근시간(1)이 걸릴 것이다.
- 주소 변환 정보가 TLB에서 찾아지지 않는 비율(1 - α)만큼은 TLB 접근시간(ε), 메모리 상에 있는 page table 접근시간(1), 실제 데이터에 접근하는 메모리 접근시간(1)이 걸릴 것이다.

결론 : TLB로부터 주소 변환이 되는 비율(α)이 굉장히 높기 때문에 2 + ε - α 이 page table만 있을 때의 접근시간(2)보다는 훨씬 작은 값이 된다.

Two-Level Page Table

• logical address (on 32-bit machine with 4K page size)의 구성
  - 20 bit의 page number
  - 12 bit의 page offset
• page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다 (각 page table entry가 4B)
  - 10-bit의 page number
  - 10-bit의 page offset
• 따라서, logical address는 다음과 같다.
  - P1은 outer page table의 index이고
  - P2는 outer page table에서의 변위(displacement)

page 하나의 크기가 4KB. 우리가 4KB 안에서 BYTE 단위로 주소 구분을 하려면 몇 비트가 필요할까?
4KB = 2^12BYTE -> 12bit가 필요

안쪽 페이지 테이블이 페이지화 되어 들어간다. 즉, 4KB.
각 엔트리가 4B이기 때문에, 엔트리가 1K개 있다.
1K(2^10)개의 엔트리 위치를 구분하기 위해서 P2는 10B가 필요하다.

마지막으로 바깥쪽 페이지 테이블을 위한 페이지 번호는 10B짜리가 만든어진다.

Q .2단계 페이지 테이블을 사용하는 이유?
프로그램을 구성하는 공간 중 상당부분은 사용이 안된다. 하지만 page table을 만들 때에는 사용되지 않는 중간의 공간들을 엔트리로 안 만들 수가 없다. 따라서, Maximum logical memory의 크기만큼 page table의 엔트리 수가 만들어져야 한다.

2단계 페이지 테이블은 이를 해소할 수 있다.
바깥쪽 page table은 전체 논리적인 메모리 크기만큼 만들어지지만, 실제로 사용이 안되는 주소에 대해서 안쪽 page table은 안 만들어지고 pointer가 그냥 null 상태로 되어있다.

결론 : 2단계 page table을 쓰는 이유는 page table의 공간을 줄일 수 있기 때문이다. 전체 주소 공간 중에서 상당부분은 실제로 사용이 되지 않는 공간이기 때문에 그에 대한 안쪽 page table이 만들어지지 않고, 결과적으로 page table이 차지하는 공간을 줄일 수 있다.

Inverted page Table Architecture

page frame 개수만큼 엔트리가 존재. 앞서 배운 page table과 들어가는 내용이 반대로 되어있다.

첫번째 엔트리 : 첫번째 page frame에 들어가는 논리적인 page 번호
두번째 엔트리 : 두번째 page frame에 들어가는 논리적인 page 번호

• Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide : 시스템 안에 하나만 존재)
• 각 page table entry는 각각의 물리적인 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address)
  - 단점 : 테이블 전체를 탐색해야 함(인덱스로 조회하는 테이블의 이점 누릴 수 없음)
  - 조치 : associative register 사용하여 병렬적으로 동시 검색이 가능하게끔 (expensive)

shared page

여러 프로세스가 공유할 수 있는 code 부분을 같은 물리적인 메모리 frame으로 매핑해주는 기법

• shared code(=Re-entrant code = Pure code)
  - read-only 로 하여 프로세스 간에 하나의 code만 메모리에 올림
  ex) text editors, compilers, window systems
  - Shared code는 모든 프로세스의 logical address space에서 동일한 위치 에 있어야 함

• Private code and data
  - 각 프로세스들은 독자적으로 메모리에 올림
  - Private data는 logical address space의 아무 곳에 와도 무방

Segmentation

• 프로그램은 의미 단위 인 여러 개의 segment로 구성
  - 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  - 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
  - 일반적으로는 code, data stack 부분이 하나씩 세그먼트로 정의됨

• Segment는 다음과 같은 logical unit들이다.

	main(),
    function,
    global variables,
    stack,
    symbol table, arrays

segmentation Architecture

• Logical address는 다음의 두 가지로 구성 <segment-number, offset(얼마나 떨어져 있는지)>
• 각 세그먼트별로 서로 다른 물리적인 메모리 위치에 올라갈 수 있기 때문에 세그먼트별로 주소 변환을 해야해서 Segment table을 두고 있다.
  - 각 테이블 엔트리는 base(세그먼트의 시작 물리 주소), limit(세그먼트의 길이)을 가진다.
• Segment-table base register(STBR)
  - 물리적 메모리에서의 segment table의 위치
• Segment-table length register(STLR)
  - 프로그램이 사용하는 segment의 수
  segment number s is legal if s < STLR.

segmentation 기법의 장단점

• segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적이다.
• segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점이 발생한다.

테이블 관련한 메모리 낭비는 Paging에 비해 Segmentation이 낭비가 적다.

Segmentation with Paging

segment 하나가 여러 개의 page로 구성된다.

• pure segmentation과의 차이점
  - segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음

7장 메모리 관리에서 사실상 운영체제가 관여하는 부분은 없음