[Operating System] Memory Management 1

memory management의 목적

1. program이 동작하기 위해
   ⇒ cpu는 main memory와 register에만 직접적으로 접근할 수 있기 때문에 program이 실행되기 위해서는 반드시 main memory에 적재되어야 한다.
2. memory를 효율적으로 사용하기 위해

program의 실행 과정

1. preprocessing(cpp)
   • main.i 생성
   • header 및 define 내용을 source file에 추가하는 역할
2. compile
   • main.s 생성
   • high language를 assembly language로 변환
   • compiler의 역할
3. assembly
   • main.o 생성
   • assembly lanugage를 machine language로 변환
   • assembler의 역할
4. linking
   • executable object file 생성
   • 여러 object file을 묶는 역할
     ⇒ 각 파일에서 다른 파일의 함수를 호출하거나 전역 변수에 접근하는 부분에 주소를 할당
   • linker의 역할
5. loading
   • executable object file을 memory에 적재
   • loader의 역할

Binding of Instructions and Data to Memory

binding : program에 memory address를 부여하는 행위

Compile time binding

compile될 때 program의 주소를 부여

• compile 시 program의 주소를 부여하기 때문에, 다른 device에서 실행하기 위해서 프로그램을 다시 compile해야 한다
• 해당 process가 실행될 때 어디로 할당될 지를 미리 알아야 한다.
  • multi program이 지원되지 않는 os에서 사용될 수 있다.
    ⇒ 무조건 user process가 1개이기 때문에 kernel process가 끝난 지점의 주소값을 그대로 할당하면 된다.

Load time binding

program이 실행될 때 주소를 부여

• 한번 load되면 메모리를 재할당할 수 없다.
  ⇒ swap 발생 시 문제가 된다.
• load되기 전까지는 memory 주소를 0번지(relocatable code)로 놔둔다.

Execution time binding

program이 memory에 적재될 때 주소를 부여

• memory에 올라오기 전까지 relocatable code로 놔둔다.
• 실제 memory에 올라오기 전까지 relocatable code이기 때문에 cpu가 memory에 접근할 때, 상대주소를 이용해 접근
• 따라서 OS가 상대주소를 적절한 실제주소로 바꿔주는 과정이 필요
  ⇒ cpu가 memory에 접근할 때마다 주소를 변환해줘야 하기 때문에 overhead가 매우 크다.
• overhead를 줄이고 속도를 개선하기 위해 주소 변환을 위한 별도의 HW를 둔다.(MMU)
• MMU가 상대주소를 절대주소로 변환하기 위해 각 process마다 별도의 base, limit register를 갖고 있다.

Logical vs Physical address space

• logical address(virtual address) : cpu가 발생시키는 주소
• physical address : process가 실제 저장되어 있고, memory unit이 접근하는 주소

compile-time binding과 load-time binding의 경우 logical address와 physical address가 서로 같다.

하지만 execution-time binding은 logical address와 physical address가 서로 다르다.

MMU(Memory-Management Unit)

CPU가 발생시키는 user program의 logical address를 실제 physical address로 변환시켜주는 unit

⇒ user program의 실제 physical address를 cpu는 절대 알 수 없다.

 

각 user program의 base(relocation) register, limit register값을 이용해 memory 주소를 변환하게 된다.

1. limit register와 cpu의 logical address의 대소비교를 통해 해당 요청이 잘못된 요청인지를 판단
   • logical address > limit register라면 해당 process가 할당받은 memory 길이보다 더 긴 주소를 요청한 것이기 때문에 오류 발생!
2. logical address에서 각 process의 base(relocation) 주소를 더함으로써 쉽게 physical address를 구할 수 있다.

💡 logical address는 uint로 읽기 때문에 logical address는 항상 양수일 수밖에 없다.

 

Dynamic Storage-Allocation Problem

어느 Hole에 process를 할당한 것인지에 대한 문제

• Hole : memory에서 사용가능한 block 모음

First-fit

process를 적재할 수 있는 첫 번째 hole에 memory를 할당하는 방식

Best-fit

process를 적재할 수 있는 전체 hole 중 채우고 남는 공간이 가장 적은 hole에 할당

