9. Main Memory

1. Background

프로세스는 실행 중인 프로그램을 말하는데 역기서 실행 중이라는 말은 main memory에 올라갔다는 뜻이다.

main memory와 register는 cpu가 직접 접근할 수 있는 유일한 저장소이다.

메모리 단위는 address+read요청 또는 address+data and write 요청만 처리한다.

main memory는 많은 cycle을 소모하여 stall을 초래한다.(약 100cycle)

cache는 main memory와 cpu register 사이 위치한다.

 

protection

프로세스를 다른 프로세스로부터 보호한다.

모든 프로세스는 해당 프로세스의 address process 내에 있는 주소에만 접근할 수 있어야 한다.

 

logical(논리적) address space를 정의하는 base register와 limit register를 사용해 보호한다.

→ Hardware address protection: base와 limit register를 load 하는 특권 명령어 이다. CPU는 user모드에서 생성된 모든 멤버로 접근이 해당 user에 대한 base와 limit register 사이에 있는지 확인해야 한다.

 Address Binding(주소 바인딩)

프로그램은 바이너리실행파일로 disk에 머무르다 실행되면 memory로 가져와서 process context내에 배치해야 한다. 

 

address(주소)는 각 stage마다 다른 방법으로 표현된다.

• source code: symbolic
• compiled code: bind to relocatable address(재배치 가능한 주소)
• Linker or loader: 재배치 가능 주소를 absolute주소(절대주소)로 바인딩

명령어와 데이터의 memory binding

• compile time: 메모리 위치 미리 알고 있으면 absolute code 생성 가능
• load time: 메모리 위치 컴파일 시간에 알 수 없으면 relocatable code 생성
• execution time: 메모리 세그먼트 간 이동 가능한 경우 바인딩을 execution(실행시간)까지 delay(지연)시킨다.

 

Logical Address vs Physical Address

logical address(논리주소): CPU에 의해 생성된 주소로 virtual address라고도 한다.

physical address(물리주소): 메모리 단위에서 보이는 주소.

 

논리주소를 물리주소에 mapping 하기 위해서는 논리적 주소공간과 물리적 주소공간이 분리되어야 한다. 

 

2. Address Space (주소공간)

 

Memory Virualization(메모리 가상화)

OS는 물리적 메모리를 가상화하여 각 프로세스가 전체 메모리를 사용하는 것처럼 보이게 한다.

목표

• 투명성(transparency): 프로세스는 메모리가 공유된다는 것을 인지하지 못해야 한다. 
• 효율성(efficiency): space측면- variable크기요청으로 fragmentation(단편화) 최소화, time측면 - HW 지원받는다. 
• 보호성(protection): isolation(고립)으로 인해 다른 프로세스에 영향 주지 않고 fail가능. 다른 프로세스로부터 보호.

초기 OS

memory에 단 하나의 process만 load 하여 실행 : 메모리 사용률과 효율성이 낮다

↓

multiprogramming과 Time Sharing

memory에 여러 process load하여 짧은 시간 동안 실행하고 프로세스 간 switching 해 메모리 사용률과 효율성을 높인다.

문제점: protection(보호) 문제가 발생한다. 다른 프로세스로부터의 잘못된 메모리 접근 때문에.

 

주소공간(Address Space)

physical memory의 추상화(abstraction)를 os가 생성한다. [ (logical) Address space -> os -> physical memory]

ex. 16KB의 주소공간 = 14bit의 주소공간

 

또 다른 예시로 32bit 시스템의 주소공간은 32bit,

64bit 시스템의 주소공간은 64bit(48 bit)이다.

 

 

• code: 명령어가 저장되는 곳
• heap: 동적메모리 할당을 위한 공간, malloc, new
• stack: 반환 주소나 값이 저장, 지역변수나 함수인자 저장

 

 

 

 

      - Logical Address(논리주소)

       : 실행 중인 프로그램의 모든 주소는 논리 주소이다. 

         OS는 논리주소를 물리주소로 변환 [ Logical address -> OS -> Physical address]

 

3. Memory API

malloc()

heap에 메모리영역 할당

brk(), sbrk() 시스템콜 이용

 

sizeof()

