운영체제의 기초 - 16. Segmentation and Paging 2

내용 정리

과거에는 1 Job이 1 Segment만 받아서 multiprogramming을 했음

이럴경우 뭐가 문제가 되느냐

프로세스의 logical한 unit은 여러개가 있음

linker에서 배웠듯이 Data section도 있고 Code section도 있고 

이것이 수행하게 되면 stack도 있게 됨

얘네들은 access 패턴이 다름

Data section은 Read / Write고 Code section은 Read Only

Code section처럼 Read only 같은 경우 여러 프로세스를 공유하는데

공유를 프로세스당 하나의 세그먼트만 했을 때 효과적으로 할 수 없음

그래서 사람들이 생각한 것이 1 프로세스에 여러개의 세그먼트를 부여하는 것

여러개의 세그먼트를 부여하는 것을 우리가 segmentation이라고 했음

좋긴한데 어떤 문제가 생김

우리가 프로세스 별로 하나의 세그먼트만 있었을 때는

base / bound register 를 이용해서 relocation을 했는데 하나의 register pair만 필요했음

이제는 세그먼트 별로 전부 다 register pair가 필요하게 됨 그래서 segment table이 등장

세그먼트 테이블은 physical 메모리에 map되지 않은 (physical 메모리 그자체로 access하는) unmap된 영역에 저장이 됨

이런 세그먼트 테이블을 access하기 위해서 MMU에는 STBR라는 것이 들어가게 됨

그리고 이제 OS 차원에서 context switching이 발생하게 되면 세그먼트 테이블을 교체해야 되고

그 세그먼트 테이블을 교체한다는 것은 segment table base address 값을 바꾼다는 의미가 된다

이렇게 했더니 좋아졌지만 여전히 문제가 생김 (더 심각한 문제)

fragmentation 문제가 발생함

fragmentation이 왜 생기느냐? Dynamic memory allocation을 받을 때 그 크기가 다르고 또 메모리 block들이 continuous 해야 된다는 제약이 있기 때문임

이런 2가지를 피하기 위해서 memory allocation의 단위를 unit 사이즈로 고정을 시키고 

메모리를 할당을 받을 때 흩어져서 받을 수 있도록 하게 하는 것이 paging 기법이다.

paging은 segmentation과 굉장히 유사 하지만 page table을 가지고 있어야 됨

그리고 page 사이즈는 swap을 고려해서 block device의 block 사이즈에 일치 시킴

각 virtual address space에 있는 모든 page 마다 translation entry 들을 페이지에 유지해야 함

그래서 32bit address space에서 페이지의 사이즈가 1K일 때 16MB의 공간이 page table space로만 소요가 됨

paging은 좋은 점도 있지만 많은 페이지 공간이 문제가 됨

또 다른 문제로는 과거에 메모리를 접근할 때 한번 reference만 하면 됐는데 페이지 테이블 access 해야하니까이제는 2번 reference 해야한다

속도가 저하되는 그런 문제가 있었음

메모리 접근할 때 속도 저하되는 문제 어떻게 하면 해결할 수 있을까? caching이용(뒤에서 배움)

메모리 hierarchy(계층) 

- 레지스터 입장에서 보면 메모리 access는 굉장히 느림

- 메모리 access가 느리기 때문에 스피드 업하기 위해서 Cache를 사용함

- 마찬가지로 페이지 테이블 entry를 access할 때 메모리 시간이 느린 것을 피하기 위해

- 페이지 테이블 entry를 caching하게 되는데 이를 Translation Look Aside Buffer라고 한다

- TLB buffer를 64개 또는 128개 정도만 유지하고 있어도 굉장히 hit ratio가 높음

- 그래서 속도 저하의 문제는 비교적 쉽게 해결할 수 있음

Paged Segmentation

- 페이징만 하면 세그멘테이션의 취지를 안한다는 의미임 (과거로 돌아가 하나의 프로세스가 하나의 세그먼트만 같는 것과 같음)

세그멘테이션 취지(하나의 프로세스가 여러개의 특성이 다른 로지컬 유닛들로 구성이 되어있으니 각 로지컬 유닛 별로 다른 세그먼트를 할당하자)

이렇게 함으로써 메모리 접근에 대해 control도 하고 공유도 쉽게 하자는 것임

Paged Segmentation

Segmentation과 Paging 각각의 장점을 한꺼번에 얻기 위해 두 기법을 동시에 사용

