14-1. 연속 메모리 할당

• 프로세스에 연속적인 메모리를 할당하는 방식

스와핑

• 사용하지 않거나, 계속 대기 중인 프로세스를 메모리에서 보조기억장치(스왑 영역)로 보냄. (스왑 아웃)
• 이때 메모리의 빈 공간에 실행할 프로세스를 넣음. (스왑 인)

메모리 할당

• 비어있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식

최초 적합 first fit

• 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식
• 검색 최소화, 빠른 할당 가능

최적 적합 best fit

• 운영체제가 메모리의 빈 공간을 모두 검색하고, 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스 배치

최악 적합 worst fit

• 운영체제가 메모리의 빈 공간을 모두 검색하고, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스 배치

외부 단편화 external fragmentation

• 프로세스들이 메모리에 연속적으로 할당되고 종료되는 과정을 반복
• 프로세스 사이에 빈 메모리 공간이 생김
• 빈 메모리 공간을 합쳐서 보면 충분한 공간이지만, 프로세스를 적재할 수 없는 상황 : 외부 단편화
• 메모리 낭비!

압축

• 외부 단편화를 해결하는 방법. 메모리 조각 모음
• 비어있는 공간들을 하나로 모으는 방식
• 이 과정에서 시스템은 하던 일을 중지해야하고, 메모리의 내용 옮기는 과정에서 많은 오버헤드 야기
• -> 가상 메모리 기법 중 페이징 기법이 등장

14-2. 페이징을 통한 가상 메모리 관리

• 가상 메모리 : 실행하고자 하는 프로그램 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
• 페이징, 세그멘테이션

페이징

• 프로세스의 논리 주소 공간을 페이지라는 단위로 자르고
• 메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 단위로 자르고
• 페이지를 프레임에 할당하는 것이 페이징
• 프로세스 단위가 아닌 프레임 단위로 페이지 아웃, 페이지 인

페이지 테이블

• 프로세스가 메모리에 불연속적으로 적재되어 있으면 CPU는 순차적 실행 불가 : 다음에 실행할 명령어 위치 찾기 힘듦
• 실제 메모리 물리 주소에서는 불연속적이더라도 CPU가 바라보는 논리 주소에는 연속적으로 배치되도록 하는 것이 페이지 테이블
• 페이지 번호와 프레임 번호를 이어줌
• 프로세스마다 프로세스 페이지 테이블이 있음
• CPU에서 0, 1, 2를 페이지 테이블을 통해 물리 주소의 프레임 위치로 찾아 감
• 내부 단편화 발생 가능
  • 프로세스를 페이지라는 단위로 자르는데, 남는 부분이 있음.
  • 프레임보다 작은 크기의 페이지를 넣게 되면, 메모리에 남는 부분이 생긴다. -> 내부 단편화
  • 일부 운영체제 (리눅스) 에서는 기본 페이지 크기보다 더 큰 페이지를 허용하여 메모리에 유지하는 경우도 있음 (대형 페이지 huge page) 라고 함
• 페이지 테이블 베이스 레지스터 (PTBR : Page Table Base Register) : CPU 내에서 각 프로세스의 페이지 테이블이 적재된 주소를 가리킴
• 메모리 접근 시간이 두 배로 늘어남
  • 메모리에 있는 페이지 테이블을 보기 위해
  • 페이지 테이블을 통해 알게 된 프레임에 접근하기 위해
• CPU 곁에 (MMU 내에) TLB Translation Lookaside Buffer라는 페이지 테이블 캐시 메모리를 둠
  • 참조 지역성에 근거해 최근 사용된 페이지 위주로 저장
  • TLB 히트 : 논리 주소에 대한 페이지 번호가 TLB에 있는 경우
  • TLB 미스 : 논리 주소에 대한 페이지 번호가 TLB에 없는 경우 (메모리의 페이지 테이블에 접근해야 함)

페이징 주소 변환

• 특정 주소에 접근하기 위해 필요한 정보
  • 어떤 페이지, 프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지, 프레임으로부터 얼마나 떨어져 있는지
• 논리주소는 페이지 번호와 변위로 이뤄져있음
• 논리주소 <페이지 번호, 변위> -> 페이지 테이블 -> 물리주소 <프레임 번호, 변위> (변위 값은 동일)

