[운영체제] 메모리 관리 Memory Management

Logical vs. Physical Address

• Logical address (=virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address임
• Physical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩: 주소를 결정하는 것
  • Symbolic Address → Logical Address → Physical Address
  •                                                               ↑ 이 시점이 언제인가
  • Symbolic Address: 프로그래머 입장에서는 숫자로 된 주소를 사용하지 않고 변수 이름이라든가 함수 이름을 가지고 주소에 접근하는데, 그것을 symbolic address라고 한다.

주소 바인딩 (Address Binding)

위에서 나온 Logical Address → Physical Address의 주소 변환이 언제 되는가.

• Compile time binding
  • 컴파일 시 주소 변환 - 굉장히 비 효율적임
  • 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
  • 시작 위치 변경시 재 컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
• Load time binding
  • 프로그램이 시작돼서 메모리에 올라갈 때 주소 변환 
  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
• Execution time binding (=Run time binding)
  • 프로그램이 시작될 때 주소가 부여되는데
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음(바뀔 수 있음)
  • CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
  • 하드웨어적인 지원이 필요 (e.g. base and limit registers, MMU)
  • 현재 OS는 런타임 바인딩을 지원한다.

Memory-Management Unit(MMU)

• MMU (Memory-Management Unit)
  • logical address를 physical address로 매핑해 주는 Hardware device
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다.
  • 기본적인 MMU에서는 register 2개를 통해서 주소변환을 함
• user program
  • logical address만을 다룬다.
  • 실제 physical address를 볼 수 없으며 알 필요가 없다

Dynamic Relocation

• 내가 원하는 주소 → physical 메모리의 시작위치 + logical address
  • 14346 = 14000 + 346
• limit register: 이 프로그램의 크기
  • 만약 악의적인 크기라서 본인의 크기가 3000임에도 불구하고 4000번째를 달라고 하면 그 위치가 다른 프로그램의 메모리 위치를 가리키기 때문에 이러한 경우를 막기 위해 사용

Hardware Support for Address Translation

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

• relocation register (= base register) : 접근할 수 있는 물리적 메모리 주소의 최소값
• limit register : 논리적 주소의 범위
  • 원하는 논리적 주소가 논리적 주소의 범위 내인지 확인

몇 가지 용어들

1. Dynamic Loading
2. Dynamic Linking
3. Overlays
4. Swapping

Dynamic Loading (= 동적 적재)

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

Dynamic Linking

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

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
  • 실제 필요 부분을 메모리에 올린다는 것은 Dynamic loading과 비슷하다. 하지만 역사적으로 좀 다르다. overlays 기법은 초창기 컴퓨터 시스템은 메모리 크기가 작기 때문에 프로그램 하나를 메모리에 올려놓는 것 마저도 불가능할 때가 있었다. 그래서 메모리에 올려서 실행시킬 때 큰 프로그램을 쪼개서 이번에는 이쪽부분, 다음에는 저쪽부분을 메모리에 올리는 것을 프로그래머가 수작업으로 프로그래밍한 것이다.
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
  • Manual Overlay
  • 프로그래밍이 매우 복잡

Swapping

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

---

물리적 메모리 주소 할당과 관련된 내용

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용
  • OS 상주 영역
    • interrypt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  •  Contiguous allocation: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
    
    • Fixed partition allocation
    • Variable partition allocation
  • Noncontiguous allocation: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
    • Paging
    • Segmentation
    • Paged Segmentation

연속 할당 Contiguous Allocation

고정 분할(Fixed partition) 방식

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

가변 분할(Variable partition) 방식

• 프로그램의 크기를 고려해서 할당
• 분할의 크기, 개수가 동적으로 변함
• 기술적 관리 기법 필요
• 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들이 생성됨
• First-fit과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐(실험적인 결과)

Paging

• Paging
  • Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
  • Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
  • 일부는 backing storage에, 일부는 physical memory에 저장
• Basic Method
  • Physical memory를 동일한 크기의 frame으로 나눔
  • logical momory를 동일 크기의 page로 나눔(frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 logical address를 physical address로 변환
  • External fragmentation 발생 안함
  • Internal fragmentation 발생 가능

위의 그림을 다르게 표현하면 다음과 같다

P 를 이용하여 page table에서 p만큼 떨어져 있는 것이 p의 물리적 주소이다. 그곳에서 offset인 d만큼 더해주어 내가 원하는 d의 주소를 찾는다. d는 p로부터의 상대적 위치이기 때문에 P의 위치가 동적으로 바뀌어도 d는 바뀌지 않는다.

Implementation of Page Table

• Page table은 main memory에 상주
• Page-table base register(PTBR)가 page table을 가리킴
• Page-table length register(PTLR)가 테이블 크기를 보관
• 모든 메모리 접근 연산에는 2번의 memory access 필요
  • 2번이나 접근해서 시간이 오래 걸림
• page table 접근 1번, 실제 data/instruction 접근 1번
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라고 불리는 고속의 lookup hardware cache 사용

Paging Hardware with TLB

TLB는 page table에서 빈번히 참조되는 일부 entry를 캐싱하고 있다. 그래서 CPU는 메모리 상의 테이블(page table)에 접근하기 전에 TLB를 먼저 검색해본다. 그래서 만약 P에 해당하는 주소 공간이 TLB에 저장이 되어 있다고 하면 TLB를 통해서 주소 변환이 일어난다. 그리고 TLB에 없는 경우에 page table을 통해 주소 변환을 한다.

TLB는 page table과 달리 어떤 주소번호가 어떤 주소로 변환되는지를 담아야 하기 때문에 page number와 frame number를 모두 가지고 있으며, 또한 TLB에 있는지 확인하기 위해서는 TLB내 모든 entry들을 검색해야 한다. 전체를 검색하기 위해서는 시간이 오래 걸리기 때문에 TLB는 보통 assciative register를 통해 병렬적으로 검색을 한다.

Associative Register

• Associative registers(TLB): parallel search가 가능
  • TLB에는 page table중 일부만 존재
  • page table은 프로세스마다 존재. 따라서 각각의 page table을 담는 TLB도 프로세스마다 존재
• Address translation
  • page table 중 일부가 associative register에 보관되어 있음
  • 만약 해당 page number가 associative register에 있는 경우 곧바로 frame number를 얻음
  • 그렇지 않은 경우 main memory에 있는 page table로부터 frame number를 얻음
  • TLB는 context switch 때 flush (remove old entries)

Effective Access Time

Two-Level Page Table

• 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
  • 32 bit address 사용시 :2^32 B(4G)의 주소 공간
    • page size가 4K시 1M개의 page table entry 필요
    • 각 page entry가 4B시 프로세스 당 4M의 page table 필요
    • 그러나, 대부분의 프로그램은 4G의 주소공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨
• page table 자체를 page로 구성
• 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)
  • 그래서 실제로 테이블 주소를 찾기 위해서 2번을 거치고, 또 테이블도 하나 더 만들어야 하기 때문에(안쪽 테이블에 매핑해줄 거) 공간도 낭비되지만, NULL이 많아서 이러한 점이 해소된다.(오히려 NULL이 많아서 사용하는 공간이 줄어듦)
• Page table의 공간을 줄이기 위한 것이 목적
• 안쪽 페이지의 크기는 페이지 크기와 동일 !!!
  • 즉 페이지 크기가 4KB라고 했기 때문에 안쪽 페이지 테이블의 크기도 4KB가 된다.

Two-level Paging Example

• 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의 page에서의 변위(displacement)

Address-Translation Scheme

2단계 페이징에서의 Address-translation scheme

Multilevel Paging and Performance

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
  • N개의 페이지 테이블이 있는 경우 N+1번의 메모리 접근 필요
  • N번의 주소 변환과 1번의 실제 데이터 접근
• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
  • TLB hit ratio가 98%인 경우
    • effective memory access time = 0.98 x 120 + 0.02 x 520 = 128 nanoseconds
  • 결과적으로 주소 변환을 위해 28ns만 소요

Valid (v) / Invalid (i) Bit in a Page Table

사용되는 페이지는 6개인데, page table에는 모든 페이지에 대해 있어야 하기 때문에 8칸을 가지고 있다. 그래서 사용되면 v, 사용되지 않으면 i를 넣어준다.

Memory Protection

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

• Protection bit
  • page에 대한 접근 권한(read/write/read-only)
    • code영역 같은 경우는 바뀌지 않고 있는거 가져다가 써서 read-only로 둠
• 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)

