6주차 (2/5 ~ 2/12)
chapter. 14 : 가상 메모리
chapter. 15 : 파일 시스템

chapter 14. 가상 메모리

➡️ 운영체제의 핵심 서비스 : 자원 접근 및 할당 - 메모리

---

14-1. 연속 메모리 할당

• 프로세스가 메모리에 적재되는 기본 전제

1.메모리크기(물리적 크기)는 정해져 있다.
2.프로세스는 메모리 빈 공간에 적재된다.

🫠 메모리에 빈 공간이 없을 경우 새로운 프로세스 실행되려면 어떻게 해야하는가? 고정된 메모리 공간에 여러개의 프로세스 동시에 실행하려면 어떻게 해야 하는가?

📌 스와핑(Swapping)
메모리에서 당장 필요로 하지 않는 프로세스는 빼고, 당장 필요한 프로세스를 메모리에 적재하여 메모리의 공간을 활용하여 프로세스 적재하는 방법을 스와핑이라고 한다.

• 스왑 아웃(swapp-out) :당장 필요로 하지 않는 프로세스는 뺀다
  예를 들어 입출력 작업 대기 상태가 된 프로세스, 오랫동안 사용하지 않는 프로세스를 임시로 보조기억장치의 스왑 영역으로 쫓아낸다. 그 빈 공간에 새로운 프로세스가 적재된다.
  
• 스왑 인(swapp-in):필요한 프로세스를 메모리에 적재 : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 말한다.

연속 메모리 할당

1. 연속 메모리 할당이란?

• 메모리 내에 프로세스들이 연속적으로 할당되는 상황
• 프로세스 전체코드가 메모리에 올라와 있음
• 스와핑 통해 여러 프로세스 실행할 수 있음

예를 들어 프로세스 A는 메모리 주소 10번지에서 50번지까지 할당, 프로세스 B는 메모리 주소 60번지에서 110번지까지 할당된다.

2. 메모리 할당 방식

메모리 내 빈공간이 여러개 있다면 프로세스 어디에 배치해야 하나?

✔️ 최초 적합(first fit)

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스 배치하는 방식
• 검색 최소화, 빠른 할당

✔️ 최적 적합(best fit)

• 운영체제가 모든 빈 공간 검색한 후
• 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스 배치

✔️ 최악 적합(wortst fit)

• 운영체제가 모든 빈 공간 검색한 후
• 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스 배치

3.외부단편화

메모리 연속 할당에 따른 한계

• (물리)메모리보다 큰 프로세스는 살행할 수 없음
• 외부 단편화 문제

외부 단편화란?

프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인하여 메모리가 낭비되는 현상

🫠 예를 들어 프로세스들 사이에 두 개의 빈 공간이 생겼다. 하나는 20MB크기의 빈 공간, 다른 하나는 30MB크기의 빈 공간이다.

이때, 50MB의 프로세스 적재할 수 있나?
적재 할 수 없다. 그러므로 그 공간들이 낭비된다.

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

✔️ 연속 메모리 할당의 한계
1. (물리)메모리보다 큰 프로세스 실행 할 수 없음
2. 외부 단편화

가상메모리 기법

• 프로세스 전체를 메모리에 적재하는 것이 아니라 필요한 만큼 일부만 가져와서 메모리에 적재하는 기술
• 연속 메모리 할당의 한계 극복
• 물리메모리의 크기의 제약 극복

페이징

1. 페이징이란?

• 가상 메모리 관리 기법 중 하나로,

  ✔️ 메모리와 프로세스를 일정한 단위로 자르고
  ✔️ 이를 메모리에 불연속적으로 할당하는 방식

• 페이지 : 프로세스의 논리 주소 공간을 자르는 단위

• 프레임 : 메모리 물리 주소 공간을 페이지와 같은 크기로 자른 단위

• 페이징 시스템에서도 스와핑 가능
  페이지 아웃 : 메모리 적재될 필요없는 페이지들 보조기억장치오 스왑 아웃 되는 것
  페이지 인 : 실행에 필요한 페이지들 이 메모리로 스왑인 되는 것

2. 연속 메모리 할당의 한계 극복
✔️ 메모리와 프로세스를 일정한 단위로 자르고
➡️ 외부단편화 극복
➡️ 메모리보다 큰 프로세스도 실행 가능

페이지 테이블

페이징기법의 특징 중 하나인 메모리에 불연속적으로 할당 한다는 점 때문에 CPU 입장에서 '다음에 실행할 명령어 위치'찾기 어려움

📌 페이지 테이블

• 어떤 페이지가 어떤 프레임에 할당되었는지 알려주는 이정표 역할
• 프로세스마다 페이지 테이블 가짐
• 페이지 테이블은 메모리에 적재되어 있음
• CPU 내 페이지 테이블 베이스 레지스터(PTBR)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있음
  
  이를 통해서 CPU는 다음에 실행할 명령어에 쉽게 접근가능하다.

✔️ 하지만 이때, CPU가 페이지 테이블로 인해 메모리 접근 시간이 두배로 늘어나는 문제 발생함

• CPU가 메모리에 있는 페이지 테이블 접근
• CPU가 메모리에 있는 프레임에 접근

📌 TLB
: 페이지 테이블의 캐시메모리 역할을 수행하기 위해 TLB(Transalation Lookaside Buffer)에는 페이지 테이블의 일부를 가져옴
: 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장

