Virtual Memory 2: clock algorithm, page frame allocation, thrashing, page size의 결정

ㅎㅎ·2023년 8월 9일
운영체제
0

운영체제, 반효경

목록 보기
19/19

다양한 캐슁 환경

  • 캐슁 기법

    • 한정된 빠른 공간(캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
    • paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용 기 위한 다양한 환경에서 사용됨
    • cache memory: cache hit, cache miss 구조
    • buffer caching: file system에 대한 read/write 요청을 메모리에서 빠르게 서비스하는 방식
    • 느린 매체로 인한 소요 시간을 절약하기 위한 것
    • Web caching: 웹 페이지 요청에 대해 server에서 수신 받아 웹브라우저에 표시, 만약 동일 URL에 대해 다시 요청한다면 server에 다시 다녀오지 않고 이미 캐시에 저장된 요청 결과를 가져옴, server와 client의 공간적 거리로 인한 소요 시간을 절약하기 위한 것

  • 캐쉬 운영의 시간 제약

    • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
    • Buffer Caching이나 Web Caching의 경우
      • O(1)에서 O(logN) 정도까지 허용
    • Paging System인 경우
      • page fault인 경우에만 OS가 관여함
      • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
      • O(1)인 LUR의 list 조작 조차 불가능

  • LRU와 LFU paging system에서 가능한가? NO!
    • Process A가 실행중에 invalid한 페이지를 읽음 -> page fault 발생
    • 프로세스가 I/O 작업을 할 수 없기 때문에, trap이 발생하고 CPU 제어권을 운영체제에게 넘김
    • O.S가 디스크에서 메모리로 요청한 page를 올림, 필요하다면 page replacement 수행
      • "과연 운영체제가 가장 오래된 혹은 가장 참조 횟수가 적은 page를 알 수 있는가?" 없다
      • why? 프로세스가 요청한 페이지가 이미 메모리에 올라와 있는 경우에는 CPU가 O.S에게 넘어가지 않음, 따라서 O.S는 이 경우에 page 접근 시간이나 접근 여부를 알 수가 없음
      • 반면 page fault가 나면 운영체제가 디스크에 있는 page를 메모리로 올린 시간을 알 수가 있음, 따라서 반쪽만 정보를 가지고 있음
      • 즉 재참조의 경우 운영체제에게 CPU 제어권이 넘어가지 않고 HW만으로 주소 변환이 이루어지므로 page 정보에 관한 list 관리를 할 수가 없음
      • 따라서 Paging System에서 LRU, LFU는 사용할 수 없음!!!(교재에 소개되어 있기에 설명하였고, 또한 buffer caching이나 web caching에서는 사용 가능함)

Clock Algorithm

  • Paging System에서 사용 가능한 replacement 알고리즘

  • HW는 page를 참조할 때 reference bit를 1로 만들어 놓음
  • page replacement 상황이 발생해 O.S가 쫓아낼 page를 찾기 위해 시계를 돌면서 reference bit를 확인함
  • 1인 page는 bit를 0으로 바꿔 놓고, 움직이다가 0인 page를 발견하면 쫓아냄
  • 이는 곧 bit가 0인 page는 replacement를 위해 시계를 한 바퀴 도는 동안 한 번도 참조된 적이 없는 page임을 의미
  • 적어도 시계바늘이 한 바퀴 도는 동안에 참조가 되지 않은 page를 쫓아내기에 LRU까지는 아니지만 근사한 작업을 수행할 수 있음
  • paging system에서 일반적으로 사용하는 알고리즘
  • 메모리에 올라온 후에 write하여 수정된 이력이 있는 page의 경우 I/O 작업을 진행해야 하기 때문에, 이를 확인할 수 있는 modity bit를 둠. 디스크 I/O 작업의 시간이 오래 걸리기 때문에 modify bit이 1인 page는 쫓아내지 읺고, 0부터 쫓아내는 방식 등으로 replace 시간을 좀 더 개선할 수 있음.

Q. Swap in, Swap out의 경우에 paging 기법처럼 modify bit가 없으면 수정됐는지 어떻게 확인하고 disk I/O 작업을 실시하는거지 그럼?

  • GPT에 따르면 dirty bit가 어떤 방식에서든지 존재한다고 함. 그래야 변경사항이 있을 경우만 디스크 I/O를 수행하게 해 효율성을 높일 수 있기 때문에

Q.Disk I/O 작업은 어차피 disk controller가 하는 거면 쫓아 내고 다른 page를 메모리에 올리는 거에는 문제가 없지않아? I/O 작업 소요 시간은 고려하지 않아도 되는 거 아닌가?

  • 메모리 관리의 효율성 측면에서 보면 수정한 이력이 있는 page라도 다시 참조될 가능성이 있는데, I/O 작업을 하고 있으면 재참조 호출 때 ready 상태에 있지 않아서 다른 page를 호출해야 하는 반면에, 수정 이력이 없는 page의 경우 이런 상황이 발생하지 않으니까 최대한 이런 상황이 발생하지 않도록 수정 이력이 없는 걸 먼저 쫓아내는 방식을 고려해볼 수 있을 듯.
  • Q. 주소변환을 도와주는 HW는 뭐가 있지? 각각의 메모리 관리 기법에서 어떻게 도와주지?

Page Frame의 Allocation

  • 지금까지는 어떤 프로세스의 page인지 고려하지 않고 알고리즘에 따라 swap out 했는데, 실제로는 해당 프로세스의 어떤 page가 사용되고 있으면 같은 프로세스의 다른 page들도 메모리에 올라와 있는 것이 효율적임

    • 예를 들어 page1에서 for문을 100만 번 반복하면서 로직을 실행할 때 page2, page3가 같이 사용된다면? 모두 메모리에 올라와 있어야 page fault가 발생하지 않음, 그러나 page2,나 3이 swap out 되어 있으면 계속 page fault가 발생함
    • 혹은 code영역을 실행 중에는 필시 data 영역에 접근하게 될텐데, 그렇다면 data 영역의 page도 같이 올라와 있는 것이 효율적일 것임
    • 이와 같이 프로세스별 page 할당 방식을 조절하는 것 중에는 Global 방식과 Local 방식이 존재
      • Global 방식의 경우 프로세스 별로 자신만의 frame 영역을 따로 할당해주지는 않음
      • 각종 알고리즘에 의해 빈번하게 실행되는 프로세스의 경우 메모리를 더 많이 할당받는 방식으로 계속적으로 조절해나감
      • Local 방식의 경우 프로세스 별로 할당된 frame 영역이 존재하고 그 내에서 각종 알고리즘을 이용하여 replacement 함

Thrashing

  • Thrashing을 막기 위해 multiprogramming degree를 조절해줘야 함
  • 이를 위한 알고리즘이 PFF, Working set 알고리즘

Working-Set Algorithm

  • locality: 프로세스가 특정 시간 동안 일정 장소만을 집중적으로 참조하는 특성, ex) for문 실행시 반복문 안의 코드만 수행되는 데 이에 해당하는 page들
  • 많은 프로세스들이 메모리에 올라와 있어 필요한 working set을 모두 할당받지 못 할 때는 모든 메모리를 반납해버림(swap out)

  • working set을 미리 알 수 없으므로, 과거를 통해 파악
  • 과거 델타 시간(windo라고 함) 동안 참조된 page들을 working set으로 봄
  • 현재 시점으로부터 window size인 과거 10번째까지 참조된 page들은 메모리에 모두 올라와 있어야 하는 page들
  • 따라서 working set page를 모두 RAM에 올릴 수 있도록 그 크기만큼 frame을 할당할 수 있으면 해당 프로세스를 메모리에 올리고, 그렇지 않으면 전부 메모리에서 swap out 시키고 suspended 상태가 됨
  • Working set은 시간이 지남에 따라 계속 변화함

