운영체제 스터디 (10) - 가상 메모리 관리

Posted on | In

운영체제 스터디 도중 쉽게 배우는 운영체제를 읽고 요약한 내용입니다. 자세한 내용은 책을 구매하여 확인 부탁드립니다.

9. 가상 메모리 관리

요구 페이징

요구 페이징의 개요

  • 사용자가 요구 할 때 해당 페이지를 메모리로 가져 오는 것을 요구 페이징이라 칭함
  • 요구페이징을 하는 이유
    • 가급적 적은 양의 프로세스만 메모리에 올라 와 있어 메모리를 효율적으로 관리 할 수 있다
    • 필요한 모듈만 메모리에 올려 응답 속도를 향상 시킬 수 있다
  • 단점
    • 필요한 모듈만 메모리에 올려 놓고, 나머지 모듈은 필요 할 때 모듈에 메모리에 올리게 되는데, 이 때 이미 올라와있는 필요한 모듈들이 장기가 사용되지 않으면 문제가 있을 수 있다
  • 미리 가져오기
    • 앞으로 필요 할 것이라고 예상되는 페이지를 미리 가져오는 방식
    • 캐시가 대표적인 예시
    • 캐시 히트율이 낮을 경우 성능에 좋지 않음 → 요구 페이징을 주로 사용

페이지 테이블 엔트리의 구조

  • 페이지가 스왑 영역에 있는 경우는 크게 두가지
    1. 요구 페이징으로 인해 처음부터 물리 메모리에 올라가 있지 못하는 경우
    2. 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우
  • 페이지 테이블에는 페이지가 메모리에 있는지, 스왑 영역에 있는지 표시 해야 하는데, 이때 사용하는 비트가 유효 비트
  • PTE ( Page Table Entry )
    • 페이지 테이블의 한 행
    • PTE는, 페이지 번호 / 프레임 번호 / 플래그 비트 로 구성 됨
    • 직접 매핑에서는, 페이지 번호는 필요 없음 ( 모든 페이지가 물리 메모리에 올라 와 있기 때문 )
  • 플래그 비트
    • PTE의 속성을 나타낸 비트
    • 접근 비트 ( Access bit )
      • 페이지가 메모리에 올라 온 후 사용 한 적이 있는지를 알려주는 비트
      • 해당 메모리에 읽거나, 실행 작업을 했다면 접근 비트의 값은 1이 됨
      • 참조 비트( Reference bit )라고도 칭함
    • 변경 비트
      • 데이터의 변경이 있었는지 알려주는 비트
      • 쓰거나 추가 작업을 했다면 변경 비트의 값은 1이 됨
      • 새로운 값으로 오염되었다는 의미로써 더티 비트 ( dirty bit )라고도 칭함
    • 유효 비트
      • 페이지가 실제 메모리에 있는지를 나타내는 비트
      • 현재 비트 ( present bit )라고도 칭함
    • 읽기 / 쓰기 / 실행 비트
      • 페이지에 대한 읽기 / 쓰기 / 실행에 대한 권한이 적힌 비트
      • 접근 권한 비트라고도 칭함
      • Segmentation table의 접근 권한 비트를 생각하면 됨

페이지 부재

  • 유효 비트가 0일 때에는 페이지가 메모리에 있으므로, 주소 필드엔 프레임 번호가 저장 됨
  • 유효 비트가 1일 때에는 페이지가 스왑 영역에 있으므로, 주소 필드엔 스왑 영역 내 페이지 번호가 저장 됨
  • 프로세스가 페이지를 요청 했을 때, 그 페이지가 메모리에 없는 상황을 페이지 부재 ( page fault ) 라고 칭함
  • 페이지 부재가 발생시 동작 방식
    • 해당 페이지를 사용 할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 함
    • 물리 메모리에 빈 공간이 있는 경우
      • 유효 비트를 0으로 바꾸고, 스왑 영역에 있는 페이지를 메모리의 비어있는 프레임에 가져감
    • 물리 메모리에 빈 공간이 없는 경우
      • 유효 비트를 0으로 바꾸고 → 페이지 교체 알고리즘 ( Page Replacement Algorithm )을 통해 대상 페이지 ( victim page )를 정함 → 대상 페이지를 스왑 영역으로 옮김 → 대상 페이지의 프레임에 옮길 페이지를 옮김

