💡9장 목표

• 메모리 관리를 위해 제공되는 하드웨어
• 메모리 관리 방법
  • Contiguous Memory Allocation
  • Paging, Page table
  • Segmentiation
• Swapping
• Example

프로그램은 disk에 있다가 메모리로 로드되어 프로세스 내에 배치되어야 실행된다.
CPU에서 메모리에 있는 데이터에 접근할 때 주소가 필요하다

• 읽을 때는 주소+읽기 요청
• 쓸 때는 주소+데이터+쓰기 요청

Background

Protection

프로세스는 자기가 할당받은 영역만 사용해야한다.

• 영역의 시작 주소는 base, 끝 주소는 base+limit(프로세스 크기)
• CPU는 메모리에 접근할 때 할당 영역을 넘어가는지 계속 확인해야한다.
  • 자주 확인하는 값이라 base와 limit는 해당 레지스터에 존재한다.
  • 영역을 넘어가면 trap을 발생시켜 프로그램 종료
• base와 limit을 로드?수정?하는 명령어는 privileged로 커널 모드에서만 가능
  
  

Address Binding

주소가 언제 정해지는지

• 프로그램의 단계에 따라 주소는 다양한 방식으로 표현된다. (각각 다른 주소 공간으로 매핑하는 과정)
  • source code: symbolic으로 표현
  • compiled code: relocatable 주소로 표현됨 (상대주소, 재배치 가능한 상태)
  • Linker or Loader: 위의 상대 주소로 재배치하여 절대 주소로 표현

명령어와 데이터의 주소 바인딩(결정)은 여러 타이밍에서 발생할 수 있다.

• Compile Time: 상대 주소만 결정된다. 근데 메모리 위치가 사전에 알려져 있으면 절대 주소가 결정될 수도 있다.(boot loader 등)
• Load Time: 위의 상대 주소를 활용하여 절대 주소 결정 (재배치)
• Execution Time: 실행 중에 주소가 결정되는 경우 → 특정 코드/라이브러리가 호출될 때 로드하는 dynamic link loader(DLL)
  

Memory-Management Unit(MMU)

• Logical address: CPU에 의해 생성된, CPU 입장에서의 주소로 프로세스마다 가지는 가상 주소이다. (상대 주소)
• Physical address: 실제 메모리 공간에 할당된 주소이다. (절대 주소)

메모리 관리 장치 MMU는 CPU에 포함되어 있으며, 논리주소를 물리주소로 매핑하는 역할을 한다.

• Relocation register의 값(base 등)을 논리 주소에 더해 물리 주소로 재배치
• 유저 프로그램은 실제 물리 주소를 결코 보지 못한다. 논리 주소와만 상호작용 한다.
  

Dynamic Loading/Linking

• 프로그램 실행할 때 전체를 메모리에 로드하는 것이 아닌 동적으로 로딩
• static linking은 exe파일을 만들 때 한꺼번에 링킹하는 것이고, dynamic linking은 execution time(특정 부분이 호출될 때) 링킹하는 것이다.
  • 공유 라이브러리나 에러처리 등과 같은 기능에 주로 사용
• 메모리 관리 및 코드 자사용 효율적으로 지원, 유연성 높임
  
  

🔹Memory management

1. Contiguous Allocation

메모리 공간을 연속적으로 할당해준다. 각 프로세스 등이 차지가는 공간을 partition이라고 한다.

• Base register와 Limit register로 MMU가 논리 주소를 dynamic하게 매핑한다.
  

Variable partition (dynamic partition)

• partition의 크기는 다 다르다. 프로세스가 요구한 크기에 따라 partition의 크기가 결정되고 그만큼 할당한다.
  • static partition: OS초기화 시 미리 partition의 크기 지정, 메모리 낭비
