[운영체제] 04. memory -b

Page Replacement Algotithms

page fault가 발생했는데 page frame에 빈자리가 없는 경우, 하나를 내쫓아야 하는데 누구를 내쫓을지 결정하는 알고리즘

modified page는 항상 저장되어야 함

자주쓰는 page는 되도록 내쫓지 않도록 함

 

1. Optimal Page Replacement Algorithm

가장 먼 미래에 필요하게 될 페이지를 내쫓는 것이 최적이지만 바로 실생활에서는 쓸 수 없음

 

2. Recently Used Page Replacement Algorithm

모든 페이지는 R bit, M bit를 가짐

-R bit: 페이지가 참조되었을 때(referenced)

-M bit: 페이지가 수정되었을 때(modified)

(R bit는 주기적으로 초기화됨)

1. not referenced, not modified
2. not referenced, modified
3. referenced, not modified
4. referenced, modified

1→2→3→4 순위로 쫒겨남

 

3. FIFO Page Replacement Algorithm

메모리에 가장 처음 로딩된 메모리를 가장 먼저 내쫓는 것(list 맨 앞에 있는 것)

→ 아주 옛날에 로딩되어 있다는 것은 인기가 좋아서 계속 사용되던 것인데, 맨 앞에 있단 이유로 쫓겨나는 문제 발생

 

4. Second Chance Page Replacement Algorithm

FIFO와 같은 방식으로 동작하지만,

R bit를 체크하여 0이면 내쫓음. 1이면 R bit를 clear 하고 맨 끝에 넣어 기회를 한 번 더 줌.

→ FIFO의 단점을 해소했지만, list 형태이기 때문에 overhead 발생 가능

 

5. The Clock Page Replacement Algorithm

앞의 알고리즘과 같은 방식이지만, circular list 형태로 list up overhead를 줄일 수 있음

 

6. Least Recently Used (LRU)

1.  가장 옛날에 사용된 페이지를 내쫓는 방법

가장 최근에 사용된 페이지는 곧 사용될 것이라고 생각함.

뒤로 갈수록 옛날에 사용한 것이고 최근에 사용된 페이지가 앞으로.

→ linked list 형태를 유지해야 하고, 매 메모리 참조마다 리스트를 업데이트해야 함

 

2. page table entry 마다 counter를 사용하여 가장 낮은 값을 가진 카운터를 가지고 있는 페이지를 내쫓음

 

7. Another LRU

1. 사용된 페이지의 가로축 1로 변환
2. 사용된 페이지의 세로축 0로 변환
3. 사용된 순서대로 반복한 후에 가로의 값을 더했을 때, 가장 작은 페이지를 내쫓음

 

8. NFU (Not Frequently Used)(Simulating LRU in Software)

자주 사용되지 않는 페이지를 내쫓음

매 clock interrupt마다 counter에 R bit 값(0 or 1)을 더해줌

자주 참조되지 않는 페이지들은 주기적으로 R bit가 0으로 초기화되기 때문에 0일 것이고, 자주 참조되는 페이지는 counter값이 자주 늘어날 것임

→ 과거에 잔뜩 참조되어 counter가 늘었던 페이지지만, 현재 시점에서는 참조되지 않는 페이지인 경우에 쫓겨나지 않는 문제 발생

 

9. Aging (Simulating LRU in Software)

매 clock tick마다 R bit를 counter에 기록하고, 다음 clock tick에서 전에 적었던 R bit를 right shift 하고 현재 R bit를 leftmost에 집어넣음

페이지 폴트가 발생했을 때, counter의 값이 가장 적은 페이지를 내쫓음

→ 유한한 counter의 개수, clock interval마다 확인하는 것이므로 과거의 값은 정확히 알 수 없음

 

10. The Working Set Page Replacement Algorithm (1)

demand paging(요구 페이징): 미리 적재하는 것이 아니라 필요할 때 페이지를 적재

locality of reference(참조 지역성): 프로세스가 실행되는 각 단계에서 전체 주소 공간의 일부 페이지들을 집중적으로 참조하는 경향

working set(작업 집합): 프로세스가 현재 자주 참조하는 페이지들의 집합

Thrashing: 많은 페이지 폴트를 야기하게 되는 것

Working set model(Prepaging): 프로세스의 작업 집합을 파악하고 이들을 프로세스가 시작하기 전에 메모리에 유지하는 것(프로세스 시작 전에 페이지를 적재하는 것)

(1)

현재 시간 t에서 볼 때, 지금까지 참조된 페이지 중에서 가장 최근에 참조된 k개의 페이지 -집합 w(t, k)

(2)

현재 작업 집합에 포함되어 있지 않은 페이지를 교체하는 기법

페이지 테이블의 각 엔트리는 (최소한) 두 개의 키 정보를 유지(페이지가 마지막으로 사용된 시간, R bit)

if(R==1)

현재 가상 시간을 엔트리의 Time of last use 필드에 기록

 

if(R==0)