지역성

  • 메모리에 접근하는 패턴이, 메모리 전체에 고루 분포되는것이 아니라 특정 영역에 집중되는 성질
  • 물리 메모리가 꽉 차 페이지를 스왑 영역으로 보낼 때엔 되도록 사용하지 않을 페이지를 보내는 것이 좋음
  • 쫒아낼 페이지를 찾을 때는 지역성을 바탕으로 진행 하는 경우가 많음
  • 공간의 지역성
    • 현재 위치에서 가까운 데이터에 접근 할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높음
  • 시간의 지역성
    • 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용 될 확률이 높다는 것
  • 순차적 지역성
    • 작업이 순서대로 진행되는 경향이 있다는 것 ( 프로그래밍은, 윗줄에서 아랫줄로 가는 경향이 있음 )
  • 캐시의 지역성
    • 캐시는 지역성 이론을 사용하는 대표적인 장치
    • 지역적으로 가까이 있는 데이터를 캐시에 가져 옴으로써 캐시 히트를 높일 수 있음
    • 따라서 프로그램을 작성 할 때 goto 문을 사용하지 말라고 하는 이유를 위 경우에서 찾아 볼 수 있음
    • 현재 실행하는 행과 가까운 행을 캐시 메모리에 가져오고 있는데, 갑자기 goto 문을 사용하여 엉뚱한 행으로 이동 해 버리면 캐시 미스가 발생 할 수 있음

페이지 교체 알고리즘

페이지 교체 알고리즘의 개요

  • 스왑 영역으로 보낼 페이지를 결정하는 알고리즘
  • 메모리에서 앞으로 사용 할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시키는 것이 목적
  • 페이지 교체 알고리즘의 성능 평가 기준
    • 페이지 부재 횟수 ( 낮을수록 )
    • 페이지 요청 후 실제 작업에 들어갈때까지 걸린 시간 ( 짧을수록 )
    • 전체 작업에 걸리는 시간 ( 짧을수록 )