Inverted Page Table Architecture

Inverted Page Table은 시스템 안에 page table이 딱 하나만 존재한다.(각 프로세스마다 존재하는 것이 아님) 그리고 page entry가 process의 page 개수만큼 존재하는 것이 아니라 물리적인 메모리의 page frame 개수만큼 존재한다.

그래서 들어가는 내용도 반대로 되어 있다. n번째 entry에는 n번째 frame에 들어가는 논리적인 page 번호와 해당 page의 process id가 들어간다. 그래서 논리적인 페이지 p가 물리적인 메모리에 어디에 위치하는지 알아보기 위해서는 page table내의 entry를 모두 찾아봐야 한다. 이는 시간적인 오버헤드가 있지만, 공간이 많이 절약된다.

Shared Page

• Shared code
  • Re-entrant Code (=Pure code)
  • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림
    • e.g. text editors, compilers, window systems
  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
    • 밑의 그림에서 ed 1, ed 2, ed 3가 각각 첫번째, 두번째, 세번째에 있는 것을 뜻함
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 logical address space의 아무 곳에 와도 무방

Shared Pages Example

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
  • 각각의 entry는 base와 limit을 갖는다
    • base: 세그먼트의 물리적 주소 시작점
    • limit: 세그먼트의 길이
• Segment-table base register (STBR)
  • 물리적 메모리에서의 segment table의 위치
