Hashed Page Table
공간은 크지만 데이터가 sparce할 때 사용하기 좋은 데이터 구조이다. 어떤 key value가 들어가면 위치가 return 되는 함수이다. Linked list 구조 속에 page number와 frame number가 저장되어있다.
Segmentation
paging은 low level 의 address를 관리하지만 segmentation은 논리적인 단위로 쪼개는 컨셉이다. 프로그램을 실행할 때 사용하는 메모리는 Code와 데이터로 나눌 수 있다. 데이터 또한 Heap과 Stack으로 나뉠 수 있고 이런 것이 논리적인 구획이 된다. 논리적인 메모리 Space를 오른쪽 그림처럼 나눌 수 있다. 하나하나를 Segment라고 부르게 된다. Memory를 쪼개서 나눠서 본다는 것이 page와 공통점이 된다. Paging은 똑같은 크기로 자르지만 Segmentation은 가변적이라는 것이 다르다.
Segmentation
Page에서는 Page number와 page offset으로 구성된다. Segmentation에서는 Segment number하고 offset을 사용한다. 실제로 이 seg를 처리할 때 어떻게 처리하는지 보자.
Example of Segmentation
3번 Seg의 500 번째 바이트가 된다. Segment table이 mapping을 해준다. Segment에는 각 시작점이 들어가게 된다. 그 주소를 base address라고 부른다. 3번 Segment의 시작주소는 segment table의 3 인덱스에 해당하는 base address 값이 된다. 시작점이 3200이고 Offset이 500이면 시작점이 3700이 된다. limit은 segment의 길이를 의미한다.
Segmentation Architecture
Segment table은 각 segment의 base와 limit 을 가지고 있다. STBR, Segmentation의 주소는 PCB에 있지만 직접 참조하기에는 시간이 오래 걸리므로 주소를 가리키는 래지스터를 갖고 있는 것이다.
Segmentation
물리적인 공간에서 editor는 하나면 가능하다. 이렇게 하면 효율이 증가한다.
Example: Intel Pentium
Segmentation이랑 page를 같이 쓴다. Segmentation이 더 큰 개념이다. CPU가 주소를 내준다. 여기 logical address에는 segment number와 offset을 가지고 있다. linear address 자체가 page address가 된다.
Pentium Segmentation
Segment Discritor table에는 두 가지 정보가 들어간다. base와 limit 값이 들어간다. LDT와 GDT 두 종류가 존재한다. 프로세스 별로 따로 읽는 segment table이다.
Pentium Page
Hierachy page와 비슷한 구조를 가진다. large pag를 가리키는 flag 변수가 존재한다.
Two major problem
Disk를 빨리 읽어와야 한다. 기존의 Frame을 하나 지우고 올려야 한다. 현실적으로 List of Free Frame을 운영하는데, 그렇게 주고 나면 List of Free frame을 줄일 수 있다. 그런 경우 누구를 지울 것인가에 대한 이슈가 있다. 그게 page replacement algorithm이다. 결국 제일 중요한 것은 Page fault rate를 줄이는 것이다.
page replacement
4개의 페이지를 사용하는 프로세스가 있다. 첫번째 페이지는 3번째의 frame을 사용한다. 이 정보는 page table에서 확인할 수 있다. M의 경우를 보면 현재 Disk에 존재한다. 올리기 위해서 Frame 중 하나를 없애야 하는데 이를 찾는 과정이 필요하다. Writing overhead가 있을 수 있다... A를 선택해서 희생하기로 했다고 가정하자. A를 내리기 위해서 Disk에 접근하고 M을 올리기 위해 Disk에 접근하면 2번을 접근하게 된다. A가 디스크에서 읽어온다음에 한 번도 수정된 적이 없는 경우 Swap out을 할 때 다시 Disk로 내릴 필요가 없다. 불필요한 Disk Access를 없앨 수 있다.
Page Replacement
일반적으로 Frame의 개수가 많을 수록 page fault가 줄어든다. 메모리가 풍부해진다는 뜻이기 때문이다. Frame의 개수하고 Page fault의 rate의 관계는 반비례에 수렴한다.
Page Replacement 알고리즘
FIFO Page Replacement
공간의 개수가 3개 이므로 나한테 주어진 page의 개수가 3개라고 가정할 수 있다. 내 프로그램이 실행하면서 읽거나 쓴 페이지의 번호가 숫자로 적혀있다. 7 -> 0 -> 1 ...로 접근을 한다. 첫 번째의 경우 page fault가 발생한다. 읽으려는 데 메모리에 없는 경우 발생하는 것이 page fault이다. 0의 경우도 page fault 발생한다. replacement는 필요없다. 1도 page fault 발생, replacement x. 2의 경우 page fault와 replacement는 둘 다 발생한다.
Belady's anomaly
page의 수가 늘어날 수록 page fault의 발생 빈도수가 발생하는 경우의 수가 조금 늘어날 수 있다는 것이다.
Optimal Page Replacement
가장 오래 사용하지 않을 page를 내려야 한다. 이론적으로 optimal하지만 미래의 값을 예측할 수 없으므로 구현할 수 없다.
LRU Page Replacement
가장 오랫동안 사용되지 않은 Page를 내려야 한다.
Implementation Of LRU
access할 때마다 시간을 기록해야 하는 단점이 있다. 그 때마다 기록하기란 쉽지가 않다. 다른 방법으로 stack을 사용한다. 이는 데이터 구조에서의 stack이 아니다. stack을 잘 구성해서 최근에 사용한 것을 위로 올리고 잘 사용되지 않은 것을 아래로 내린다. 제일 아래 있는 친구를 버리는 것이 바람직하다.
LRU Approximation Page Replacement
사용한 시스템을 1로 바꾸는 reference bit를 놓는 방식이 있다. LRU는 어떤 친구를 택해야 하면 reference bit이 0이 친구를 지우면 된다. 이를 보완하는 알고리즘이 있다.
LRU Approximate Page Replacement
reference bit을 가지고 어떻게 보충을 하는가. 특별한 래지스터를 사용한다. 일정 시간마다 오른쪽으로 shift 시키는 기능을 구현한다. bitwise shift operation과 비슷한 기능이다. 최근에 접근한 프로그램은 왼쪽에 1이라는 숫자가 있을 확률이 높다.
Second chanve
기본적으로 FIFO 알고리즘을 사용한다. 자주 사용되는 프로세스는 bit가 1이 되고 아니면 0이 된다. 작은 OVerhead를 가지고 LRU를 만들기 위한 방식이 이것이 된다. (설명 잘 못들음..ㅜ)
Page Buffering Replacement
list of free frame을 봤더니 일부 frame은 modify bit이 1이고 0이다. 1인 친구들은 언제 요구될지 모르지만 당장은 급한 것이 없지만 미래를 위해서 대비하기 위해서 modify bit이 0인 친구를 계속 write하는 것이다. 이 경우 modify bit이 0으로 되고 Read만 할 수 있게 되는 것이다.
Allocation of Frames
각 프로세스한테 Physical Frame을 몇 개씩 나눠줄 것인가이다. 일정 숫자 이후로 Free Frame들이 떨어지면 Page fault가 급격하게 많이 발생한다.
Allocation ALgorithm
프로세스가 n 개 있다고 하자. m / n개씩 프로세스를 나눈다고 해보자. 프로세스의 사이즈에 비례하는 방법이 있다. si는 프로세스의 크기이고 S는 전체 프로세스들의 크기이다. 우선순위에 따라 중요도를 부여하자.
Thrashing
page fault가 급격하게 발생하면 소리가 커진다. 세로축이 CPU Utilization이다. 프로세스가 많아지면 할일이 많아지므로 할일이 증가한다. 일정 숫자 이상으로 늘어나면 CPU Utilization이 이하로 확 떨어진다. 여기서는 일을 못한다. Swapping만 계속 하고 이때 Disk를 사용하므로 CPU의 Utilization이 확 떨어진다.
Thrashing
세로축은 page 번호이고 가로축은 시간이다. 회색 부분이 CPU Access에 해당한다. 메모리가 균일하게 Access하지 않는다.
Working Set
최근에 Access된 페이지 들의 집합이다. 저 그림에서 window size가 10이다. 10칸짜리 안에 들어오는 페이지의 Set이 몇 종류 안된다. working set size의 이상을 주면 Threshing을 줄일 수 있다는 것을 의미한다.
Working-Set
새로운 Working Set이 나오는 경우에 Page fault 가 계속 발생하게 된다. 그 이후 Page fault가 발생하지 않다가 다른 Working Set이 또 올라오게 되면 그 때 fault가 또 발생한다.
