Operating System 기본 개념 - 메모리

메모리 관리

virtual address에서 physical address로 어떻게 변환 할 것이냐?

1. 메모리 주소는 execution time때 binding되며 매 수행마다 주소가 바뀔수 있다. 빠른 수행을 위해서는 하드웨어에 도움과 mapping table이 필요하다.
2. Process마다 각자 address space를 가지고 있다. => 각 process마다 가지고 있는 address space(virtual memory)를 physical memory로 올려야된다.
3. H/W에 도움을 받아서 빠르게 변환이 가능하다. (MMU(Memory Management Unit) : 메모리 관리에 사용되는 H/W를 통칭하여 부르기도 함)

Concept	Address transration	MMU(H/W)	Protection	Issue
ContiguosAllocation(process 메모리 영역을 연속적으로)	Base address +Logical address=physical address	Reloation registerLimit register	Logical address <=Limit register(범위가 벗어나는 것을체크함)	External Fragmentation(process의 physical memory가 전체 메모리의 합보다는 작지만 들어갈 수 없는 상황)
Paging(같은 크기 size로 logical과 physical를 나눈다.)	Page Table(Page#와 Frame#와 mapping정보가 있는 Table)Process마다 하나씩 가지고있다.(Frame# * frame size) + offset	PTRR, PTLR->page table을 빠르게 접근하기 위해TLB->page table를 접근하는게 자주 접근하는 page를 따로 저장하여서 빠르게 frame#를 찾는다.	Page Table에 하나의 비트가 더 존재(V/I bit)하여서 잘못된 접근인지 알 수 있다.	Page Table의 크기 해결제시1) Hierarchical paging 해결제시2) Hashed page table 해결제시3) inverted page tableInternal Fragmentation
Segmentation(같은 segment는 연속적이어야한다.)	Segment table	STBR,STLR	Limit와 offset비교(limit > offset)	Protection(segment에 특정한 옵션을 줄수 있다.)

Paging (매우 중요)

• virtual address와 logical address를 특정 size로 나눈다. 그 나눈 virtual address영역을 page라고 하고 logical address영역을 frame이라고 한다. 각 process는 page와 frame이 mapping되어진 table를 가지고 있다. 그런데 이 page table을 접근하여서 frame#를 찾는데 2번의 메모리 접근이 필요해서
• 문제1) 너무 많은 시간이 걸린다. 그래서 빠르게 도와주는 TLB라는 하드웨어(H/W cache)가 도와준다.
• 그런데 process마다 문제2) page table을 가지고 있다보니 많은 메모리 공간을 차지하게 되고 그것을 줄이기 위해 3가지 방법이 제시되었다.
  • (Hierarchical paging)Page table이 단계적으로 존재하여서 여러 단계로 존재하는 page table을 접근하면서 존재하지 않은 page table은 사용x
  • (Hashed page table)Hash table을 이용한 방법
  • (inverted page table)frame#와 page#를 바꾼 page table을 만든다. 하지만 pid를 찾는데 search time이 오래걸린다.

Demand paging

전체 virtual memory의 합은 physical memory의 합보다 크기 때문에 virtual memory를 항상 physical memory에 올릴 수 없는 상황이기에 process의 특정 부분만 memory에 올라가 있다. 그래서 process가 그 page가 필요할 때만 physical memory를 올리기 위해 요청을 하여 physical memory에 올릴 수 있다.

Valid & invalid bit

Page table에 V/I bit는 현재 이 page가 메모리에 올라가 있는지 확인시켜준다. Vaild인 경우 현재 메모리에 올라가 있고 바로 접근가능하지만 invalid인 경우 page fault로 trap이 발생

Page-fault trap 과정

1. Page table에서 해당 page가 invalid인 경우(물리 memory에 안올라가있는상태)
2. Trap 발생
3. 올릴려고 하는 page를 backing store(disk)에서 찾는다.
4. 빈 frame를 찾는다. -> 없는 경우 victim frame를 설정하여서 쫓아낸다.
5. 빈 frame에 backing store(disk)에 page를 넣는다.
6. Page table과 frame table을 업데이트시킨다.(V/I bit -> v로 변경)
7. 다시 그 명령어를 수행한다.

Pure paging

실제 demand paging으로 설계를 했을때 무조건 처음에는 page fault가 난다. 그런데 page fault로 인해 발생하는 오버헤드가 매우 커서 줄이는게 좋다. 실제 program마다 집중적으로 접근하는 page가 존재하여서 실제로 많은 page fault가 발생하지 않는다. (locality(지역성)를 따른다.)

Page replacement의 과정

1. 해당 Page를 disk에서 찾는다. (backing store)
2. Free frame를 찾는다. 존재한다면 그것을 사용하고 존재 하지 않는다면 victim frame를 찾는다.
3. 해당 frame에 사용되던 Page를 다시 disk에 저장하고 (업데이트되지 않았더라면 저장할 필요x) victim frame에 해당 page를 올린다.
4. 그 후 table을 업데이트하고 다시 명령을 수행한다.

Replacement algorithm

⇒ Page fault를 줄이는 것을 목표로 한다.

1. FIFO algorithm
   • 먼저 들어온 page를 victim으로 선정
2. Optimal algorithm
   • 미래를 봐서 가장 오랫동안 접근 안되는 page를 victim으로 선정 (불가능)
3. LRU(Least Recently Userd)
   • 가장 최근에 안쓰는 frame를 victim으로 선정
   • 구현을 위해 두가지 방법(Counter와 stack)

LRU approximation algorithme(LRU를 구현을 위한 algorithm)

1. Reference bit
   • 방법) Frame마다 참고bit를 만들어서 참고했을 경우 체크를해준다.
   • 단점) 언제 참조되었는지 확인하지 못하여서 순서를 모른다.
2. Additional-reference-bit algorithm

• 방법) 각 시간별로 참조하였는지 bit를 만들어서 확인한다. 가장 왼쪽에 있는 bit가 켜져있다는 것은 가장 최근에 사용한거임.
• 단점) 이 bit를 관리하는데 overhead가 존재

1. Second chance algorithm(clock algorithm)

• 방법) 하나의 reference bit가 존재. Physical memory에 있는 page들을 계속 순환하면서 reference bit가 1이면 0으로 바꾸고 다음 page를 확인하며 reference bit가 0이면 그 page를 victim으로 설정한다. 그리고 새로운 page가 들어가고 reference bit는 1로 설정되고 clock hand는 다음 page를 가르킨다.

Thrashing

physical memory가 부족하여서 swapping(paging) 빈도가 많아지고 그러면서 disk I/O(page를 disk에서 가져와야되기 때문에)가 많아지면서 cpu 처리율이 떨어지는 현상

working set model

thrashing이 발생되는지 여부를 파악하는 방법. 특정 시간에 process별 locality의 합이 전체 physical memory보다 큰 경우.(전체 process별 page요청 수의 합 > physical memory size)