• 빈 공간들이 있을 때 어느 공간을 할당해 줄 것인가?
  1. First-fit: 충분한 크기를 가지는 첫 공간
  2. Best-fit: 충분한 크기를 가지는 공간들 중 가장 작은 공간
  3. Worst-fit: 가장 큰 크기를 가지는 공간
  • 보통 1, 2번은 성능이 좋고 3번은 성능이 안좋다.
  • best-fit은 모든 공간을 다 찾아야해서 시간이 걸린다. 속도 저하

Fragmentation

메모리 공간에서 애매한 크기로 사용하지 못하는 공간을 의미한다.

• External Fragmentation: 파티션 사이 작은 공간으로 사용 못하는 공간
• Internal Fragmentation: static partition에서 정해진 파티션 공간에 프로세스가 들어오고 남은 공간

이를 해결하기 위해 파티션을 위로 모으는 Compaction을 한다.

• 쓸모있는 공간 만들어내기, 조각 모음
  
  

2. Paging

Contiguous 공간을 찾기 어렵다. 그래서 메모리 공간을 잘게 쪼개서 사용하자

• physical 메모리는 frame단위로, logical 메모리(프로세스)는 page 단위로 쪼갠다. (frame과 page는 절대/상대 주소 차이)
• 프로세스에 메모리를 할당 할 때 n개의 페이지를 할당하는 것
• 하지만 여전히 Internal fragmentation이 발생할 수 있다. (page의 남은 공간)

프로세스는 physical 메모리의 연속적이지 않은 frame들을 page로 가져와서 자기 공간에 연속적으로 배치해서 사용한다. 프로세스 입장에서는 연속적인 공간을 사용한다고 느낀다.

Page table

프로세스의 page를 메모리의 frame으로 매핑하기위한(절대 주소로 바꾸기 위한) 정보를 담고있으며, 프로세스마다 존재한다.

아래와 같은 자료 구조가 page table의 입출력으로 사용된다.

• Page/Frame number(p/f): 프로세스에서 page 번호, page table의 인덱스로 사용된다. page table을 거치면 frame 번호로 변환된다.
• Page offset(d): 해당 page의 주소(상대 주소), 절대 주소로 변환하기 위해 base주소와 더해질 값

아래와 같이 매핑

Internal fragmentation

계산은 아래와 같다.

page는 protection, 재배치? 등의 역할도 해줘야하므로 메모리가 커지면 page도 커져야한다.
→ 그래서 Solaris는 크기가 다른 2개의 페이지를 지원하여 page 개수를 많이 사용할 수 있게했다.

Free frames

OS는 메모리의 빈 공간을 관리한다. 새로운 프로세스가 메모리 할당을 요청하면 OS가 빈 공간을 내어주고 그 공간으로 page table이 결정된다.

Implementation of Page table

페이지 테이블은 메인 메모리에 있다.

page table은 자주 사용되는 값이니까 레지스터를 사용한다.

• PTBR(page table base register)
• PTLR(page table length register)

그래도 page table을 가지러 메모리에 한 번, page table을 보고 알맞은 메인 메모리 위치로 또 한 번 → 2번 거쳐야해서 속도 2배 느려짐

• TLBs(Translation look-aside buffers)라는 캐시를 사용해서 빠르게 조회할 수 있도록 한다.
  
  

TLBs

여러 프로세스들이 공유하는 버퍼로, page table의 캐시이다.

• page table에서 페이지 번호를 찾을 때, TLBs에서 먼저 찾고 있으면 TLB hit, 없으면 TLB miss
• miss가 발생하면 page table의 값을 메모리에서 캐시로(TLBs로) 가져오기
  • 가져올 때 페이지 번호와 프레임 번호를 매핑하여 가져와야한다. (하나만 갖고오면 나머지를 알 수 없어 주소 변환 수행 불가능)

TLB에서 페이지 번호를 찾는 비율을 Hit ratio라고 한다.

