[OS Chapter 8] Memory Management

Address

Logical address(= virtual address)

• 논리적 주소
• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소는 logical address임

Physical address

• 실제 메모리 주소 

---

주소 바인딩(Address Binding)

주소 바인딩(주소 결정) - Symbolic Address -> Logical Address -> Physi cal address

 

주소 바인딩이 언제 발생하는가?

출처: 강의

1. Compile time binding

• 컴파일 시점에 물리적 메모리 주소가 결정
• 컴파일러는 절대코드(absolute code)를 생성

2. Load time binding

• Loader가 물리적 메모리 주소를 부여
• 컴파일러가 재배치 가능 코드(relocatable code)를 생성

 

3. Execution time binding(=Run time binding)

• Load될 때 변환되는건 같지만 실행 도중 메모리주소가 이동 될 수 있음
• CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
• 하드웨어적인 지원이 필요(MMU)
• 현대 바인딩 개념이다.

---

Memory-Management Unit(MMU)

: logical address를 physical addrees로 매핑해주는 하드웨어 장비

 

Dynamic location

출처: https://jhi93.github.io/category/os/2019-12-20-operatingsystem-08-1/

• register 2개를 가지고 변환을 함
• relocation register(=base register)와 limit register
  • relocation register(=base register) - 접근할 수 있는 물리적 메모리 주소의 최소값
  • limit register - 논리적 주소의 범위

• logical address + relocation register값 을 더해서 시작위치를 얻게 됨
• limit register는 프로그램의 최대 크기로 첫번째로 체크하는 조건이다.

사용자 프로그램은 logical address만 다룬다. 실제 physical address를 다룰 필요가 없다.

---

용어 설명

Dynamic Loading

• 프로세스 전체를 메모리에 다 올리는 것이 아닌 해당 루틴이 불려질 때 메모리에 load 하는 것
• memory utilization 향상
• 운영체제는 라이브러리를 통한 지원

 

Overlays

• 메모리의 실제 필요한 정보만 load한다.
• Dynamic loading과의 차이점은 프로그래머가 수작업으로 한다는 점이다.

Swapping

• 프로세스를 일시적으로 메모리에서 backing store(=swap area)로 쫓아 내는 것
• backing store(=swap area): 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• swap in / swap out
  • 중기스케줄러(=swapper)가 swap out할 프로세스를 선정
  • priority기준으로 swap out한다.
  • swap time은 대부분 transfer time(swap 되는 양에 비례하는 시간)임

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법
• static
  • 프로그램의 실행 파일 코드에 포함됨
• dynamic
  • 라이브러리가 실행시 연결되어 실행
  • 이미 메모리에 있으면 루틴의 주소로 가고 아니면 디스크에서 가져옴
• 실행 파일 내에 포함되어있냐 없냐의 관점으로 살펴보면 됨.

---

Allocation of Physical Memory

두 영역으로 나뉨

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

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

• Contiguous allocation
  • 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것 
  • Fixed partition allocation
  • Variable partition allocation
• NonContiguous allocation
  • 하나의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
  • Paging
  • Segmentation
  • Paged Segmentation

사용자 프로세스 영역에서 메모리할당 방법들을 각각 아래에서 설명하겠습니다.

---

Contiguous Allcation(연속 할당)

고정 분할 방식(Fixed partition allocation)

출처: https://0eun.tistory.com/94

• 물리적 메모리가 영구적 분할(partition) 됨
• 고정된 크기내에 프로그램이 들어간다
• 낭비되는 메모리가 생긴다.
  • 외부조각(External fragmentation): 프로그램 크기보다 분할의 크기가 작은 경우
  • 내부조각(Internal fragmentation): 프로그램 크기보다 분할의 크기가 큰 경우 

 

가변 분할 방식(Variable partition allocation)

출처: https://0eun.tistory.com/94

• 프로그램이 실행될때마다 순서대로 차곡차곡 올려놓는 방법
• 가변방식을 쓰더라도 외부조각은 생긴다. 내부조각은 안생긴다.

Hole

• 가용 메모리 공간
• 운영체제는 할당공간과, 가용 공간(hole)의 정보를 유지

Dynamic Storage-Allocation Problem

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

 

• First-fit
  • 사이즈가 n이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit
  • 사이즈가 n이상인 것중 가장 근접한 hole을 찾아서 할당
  • 모든 hole을 검색해야함
• worst-fit
  • 가장 큰 hole에 할당

=> first-fit이 실험적인 결과로서 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐.

 

* compaction

• 외부 조각 문제를 해결하는 방법
• 사용중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block으로 만드는 과정
• 매우 비용이 많은 문제로 최소한의 비용으로 메모리를 이동시키는 것은 매우 어려움

---

Noncontiguous allocation(비연속적 할당)

: 메모리의 여러 영역에 분산되어 올라갈 수 있음

 

Paging

출처: https://medium.com/@esmerycornielle/memory-management-paging-43b85abe6d2f

• Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
• Virtual memory의 내용이 page단위로 noncontiguous하게 저장됨
• 페이지의 크기에 따라 외부조각이 발생할 수 있음.
• page table은 논리적 페이지의 개수만큼 존재
• 각각의 페이지의 엔트리에는 논리적페이지 -> 물리적페이지의 번호를 담고 있음

• 다른 그림으로 살펴본 것으로써
• p는 페이지 번호로서 page table에서 f(frame number)를 찾기 위한 숫자이다.
• d는 offset으로 상대적인 주소로서 logical이나 physical address 둘다 같은 offset을 가진다.

page table

• page table은 메인 메모리에 상주
• Page-table base register(PTBR)가 page table을 가리킴
• Page-table length register(PTLR)가 테이블 크기를 보관
• 모든 메모리 접근 연산은 2번의 메모리 접근이 필요(page table 1번, data/instruction 1번)