페이지 교체 알고리즘의 종류

  • 무작위 페이지 교체 알고리즘
    • 스왑 영역으로 쫒아 낼 대상 페이지를 특별한 로직 없이 무작위로 선정
    • 지역성을 전혀 고려하지 않은 방식
    • 구현이 간단하나, 성능이 별로라 사용되지 않음
  • FIFO 페이지 교체 알고리즘
    • Queue를 사용하고, 메모리가 꽉 차면, 먼저 들어온 페이지 부터 순서대로 스왑 영역으로 내보내는 방식
    • 메모리에 올라온지 오래 되더라도 자주 사용되는 페이지가 있는데, 이런 경우를 전혀 고려하지 않은 방식
    • 거의 사용되지 않으며, 이를 개선한 2차 기회 페이지 알고리즘이 존재 함
  • 최적 페이지 교체 알고리즘
    • 메모리가 앞으로 사용할 페이지를 미리 살펴보고, 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김
    • 미래의 접근 패턴을 아는 것이 불가능 하여 실제로 구현 할 수 없는 방식
  • LRU ( Least Recently Used page replacement algorithm )페이지 교체 알고리즘
    • 메모리에 올라 온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 보냄
    • 최근에 사용된 페이지는 놔두고, 오래전에 사용된 페이지를 대상 페이지로 선정
    • 최소 사용 페이지 교체 알고리즘이라고도 불림
    • 구현 방법은 여러가지가 있음
    • 페이지 접근 시간에 기반한 구현
      • 페이지에 접근한 시간을 기록하여 구현하는 방식
      • 페이지에 읽기 / 쓰기 / 실행과 같은 연산이 이루어진지 가장 오래된 페이지를 스왑 영역으로 보냄
      • FIFO 페이지 교체 알고리즘보다 우수하고, 최적 페이지 교체 알고리즘보다는 낮은 성능으로 알려짐
      • 접근 시간 기록을 위한 추가적인 메모리 공간을 필요로 하는것이 단점
    • 카운터에 기반한 구현
      • 접근 시간을 기록하여 구현 하는것과 비슷하게, 최초 시작 시간으로부터 지난 시간을 기록한 값인 카운터를 사용하여 구현
      • 카운터 기록을 위한 추가적인 메모리 공간을 필요로 하는것이 단점
    • 참조 비트 시프트 방식으로 구현
      • 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것
      • 참조 비트의 초깃값은 0 이며, 페이지에 접근 할 때마다 1로 바뀌고, 페이지에 접근 시 마다 비트 값이 오른쪽으로 한칸씩 이동
      1
      2
      3
      4
        페이지 참조비트
    A   01011010 ( 4번 접근 )
    B   10000000 ( 한번 접근 ) 
    C   00111101 ( 다섯번 접근 )
      • 위 경우를 보면, 값이 가장 작은 값은 C의 참조비트
      • 참조 비트가 가장 작은 값이 가장 나중에 참조 된 것을 의미하므로, 대상 페이지를 선정 할 필요가 있을 때, 참조 비트 중 가장 값이 작은 값을 대상 페이지로 선정
      • 적지 않은 공간을 사용
  • LFU( Least Frequently Used page replacement algorithm ) 페이지 교체 알고리즘
    • 페이지가 몇번 사용 되었는지를 기준으로 대상 페이지 선정
    • 최소 빈도 알고리즘으로도 칭함
    • 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김
    • 일반적인 경우 LRU 방식과 비슷한 성능을 띈다고 알려짐
  • NUR ( Not Used Recently page replacement algorithm )
    • 알고리즘에서 접근 시간이든, 접근 빈도든 정확한 값을 유지하는것은 의미가 없어 순위만 정할 수 있으면 된다는 생각을 기반으로 구현 한 알고리즘
    • 추가 비트 2개만 사용하여 미래를 추정하는 알고리즘 ( 접근 비트 ( read / execute 되면 1 ) / 변경 비트 ( write / append 되면 1 ))
    • 최근 미사용 페이지 교체 알고리즘 이라고도 칭함
    • LRU / LFU 방식과 비슷 한 성능을 보임
    • 초기상태는 모두 (0, 0) 인데, 접근이 발생하면 (1, 0) / 변경이 발생하면 (0, 1)로 변경하고, 둘 다 발생하면 (1, 1) 이 됨
    • 이중에서 (0, 0) → (0, 1) → (1, 0) → (1, 1)의 순서로 페이지를 스왑 영역으로 옮김, 즉 가장 사용이 안된 페이지를 스왑 영역으로 옮김
    • 모두 순위가 같다면 무작위로 옮기고, 모두 (1, 1) 이라면 모두 (0, 0)으로 변경 함
    • 가장 많이 사용되고 있음
  • FIFO 변형 알고리즘
    • 2차 기회 페이지 교체 알고리즘
      • 큐를 사용하지만, 특정 페이지에 접근하여 페이지 부재 없이 성공 할 경우, 해당 페이지를 큐의 맨 뒤로 이동하여 기회를 한번 더 주는 알고리즘
    • 시계 알고리즘
      • 큐를 사용하지만, 원형 큐를 사용하고, 큐에 참조 비트 하나가 추가 됨
      • 참조 비트는 해당 페이지가 참조 된 적이 있는지 없는지를 나타냄
      • 시계 알고리즘은 대상 포인터를 갖고 있는데, 스왑 영역으로 페이지를 보내야 할 경우 대상 포인터에 있는 페이지를 스왑 영역으로 보냄
      • 대상 포인터가 가리키고 있는 페이지가 스왑 영역으로 옮겨지면, 대상 포인터를 밑으로 이동시킴
      • 이때, 참조 비트가 1인 페이지는 건너 뛰고, 참조 비트를 0으로 변경 ( 자주 참조되었다고 간주 한번의 기회 더줌 )
      • 대상 포인터로 가리키고 있는 페이지가 hit가 되면, 참보 비트의 변경 없이 대상 포인터를 밑으로 이동 시킴
      • NUR 보다 적은 공간을 차지하지만, 복잡하고 계산량이 많은것이 단점

스레싱과 프레임 할당

스레싱

  • 물리 메모리가 작으면, 컴퓨터 속도가 느려지는데, 이는 스왑 영역에서 메모리로 페이지를 가져오는 과정이 자주 발생하기 때문
  • 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱이라 칭함
  • 물리 메모리 크기가 부족 할 때, 프로그램을 계속 실행 시키면 CPU 사용률이 증가 하다가 어느 구간부터 떨어지는 구간이 존재 하게 됨
  • 이 구간이 스레싱 발생 지점
  • 물리 메모리가 작으면, 스레싱 발생 지점이 메모리가 큰 경우 보다 빨리 올 가능성이 높음
  • 물리 메모리가 충분히 크면, 더 크다고 해서 컴퓨터 전반적인 속도에 의미는 없음
  • 남아 있는 프레임을 프로세스에 할당하는 방식도 스레싱에 영향을 줌

