[OS][운영체제] 8. Memory Management / 메모리 관리

1. Background

2. Swapping

3. Contiguous Allocation

4. Paging

5. Segmentation

6. Segmentation with Paging

---

1. Background

- 모든 프로그램은 실행하기 위해 디스크(Input queue)에서 메모리로 올라와야 한다.

 

- 메모리로 올리기 위해 주소 바인딩(binding) 작업이 이뤄져야 한다.

이는 다음과 같은 세가지 경우가 있다.

• Compile-time
  • : 메모리 위치를 안다면 absolute code 생성
  • : 시작 위치가 변경되면 recompile
• Load-time
  • : relocatable code(재배치 코드) 생성
  • : 이는 임시 코드이므로 바인딩 작업이 지연이 됨
• Execution-time
  • : 프로세스가 다른 메모리 영역으로 위치 이동할 때 최종 바인딩 작업은 execution 시에 일어남
  • : base, limit 레지스터 같은 하드웨어 지원이 필요

[사진 1] Address binding

- Compile-time 혹은 Load-time에서 Logical, Physical 주소는 같지만, Execution-time 주소 바인딩 때는 다르다.

• Logical address
  • : CPU에 의해 발생한 가상 주소
• Physical address
  • : 메모리의 주소

- MMU(Memory-Management): 하드웨어 장치, 가상 주소를 피지컬 주소로 메핑하는 하드웨어이다.

[사진 2] MMU

- Dynamic Loading: 사용하는 루틴만 loading 함으로써 메모리 공간 활용을 효율적으로 할 수 있도록 한다.

[사진 3] Dynamic Loading

- Dynamic Linking: Execution-time까지 linking 을 지연시킨다.

이 때 Stub 을 이용하여 루틴의 주소정보를 기록하고, 이를 실행한다.

OS는 루틴이 프로세스 메모리 주소에 있는지 체크한다.

[사진 4] Dynamic Linking

 2. Swapping

메모리에 공간이 한정적이므로 많은 프로세스를 수용하기 위해 공간을 하드디스크(백업장치)로 내려보내고(swap out, roll out),

후에 실행시킬 때 메모리로 가져올라온다(swap in, roll in).

이는 우선순위를 기반 스케줄링 알고리즘으로 이뤄지고,

swap time 은 거의 transfer time 이다.

[사진 5] Swapping

 3. Contiguous Allocation

우선, 메인 메모리는 다음과 같이 두 영역으로 나뉜다.

• Resident OS
  • : 운영체제가 사용하는 파트
  • : low 메모리 + 인터럽트 벡터
• User processes
  • : 사용자 프로세스가 사용하는 파트
  • : high

 - Single-partition 할당

: 한 덩어리로 된 빈 메모리 공간을 할당해주는 기법

이 때 레지스터로 어느 한 프로세스의 시작 physical 주소값을 표시(Relocation register; Base register)하고,

logical 주소의 할당된 범위를 표시(Limit register)한다.

-> 유저 프로세스를 다른 프로세스의 code, data 변경 등으로부터 보호한다.

 

[사진 6] base, limit 값

[사진 7] Single Partition 할당

- Multiple-partition 할당

쓸 수 있는 비어있는 메모리를 Hole이라고 한다.

프로세스가 오면 수용가능한(큰) hole의 메모리를 할당해준다.

이 때 OS는 누가 어느 공간을 쓰고 hole이 어디 있음을 관리한다.

이에는 다음과 같은 방법이 있다.

• First-fit
  • : 수용가능한 hole 중에 첫 hole 사용
  • : 시간측면에서 좋음
• Best-fit
  • : 남는 부분이 최소인 부분을 찾아 사용
  • : 전체 리스트를 searching 함
  • : 자원 활용 측면에서 좋음
• Worst-fot
  • : 가장 큰 규모의 hole을 사용 (남는 부분을 또다른 hole로 관리할 수 있도록)
  • : 전체 리스트를 searching 함

- Fragmentation(조각) 개념

• External Fragmentation(외부 조각)
  • : 프로세스가 달라고 한 메모리 공간을 여기저기 조금씩 쪼개서 할당
• Internal Fragmentation(내부 조각, 내부 단편화)
  • : 요청된 메모리보다 큰 메모리를 할당시켜줌

Compaction 하여, 외부 조각(External fragmentation)을 줄인다.

Compaction은 Execution-time에 dynamic relocation으로 프로세스를 밀어 큰 hole을 만드는 방법이다.

-> I/O 문제) return 값을 엉뚱한 곳에 write하게 됨

-> I/O 작업을 모두 OS 버퍼로 return 한다

4. Paging

Paging은 바둑판처럼 쪼개진 메모리 공간을 말한다.

바둑판 한 칸 한 칸을 physical 메모리는 Frame / logical 메모리는 Page라고 한다.

 