이를 위해서 먼저 Segmentation을 수행하고 각 Segment 별로 Paging을 수행

Segmentation과 Paging을 할 때 가장 큰 이슈가 table임

paged segmentation을 하면 table들이 어떻게 구성되어야 할까?

먼저 세그먼트 테이블에 들어가는 정보는?

- 각 테이블의 index는 segment number임

- address bus의 상위 몇개의 비트를 이용하여 segment number를 얻어서

- segment table의 entry를 얻게 되면 base address와 bound address값이 들어있음

페이지 테이블에 들어가는 정보는?

- 이것도 똑같이 index는 페이지 넘버가 됨

- 그 페이지가 어느 physical memory에 들어갔는지 페이지 frame number가 있어야 함

그렇다면 paged segmentation을 하게 되면 table 중에 뭐가 바껴야 할까?

- segmentation하기 전에는 그 세그먼트의 시작주소 base register와 bound register 값을 가지고 있었음

- segmentation을 하게 되면 여러개의 segment가 존재하니까 이것을 register에 넣을 수 없어 테이블을 만들었음

- 그대신 이 표를 access하기 위해서 어떤 H/W unit이 필요했죠? MMU 안에 STBR가 있었음

- paged segmentation을 하게 되면 seg table에 가서 base 대신에 페이지 테이블 위치

- bound값 대신에 페이지가 몇장인지 개수를 저장한다

- 이것 외에는 다른 것이 없음 

Paged Segmentation을 위해 기존 segmentation에서 변경되는 부분

1. 기존 Base Address 대신 해당 Segment의 Page Table 위치를 저장

2. 기존 Bound 값 대신 해당 Segment의 page 개수를 저장

단점은? 

이제 1 memory reference 당 extra memory reference가 2번

총 3번이 필요하게 됨

즉, 성능이 더욱 저하되는 문제가 발생함

- 페이지의 사이즈 얼마? 2^12 = 4KB

- 세그먼트당 최대 몇개의 페이지까지 있을 수 있나? 2^8 개

- 시스템 전체가 하나의 프로세스에게 부여할 수 있는 세그먼트의 개수는? 2^4 = 16 개

우리가 공부한 것은 data, code, stack, heap segment 총 4개인데 왜 16개까지 있냐?

OS에게 그만큼 선택의 기회를 준 것임 

예를 들어 2개의 프로세스가 어떤 메모리 region을 공유한다 했을 때

별도에 메모리 세그먼트를 만들어 부여하면 서로 공유할 수 있게 됨

이렇듯 세그먼트가 충분히 주어지면 OS가 새로운 기능을 구현하는데 도움됨

- address translation을 얘기하려면 먼저 2가지를 생각해 보아야 함

1. 세그먼트 테이블이 어떻게 생겼느냐?

   세그먼트 테이블에는 당연히 16개의 entry가 있고 각각의 entry에게는 자기의 page table base address가 있다