• 전체 hole을 search하는데에 overhead가 존재
• 채우고 남는 공간이 너무 작아 더 이상 활용할 수 없게된다는 문제가 발생

Worst-fit

process를 적재할 수 있는 전체 hole 중 채우고 남는 공간이 가장 많은 hole에 할당

• 전체 hole을 search하는데에 overhead가 존재
• 이름과 다르게 채우고 남는 공간이 커 해당 공간을 계속 활용할 수 있다는 장점도 존재

Fragmentation

Hole에서 process를 할당하고 남은 leftover

External fragmentation

아직 할당되지 않은 공간이지만 공간이 너무 작아 다른 process가 할당되지 못 하는 공간

• best fit에 의해 많이 양산된다.
• 논리적으로는 해결이 가능

Internal fragmentation

process에 할당은 되었지만 실제 process가 사용하는 공간보다 크게 할당되어 해당 공간이 process에 의해 사용되지 않는 공간

• 논리적으로 해결이 불가능
  ⇒ 실제 process가 얼마나 공간을 사용하지를 모르고, block을 byte 단위로 쪼갤 수 없기 때문

Compaction

External fragmentation의 문제를 해결하기 위한 방법

모든 process를 0쪽으로 밀어붙여 external fragmentation을 제거하는 방법

 

compaction 방법은 결국 memory 영역 전체를 copy해 다시 순서대로 write하는 과정을 거쳐야 한다.

위 연산은 모두 memory operation이기 때문에 overhead가 너무 심해 실제로 사용할 수 없다.

single partition vs multi partition

single partition : memory에 kernel영역과 user영역 두 가지로만 분리되어 있는 방식

• 각 process마다 별도의 크기를 갖고 memory에 할당된다.
• internal fragmentation은 줄지만, external fragmentation은 증가

multi partition : memory에 kernel영역과 별도의 block 크기의 여러 user 영역으로 분리하는 방식

• 각 process마다 주어진 block의 크기만큼 memory를 할당받는다.
  ⇒ 해당 block보다 더 큰 memory가 요구되는 경우에는 두 block을 merge
• external fragmentation은 줄지만, internal fragmentation은 증가

Paging

이전까지의 MMU는 contiguous allocation을 가정

contiguous allocation에서 multi partition은 process의 max(block size)를 어떻게 설정할 것인가에 대한 문제가 존재

• max가 큰 경우 지나치게 memory가 낭비될 수 있다.
• max가 작은 경우 stack과 heap 사이 공간이 적어 memory 침범이 발생
  ⇒ stack과 heap은 process 실행 시에 결정되는 공간이 아닌, 동적으로 사용되는 공간이기 때문에 block size를 작게 잡게 되면 공간이 부족하게 될 수 있다.

따라서 paging 기법에서는 noncontiguous allocation을 적용한 뒤, process의 max를 최대치로 설정해 위 문제를 해결

⇒ virtual memory에서 위 크기 중 실제 필요한 부분만 memory에 올리는 방식을 사용

1. memory와 process를 fixed-sized blocks으로 모두 쪼갠다.
   • blocked memory : frame, blocked process : page
2. OS는 현재 frame 중 할당 가능한 frame의 list를 유지 : free frame list
3. process가 memory에 적재될 때 각 page를 free frame에 할당
4. 각 process는 자신의 page가 어느 frame에 mapping되어 있는지를 page table에서 관리
   ⇒ MMU에서 address translation에 사용

💡 internal fragmentation은 각 process 당 1 frame에서만 발생하고 external fragmentation은 발생하지 않는다.

Address Translation Scheme in Paging

데이터를 얻기 위해 다음 정보를 확인할 필요가 있다.

1. page가 어느 frame에 있는지 확인
2. 현재 page에서 원하는 데이터가 어디에 있는지 확인

cpu가 발생시킨 data의 logical address로부터 다음 정보를 얻을 수 있다.

1. 해당 데이터가 몇 번째 page에 존재하는지(page number)
   ⇒ logical address/block size의 몫
2. 할당된 page에서 해당 데이터가 어디에 있는지(page offset)
   ⇒ logical address/block size의 나머지

