[OS] 8장 - Memory Management

반효경 교수님의 운영체제 강의를 참고하였습니다.

(https://core.ewha.ac.kr/publicview/C0101020140318134023355997?vmode=f)

Logical vs Physical Address

• Logical

  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address
    • instruction 내에 있는 주소는 logical address이고 실행할 때 physical address로 주소변환을 함

• Physical

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

• 주소 바인딩 : 주소를 결정하는 것 Symbolic Address → Logical Address → Physical Address

주소 바인딩(Address Binding)

• Compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경시 재컴파일
  • 컴파일러는 **절대 코드(absolute code)**생성
  • 프로그램이 하나만 실행되는 옛날 컴퓨터에서 사용
• Load time binding
  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 **재배치가능코드(relocatable code)**를 생성한 경우 가능
  • 메모리에 비어있는 곳에 배치
• Execution time binding(=Runtime binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검
  • 하드웨어적인 지원이 필요

Memory-Management Unit(MMU)

• logical address → physical address로 변환하는 장치(hardware device)
• base register + logical address
• limit register : 메모리 크기 → 다른 메모리의 주소를 접근하지 않기 위해
• user program은 logical address만을 다루며 실제 physical address를 알 필요가 없음

Dynamic Relocation

Dynamic Loading

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

Overlay(Manual Overlay)

• 메모리에 프로세스의 부분 중 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현
• Dynamic Loading과 다른 점은 운영체제의 지원을 받냐 안받냐의 차이

Swapping

• 프로세스를 메모리에서 backing store로 쫓아내는 것
• backing store(=swap area)
  • 디스크
  • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm
    • priority가 낮은 프로세스를 swapped out
    • priority가 높은 프로세스를 swapped in
  • swap in이 효율적으로 사용되려면 runtime binding이 되어야 함 compile/load time의 경우 원래 메모리 위치로 swap in 해야 함
  • 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
  • Non-Contiguous allocation
    • Paging
    • Segmentation
    • Paged Segmentation

Contiguous allocation

고정분할 방식

• 물리적 메모리를 몇 개의 영구적 파티션으로 나눔
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
• 분할당 하나의 프로그램 적재
• Internal fragmentation과 external fragmentation 발생

가변분할 방식

• 프로그램이 실행될 때마다 크기를 고려해서 할당
• 분할의 크기, 개수가 동적으로 변함
• 기술적 관리 기법 필요
• external fragmentation 발생

외부 파편(External Fragmentation)

• 프로그램 크기보다 파티션의 크기가 작은 경우
• 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 구간

내부 파편(Internal Fragmentation)

• 프로그램 크기보다 파티션의 크기가 큰 경우
• 하나의 파티션 내부에서 발생하는 사용되지 않는 메모리 조각
• 특정 프로그램에 배정되었지만 사용되지 않는 공간

Hole

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

가장 적절한 hole을 찾는 문제

• First-fit
  • Size가 n이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit
  • Size가 n이상인 것 중 가장 작은 hole을 찾아서 할당
  • sorting이 되어있지 않은 경우 모든 hole을 탐색
  • 많은 수의 아주 작은 hole들 생성
• Worst-fit
  • 가장 큰 hole에 할당
  • 모든 리스트 탐색
  • 상대적으로 큰 hole 발생

First-fit과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적

Compaction

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

Non-contiguous allocation

Paging

• Process의 virtual memory를 동일한 사이즈의 page단위로 나눔

• Virtual memory의 내용이 page 단위로 저장 됨

• 일부는 backing storage에, 일부는 physical memory에 저장

• 주소 변환 방법

  

  • page table에서 매핑되는 frame을 찾음
  • 찾은 frame과 logical address를 결합하여 physical memory에 접근 함

• page 테이블의 용량이 너무 크기 때문에 register에 둘 순 없고, main memory에 둠

• 위에 나왔던 base register와 limit register는 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) 라는 cache 사용

• TLB는 context switch 발생시 flush

Two-Level Page Table

• 32 bit address 사용시 : 2^32(4G)
  • page size가 4K시 1M(2^20)개의 page table entry 필요
  • 각 page entry가 4B시 프로세스당 4M의 page table필요
  • 그러나, 대부분의 프로그램은 4G의 주소 공간 중 극히 일부만 사용하므로 page table이 낭비 됨
• page table 자체를 page로 구성
• 사용되지 않는 주소 공간에 대한 outer page table의 entry값은 NULL로 구성(대응 하는 inner page table이 없음)
• page table 하나당 4K고, page table entry는 4B임 그래서 약 1K(2^10)개의 entry가 들어가게 됨

• 20 bit의 page number
  • 각 page table entry는 4B
  • 10 bit의 page number
  • 10 bit의 page offset
• 12 bit의 page offset
  • 12 bit인 이유는 page table이 4KB이기 때문(2^12)
• P1은 outer page table의 index
• P2는 outer page table의 page에서의 변위(displacement)

❓ 그럼 64 bit일 때는 어떻게 page bit를 나눌까?

Memory Protection

Page table의 각 entry마다 아래의 bit를 둠

• Protection bit
  • page에 대한 접근 권한(read/write/read-only)
• Valid-invalid bit
  • valid → 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
  • invalid → 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허)

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만 메모리에 올림(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
• Logical address는 다음과 같이 구성 <segment-number, offset>
• Segment table
  • base - starting physical address of the segment(STBR)
  • limit - length of the segment(STLR)
    • 의미 단위로 자르는 것이므로 page와는 다르게 limit이 존재 함
• segment의 길이가 동일하지 않으므로 가변분할 방식에서 동일한 문제점들이 발생 → external fragmentation
• 의미 단위로 잘랐기 때문에 각 세그먼트 별로 protection bit가 있음
• segment는 의미 단위기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 효과적

Segmentation with Paging

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