malloc에 크기 직접 입력하는 대신 routine과 macro이용해 크기결정

 

free()

malloc으로 할당된 메모리 영역을 해제한다.

 

Memory allocation 에러

->해결! malloc이용

 

4. Address Translation (주소변환)

메모리 가상화: 효율성과 제어를 위해 Limited Direct Execution(LDE) 전략 사용, HW 지원을 받음

 

Address Translation

H/W는 logical을 physical주소로 변환한다.

OS는 특정지점에서 하드웨어를 설정하고 메모리를 관리해 어느 공간이 free이고 use인지 추적해야 한다.

 

초기 가정: user의 주소공간은 물리메모리에서 연속적으로 배치되어야 하고 

                 주소공간의 크기는 더 작아야 하고 (물리메모리보다)

                 각 주소공간의 크기는 동일해야 한다.

 

ex. 메모리에서 값 load 하고, 3을 더한 후, 다시 메모리에 store 한다.  -> memory access 5번!

void func() {
    int x;
    ...
    x = x + 3; // 이 부분의 코드가 관심 대상입니다.
}

 

Relocation Address Space(재배치된 주소 공간)

• Static Relocation

sw기반의 재배치로 os가 프로그램을 메모리에 load 하기 전에 각 프로그램을 재작성한다.
장점: 하드웨어 지원 필요 없다
단점: 보호가 잘 안 된다( no protection, no privacy)
         주소공간 배치한 후에는 위치를 바꿀 수 없다.
          -> external fragmentation(외부 단편화)으로 인해 새로운 프로세스 할당할 수 없을 수 있다. 

• Dynamic Relocation

hw기반의 재배치로, MMU(Memory Management Unit)가 모든 메모리 참조 명령어에 대해 주소변환을 수행한다.
보호가 hw에 의해 강제된다. 
OS relocation register가 존재해 주소공간정보를 MMU에 전달한다.

 

Base and Limit Register

Base register: 주소공간 시작위치 저장

Limit Register: 접근가능한 주소공간의 크기 정의

 

OS문제: Context Switch 발생할 때

OS는 base와 limit 레지스터를 쌍으로 저장하고 복원해야 한다.

context switch시 새로운 프로세스가 cpu에 배치되면 이전 프로세스의 base와 limit 레지스터 값을 저장하고 새로운 process값을 복원한다.

 

5. Contiguous Allocation(연속 할당)

Main memory는 OS와 user process 둘 다 지원해야 한다.

• OS 있는 곳 (low memory)
• user process 있는 곳 (high memory)

프로세스를 단일구역(single section)에 할당한다. 여러 구역에 나눠서가 아니라 한 구역에 할당하기 때문에 연속적이다.

 

이때 메모리 보호(protection)는 Relocation register을 통해 이루어진다.

- base 레지스터는 작은 물리주소 값을, limit레지스터는 논리주소의 범위를 포함한다

 

variable partition 사이즈가 효율성을 위해 좋다.

하지만 프로세스의 할당과 해제를 반복하다 보면 빈 공간인 hole이 생긴다.

 

결국 이 hole을 어떻게 관리하는 것이 하나의 이슈가 되었다.

 

저장공간에 동적으로 메모리를 할당할 때, 여러 구멍들 중 크기 n만큼의 메모리를 어느 구멍에 할당할지에 대한 문제가 발생한다.

아래는 3가지 해결방법이다

• first-fit: 할당할 수 있는 가장 첫 번째 구멍(크기만 맞으면 됨)
• best-fit: 가장 작은 구멍
• worst-fit: 가장 큰 구멍

 

Fragmentation(단편화 문제)

• External fragmentation(외부단편화): 메모리공간이 연속적이지 않아서 메모리할당요청받을 수 없는 상태                                                                               -> 연속 할당 시 문제                                                                                                                                                           해결책! 동적일 때 compaction(압축)으로 문제 줄일 수 있다.
• Internal fragmentation(내부단편화): 빈 공간에 메모리를 할당한 후 공간이 남아 다른 메모리를 할당할 수 없는 상태                                                                -> 페이징시 문제

 

6. Paging