• TLB 히트 : CPU가 발생한 논리주소에 대한 페이지번호가 TLB에 있을 경우
• TLB 미스 : CPU가 발생한 논리주소에 대한 페이지번호가 TLB에 없을 경우

페이징에서 주소 변환

✔️ 페이지 =논리주소, 프레임 = 물리주소 로 보면

CPU가 메모리와 상호작용해서 프로세스 실행하려면 논리주소(페이지)를 물리주소(프레임)로 변환하는 과정 거처야 한다.

고려사항

• 어떤 페이지 혹은 프레임에 접근하고 싶은지
• 접근하려는 주소가 그 페이지 혹은 프레임으로 부터 얼마나 떨어져 있는지

논리주소 구성<페이지 번호, 변위>
물리주소 구성<프레임 번호, 변위>

참고 : Chapter 6. 메모리의 주소공간(p. 188)에서 학습한 것과 같은 개념

페이지 테이블 엔트리

페이지 테이블을 구성하는 행들

✔️ 페이지 테이블 엔트리에 들어가는 정보

• 1 페이지 번호

• 2 프레임 번호

• 3 유효 비트
  현재 해당 페이지에 접근 가능한지 여부 알려줌

  • 유효비트 0 : 페이지가 메모리에 적재되어 있지 않음. 보조기억장치에서 가져와야 함
  • 유효비트 1 : 페이지가 메모리에 적재되어 있음.

    ✔️ 페이지 폴트(page fault)
    예외(exception) : CPU가 유효비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려 할 때 발생
    
    ✔️ 페이지 폴트 처리과정
    1. CPU는 기존의 작업 내역 백업
    2. 페이지 폴트 처리 루틴 실행
    3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효비트를 1로 변경해 줌
    4. 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있음

• 4 보호 비트
  페이지 보호 기능

  • 보호비트 0 : 읽기만 가능 페이지
    _ 보호비트 1 : 읽기와 쓰기 모두 가능 페이지

• 5 참조 비트
  CPU가 페이지에 접근한 적 있는지 여부 나타냄

• 참조비트 0 : 접근한 적 없는 페이지
• 참조비트 1 : 접근한 적 있는 페이지

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

  • 참조비트 0 : 수정된 적 없는 페이지
  • 참조비트 1 : 수정된 적 있는 페이지

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

요구페이징

요구페이징(demand paging)이란?
프로세스를 메모리에 적재할 때 필요한 페이지만 메모리에 적재하는 기법

요구페이징 시스템 안정적 작동을 위한 전제

• 페이지 폴트 적게 발생하여야 한다.

  ✔️ 페이지 폴트(page fault)
  유효비트가 0인 상태로 CPU가 접근하려는 페이지가 현재 메모리에 적재되어 있지 않음을 나타냄. 보조기억장치에서 페이지를 가져와야 해서 컴퓨터 성능 저하됨

• 페이지교체 : 필요없는 페이지 보조기억장치로 보낸다.

• 프레임 할당 : 충분한 메모리공간(프레임) 확보. 최소 프레임 유지해야 한다.

페이지 교체 알고리즘

필요없는 페이지 보조기억장치로 보낼 때(페이지 교체), 어떤 페이지를 보낼 지 결정하는 방식

가정
프레임 갯수 : 3개
페이지 참조열 : 2 3 1 3 5 2 3 4 2 3

• FIFO 페이지 교체 알고리즘
  : 가장 먼저 메모리에 올라온 페이지(=메모리에 오랜기간 올라와 있음)부터 보조기억장치로 보내기

• 최적 페이지 교체 알고리즘
  CPU에 의해 참조된 횟수를 고려하는 페이지 교체 알고리즘 즉, 앞으로 사용 빈도가 가장 낮은페이지 교체하는 알고리즘
  

• LRU 페이지 교체 알고리즘
  가장 오랫동안 사용되지 '않은' 페이지를 교체하는 알고리즘
  

스레싱과 프레임 할당

페이징 교체가 빈번히 일어나느 것을 막기 위해 충분한 메모리공간(프레임)가지는 방식, 즉 최소한의 프레임 수를 유지하는 방식

스레싱(thrashing)
: 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제

• 정적 할당 방식

1. 균등 할당
   모든 프로세스에 균등하게 프레임 제공하는 방식
2. 비례 할당
   프로세스 크기에 비례하여 프레임 제고아는 방식

• 동적 할당 방식 : 프로세스 실행해보고 결정

1. 작업 집합 모델
   작업집합(실행 중인 프로세스가 일정 시간 동안 참조한 페이지 집합) 크기만큼 프레임 할당하는 방식
2. 페이지 폴트 빈도
   페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임 할당 하는 방식

🏅 기본미션

p. 400의 확인 문제 1번 풀고 인증하기

1. 최초 적합 : 최초로 발견한 적재 가능한 빈 공간에 프로세스 배치하는 방식
2. 최악 적합 : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
3. 최적 적합 : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

🎁 선택미션

Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

3번의 페이지 폴트 발생

LRU(Least Recently Used Page Replacement Algorithm) 교체 알고리즘 :
페이지마다 가장 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체하는 방식

페이지 참조열 2-3-1-3-5-2-3-4-2-3

프레임(2,3,1)
프레임(5,3,1) : 페이지 폴트 5 - 보조기억장치 : 2
프레임(5,3,2) : 페이지 폴트 2 - 보조기억장치 : 1
프레임(4,3,2) : 페이지 폴트 4 - 보조기억장치 : 5