정적 할당

  • 프로세스 실행 초기에 프레임을 나누어 준 후 프레임 크기를 고정 하는 방식
  • 프로세스를 실행하는 동안 메모리 요구를 반영하지 못하는 단점이 있음
  • 균등 할당 방식
    • 프로세스의 크기와 상관 없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당
    • 크기가 큰 프로세스의 경우 필요한 만큼 프레임을 할당받지 못하기 때문에 페이지 부재가 빈번하게 일어남
    • 크기가 작은 프로세스의 경우 메모리가 낭비 됨
  • 비례 할당 방식
    • 프로세스의 크기에 비례하여 프레임을 할당하는 방식
    • 좀 더 현실적인 방식이지만 아래의 문제점이 있음
      • 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 할당하지 못함
        • 동영상 프로그램 같은 경우, 플레이어의 메모리 사용량은 적으나 동영상의 크기가 크기 때문에 메모리를 더 크게 잡아먹는데, 이 경우 처음에 받은 메모리가 부족 해 질 수 있음
      • 사용하지 않을 메모리를 미리 확보 해 놓기 때문에 공간을 낭비 할 수 있음
        • 큰 프로세스를 실행 하면서, 당장 필요 없는 프레임을 미리 할당해놓기 때문에 메모리가 낭비 되는 경우가 있음

동적 할당

  • 시시각각 변하는 요청을 수용하는 방식
  • 작업 집합 모델 방식
    • 최근 일정 시간동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지
    • 작업 집합 → 최근 일정 시간동안 참조된 페이지의 집합
    • 작업 집합 크기 ( working set size )
      • 물리 메모리에 유지할 페이지의 크기
      • 작업 집합에 들어갈 최대 페이지의 수
      • 현재 시점으로부터 시간적으로 가까운 페이지 부터 집합에 들어 감
      • 얼마나 자주 작업 집합을 갱신 하는것인지를 의미하기도 함
    • 작업 집합 윈도우 ( Working Set Window )
      • 작업 집합에 포함되는 페이지의 범위
      • 현재 시점에 최대 어느 범위까지의 페이지를 살펴 볼 것인가를 결정하는 것
      • 현재 시점으로 부터 시간적으로 가까운 페이지 부터 계산 됨
    • 작업 집합 윈도우의 크기에 따라 프로세스의 실행 성능이 달라 짐
    • 작업 집합 윈도우의 크기를 너무 크게 잡으면, 필요 없는 페이지가 작업 집합에 남음
    • 작업 집합 윈도우의 크기를 너무 작게 잡으면, 필요한 페이지가 스왑 영역으로 옮겨짐
    • 어떤 프레임을 물리 메모리에 담아 놓아야 하는지는 알 수 있지만, 프레임을 얼마나 할당 해야하는지는 알 수 없음
  • 페이지 부재 빈도 방식
    • 페이지 부재 횟수를 기록하여, 페이지 부재 비율을 계산하는 방식
    • 페이지 부재 비율의 상한선과 하한선을 설정
    • 페이지 부재 비율이 상한선을 초과 할 경우 → 할당한 프레임이 프로세스에 비해 적음을 의미 → 프레임을 추가적으로 할당
    • 페이지 부재 비율이 하한선을 초과 할 경우 → 할당한 프레임이 프로세스에 비해 많음을 의미 → 할당된 프레임을 회수
    • 프로세스가 처음 시작 될 때는 예측이 어려우나, 실행하며 적정 량을 조절 해 나감

프레임 관련 이슈

전역 교체와 지역 교체

  • 페이지 교체 알고리즘에 따라 페이지를 교체하는 방식을 나눌 수 있음
  • 전역 교체
    • 전체 프레임 ( 물리 메모리 전체 ) 을 대상으로 교체 알고리즘을 적용
    • 실행중인 프로세스의 프레임이 아닌, 다른 프로세스의 프레임을 스왑 영역으로 옮긴다면, 옮겨진 프로세스가 스레싱 발생 지점에 도달 할 수 있음
  • 지역 교체
    • 현재 실행중인 프로세스의 프레임 ( 현재 실행중인 프로세스가 차지하고 있는 만큼의 물리 메모리 전체 )만을 대상으로 교체 알고리즘 적용
    • 자신에게 할당된 프레임의 전체 개수에 변화가 없음 → 페이지 교체가 다른 프로세스에 영향을 미치지 않음
    • 자주 쓰여지는 페이지가 스왑 영역으로 가서 해당 프로세스가 스레싱 발생 지점에 도달 할 수 있음
  • 전체 시스템의 입장에서는, 전체 교체 방식이 지역 교체 방식보다 효율 적인 양상을 보임