페이지 테이블 엔트리

• 페이지 테이블 엔트리 PTE Page Table Entry : 페이지 테이블의 각 행
• 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트

유효 비트 valid bit

• 현재 해당 페이지 접근 가능 여부
• 페이지가 보조기억장치(스왑 영역)에 있는 경우는 메모리에 적재되어 있기 않기 때문에 접근 불가
• 메모리에 없는 페이지(유표비트가 0)로 접근하고자하면 페이지 폴트 예외 발생 - 하드웨어 인터럽트 처리 방식처럼 처리
• CPU는 기존 작업 백업
• 페이지 폴트 처리 루틴 실행
  • 페이지를 메모리로 가져오고 유효 비트를 1로 변경
• CPU는 해당 페이지에 접근 가능

보호 비트 protection bit

• 페이지 보호 기능. 읽고 쓰기가 가능한 페이지인지, 읽기만 가능한 페이지인지 표기
• 접근권한을 제한하여 페이지 보호
• 읽기, 쓰기, 읽기/실행, 읽기/쓰기/실행

참조 비트 reference bit

• CPU가 이 페이지에 접근한 적 있는지

수정 비트 modified bit 더티 비트 dirty bit

• 데이터를 쓴 적이 있는지 없는지 수정 여부
• 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지, 할 필요가 없는지 판단

14-3. 페이지 교체와 프레임 할당

요구 페이징

• 필요한 페이지만을 메모리에 적재하는 기법
• 순수 요구 페이징 기법 : 메모리에 페이지 적재하지 않은 채로 시작. 초기에는 페이지 폴트 발생. 이후에는 페이지 폴트 빈도 줄음
• 페이징 시스템이 안정적으로 작동하려면 페이지교체, 프레임할당이 원활히 이루어져야 함

페이지 교체 알고리즘

• 메모리에서 쫓아낼 페이지를 결정하는 방법
• 페이지 폴트 횟수를 알아야하며, 이는 페이지 참조열로 알 수 있음
  • 페이지 참조열 : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

FIFO 페이지 교체 알고리즘

• 메모리에 가장 먼저 올라온 페이지부터 내쫓음
• 구현 간단. 효율 낮음
• 2차 기회 페이지 교체 알고리즘 : FIFO 페이지 알고리즘 + 페이지의 참조 비트 참고

최적 페이지 교체 알고리즘

• 앞으로 사용할 빈도가 가장 낮은 페이지를 내쫓음
• 페이지 폴트율 제일 낮음
• 구현 어려움

LRU 페이지 교체 알고리즘

• 오랫동안 사용하지 않은 페이지를 내쫓음

스래싱과 프레임 할당

• 스래싱 thrashing : 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제
  • 값이 높으면 CPU 효율 높음
  • 값이 낮으면 CPU 효율 낮음
• 멀티프로그래밍 정도 : 현재 메모리에 동시에 실행 중인 프로세스의 양
• 멀티프로그래밍 정도를 지나치게 높이면 각 프로세스가 사용가능한 프레임수가 적어지고, 페이지 폴트는 빈번하게 발생. CPU 효율 저하
  • CPU 성능 좋아도 메모리에서 동시 실행 프로세스 수용 못하면 컴퓨터 성능 저하

프레임 할당 방식

• 정적 할당 방식 : 프로세스 실행 과정 고려 없이 프로세스 크기, 물리 메모리 크기만 고려
  • 균등 할당 : 모든 프로세스에 균등하게 프레임 할당
    • 프로세스 크기가 각기 다르므로 비추천
  • 비례 할당 : 프로세스 크기 크면 많은 프레임을, 작으면 적은 프레임을 할당
• 동적 할당 방식 : 프로세스 실행을 보고 할당할 프레임 수 결정
  • 작업 집합 모델 사용 방식
    • 작업 집합 : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
    • 스래싱은 빈번한 페이지 교체에 의해 발생
    • 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체 방지
    • CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면, 운영체제는 작업 집합의 크기만큼만 프레임 할당
  • 페이지 폴트 빈도 (PFF) 사용 방식
    • 페이지 폴트율이 높으면 그 프로세스는 너무 적은 프레임을 갖고 있음
    • 페이지 폴트율이 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있음
    • 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임 할당

p.400 1번