PFF(Page-Fault Frequency) Scheme

Page Size의 결정

  • page size는 어떻게 결정하는가?

  • 주소체계가 64bit, RAM 크기도 커지면서 4KB 페이지가 아닌 더 큰 페이지 크기를 사용하는 시스템도 늘어나고 있음

  • 메모리 크기가 커지면 page table도 커지기 때문에 그만큼 낭비하는 공간이 많아질 수 있음, 따라서 페이지 사이즈를 키워줄 필요가 있음

  • Page size를 감소시키면

    • 페이지 수 증가
    • 페이지 테이블 크기 증가
    • 내부 조각 감소
    • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적, page fault가 났을 때 해당 부분만 선별하여 메모리에 올릴 수 있으므로
    • 반면 locality 활용 측면에서는 좋지 않음, 프로그램이 함수를 실행하면 그 함수를 구성하는 코드들이 순차적으로 연달아 참조되는데, page 크기가 크면 이 코드들을 한 페이지에 담아서 바로 메모리에 올릴 수 있으므로 첫 참조 이후 page fault 발생 확률이 감소함
    • Disk transfer의 효율성 감소
      • disk의 head가 이동하면서 rotation을 하는 시간이 오래 걸리기 때문에 가능한한 많은 용량을 메모리에 올려 놓으면 disk seek time이 감소함
profile
ㅎㅎ
Hello World
이전 포스트

Virtual Memory 1: Demand paging, page fault, page replacement algorithms

0개의 댓글