cs/운영체제

10강 - 2. Virtual Memory

Tomato_Coffee 2023. 11. 13. 18:06

  • 어떤 걸 쫓아낼까? = 캐슁 기법
    • 한정된 빠른 공간에 저장 후, 후속 요청 시 캐시에서 서비스함.
    • cache memory, buffer caching, Web caching - 멀리 떨어져 있는 컴퓨터에서 꺼내오는데 시간이 걸리기 때문에 캐시를 사용
    • 캐시 운영을 할 때, 시간 제약이 있다.

  • Paging System에서 LRU, LFU 가능?
    • page table에서 주소 변환을 할 때, 주소 변환은 하드웨어가 한다. (운영체제는 관여하는 일이 없다)
    • 그러나 page fault가 발생하면 disk(i/o 발생)에 접근해야 하기 때문에, cpu의 제어권이 운영체제에게 넘어감.
      • 과연 운영체제가 어떤 페이지가 얼마나 오래되었는지, 얼마나 참조되었는지 알 수 있을까?
        • 결론은 운영체제는 알 수 없다이다.! 
        • 어떤 프로세스가 요청한 페이지가 이미 메모리에 있으면 운영체제에게 cpu가 안 넘어간다.
          • 하드웨어적으로 주소 변환을 해서 cpu로 읽어 들인다.
            • 그러면 해당 페이지의 접근시간을 운영체제가 알 수가 없다(cpu 제어권이 운영체제로 넘어가지 않았기 때문)
        • 반면에 page fault가 발생하면, cpu 제어권이 운영체제로 넘어가게 되는데
          • 이때는 운영체제가 disk에 있던 페이지가 메모리로 올라온 시간을 알 수 있다.
        • 결론 : paging system에서 운영체제에게 반쪽자리 정보만 전해진다.
    • Paging system에서 LRU, LFU 같은 알고리즘은 virtual memory system에서 사용할 수 없다.
      • 그러나 buffer caching, Web caching에서는 사용할 수 있다.

  • Clock Algorithm
    • LRU의 근사 알고리즘 
      • second chance algorithm
      • NUR (Not Used Recently)
      • NRU (Not Recently Used) 
        • 운영체제는 가장 오래전에 참조된 page를 모른다.
        • 그래서 최근에 사용되지 않은 page를 내쫓는다.
    • 어떤 page가 참조가 되어서 cpu가 그 page를 사용하게 되면 
      • page에 붙어있는 reference bit을 1로 세팅한다. - 하드웨어가 bit를 세팅해 준다, 운영체제가 해주는 게 아님
      • page fault가 발생하여 page를 쫓아낼 상황이 온다면? 
        • 운영체제는 하드웨어가 세팅한 reference bit을 참조하게 된다.
          • reference bit == 1이면?
            • 해당 레퍼런스 비트를 0으로 바꾸고 그다음 bit를 확인한다(마치 시곗바늘이 움직이는 것처럼).
          • reference bit == 0 이면?
            • 레퍼런스 비트가 0인 페이지를 쫓아낸다.
    • LRU와 정확히 일치되는 운영은 하지 못하지만 적어도 시계 한 바퀴를 돌아오는 동안 참조가 안된 페이지를 쫓아내기 때문에 어느 정도는 LRU와 비슷한 효과는 낼 수 있다.
    • modified bit ( = dirty bit)
      • 어떤 페이지가 write가 발생하면 하드웨어가 modified bit을 1로 세팅한다. 
        • 그 페이지는 적어도 한 번은 cpu에서 write를 한 것이다.
        • 이 페이지가 메모리에서 쫓겨날 때는 그냥 쫓겨내는 게 아니라 backing store에 수정된 내용을 반영을 한 후에 메모리에서 지워야 한다.
        • 이걸 응용을 해서 modified bit = 0 인걸 우선 쫓아낸다면, 디스크에 쫓겨난 페이지를 써줄 필요가 없기 때문에 i/o가 적게 일어난다.
          • 조금 더 빨라진다.

  • 예를 들어서 어떤 loop를 구성하는 page가 여러 개 있다고 하면, 해당 페이지들은 전체 할당해 주는 게 효율성이 높다.
    • 어떤 for문이 3개의 page로 구성되었을 때, 이 프로그램에게 page를 2개만 줬으면 page fault가 일어나기 때문이다.
  • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수를 맞춰서 메모리에 할당해 주는 게 좋다.
  • 프로그램 별로 allocation을 해주지 않으면, 특정 프로그램이 메모리 전체를 장악하는 문제가 생길 수 있다.
    • 그래서 allocation이 필요하다.
  • Equal allocation
    • 똑같은 개수 할당
    • 프로그램마다 크기가 다르기 때문에 비효율적이다.
  • Proportional allocation
    • 프로그램 크기에 따라서 비례하여 페이지 할당
    • 같은 프로그램이라도 시간에 따라 필요로 하는 페이지 개수가 다를 수 있다.
      • 그래서 꼭 크기에 비례해서 메모리를 할당해 주는 방법이 적절하지 않을 수 있다.
  • Priority allocation
    • 프로세스의 우선순위에 따라서 할당.

  • 사실 allocation을 해주지 않더라도 LRU, LFU 같은 replacement  알고리즘을 사용하다 보면 알아서 어느 정도 할당이 되는 효과를 얻을 수 있다.
  • Global replacement 
    • 그때그때 프로세스 별로 메모리 할당량이 자동으로 조절이 된다.
    • 다른 프로그램의 페이지도 쫓아낸다.
    • 그래서 굳이 미리 allocation을 하지 않는다는 방식
  • Local replacement
    • 자신에게 할당된 메모리에 대해서 쫓아내고, 대체한다.

  • Thrashing : 프로그램에게 메모리가 너무 적게 할당이 되어서, page fault가 지나치게 자주 일어나는 일