페이지 테이블 크기

  • 윈도우 NT ( 32Bit )의 경우
    • 가상 주소 공간의 크기 : 2의 32승 Bit
    • 페이지 한개의 크기 : 2의 12승 Bit
    • 가상 주소 하나당 행의 개수 → 가상 주소 공간의 크기 / 페이지 한개의 크기 = 2의 20승개
    • 각 행을 표현할 주소 공간 → 20 Bit
    • 페이지 테이블 하나가 차지하는 물리 공간 → 2의 20승 * 20Bit → 약 2.62MB
  • VAX 운영체제의 경우 ( 32Bit )
    • 가상 주소 공간의 크기 : 2의 32승 Bit
    • 페이지 한개의 크기 : 2의 9승 Bit
    • 가상 주소 하나당 행의 개수 → 2의 23승 Bit ( 윈도우 NT보다 8배, 주소 공간으로 23Bit 필요 )
    • 페이지 테이블 하나가 차지하는 물리 공간 → 2의 23승 * 23Bit → 약 24.11MB ( 윈도우 NT 보다 9.2배 )
  • 페이지 한개의 크기를 늘림 → 가상 주소 하나당 행의 개수가 줄어듬 → 각 행을 표현할 주소공간의 크기가 줄어듬 → 페이지 테이블 하나가 차지하는 물리 공간이 줄어듬
  • 페이지 한개의 크기를 줄임 → 가상 주소 하나당 행의 개수가 늘어남 → 각 행을 표현할 주소공간의 크기가 늘어남 → 페이지 테이블 하나가 차지하는 물리 공간이 늘어남
  • 페이지 테이블의 크기를 줄이기 위함 → 페이지 크기를 크게 하면 됨 → 무작정 페이지 하나의 크기를 늘리면, 내부 단편화로 낭비되는 공간이 많아짐
  • 현대 컴퓨터 시스템은, 물리 메모리도 커지고, 응용 프로그램도 커지고 있기 때문에, 페이지의 크기를 점점 늘리고 있는 추세

쓰기 시점 복사

  • 한 컴퓨터에 여러 사용자가 동시에 접근해서 사용 중일 때, 같은 크롬 브라우저를 사용하는 상황을 가정
    • 이 때, 메모리 낭비를 줄이는 방법은 메모리에 크롬 브라우저를 하나만 올려놓고 공유하는 것
    • 만약 모든 사용자가 크롬 브라우저에서 같은 페이지를 보고 있다면, 데이터 영역을 공유 가능
    • 하지만 한 사용자라도 다른 페이지를 보고 있다면, 다른 페이지를 보고 있는 유저를 위해 메모리의 다른 영역을 사용 해야 함
  • 한 사용자가 똑같은 크롬 브라우저를 여러개 띄워 사용 하려고 하는 상황을 가정
    • fork를 활용하여 전체 페이지 테이블을 복사하여 프로세스 복사 가능
    • 하지만, 한 브라우저에서 다른 페이지를 보면, 데이터 영역 공유가 불가능
    • 새로운 데이터 영역을 메모리에 저장하기 위한 공간을 확보 해야 하는데, 미리 확보해놓는 것이 아니라 필요 할 때 확보 함
    • 요구 페이징과 비슷하게 동작

"Operation System" 카테고리의 최근 포스팅

카테고리 모든 글 보기
운영체제 스터디 (13) - 네트워크와 분산 시스템 2021. 03. 14
운영체제 스터디 (12) - 파일 시스템 2021. 03. 14
운영체제 스터디 (11) - 입출력 시스템과 저장 장치 2021. 03. 11
운영체제 스터디 (10) - 가상 메모리 관리 2021. 03. 10
운영체제 스터디 (9) - 가상 메모리의 기초 2021. 03. 08
운영체제 스터디 (8) - 물리 메모리 관리 2021. 03. 07
운영체제 스터디 (7) - 교착상태 2020. 12. 04
운영체제 스터디 (6) - 프로세스 동기화 2020. 11. 10
운영체제 스터디 (5) - interrupt 2020. 10. 20
운영체제 스터디 (4) - CPU 스케줄링 2020. 10. 19