반효경 운영체제 - 7. 메모리 관리

Logical vs Physical Address

• Logical Address(Virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address임
• Physical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩 : 주소를 결정하는 것
  • Symbolic address(변수 이름 등) → Logical Address → Physical Address

주소 바인딩

• Compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
  • 실행 파일에 지정된 주소로 메모리에 load해야하므로 매우 비효율적으로 사용하지 않는다.
• Load Time Binding
  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
• Execution time binding(Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
  • 하드웨어적인 지원이 필요
    • MMU

Memory Management Unit(MMU)

• MMU
  • Logical address를 physical address로 변환시켜주는 Hardware device
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소 값에 대해 base register의 값을 더한다.
• User program
  • logical address만을 다룬다
  • 실제 physical address를 볼 수 없으며 알 필요가 없다.

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
• memory utilization의 향상
• 가끔 사용되는 많은 양의 코드의 경우 유용
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)

Overlays

• 메모리에 프로세스 중 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제 지원 없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
  • “manual overlay”
  • 매우 복잡한 프로그래밍

Swapping

• 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
• Backing store(swap area)
  • 디스크
    • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in/ Swap out
  • 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm
    • priority가 낮은 프로세스를 swapped out 시킴
    • priority가 높은 프로세스를 swap in 시킴
  • Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야함
  • Execution time binding에서는 빈 메모리 영역 아무 곳에서나 올릴 수 있음
  • swap time은 대부분 transfer time(swap 양에 비례하는 시간)

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법
• Static Linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각 프로세스가 메모리에 올리므로 메모리 낭비
• Dynamic linking
  • 라이브러리가 실행 시 link됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용
  • OS 상주 영역 : interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역 : 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation
    • 각각의 프로세스가 메모리의 연속적 공간에 적재되도록 하는 것
    • Fixed partition allocation, Variable partition allocation
  • Noncontinuous allocation
    • 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감
    • Paging(동일 페이지로 나눔), Segmentation(의미있는 데이터 단위), paged segmentation

Contiguous Allocation

• 고정 분할 방식
  • 물리적 메모리를 몇 개의 영구적 분할(파티션)으로 나눔
  • 분할의 크기가 모두 동일한 방식, 서로 다른 방식이 존재
  • 분할당 하나의 프로그램
  • 융통성이 없음
    • 동시 메모리 load되는 프로그램 수 고정, 최대 수행 가능 프로그램 크기 제한
  • Internal fragmentation 발생(external fragmentation도 발생)
• 가변 분할 방식
  • 프로그램의 크기를 고려해서 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 기술적 관리 기법 필요
  • external fragmentation 발생

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

Dynamic storage-allocation problem

• 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
• First-fit
  • n 이상인 hole 중 최초로 찾아지는 hole에 해당
• Best-fit
  • n 이상인 것 중 가장 작은 hole을 찾아 할당
  • Hole들의 리스트를 탐색하는데 시간이 많이 걸린다는 단점
  • 많은 수의 아주 작은 hole 생성
• Worst-fit
  • 가장 큰 hole에 해당
  • 모든 리스트 탐색, 아주 큰 hole 들이 생성됨

Compaction

• external fragmentation 문제를 해결하는 한 가지 방법
• 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로몰아 큰 block을 만드는 것
• 매우 비용이 많이 드는 방법
• Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행 가능

Paging

• page 번호를 페이징 테이블에서 물리적 page frame의 주소를 얻음
• page frame number + logical address로 실제 주소를 얻을 수 있다.
• 프로그램마다 페이지 테이블이 별도로 존재, 용량이 크기 때문에 레지스터에 있을 수 없다.(캐시 메모리도 불가)

Implementation of Page Table

• 페이지 테이블은 메인 메모리에 상주
• Page-table base register(PTBR)가 page table을 가리킴
• Page-table length register (PTLR)가 테이블 크기를 보관
• 모든 메모리 접근 연산에는 2번의 메모리 접근 필요
• 페이지 테이블 접근 1번, 실제 date/instruction 접근 1번
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB) 사용
  • TLB는 index가 모든 것이 저장되지 않으므로, page number와 frame number를 쌍으로 가진다.
  • 조회 시 전체를 조회해야한다.
• TLB는 context switch 때 flush된다.
• Effective Access Time

Two-Level Page Table

• 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
• 32 bit address 사용 시 : 2^32(4GB)의 주소 공간
  • page size가 4K시 1M개의 page table entry 필요
  • 각 page entry가 4B시 프로세스 당 4MB의 page table 필요
  • 그러나, 대부분의 프로그램은 4G 주소 공간 중 지극히 일부만 사용하므로 page table 공간이 낭비된다.
• logical address (on 32bit machine with 4K page size) 구성
  • 20 bit의 page number
    • 안쪽 페이지 테이블이 4K인데, 각 entry가 4b이므로 엔트리 총 개수는 1K=10 bit 필요
    • 남는 10 bit는 바깥쪽 테이블 number로 사용
  • 12 bit의 page offset (4K의 page size이므로)
• 2단계 페이지 테이블을 사용하면, 사용이 안되는 주소 공간에 대한 outer page table의 엔트리 값은 null처리가 가능하므로(대응하는 inner page table 없음) 사용안되는 공간이 많을 때 메모리 절약이 된다.

Multilevel paging and performance

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계 페이지 테이블이 메모리에 존재하므로 logical address의 phisical address 변환에 더 많은 메모리 접근 필요
• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns, hit ratio가 98%인 경우 : 128ns

Memory Protection

• Protection bit
  • 페이지에 대한 접근 권한(read/write/readonly)
• Valid / Invalid Bit in a page table
  • 자료구조의 특성상 반드시 모든 index에 대해 page table을 만들어야함. valid-invalid bit을 이용해서 유효한 페이지만 표시한다.
  • valid : 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
  • invalid : 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허)
    • 프로세스가 사용하지 않는 경우 혹은 swap area에 있는 경우

Inverted Page Table

• page table이 매우 큰 이유
  • 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
  • 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재
• Inverted page table
  • page frame 하나당 page table에 하나의 entry를 둔 것(system-wide)
  • 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address)
  • 단점
    • 테이블 전체를 탐색해야 함
  • 조치
    • associative register 사용(expensive)

Shared Page

동일한 프로그램을 여러 개 띄운 경우 코드와 같은 경우는 메모리에 하나만 로딩해도 된다.

• Shared code
  • Re-entrant code(pure code)
  • read-only로 하여 프로세스 간 하나의 code만 메모리에 올림
  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야함.
  • 코드 안에 Logical Address가 포함되어 있기 때문, 동일해야 한다.
• Private code and data
  • 각 프로세스들을 독자적으로 메모리에 올림

Segmentation

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

Segmentation Architecture

• Logical address는 segment number, offset으로 구성
  • base - starting physical address of the segement
  • limit - length of the segment
• Segment-table base register(STBR)
  • 물리적 메모리에서의 segment table 위치
• Segment-table length register(STLR)
  • 프로그램이 사용하는 segment의 수
• Protection
  • 각 세그먼트 별로 protection bit가 있음
• Sharing
  • shared segment
  • segment는 의미단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적이다.
• Allocation
  • segmentation 길이가 동일하지 않으므로 가변 분할 방식에서와 동일한 문제점 발생
  • first fit / best fit
  • external fragmentation 발생

Paged Segmentation

물리적 메모리에는 page로 올라가기 때문에 allocation 문제를 해결

protection, sharing은 의미단위로 가능