이번 클록 틱이 발생한 간격에 참조되지 않았다는 의미이며 교체의 후보가 됨

교체할지 여부는 ‘현재 시간 - Time of lasy use 필드에 기록된 시간’에 의해 결정

-나이가 τ(tau) 보다 크면 새로운 페이지가 이것을 교체

-나이가 τ(tau)보다 작거나 같으면 가장 큰 나이를 갖는 페이지(가장 작은 Time of last use를 갖는 페이지)를 기억해 둠

 

만일 모든 페이지의 R이 1이었다면, 기억해 둔 페이지 중에 하나가 임의적으로 교체

 

11. Thw WSClock Page Replacement Algorithm

환형 리스트로 관리

 

요약

지금까지 논의된 페이지 교체 알고리즘

 

Segmentation

1차원 가상 메모리는 특정 크기만큼 자라며 이때 다른 공간과 충돌할 수 있다.

세그먼트(segment)라고 부르는 여러 개의 서로 완전히 독립된 주소 공간을 제공

한 세그먼트는 다른 세그먼트들에게 영향을 주지 않고 독립적으로 증가하거나 감소할 수 있음

 

페이징과 세그멘테이션의 차이

 

pure segmentation의 구현

(a)는 5개의 세그먼트를 포함한 물리 메모리의 초기 상태

시스템이 계속 실행됨에 따라 메모리는 작은 조각으로 계속 분할되고, 일부 조각은 세그먼트를 위한 공간이 되고, 나모지 조각은 비어 있는 공간이 된다.

이렇게 빈 조각들은 메모리 낭비를 초래하며 이러한 현상을 체커판되기(checkerboarding) 또는 외부 단편화(external fragmentation)라고 한다.

이러한 현상은 (e)처럼 사용되지 않고 낭비되는 부분을 수집하는 compaction을 통해 해결한다.

 

Pentium(펜티엄)

펜티엄은 세그멘테이션과 페이징을 모두 사용

16K 개의 세그먼트를 지원하며, 각 세그먼트의 크기는 최대 4 Gx32 비트 워드까지 가능하다.

논리주소에서 물리주소로 변환하는 과정을 나타냄

논리주소는 selector와 offset으로 구성 (selector: 세그먼트를 지정하는 정보, offset: 해당 세그먼트에서 위치)

 

펜티엄 셀렉터

GDT(Global Descriptor Table): 운영체제 같은 시스템 세그먼트를 관리, 전체 시스템에 하나 존재하고 각 프로그램을 이를 공유한다.

LDT(Local Descriptor Table): 각 프로그램의 지역 세그먼트(텍스트, 데이터, 스택 등) 정보를 관리하며, 각 프로그램은 자신의 LDT를 각각 갖는다.

GDT와 LDT에서 적절한 세그먼트 디스크립터를 찾아감

 

각 셀렉터는 16비트 구조

-13개의 다른 비트는 LDT 또는 GDT 테이블의 엔트리를 가리킨다.

-한 비트는 세그먼트가 지역인지 전역인지 (LDT에 속해있는지 GDT에 속해있는지) 구분한다.

-마지막 2비트는 보호와 관련 있다.

(디스크립터 0은 주로 세그먼트 레지스터가 현재 사용 가능하지 않다는 것을 나타냄)

 

펜티엄의 코드 세그먼트 디스크립터

8바이트로 구성되어 있으며, 세그먼트 기본 주소, 크기 등의 정보를 포함한다.

base: 세그먼트의 시작 주소, limit:세그먼트의 크기, other fields: 권한 정보

 

선형 주소가 만들어지는 과정

base와 offset이 더해져 선형주소(linear address)가 만들어진다.

 

선형 주소

32비트로 구성

Dir(디렉터리): 상위 10비트, 페이지 디렉터리에서 항목을 선택

Page: 중간 10비트, 페이지 테이블에서 항목을 선택

Offset: 하위 12비트, 선택된 페이지 내부의 특정 위치를 나타냄

 

선형주소를 물리주소로 매핑

페이징: 메모리를 일정한 크기의 페이지로 나누어 관리하는 방법

Page Directory: 1024개의 엔트리를 가진 데이터 구조, 각 엔트리는 페이지 테이블의 시작 주소를 가리킴

Page Table: 페이지 디렉터리가 가리키는 실제 테이블, 각 엔트리는 메모리의 특정 페이지를 가리킴

Page Frame: 실제 물리 메모리에 해당하는 페이지

 

보호

4단계의 보호 레벨 (레벨 0이 가장 권한이 높은 수준, 레벨 3이 가장 낮은 수준)

프로그램이 자기와 동일한 레벨이나 큰 숫자 레벨(낮은 권한)을 갖는 세그먼트에 접근은 허용되지만, 작은 숫자 레벨(높은 권한)을 갖는 세그먼트의 데이터로 접근은 허용되지 않고 트랩을 야기한다.

서로 다른 레벨을 갖는 코드 세그먼트는 콜게이트를 경유한다.