TLB

• 메인메모리와 CPU사이에  TLB라는 별도의 하드웨어를 둠
• 메모리 접근을 줄이기 위함
• 주소변환을 위한 캐시메모리
• TLB는 Associative registers를 통해 구현하여 parellel하게 검색하여 TLB를 전체 탐색함.
• TLB는 context switch할 때 entry를 비워줘야 한다.

주의! page table은 parellel한 검색이 필요없다 sequential하게 찾기 때문이다.

TLB를 포함한 Paging

출처: https://dailyheumsi.tistory.com/138

• page table이 실제로는 physical memory에 존재함
• page number가 TLB에 있으면 변환 후 물리적 메모리 접근
• 없으면 page table로 메모리 접근 후 물리적 메모리 접근
• 논리적 페이지 / 물리적 페이지의 쌍을 갖고 있음

---

Two-Level Page Table(2단계 페이지 테이블)

페이지 테이블이 하나 더 존재하는 것이다.

출처: https://dailyheumsi.tistory.com/138

 

왜 사용하느냐? 속도는 줄어들지 않는다. 공간이 더 줄어든다.

 

32bit address 체계기준

• 0 ~ 2^32 - 1까지 존재  = 4GB  주소공간
• page size가 4k면 1M개의 페이지 엔트리 개수가 필요
• 각 page entry가 4byte이면 4M page table이 필요하게 됨
• 그러나, 대부분의 프로그램은 4G의 주소공간중 일부만 사용하므로 page table 공간이 낭비

전체 메모리중에서 실제 프로그램이 사용하는 공간이 크지 않으므로, 2단계 페이지 테이블을 사용함

출처: https://slideplayer.com/slide/6026617/

• p1으로 outer page table(바깥 테이블) 찾고  p2로 내부 테이블 찾음
• 내부테이블은 페이지크기와 같음
  • 페이지테이블 4kb 페이지 엔트리 4byte로 1k개만큼 들어갈 수 있다.
• offset bit
  • 4kb 페이지 크기를 구분할려면 2^12승이 필요 = 12bit
• p2 bit
  • 각 페이지블록은 4byte의 엔트리가 1k개로 4kb로 구성되어있음
  • 1k개의 페이지를 구분하기 위해선 10bit가 필요
• p1 bit는 자동으로 나머지 bit이다.

실제로  상당부분의 주소는 사용이 안된다.

outer-page table은 다 존재하지만 page table을 사용하지 않으면 내부 페이지로 향하는 포인터를 NULL값으로 만든다.

 

Multilevel Paging and Perfomance

address space가 더 커지면 다단계 페이지 테이블이 필요

TLB를 통해 메모리 접근 시간을 줄일 수 있음

---

bit in page table

valid(v) invalid(i) bit

출처: https://woodforest.tistory.com/10

• page table은 모든 엔트리가 다 만들어 진다.
• valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함
• invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함
  • 주소 부분을 사용하지 않거나
  • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

protection bit

• page에 대한 접근 권한(read/write/read-only)
• code같은 경우는 내용이 바뀌면 안되기 때문이다.(read-only)

---

Inverted Page Table

출처: https://baked-corn.tistory.com/17

• 프로세스마다 존재하던 page table을 시스템 내에 하나에 존재
• physical address를 보고 logical address를 구함
• page table의 공간을 줄이고자 씀. 하지만 주소검색을 위해 전체를 검색해야함
• TLB처럼 associative register를 사용함
• pagetable에 어떤 process인지 설명하는 pid도 들어가야함

---

Shared Page

출처: https://woodforest.tistory.com/10

• 공유할 수 있는 코드(=Re-entrant code, pure code, shared code)들은 같은 물리적 메모리에 올리는 것이다.
• 코드가 read-only로 설정되어 있어야 한다.
• shared code는 모든 프로세스에서 같은 logical address space에서 동일한 위치에 있어야 함.

---

Segmentation

출처: https://www.geeksforgeeks.org/segmentation-in-operating-system/

• 프로그램은 의미 단위인 여러 개의 segment로 구분
• segment table - base(세그먼트의 물리적 메모리 시작주소), limit(세그먼트의 길이) 
• segment-table base register - 물리적 메모리에서의 segment table의 위치
• segment-table length register - 프로그램이 사용하는 segment의 수 
• segmentation은 base와 limit으로 정확한 메모리 주소가 주어져야함
• 할당 부분에서 크기가 균일하지 않기때문에 외부조각이 발생함
• 의미단위로 일하는 것에 효과적임 (공유와 보안)
• paging은 최대 영역만큼 만들어지는데 세그먼트 테이블은 세그먼트의 개수에 따라 정해짐
• offset이 limit보다 큰지 작은지 비교해보고 범위 내에 있으면 변환
• 테이블을 위한 메모리 낭비는 segmentation이 더 낮다.

세그먼트의 공유: 같은 논리적 주소를 가지고 있어야 한다.

---

Paged Segmentation

: segment를 여러개의 page로 구성하는 기법

출처: https://www.gatevidyalay.com/segmentation-and-paging-segmented-paging/

 

• segmentation에 대한 주소 변환을하면 page table의 base address를 가지고 있음
• 의미적인 부분은 segment를 진행하고 물리적 메모리에 올라갈 때는 page단위로 올라감.
• 첫번째 d는 offset 이걸 또 나누어 page 번호와 offset으로 또 나눈다.

 

여기까진 물리적 메모리 관리이다. 주소변환이 핵심!

주소변환에 있어 운영체제의 역할은 없고 전부 하드웨어가 진행한다.