`

- 0번 세그먼트는 Read only 코드세그먼트 

- 2번 세그먼트는 Read/Write 데이터세그먼트

- 1번 세그먼트는 bound를 0으로 만들어놨으니까 이건 아예 쓰지 않겠다

- 실제로는 2개의 세그먼트만 사용하는 예임

address가 24bit = 3byte가 사용이 되겠죠?

logical address 0x 00 20 70

아래처럼 address 포맷을 분해할 수 있음

- page number가 어느 frame number로 매핑되는지 알기 위해서 우리가 해야하는 일은 segment table을 살펴보기

- 0번 segment table에 가보면 physical memory 0x2000 번지에 저장됐다고 나옴

- 그리고 page number가 02(바이너리)이기 때문에 3번째 테이블 entry를 의미함

- 그 entry를 얻어오니 0x0003 값이 오게 됨 (이 값은 physical frame number를 의미함)

- page no 02가 frame no 03에 매핑이 된다.

- frame no 03과 offset을 합치면

- 얘의 주소는 0x003070로 virtual address가 physical address로 변환이 됨

다시 ppt 를 보면 변환된 주소값이 적혀 있음

- 다시 설명을 해보면

- segment no를 통해서 해당 table entry를 얻어왔고

- 이 segment의 page table entry가 몇번지에 저장이 되어있는지 확인이 됐고

- 해당되는 페이지 number가 그러니까 0x0003이 frame number가 됨

- frame number와 offset을 합치면 physical address를 얻어올 수 있게 됨

이런 작업을 누가 하는 걸까요? MMU

- 지금 이 복잡한 Translation 과정이 있는데 이것을 OS도 모르는 사이에 H?W가 하는 것이라는 걸 알았음

- 이 MMU H/W는 OS 상에서 완전히 transparent하냐? transparent 하지 않음

- 프로세스가 context switching을 당하게 되면 이와같은 segment table이나 page table을 교체해줘야 함

- 교체해준다는 의미는 segment table base address register를 교체해준다는 의미

- 그런식으로 OS이 프로세스 context switching을 할 때 참여를 해야 함

- 그리고 OS가 또 해야할 것은 새로운 프로세스가 생성될 때 fork()가 될 때

- 이 mapping table도 다 그때 만들어 져야 함

- 이런 의미에서 MMU가 transparent 하지 않음

Segment Table과 Page Table을 사용한 주소 변환

MMU에 의해 HW적으로 수행

그러나 프로세스의 문맥 전환이나 새로운 프로세스의 생성등이 일어날 때,

운영체제가 Base/Bound Register 및 Segment/Page Table들을 관리해야 하므로

운영체제에게 Transparent 하지는 않음

Paged Segmentation (VAX VMS Case)

Paged Segmentation 장단점

- Segmentation이 같던 고유의 기능들 프로세스의 logical unit들에 memory access control을 용의하게 해주고

- 프로세스들 간에 segment sharing을 용의하게 해준다.

- Paging을 하니까 external fragmentation 문제도 다 해결한다

그런데 항상 address translation에 의한 메모리 관리를 생각할 때 2가지를 생각해야 함

1. space overhead: 그냥 pure paging과 비교했을 때 page table space를 굉장히 줄일 수 있음

   왜? pure paging만 하게 되면 어느 페이지가 사용이되고 안사용이 되는지 확인하기 어려움

   그냥 virtual address space 상에 hole들이 존재하게 됨

   hole 들이 있다고 해도 page table entry는 잡아놔야함

   그런데 segmentation을 하게 되면 그럴 필요가 없어짐

   왜? 세그먼트 별로 page 몇개인지를 다 count 해서 그 양만큼만 page table을 만들기 때문

   그래서 space 문제를 해결하는 장점이 있음

   단점은 address translation을 할 때  extra memory reference가 2개가 더 증가한다는 문제가 발생 (심각한 문제)

2. performance overhead

요즘에 가장 핫한 많이 쓰는 OS은? 리눅스

리눅스 OS는 지금까지 배운 것 중에 어떤 memory management를 사용할 것 같나? pure paging

(paging, segmentation, paged segmentation)

paged segmentation이 필요하다고 했는데 그렇다면 틀린 얘기 아니냐?

먼저 segmentation을 하는 이유는 segment 단위로 memory access control를 쉽게 하기 위해서 임

그렇다면 리눅스에서는 paging만 함으로써 어떻게 access control 할까?

과거에 segment 단위로 하던 access control을 paged table로 다 내림

어느 페이지가 코드에 속한 페이지라면 걔는 읽기만 페이지 테이블에 기록하고

데이터나 스택이면 읽기쓰기로 기록하는 것

페이지 단위로 control 해서 memory access control도 가능하게 함

그렇다면 sharing 문제는 어떻게 해결할까?

sharing도 페이지 단위로 함

fork() exec() 설명을 할 때 parent process의 코드/데이터 세그먼트 다 copy한다고 했잖아요?

그때 페이지 단위로 sharing을 하게 됨

완벽하게 segmentation을 하지 않는 건 아님

OS이 S/W적으로 어느 페이지가 코드세그먼트인지 데이터세그먼트인지 region(지역)을 다 관리함

그러나 paged segmentation처럼 H/W MMU가 세그먼트 주소를 찾아가서 테이블 뒤지고 이러는 것이 아니고

OS이 관리하고 실제로 address transition 단계에서는 얘는 그냥 paging만 한다고 생각하면 됨

즉, segmentation에 필요한 많은 일을 OS가 해주는 대신에 pure paging만 한다

그러므로써 segmentation에 필요한 어떤 기능들을 OS이 보충해준다고 이해할 수 있음

(Paged segmentation을 하면되지) 왜 리눅스는 복잡하게 paging만 할까?

OS 코드를 대략 크게 2가지로 나눌 수 있음

1. 머신 independent(독립된) code

2. 머신 dependent(의존하는) code

머신이라고 하는 것은 3가지 차이를 갖음 (하드웨어 차이를 말할 때 3가지를 말함)

1. CPU architecture의 차이

2. 전체 시스템 (bus / memory map 을 어떻게 할 건지에 대한) 차이 - System architecture

3. I/O device 의 차이

OS을 작성하게 되면 이런 3가지 차이와 무관하게 작성할 수 있는 코드가 있음

이 부분을 OS에 머신 independent code 라고 함

OS을 개발하는 사람들은 최대한 머신 independent code를 많이 만들고 싶어함 (비중을 크게 하고 싶어함)

왜 그럴까? H/W가 변하더래도 동일한 OS을 많이 Porting(이식)해서 쓸 수 있으면 그만큼 usage(사용량)가 높이지기 때문

Q. 운영체제에서 Machine-Independent한 코드의 비중을 가능한한 높이는 이유는?

A. 운영체제의 Portability(이식성)를 높여 다른 하드웨어에서도 동일한 운영체제를 사용하기 위해서

그런데 앞에 말했던 하드웨어적 3가지 차이 때문에 어쩔 수 없이 머신 dependent한 부분이 있게 됨

머신 dependent한 대표적인 부분은? context switching code, task creation 

특히 CPU architecture 부분임!!!

왜냐? CPU가 제공하는 register 들을 손으로 주물러야 하는 부분이기 때문

여기는 피할 수가 없음

심지어 머신 dependent한 code 중에 C로 작성할 수 있는 부분도 있지만

context switching은 그것도 안되고 어셈블리 랭귀지로 작성해야 함

Q. 대표적인 Machine-dependent한 코드는?

A. 문맥 전환, 프로세스 생성, I/O 관리, 메모리 관리 등

메모리 관리는 CPU architecture가 MMU를 지원해주느냐 안해주느냐 차이도 생기고

시스템의 메모리 맵에 차이에서도 생기고 굉장히 머신 dependent한 부분이기 때문에

심지어는 리눅스가 원래 개발됐던 인텔 processor는 

태생적으로 paged segmentation을 지원할 수 있는 segmented architecture로 되어있음

그런데 리눅스가 인텔 못지않게 많이 사용되는 processor ARM은 이런 Segmentation구조를 갖고 있지 않음

모든 H/W가 segmentation을 지원하는 것은 아님

그래서 리눅스 개발자들은 segmentation은 아예 없다고 생각하고

인텔 프로세스에서도 플랫 메모리 모델이 지원이 되는데 

그것을 통해서 거기에 페이징만을 지원함

결론적으로 리눅스는 가장 모던 OS이지만 paged segmentation을 지원하는 것이 아니라 pure paging만 지원하고

그대신 segmentation에 해당하는 부분은 OS가 S/W적으로 해결을 한다

이렇게 한 이유는 Portability(이식성) 높이기 위한 것이다.

이제는 2가지 이슈를 계속 고민해야 함

1. 성능저하의 문제

2. 큰 페이지 테이블의 문제 (large table space의 문제)

특히 페이지 테이블이 요즘은 점점 더 커질 수 밖에 없음

왜냐하면 memory address space가 64bit 되기 때문 (손으로 계산할 수 없을 정도의 페이지를 쓰고 있는 것임)

이제는 손으로 계산할 수 없는 엄청 큰 Space가 페이지 테이블이 사용되고 있는 것임

뒤에서 더 자세히 나오겠지만

physical memory가 작은 조각으로 나누게 되고 이것을 page frame이라고 했음

이 page frame들은 어떤 속성들을 가지고 있음

대표적인 속성이 mapped page, unmapped page, cached page, uncached page 임

각 frame page들이 이런 특성들을 갖게 됨

만약 어떤 frame이 cached page라고 하면 무슨 얘기일까?

L1 cache, L2 cache를 사용함 (그렇다면 Data일수도 있고 instruction일수도 있는데)

일반 페이지들은 전부 cached page임

다시 말해 한번 특정 word가 access 됐으면 그것을 Cache에 빈공간이 있는 한 caching을 시켜서 나중에 hit 시키는 것임

(cache hit: 캐시에서 읽어 들이는 것)

그런 일반적인 페이지를 cached page라고 함

그것에 비해서 uncached page는 뭘까?

절대 caching을 하지 말라는 의미임

왜? caching은 성능을 향상시키는 굉장히 좋은 메커니즘인데 왜 캐싱을하면 안될까?

어떤 메모리에 페이지 프레임이 있으면 그것을 읽고 쓰는 놈이 있음

읽고 쓰는 놈이 1개 밖에 없으면 걔는 캐싱을 하던 뭐를 하던 상관없음

그런데 sharing을 해서 한놈이 읽고 쓰고 있고 다른놈이 읽고 쓰고 있으면 캐싱을 하면 안됨

왜냐? 내가 어떤 page를 modify하고 있는데 CPU는 옛날에 캐싱한 entry를 가지고 연산하고 있으면 안되기 때문

이런 경우 언제 생길까? DMA operation

DMA operation이라는 것은 cpu bus에 master가 여러개 있어서 한놈이 메모리를 읽고 쓰고 하는 동안 다른 놈도 쓸 수 있는 것

그래서 DMA에 타겟이 되는 페이지들은 우리가 caching을 하면 안됨

(이럴 경우 각 페이지 프레임에 flat으로 unmap, uncached page로 만들 필요가 있음)

Uncahced Page

Cache하지 않도록 설정된 page

DMA의 대상 Page처럼 여러 프로세스에 의해 동시에 읽고 쓰기가 일어날 수 있는 경우 사용

mapped와 unmapped는 무엇인가?

mapped page 라는 것은 전통적인 페이지 address translation 메커니즘을 거쳐서 그 주소를 얻어오는 페이지 그래서 access하는 것을 얘기하는 것이고

unmapped page 라고 하는 것은 physical memory를 날려서 translation 없이 access 하는 것

physical memory 가 있으면 모든 영역을 다 virtual address 에 매핑해서 쓰는 것은 아니고

그 영역 중에 일부는 이렇게 direct access를 하는데 씀

그렇다면 page table은 어디에 들어 있어야 할까? unmapped memory space에 들어있어야 한다

page table이라는 것은 mapped 된 address를 translation해주는 건데 갔더니 

그 table address가 또 translation 이 필요한 거다 그러면 계속 reclusion이 걸림

그렇다면 translation이 끝이 안나게 됨

그런 문제가 있기 때문에 unmapped memory space에 page table을 넣음

Unmapped Page

직접 Physical Address를 사용해서 별도의 주소 변환 없이 바로 접근 가능한 Page

Page Table 등에 사용

그리고 또 하나

page table은 unmapped영역 그러니까 physical memory에 흩어져있어도 될까? 아니면 continuous하게 쫙~있어야 할까?

array를 access할 때 여러분은 뭘로 access하죠? array index로 access함

그 근거는 한 아이템이 바로 다음에 있고 다음에 있는 연속되어 있다는 의미를 뜻하기 때문

이 table도 마찬가지임 table이라는 것은 continuous하게 있어야 함

시스템에 unmapped된 physical 메모리를 low memory를 많이 유지하겠어요? 

Nope 조금만 유지함

여러가지 OS에 필요에 의해서 조금만 유지하는데 

거기에 continuous한 거대한 페이지 테이블이 딱 차지하고 있다면 

시스템에 성능이 별로 안좋겠죠

그리고 context switching 할 때는 새로운 페이지 테이블로 바꿔야 하니까

어마어마한 디스크 operation. swap device의 operation이 필요함

이런 것은 서로 바람직하지 못한 문제가 됨

그래서 우리가 large page table을 handling하는 문제는 항상 뭐를 공략하게 되냐면

페이지 테이블이 (거대한 페이지 테이블이) continuous하게 있어서는 안되겠다라는 것에 중점을 많이 둠

페이지 테이블 사이즈를 줄이려고 노력도 하지만 페이지 테이블 그 자체가 physical memory에 continuous하게 있게 되면

시스템에 엄청난 부담이 된다는 거죠 이런 것들을 풀고자 함

Large Page Table의 문제의 해결 조건

1. Page Table의 크기를 줄임

2. 연속적인 메모리 공간 요구량을 줄임

그래서 옛날에 이 문제를 풀려고 했던 대표적인 컴퓨터 아키텍쳐가 벡스 아키텍쳐임 (VAX)

- VAX 라는 것에 VMS라는 OS가 있었음 (VAX는 H/W 이름)

- VMS가 Large page table 특히 continuous한 Large page table의 문제를 해결하는 기법임

- Virtual Address Extension (VAX): 아키텍쳐를 디자인할 때부터 virtual memory management를 잘해주려고 설계된 아키텍쳐

- 전체 컴퓨터 시스템(virtual address space)을 4개의 segment로 나눔 (system, p0, p1, unused) 

virtual address space가 있으면 우리가 OS를 위치시키는 방법이 2가지 있음

1. virtual address space 일부를 OS에게 할당하고 user는 virtual address space의 뒷부분을 사용하는 것

2. user가 전체 virtual address space를 다 사용함. OS 코드가 돌아야 하니 별도의 address space 갖는 방법

- VAX 같은 경우 1번 방법을 사용함

- 그리고 user space 부분을 2개로 나눔 ( p0, p1 )

여기서의 Key는 

- user process들이 수행을 하면 virtual address들을 날림

- 그 virtual address를 translation 해주기 위한 페이지 테이블이 System 영역 안에 존재함

- 즉 시스템 영역(OS 영역)안에 각 2개의 (P0, P1) 페이지 테이블을 넣음

- OS 영역은 mapped area인가? unmapped area인가?

mapped area와 unmapped area의 기준이 뭐였죠?

unmapped는 physical memory로 access할 수 있는 것

OS 영역은 OS이지만 user에 virtual address space 안에 위치하고 있음

그러니 이것 또한 virtual address space영역이기 때문에 mapped area임

- user의 페이지 테이블이 OS 영역에 있다는 것은 무엇을 의미하는가?

user 페이지 테이블의 entry의 주소를 얻어 올텐데 

( user table base address를 알아서 가보면 이 영역의 주소가 virtual address 주소로 다시 나오게 됨 )

왜냐면 virtual address space 안에 있기 때문에 

- user 페이지 테이블이 OS 메모리 영역 안에서는 continuous한데 이들을 

실제 물리메모리에서 continuous할까? nope continuous하지 않음 (이것이 key)

- large table space의 문제 중 페이지 테이블이 physical memory에서 continuous하게 있어야 한다는 것인데

VAX는 virtual address space 상에서는 continuous하지만 physical address space 상에서는 흩어져서 페이지 단위가 구성되어 있음

이렇게 되기 때문에 user의 페이지 테이블들이 아무리 커도 흩어져 있고 그 중의 일부는 swap device에 out되어 있을 수도 있고 이런 장점을 얻을 수 있음

페이지 테이블의 entry 주소를 얻어왔음

근데 그 주소가 physical 주소가 아님 그렇다면 뭘 또 해야하는가? translation

어떻게 translation을 하는가? 

- 시스템 영역에 페이지 테이블을 얻어와서 그것을 translation 해야 함

- 걔는 physical 메모리에 있어야 함 어쩔 수 없이

- 결국 physical memory에 있는 페이지 테이블은 OS에 주소를 번역해주는 페이지 테이블 딱 1개만 물리적 메모리에 continuous하게 있어야 하고

- 나머지는 흩어져 있어도 된다

<정리>

user가 어떤 logical address를 generation하면 

- 먼저 user page table을 lookup함

- 그 user table entry가 나오게 되는데 그 page table entry의 주소가 virtual address니까

- 다시 system page table로 lookup해서

- 걔의 physical address를 얻어 오면

- 그때 비로서 그 페이지 테이블의 entry를 얻어올 수 있게 됨

- page table entry안에 physical frame number가 들어가 있게 됨

address translation하는데 overhead가 많이 들지만

large page table의 continuous한 allocation에 대한 문제는 해소를 할 수 있게 됨

Translation Look Aside (TLB) Buffer

large page table 문제를 설명했는데, 두번째는 성능저하의 문제를 설명하도록 하겠습니다.

logical address에서 physical address를 얻어오려면 반드시 page table lookup을 해야하는데 

그중에 자주 lookup되는 page들의 entry를 가지고 와서 cache에 넣으면 좋겠다

이것이 TLB(Translation Look aside Buffer)임

- TLB가 잘 동작하려면 뭐가 중요할까? hit ratio(적중률)

- hit ratio를 높이려면 어떻게 해야할까? 크게 만들면 됨 (크게 만들면 좋지만 비용이 듦)

  그래서 적절한 선을 찾아야 함 64~128개만 있어도 됨 (98% 이상 나옴)

  TLB 사이즈가 작아도 생각보다 hit가 잘 나오는 이유가 뭘까요?

  프로그램의 수행에는 locality(집약성)이라고 하는 특징이 있기 때문임

Locality 를 2가지로 나눌 수 있음

- Spatial Locality: 내가 한번 수행이 됐으면 내 위나 아래에 있는 instruction이 수행될 가능성이 굉장히 높은 것

- Temporal Locality: 내가 instruction이라고 할 때 한번 수행이 됐다고 하면 매우 짧은 시간안에 다시 수행이 된다는 의미임

- 왜 Temporal Locality가 발생할까? loop 때문임

  프로그램이 90% 이상의 시간을 loop안에서 보내더라 

- 그렇다면 왜 Spatial Locality가 발생? 이것도 loop 때문임

  loop가 여러번 도니까, Function call같은 것 (한 번수행이되면 그 근처있는 것들이 수행이 되니까)

이와같이 어떤 page가 한번 access됐고 특히 그 page가 loop를 가지고 있다면 얘는 계속 access가 될 것임

그런 entry들을 TLB에 넣어놓으면 hit ratio가 또 높아지겠죠

그다음에 hit ratio를 또 높일 수 있는 방법이 있음

생각보다 비용이 들지 않는 방법임 (물론 trade off가 있지만)

page의 사이즈를 키우면 한 page의 entry가 카버하는 address space가 커지니까 

이것도 hit ratio가 높이지게 되겠죠.

Translation Look aside Buffer 슬라이드로 설명

- logical address가 발사가 되면

- MMU가 table lookup하여 사용하는 것이 아니라 오히려 MMU 안에 있는 TLB를 먼저 뒤져보고 

  TLB hit가 나게 되면 그 frame number를 얻어와서 더하고

- 만약에 실패하면 그때 page table lookup을 하게 되는 cache의 기본적인 operation이 되겠음

TLB를 어떻게 구성할 것인가?

cache를 구현하는 3가지 방법

- 오른쪽 극단이 Direct Mapped Cache

- 왼쪽 극단이 Fully-Associative cache

- 중간에 있는 것이 Set Associative cache

이것으로 TLB를 구현함 (자세히 설명할 필요는 없다고 교수님이 설명 안함)

참고: http://eldora.tistory.com/96

결국 중요한 것은 TLB를 어떻게 빨리 검색해서 데이타를 넘기느냐

제일 안좋은 방법은

- sequentially(연속하여, 순차적으로) table search해서 테이블을 매번 뒤지는 것

두번째 방법은

- page table entry가 있으면 특정영역에만 매핑을 시키는 것

- 예를들면 Direct Mapped Cache를 의미함

Direct Mapped Cache란 캐시 라인이 4개 일때, 페이지 넘버의 제일 하위 2비트만 보고 캐시라인주소에 매핑이 되어있는지 확인하는 방법이다.

어떤 페이지 넘버가 왔는데 어떤 특정 캐시라인에 있는지 없는지 어떻게 확인할까?

상위태그를 캐시라인에 추가로 저장한다.

페이지 넘버를 캐시라인에 매핑시킬 때 제일 하위비트를 따서 볼 수도 있고 중간에서 볼 수도 있고 맨 앞에서 볼 수도 있음

맨 앞부분에서 따서 보는건 어떻게 생각하는가? 나쁜방법임

왜냐하면 똑같은 근처에 있는 페이지들이 전부 하나의 캐시라인에 매핑이 되기 때문이다

special locality(집약성, 인근) 때문에 똑같은 캐시라인에 근처에 있는 것들이 많이 들어가게 되면 

충돌이 많이 나고 결국은 효과적이지 않게됨

세번째 방법은

캐시 라인을 전부 comparator(비교기)를 설치하는 것

페이지 넘버가 쫙~ 들어오면 캐시라인랑 parallel(병행)하게 비교 그래서 걔가 있으면 찾아서 보내 주는 것

이 방법이 Fully-Associative cache가 됨

Fully-Associative cache는 굉장히 빠름 그리고 어느 페이지 넘버를 특정 캐시라인에 매핑시킬 필요도 없음

충돌이 나도 따른 곳에 보내도 됨 그대신 하드웨어적으로 구성. 비싼것이 단점임

정리

Direct Mapped Cache는 싸다

Fully-Associative cache는 빠르지만 비싸다

Direct Mapped Cache 싼 대신에

00번 캐시라인에 페이지 넘버가 많이 매핑이 되어 충돌이 났다고 하면

계속 이 페이지 라인이 교체가 되면서 hit ratio(적중률)가 떨어지게 됨

이럴때 어떻게 하죠? 캐시라인을 두개의 세트로 나눔

그래서 끝자리가 0인 페이지넘버는 캐시라인 위로 보내고 끝자리가 1인 페이지넘버는 캐시라인 아래로 보냄

결국 1비트만 매핑을 시킴 collision(충돌)이 나도 2개의 캐시라인을 갖고있으니 하나더 포함할수 있음

이렇게 캐시라인을 구성하는 것을 Set Associative cache라고 함

set 안에 multiple(많은) 캐시라인을 줘서 collision(충돌)을 회피하는 방법

그대신 set안에서의 비교는 병렬적으로 Associative하게 비교함

예시와 같은 경우는 set의 개수가 2개기 때문에 2-way set Associative cache라고 한다.

Direct Mapped Cache를 사용하던 Set Associative cache를 사용하던 TLB를 하드웨어적으로 구성을 할 수가 있음

이것이 TLB의 이슈가 됨

마지막으로 2가지만 더 보겠음

TLB에 어떤 정보들이 들어가 있어야 할까?

TLB의 캐시라인 안에는 

제일 먼저 TLB에서 얻고자 하는 정보인 physical frame number(PFN)가 있음

Direct Mapped Cache를 하게 되면 태그가 있어야지 비교할 수 있으니 PFN 뒤로 page number(PN)가 오게됨

그리고 여러가지 flag bit들이 쫙~ 오게됨

PFN: TLB에서 얻고자 하는 정보

PN: 캐시라인에 hit가 났는지 비교하기 위해 page number가 옴

어떤 플래그가 오느냐?

예를들어 

N: uncached page (캐시하지 마라)

D: Dirty bit (이 페이지가 swap device에서 읽혀온 다음에 내용이 modify된 것)

    - swap out을 할 때 어떤 페이지가 clean하면 그냥 버림

    - 왜냐하면 swap device에 이미 그 페이지의 원본이 있기 때문

    - dirty하면 실제 disk operation함

    - 그래서 성능향상을 위해서 dirty가 필요함

V: 그 페이지가 실제로 valid한 것인지 메인메모리에 있는거냐? 아니면 swap device에 있고 아직 메모리에 없는거냐?

    - 기타 등등 여러가지 플랙정보들

    - 나중에 virtual memory management할 때 MMU를 메커니즘으로 활용해서 여러가지 정책을 구현하게 되는데

    - 그때 필요한 정보들이 여기에 위치하게 됨

이것이 바로 TLB에 각 캐시라인에 entry들 정보값이 됨

질문1> TLB는 H/W? S/W? 하드웨어임

질문2> TLB는 OS에게 transparent한가? 얘의 존재를 무시해도 되는가? 무시하면 안되는가? 

          프로그램을 돌릴 때 캐시가 있으면 어떻게 될까요?

          무시하면 안됨 왜? 어떤 프로세스가 TLB에 자기 페이지테이블엔트리를 채워놓가 나감

          문맥교환이 발생함 다음 프로세스가 들어왔는데 TLB를 뒤져보니 hit가 남

          그리고 나서 PFN를 받아왔는데 그건 자기의 frame number가 아님

          이런 상황에서 OS는 뭘 해줄까? 문맥교환이 발생했을 때 TLB를 flush시켜야 함 (TLB내용을 버림)

          그래서 문맥교환하게 되면 Empty(빈) TLB 때문에 memory reference가 굉장히 느려지는 성능저하까지도 발생하게 됨

메모리 관리까지도 고려하면 문맥교환은 굉장히 비싼 operation임

그런데 어떤 마이크로 프로세서 에서는 이 TLB를 OS transparent하게 만들었음

어떻게 만들었을까? 그것이 바로 과거에 사용하던 MIPS 마이크로 프로세서

이렇게 생겼음

TLB의 캐시라인에 PID를 넣었음

그래서 TLB에 look-up을 할 때, page number만 태그로 사용하는 것이 아니라 지금 수행하고 있는 프로세스 ID까지 태그하여 PID도 맞아야 나의 valid한 entry라고 생각했음. 이렇게 되면 OS은 TLB에 대해 신경쓰지 않아도 됨

하드웨어 기능이 추가가 되면 OS이 어떻게 대처해야 할지를 고려해야 함

PID는 다른말로 ASID라고도 함 (Address Space ID)

TLB의 캐시라인 entry들은 address space 별로 다른 entry를 갖여야 되기 때문에 그렇다

TLB를 운영체제에 Transparent하게 만드는 방법 (MIPS)

Page Number와 함께 PID를 추가적으로 사용해서 TLB Look-Up에 사용하도록 TLB를 설계

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=669

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=670

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=671