X축 : 프로그램이 메모리에  load 되어있는 개수, Y축 : CPU 이용률

  • 어느 시점에 cpu의 이용률이 뚝 떨어진다.
    • thrasing 발생
      • OS는 cpu utilization이 낮아진 것을 보고 MPD(Multiprogramming degree)를 높여야 한다고 판단해서 더 많은 프로그램을 메모리에 load 한다. 
      • 이로 인해서 프로세스 당 할당된 frame 수가 더욱 감소한다. (악순환)
    • 이런 상황을 막기 위해서  MPD를 조절해 줘야 한다.
      • 동시에 메모리에 올라갈 수 있는 프로세스의 개수를 조절해야 한다.
      • 프로그램이 어느 정도는 메모리 확보를 할 수 있도록 해줘야 한다.

  • Working set : 빈번히 참조되는 page들의 집합.
    • Working set은 적어도 메모리에 한꺼번에 올라와 있도록 보장해 주는 기법이 있어야 page fault가 잘 안 난다. 
    • 어떤 프로세스의 Working set이 한꺼번에 올라가는 게 보장이 되지 않는다면, 그 프로세스의 메모리를 통째로 빼앗는다.
      • swap out 한다.

  • working set 알고리즘
    • working set은 우리가 미리 알 수 없다.
      • 따라서 과거를 통해서 working set을 추정한다.
      • 과거 델타 시간 동안 참조된 페이지들을 working set으로 간주
        • cf) delta 시간을 '윈도'라고 부름
          • 창문을 한 뚫어놓음
        • t1이 현재시점일 때
          • 윈도 사이즈만큼 창문을 뚫는다. 
            • 여기서는 윈도 사이즈를 10으로 설정
              • 현재 페이지부터 과거 10번째 참조된 페이지까지 해당 프로그램의 working set으로 설정
          • WS(t1) = {1,2,5,6,7} : 여기 5개의 페이지가 현재시점에서의 working set이다.
          • working set 알고리즘은 이 프로그램에게 5개의 page frame을 줄 수 있으면 {1,2,5,6,7}를 메모리에 올려놓는다. 만약에 메모리 공간이 부족해서 5개를 못준다면, 전부다 disk로 swap out 하고 해당 프로그램은 suspend 한다.
      • working set의 크기는 바뀐다.!
        • t2 시점일 때의 working set은 2개이다.
          • 2개의 프레임만 할당해 주면 working set을 만족한다.
    • 이런 식으로 working set 알고리즘은 멀티프로그래밍 degree를 조절하면서 working set을 메모리에 보장하게 된다.

PFF

  • 이 방법도 Multiprogramming degree를 조절하면서 Thrasing을 방지하는 알고리즘이다.
  • 이 방식은 직접 page fault를 보는 것이다.
    • 현재 시점에 시스템에서 page fault가 얼마나 나는지 본다.
    • 특정 프로그램이 page fault를 얼마나 내는지 본다.
      • page fault를 많이 일으키는 프로그램은 page frame을 더 준다.
      • page fault가 많이 안나는 프로그램은 page frame을 줄인다.

  • page size는 4KB
  • 근데 64bit 주소체계로 바뀌고, 메모리 크기도 커지기 때문에 page size가 작으면 page table이 커져야 한다.
  • 따라서 최근에서 대용량 page를 사용하기도 한다.
  • 만약에 페이지 사이즈를 줄이면 페이지 개수가 증가, 페이지 테이블의 entry가 증가하므로 페이지 테이블의 크기가 커진다.
    • 페이지 테이블 안에서 사용이 안 되는 부분이 줄어 들것이다.
      • 잘게 썰어서 효율적
    • 메모리 이용이 효율적
      • 페이지 크기가 크면, page fault가 났을 때 꼭 필요한 정보만 메모리에 올라오지 않을 수 있다.
      • 반대로  Locality 활용에서는 페이지 크기가 큰 것이 좋다.
        • 왜냐하면 프로그램에서 어떤 함수가 실행이 되면, 그 함수를 구성하는 code들이 순차적으로 참조가 되기 때문에 page fault가 발생했을 때, page 하나를 통째로 올려놓으면 아래쪽에 있는 메모리 위치들은 메모리에 올라온 이후로 page fault가 발생하지 않고 참조할 수 있게 된다.
    • 페이지의 크기가 커지면 Disk transfer의 효율성이 증가
      • seek : 디스크 헤드가 이동을 해서 특정 위치를 읽거나 써야 함
        • seek를 하는데 시간이 많이 걸린다.
        • 그래서 가능하면 많은 양의 뭉치를 읽어서 메모리에 올리는 게 디스크 효율성 측면에서 좋다.
    • 최근에는 page size를 키워주는 추세이다.
저작자표시 비영리 변경금지 (새창열림)