프로세스의 물리적 주소 공간을 불연속적으로 쪼개서 관리하는 것. 
외부단편화 문제를 해결할 수 있다.

물리메모리는 동일한 크기의 frame으로,

논리메모리는 동일한 크기의 page로 나눈다.

 

아직 내부단편화문제는 있다.

 

p번 페이지에 있는 d번째 메모리에 할당해줘! 하면 주소 넘겨진다. 논리주소공간은 2^이고 page사이즈는 2^n이다.

 

논리주소를 실제 물리주소로 변환하기 위해 page table 사용한다.

virtual address 21 in 64 byte주소공간

 

paging of logical and physical memory

Page Table 작동법

page table은 main memory에 있다. 

page table은 os로부터 관리되고, MMU가 접근해서 읽는다.

그래서 PTBR과 PTLR 이 위치와 크기를 나타낸다.

• Page-table Base Register(PTBR) : 페이지 테이블의 시작주소(Page Table Entry, PTE)를 가리킨다.
• Page-table Length Register(PTLR): 페이지 테이블의 크기를 나타낸다.

그런데 문제는... page table 찾으려고 매번 memory access 한번 더 해야 해! 너무 느리다...

그래서 이런 페이징의 단점을 보완하기 위해 TLB라는 장치를 만들었다.

 

TLB(Translation Lookaside Buffer)

최근에 translation 했던 page에 대한 물리적 정보를 담는 buffer이다.

 

TLB는 cache메모리 이기 때문에 매우 빠른 속도로 메모리에 접근한다. 

TLB는 하드웨어에서 작동한다.

full assosiative memory로 구성된다. 

page table에 접근하기 전에 먼저 TLB에 접근하고, miss가 나오면 그제야 page table에 접근한다. -> 다음번에 더 빨라져

Context switch 문제가 발생할 땐 TLB에 ASIDs(Address-space Identifier) 넣는다.

 

결국 TLB hit가 얼마나 발생했는지에 따른 hit ratio에 따라 EAT(Effective Access Time)가 달라진다.

EAT=Hit + miss

 

공유 페이지(shared page)

때로는 페이지도 공유해서 읽을 수가 있다.

read-only로 코드를 올려 에러를 방지한다.

재진입가능한 코드(reentrant code)라면 프로세스끼리 공유하는 게 좋다.

재진입가능한 코드란 실행 중에 스스로 수정될 일이 없는 코드를 말한다.

 

8. Page Table Structure

문제: page table이 너무 크다!

 

① Linear page table

모든 virtual address의 page를 순서대로 다 담아놓은 page table
너무 크다
-> page를 더 크게 한다: big page는 내부단편화문제를 일으킨다.

 

문제점! 단일 페이지 테이블이 주소 공간 전체에 대한 엔트리를 가지는 것인데 이때 대부분의 엔트리를 invalid로 사용되지 않는다. 그렇다면!

② Multi-level page table : page directory

linear page table을 tree처럼 바꾼다.
유효한 페이지 테이블만 추적해서 page directory에 page directory entry(PDE) 넣는다.
장점: 사용하는 주소공간만 page table에 할당한다, 다음 free page를 os가 잡을 수 있다.
단점: 복잡하다, time-space trade-off

③ Inverted Page Table(역페이지테이블)

반대로 Physical address를 보고 Virtual address를 찾는 방식
pid(process identifier)를 추가하여 해당 pid의 페이지를 역으로 저장한다.
장점: 프로세스마다 page table을 안 만들어도 된다.
단점: 수백만 개의 entry로 늘어날 수 있다.
해결책! 하나의 entry만 메모리의 real page에 유지한다.

 

9. Swapping

프로세스가 실행되기 위해서는 memory에 있어야 하지만 프로세스는 실행 중에 임시로 backup store로 내보내어졌다가 실행을 계속하기 위해 다시 memory에 되돌아올 수 있다.

스와핑을 통해 실제 물리 주소 공간의 크기보다 훨씬 큰 프로세스도 문제없이 실행할 수 있다.

 

swap in 해서 메모리에 올리고, 다른 작업을 수행해야 하는 경우 swap out 한다. 이후 다시 필요할 때 메모리에 다시 올릴 수 있다.