• 80%의 hit ratio, 메모리 접근 시간이 10ns라고 하면
  • 20%의 페이지를 못찾는 경우는 메모리 두 번 접근으로 20ns이다. (2배)
  • 이때의 Effective Access Time(ETA)를 구하면 아래와 같다.
    → 0.8 10 + 0.2 20 = 12 ns
    
  
  

Memory Protection

각 프레임에 protectioin bit를 연결하여 할당 영역만 사용할 수 있도록하고, 읽기 전용 또는 읽기 쓰기 접근 허용을 나타낸다.

Shared Pages

여러 프로세스 간에 공유되는 페이지

ex) 여러 프로세스가 같은 라이브러리를 사용하는 경우, 메인 메모리에 공유 페이지를 만들어 같이 사용

Structure ⭐

단순하게 페이지 처리를 하면 페이지 테이블이 매우 커질 수 있다는 단점을 가진다.

ex) 32비트 logical address 공간

• 페이지 크기 4kb (2^12)
• 페이지 테이블은 1백만개의 항목을 가진다 (2^32, w^12)
• 각 항목이 4바이트라면, 각 프로세스는 페이지 테이블만을 위해 4mb의 physical address 공간을 차지하게된다.

이를 보완하기 위한 ⭐3가지 페이지 테이블 구조⭐는 아래와 같다. (흐름 알기)

1. Hierarchical Paging

• 2 level page table: 페이지 테이블도 페이지로 나눠 페이지 테이블의 페이지 테이블을 만든다.
  

ex) 32비트 logical address

• 아래와 같은 구조를 가진다. p1은 outer page number, p2는 page number

ex) 64비트 logical address

• 3 level로도 가능
  

2. Hash Page Tables

• 논리 주소를 해시 함수를 통해 해시화하여 테이블에 매핑 → 인덱스로 빠르게 찾을 수 있도록 해줌
  • 해시값이 같은 논리 주소 값들이 존재할 수 있으므로 linked list로 관리
  • 테이블은 페이지 번호, 프레임 번호, 다음 요소의 포인터로 구성
• 하지만 크기가 너무 커지면 오히려 더 복잡해질 수 있다. 그래서 모여있는 페이지 그룹을 가리키는 clustered page table도 있다.

3. Inverted Page Tables

• 기존 페이지 테이블과 반대로 논리 주소가 아닌 물리 주소의 frame 순서에 따라 page table을 구성
• 프로세스마다가 아닌, 한 시스템이 가지는 테이블 (어떤 프로세스가 사용하는지 구별하는 pid 필요)
• 테이블 크기는 줄어들지만, page number를 찾는데 시간이 걸린다.
  
  

in Oracle Solaris

• hashing page table
• 가상 contiguous area를 가리킴 → 각 페이지에 대한 해시 테이블보다 효율적
• TBL (cache)
  
  

🔹Swapping

메인 메모리의 하위 계층(하드디스크 등) 공간을 swap 공간으로 사용한다.

• Backing store: 하위 계층 공간, 넓은 공간
• 거의 모든 OS에서 사용하며, 메모리 공간이 부족할 때만 Swapping을 한다.
• 메인 메모리의 공간 확보
  • Roll out: 당장 CPU가 필요없는 wait 상태나 우선 순위가 낮은 프로세스를 잠시 backing store로 보냄
  • Roll in: backing store에 있는 것들이 CPU가 필요해지면 다시 메인 메모리로 올려서 CPU 할당
    

Context switch

swapping time

• context switch는 CPU에 다음으로 할당할 프로세스가 메인 메모리에 없으면, swapping 해야해서 시간이 걸린다.
  • 이때 swapping 한다는 것은 context switch로 놓아주는 프로세는 swap out을 하고, 필요한 프로세스를 swap in하는 것
• 만약 100mb 프로세스를 50mb/s 속도로 하드 디스크로 swapping한다면 swap out 시간은 2초, swap in도 2초로 총 4초가 걸린다.
• 이런 swapping time을 줄이기 위해서는 스와핑 메모리 크기 줄이기