아래와 같이 block size의 bit만큼 bit를 쪼개면 두 값을 한번에 얻을 수 있다.

 

logical address로부터 page number와 page offset를 얻은 뒤, 각 process의 page table을 통해 해당 page가 할당되어 있는 실제 주소를 얻어 page offset과 더해주면 physical address를 얻을 수 있다.

• page table의 경우 순서대로 저장되어 있기 때문에 page number만 알면 random access가 가능
• frame은 4kb 단위로 할당되기 때문에 결국 앞 4kb에 해당하는 부분은 모두 0임을 알 수 있다.
  ⇒ frame의 주소를 4kb로 나누면 나머지가 0이 되어야 하므로 앞 12자리가 0임을 double checking할 수 있다.
• 따라서 page table에서 frame의 주소를 저장할 때에도 앞 12자리를 빼고 나머지 20자리만 저장한 뒤 page offset과 concat해주면 frame address와 page offset을 더해주는 것과 동일하게 된다.

example

• logical address : 2
• page size(block size) : 4-byte = 2bits
• page number : 2/4 = 0
• page offset : 2%4 = 2
• frame address : 5
• physical address : 101 + 10 = 10110 = 22

Free Frames

OS는 내부적으로 free-frame list를 관리

Page Table implementation

• page table은 main memory에 항상 상주해야 한다.
• page-table base register(PTBR)은 page table의 위치를 가리키는 pointer
• page-table length register(PTLR)은 page table의 크기를 나타내는 register로 에러 탐지를 위해 사용된다.

page table의 경우 main memory에 존재하기 때문에 결국 cpu가 주소를 읽어오기까지 총 2번의 memory access가 발생

1. page table에서 frame의 위치를 읽어오는 것
2. frame주소와 page offset을 통해 알아낸 physical address로 실제 접근

즉, 이전 contiguous allocation은 memory access가 1번 발생한 것에 비해 overhead가 2배나 증가

따라서 이러한 memory access overhead를 해소하기 위해 Translation Look-aside buffer(TLB)라는 cache를 이용

TLB(Translation Look-aside Buffer) : associative memory

장점

위 cache도 locality 특성 덕분에 hit ratio가 높기 때문에 유의미한 성능 향상이 있다.

 

단점

page table에서처럼 page number가 연속적으로 저장되어있지 않기 때문에 random access가 불가능하다.

⇒ SW적으로는 search algorithm이 필요하지만 이 역시 overhead가 너무 커 사용할 수 없어 결국 HW로 해결해야 한다.

 

TLB를 parallel search가 가능하도록 설계해 전체 cache table을 동시에 searching하도록 하였다.

💡 TLB 역시 각 process에 맞는 page number와 frame 주소가 다르기 때문에 context switching이 발생하면 flush된다.
따라서 context switching된 직후에는 hit ratio가 낮다!

 

 

Access Time

• TLB lookup : $\alpha$
• memory access time : $\beta$
• hit ratio : $\epsilon$

• $\epsilon=1$인 경우가 최대 성능으로 $EAT = \alpha + \beta$가 된다.
  ⇒ 실제 locality 덕분에 $\epsilon \approx1$에 가깝게 된다.

Memory Protection

process size를 max로 설정했기 때문에 page table의 크기도 max로 할당해줘야 했다.

⇒ 32bit에서의 max page table은 4kb의 page size인 경우에 1MB*(표현 bit)가 된다.

 

따라서 해당 page table에서 현재 process에 할당된 frame과 할당되지 않은 frame을 관리해 접근하지 못 하도록 할 필요가 있다.

 

valid/invild bit

각 page table에 접근 가능 여부 bit를 추가

PTLR

PLTR와 offset의 크기를 비교해 현재 page table을 벗어나는지를 확인

⇒ 위 그림에서 PLTR은 6번을 가리키고 있을 것이므로

Shared Pages

서로 다른 process가 동일한 page를 공유

• page table에서 공유되는 부분의 frame address를 동일한 값으로 설정
• 반드시 공유되는 부분의 logical address space도 동일해야 한다.
  ⇒ self-reference가 발생할 수 있기 때문

즉, page table만 공유하면 자연스럽게 공유가 가능