ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Operating System: Virtual Memory (Chapter 8)
    카테고리 없음 2022. 3. 10. 19:49

    Virtual Memory

    • physical memory보다 더 큰 프로세스를 돌리고 싶어졌다
    • 그래서 'process 전체가 memory에 올라와야 실행 가능하다'라는 대원칙을 깨리고 하면서 탄생한 것이 virtual memory
    • CPU는 virtual memory만 알고 있고, OS가 virtual memory와 physical memory 사이 연결을 돕는다
    • memory space가 무한대로 늘어나는 것. memory utilization이 증가한다

    Demanding Paging

    • Virtual memory의 핵심 기술
    • CPU가 요청할 때, OS가 해당 page를 memory에 올려주는 것 
    • 장점: less I/O needed, less memory required, fast response time, more processes
    • Lazy swapper: process 실행 시, 전체를 다 통으로 memory에 올리는 것이 아니라, CPU가 필요로하는 것만 그때 그때 올리는 것. (필요로하지 않는 애는 계속 올라오지 않음)
    • 또다른 장점: Copy-on-Write
      • parent process에서 fork해서 생긴 child process는 서로 virtual memory address는 다르지만, 같은 physical memory address를 참조하고 있다
      • 그러다가 두 process 중 하나가 reference에 대해 write를 시도하면, 그 시도한 process가 (그때서야) copy된 physical memory를 갖는다
      • 장점: memory 효율 증가, response time 감소
      • 단점: write하는 순간에 성능 저하 (시간 오래 걸림)

    Page valid-invalid bit

    • page table에서 해당 page의 상태를 표시하는 bit
    • 아래 세가지 의미를 지닌다
      • illegal: page에 접근할 수 없는 상태
      • not in memory: memory에 해당 page가 올라오지 않는 상태 >> page fault를 일으킴
      • obsolete: memoery에 page가 있긴 한데 뭔가 잘못된 상태 >> page fault를 일으킴

    Page fault

    • page의 valid-invalid bit이 not in memory나 obsolete을 의미해서, physical memory에 해당 page를 (re)load 해야하는 상황
    • 이 때, OS는 kernel mode로 전환되어, page fault handler를 작동시킨다
    • page fault handler 작동 과정
      1. page table에서 invalid bit 확인 (illegal -> abort, not in memory/obsolete -> continue)
      2. OS가 kenrnal mode로 전환 (page fault trap = page fault handler 시작)
      3. disk로 가서 page 가져옴 (I/O 발생)
      4. 동시에 physical memory에 free frame이 있는지 확인, 있으면 거기에 해당 page 넣어줌
      5. page table에서 bit을 valid로 전환 (이때 process state는 waiting -> ready queue로 전이)
      6. process state가 running으로 바뀌면 page fault handler의 역할은 끝난다

     

    Page Replacement

    • memory에 빈 공간이 없을 경우, page를 하나 memory에서 내려야 한다
    • 이 알고리즘이 잘못되면, page fault가 많이 발생한다
    • 따라서 최대한 page fault가 적게 일어나는 알고리즘을 찾아야한다

    First in First out (FIFO)

    • Belady's Anomaly: 사용가능한 frame 수가 늘어남에도 불구하고 page fault 횟수가 증가하는 이상 현상
    • 즉 알고리즘을 잘 짜지 않으면, resource의 풍부함을 누리지 못한다

    Least Rencently Used (LRU) Algorithm

    • FIFO보다 나음
    • 그러나 최근 reference된 page 정보를 담고 있는 stack을 관리/유지해야하는 overhead가 너무 크다
    • 따라서 실제로 사용하기는 어려움

    LRU Approximation Algorithm

    • LRU랑 최대한 비슷하게 알고리즘을 짜보자는 아이디어
    • LRU스럽게 만드는 대신, overhead를 최대한 줄여보자
    • Valid/invalid bit 방식: overhead는 많이 줄지만, victim page의 퀄리티가 너무 떨어진다
    • Additional-reference bit 방식: 8bits를 두고, 참조될 때 마다 수를 하나씩 올림
    • Second-chance (clock) algorithm 방식: FIFO나 circular queue에 reference bit들이 들어있다. 해당 page를 replace해야할 때가 되면, 우선 잠시 reference bit을 확인한다. 이때 이 bit가 0이면 replace하고 1이면 기회를 한 번 더 준다. 

    Physical Memory Allocation Policy

    • Fixed Allocation (= local allocation): 사용가능한 frame 수 / 전체 프로세스 수 만큼을 각 프로세스에게 제공한다
    • Priority Allocation (= global allocation): priority가 높은 프로세스에게 더 많은 수의 frame을 제공한다

    Thrashing

    • CPU가 자주 참조하는 page보다 frame 수가 적으면, 급격하게 많은 page fault가 발생하면서 CPU utilization이 저하되는 현상
    • 이를 방지하기 위해서는 allocated memory size > sum of locality를 보장해야한다
      • locality (spatial locality & temporal locality)를 활용해서 window size를 잡는데, 이를 working set이라고 한다

     

    Virtual Memory의 몇가지 Issue

    1. Prepaging: page fault 발생 수를 줄이기 위해서 process 시작 시, 미리 page를 여러개 memory에 올리는 것

    2. Page size: page size를 결정하는 문제. 최근 트랜드는 larger page size를 선호한다. (장: page memory size 감소, page fault 감소, 단: internal fragment 증가)

    3. TLB Reach = (TLB Size) X (Page Size): TLB에 의해서 접근 가능한 memory size를 의미. 당연히 클 수록 전체 속도가 빨라짐

    4. Progrma Structure: 프로그램을 어떻게 코딩하느냐에 따라서 page fault 발생 수가 차이난다

    for(j=0; j<128; j++)
    	for(i=0; i<128; i++) //page fault
        	data[i][j] = 0
    for(i=0; i<128; i++) //page fault
    	for(j=0; j<128; j++)
        	data[i][j] = 0

     

    위에는 page fault 가 128 x 128회 발생하고 아래는 128회만 발생

    댓글 0

Written by Geulleun