어느 logical page는 어느 physical frame으로 할당되는지 Page Table에 설정한다.

내부 조각(Internal fragmentation)이 있고, 각각의 프로세스는 각각의 Page Table을 갖는다.

 

주소 변환 과정을 살펴보자.

CPU로 생성되는 주소는 다음과 같이 나뉜다.

• 앞쪽의 Page number(p)
• 뒤쪽의 Page offset(d)

[사진 8] Paging

[사진 9] paging

- 페이지 테이블(Page Table) 구현

페이지 테이블은 메인 메모리에 있으며,

PTBR(Page-table base register)이 가리키고,

PRLR(Page-table length register)이 사이즈를 나타낸다.

-> 문제) 이는 각 데이터와 명령이 두 가지의 정보가 필요하게 됨

-> TLB(Translation Look-aside Buffers) 또는 Associative 메모리라고 불리는 하드웨어 캐시를 사용한다.

 

Associative Memory는 Page #의 주소를 찾고, Frame #을 메모리로 가져가는 Parallel search 메모리다.

[사진 10] Associative Memory

[사진 11] page table

이의 Effective Access Time(EAT)은 다음과 같다.

Associative를 찾는 시간이 ε(충분히 작은 수)이고,

메모리 사이클을 도는 시간이 1msec이고,

Page number를 찾을 확률이 α이라면,

EAT은

= (1 + ε) α + (2 + ε)(1 – α)         //한번에 찾는 경우 + 못찾았을 때 한 번 더 도는 경우

= 2 + ε – α

이다.

- 메모리 보호

메모리 보호는 각 frame에서의 Associating Protection Bit으로 시행된다.

유효한 page에는 v, 유효하지 않은 페이지 (logical 주소를 벗어남) 에는 i를 지정하여 표시한다.

[사진12] Associating Protection Bit

- Page Table의 구조

Hierarchical Page Tables

logical 주소를 여러 개의 페이지 테이블로 쪼갠다.

간단하게 two-level Page Table을 살펴보자.

 

예를 들어 32-bit 머신, 4K page 크기라면

12bits(2^12 > 4K)가 page offset으로 구성되고 /

나머지 20bits가 page number로 구성된다.

이는 다시 10bits씩 outer page table의 값 / 그 page table 내의 displacement를 나타낸다.

[사진 13] 계층적 page table

Hashed Page Tables

보통 32bits로 hash function을 거쳐 hash table에 매핑된다.

 

예를 들어, 10으로 나눈 값인 0~9로 포인터(chain)을 쫓아가며 frame number( r )을 찾을 수 있고, ( d )를 붙여 physical 메모리에 저장한다.

[사진 14] Hash page table

Inverted Page Tables

이는 메모리의 각 frame마다 하나의 entry가 있다.

모든 프로세스의 page 정보가 한 page table에서 관리되므로,

메모리 공간은 적게 차지할 수 있으나

search하고 매핑하는 데에 시간소요 길어진다.

[사진 15] 거꾸로 된 page table

 - Shared Page

프로세스들 사이에서 공유되는 Shared Page 코드(read-only)는 각 프로세스들 logical 주소의 같은 위치에 있다.

Shared Pages에는 각 프로세스의 private 코드와 데이터가 존재한다.

[사진 16] 공유 page

5. Segmentation

프로그램의 모든 구성요소가 한 덩어리일 필요 없다.

메모리를 볼 때 user view로 관리하는 방법으로 다음 과 같은 logical unit이다.

main program / procedure / function / method / object / local variables / global variables / common block / stack / symbol table / arrays

 

각각을 Segment table에서 관리한다.

• base
  • : 시작 주소 정보 (segment table’s location)
  • -> STBR에 저장
• limit
  • : segment의 수 지정 (> 현재 segment 수)
  • -> STLR에 저장

[사진 17] segment table

 

- 세그먼트 테이블 통해(base값을 바꿔) dynamic relocation하여 physical 메모리에 할당한다.

- 세그먼트 단위로 공유한다.

- Allocation 할 때 hole 정해서 할당하고,

external fragmentation -> compaction 하여 해결한다.

- 세그먼트 단위로 보호한다.

-> validation bit = 0이면 illegal segment

-> read/write/execute 권한

[사진 18] Sharing of Segments

6. Segmentation with Paging

MULTICS라는 운영체제 시스템에서 사용하는 방법으로,

external fragmentation 문제와 paging에 의한 search time 문제를 해결한다.

segment table에서 base 주소가 아닌 page table의 base 주소를 넣으며 구현한다.

[사진 19] Segmentation with Paging

segment table 길이가 더 크면 -> d를 페이지단위로 쪼갠다 -> 쪼갠 p값을 더해 프레임 넘버 값을 만들고 -> physical address에 할당한다.

3개의 frame과 979번째 워드에 할당(d’값)