• Segment-table length register (STLR)
  • 프로그램이 사용하는 segment의 수
  • segment number s is legal if s < STLR.

Segmentation Hardware

• Entry의 수
  • Paging 기법의 경우 프로세스 주소공간이 가질 수 있는 최대 영역만큼의 entry 수가 만들어진다.
  • Segment 기법의 경우 segment table의 entry 개수가 해당 프로그램이 사용하는 segment의 개수로 정해진다.
•  Protection
  • 각 세그먼트 별로 protection bit가 있음
  • Each entry:
    • Valid bit = 0 ⇒ illegal segment
    • Read/Write/Execution 권한 bit
      • 이러한 것들을 의미단위별로 지정 가능하다는 장점이 있음
• Sharing
  • shared segment
    • 같은 논리적인 주소단위가 있어야 함
  • same segment number
  • segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적이다
• Allocation
  • first fit / best fit
  • external fragmentation 발생
  • segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생
    • Hole들이 생김 !

Segmentation with Paging

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

---

다시 돌아가보자. 이 챕터의 이름은 Memory management였다. 정확히 말하자면 물리적인 메모리 관리이다.

이 물리적 메모리 관리에서의 OS의 역할은 무엇일까? 이 챕터에서 주요한 내용은 주소 변환이다. 어떠한 프로세스가 논리적인 주소를 가지고 있고, cpu가 논리적인 주소를 주면 물리적인 주소로 변환되어 메모리 참조를 한다는 것이다.

주소 변환에 있어서 OS의 역할은 없다 !!! 다 하드웨어가 해줘야 하는 역할이다.(MMU 등)

어떤 프로세스가 CPU를 잡고 실행하고 있으면서 어떤 프로세스를 요청하면 메모리 참조를 하는 것은 OS의 도움을 받지 않는다. 운영체제의 도움이 있으려면 매 요청마다 CPU가 운영체제한테 넘어갔다가 다시 사용자 프로세스로 돌아오고 이 작업을 반복하는 것은 비효율적이기 때문이다. 그래서 주소 변환은 하드웨어 적으로 해야한다.

물론 메모리 접근이 아니라 I/O 접그을 할 때에는 OS의 도움을 받는다.