Pending I/O

• I/O를 대기 중인 프로세스를 swapping하면, 잘못된 프로세스에 I/O가 발생할 수 있다. (꼬일 수 있다..)
  • 왜냐하면 I/O는 operation을 하기 위해 메모리 공간을 가지고 있다(double buffering, 커널이 관리하는 공간). 근데 이 메모리 공간을 가지고 있는 프로세스를 swapping해버리면(메모리에서 뻬버리면)
• 그래서 I/O 대기 중일 때는 swapping을 금지하는 등의 방안이 있음
  
  

in Mobile System

모바일 시스템은 일반적으로 스와핑을 지원하지 않는다. 메모리 공간이 부족해서 스와핑을 하기 보단 종료를 해버림

• 모바일 기기는 주로 flash memory를 사용하는데, 이는 저장 공간이 작고, wrtie속도가 느리며 write할 수 있는 횟수가 제한적 → 쓰기를 많이 하면 수명 단축
• 그래서 swap out보단 종료해버리기

각 모바일 운영체제는 메모리 공간이 부족할 때 아래와 같은 방법을 사용한다.

• IOS
  • 애플리케이션이 메모리를 자발적으로 반납하도록 요청
  • 가급적 read-only 데이터를 삭제 (write 데이터는 꼭 하위 계층에 저장하고 삭제)
  • 메모리 해제 안하면 애플리케이션 종료
• Android
  • 애플리케이션 종료
  • 종료 전 상태를 플래시에 기록하여 빠른 재시작 가능하게 함

with paging

페이지 단위의 프로세스라면 backing store에서 페이지들이 swap in/out된다. → page in/out

🔹Intel Architectures

하드웨어적으로(Intel CPU) 메모리 관리를 지원하는 예시

Intel CPU 32bit

• segmentation, paging 지원
  • paging은 일정한 크기로 쪼개는 반면에, segmentation은 성질(text, data, stack등)에 따라 다른 크기로 쪼갬
  • segment table은 logical 시작 주소를 physical 시작 주소로 바꿔준다. (page table은 logical 주소를 physical주소로 바꿔줬음)
    • LDT(local descriptor table): private segment table
    • GDT(global descriptor table): 프로세스가 공유 가능한 segment table
• 둘을 융합한 segmentation with paging 지원

주소 변환 과정

• CPU가 logical 주소를 생성하고, 이는 segmentation unit에 전달되어 linear 주소로 변환된다.
• linear 주소는 paging unit에 전달되어 physical 주소로 변환된다.
  • 이때 page의 크기는 4kb 또는 4MB
  • segment를 page로 관리하는 2 level 기법

segment number로 segment table 인덱싱해서 시작 주소를 얻음. 이를 offset과 더해서 liner 주소로 변환

작은 page는 2 level로, 큰 page는 1level로 paging하여 physical 주소 얻음

Page address extension (PAE)

• 32비트 주소 한계로 인해 도입
  • 32bit address는 4GB의 메모리 공간 사용 가능
• 3 level의 paging으로 변경하고.. 어쩌구해서 4bit가 증가된 36bit address 공간으로 바꿈 → 64GB 메모리 공간 사용 가능 (16배)
  
  

Intel CPU 64bit

• 64bit 주소 공간 → 16exabytes로 매우 큰 메모리 공간을 사용 가능하지만 다 쓰진 않고 48bit의 주소 공간만 사용한다.
  • PAE를 쓰면 virtual address 48bit, physical address 52bit
• 페이지의 크기는 필요에 따라 4kb, 2mb, 1gb 사용 가능
• 4 level paging
  

🔹ARM Architecture

모바일에서 많이 사용되는 아키텍처(칩)

• 저전력 중점
• paging 지원
  • 4kb, 16kb
  • 1mb, 16mb의 큰 페이지는 section이라고 부름
• 작은 페이지는 2level, 큰 페이지는 1level
• TLBs(캐시) 사용