혼공 컴+운 chapter14. 가상메모리

14-1. 연속 메모리 할당

스와핑

• 메모리에 적대된 프로세스 중에서는 현재 실행되지 않는 프로세스가 있을 수 있다. 이러한 프로세스들을 임시로 보조기억 장치 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식.
• 스왑영역 : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역. 
• 스왑 아웃 : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것. 
• 스왑 인 : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것

메모리 할당

• 최초 적합 : 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식.

• 최적 적합 : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식. 

• 최악 적합 : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식

외부 단편화

• 프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 당연하게 느껴질 수 있지만, 메모리를 효율적으로 사용하는 방법이 아니다. 연속 메모리 할당은 외부 단편화라는 문제를 내포하고 있다. 
• 외부 단편화 : 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다. 프로세스 바깥에 생기는 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어진다.
• 외부 단편화 해결 방안 : 압축
  • 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식. 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법. 
  • 단점 : 작은 빈공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다. 

---

필수 문제

1.  메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

< 보기> 최초 적합, 최적 적합, 최악 적합

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

---

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

- 가상 메모리 : 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술. 

페이징이란

• 연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문.
• 페이징 : 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법. 
• 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃되고, 실행에 필요한 페이지들은 메모리로 스왑 인된다.
  • 스왑 아웃 : 페이지 아웃
  • 스왑 인 : 페이지 인

페이지 테이블

- 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 다음에 실행할 명령어 위치를 찾기가 어려워진다.

• 페이징 시스템이 프로세스가 비록 물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 하는 것. 
• 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
• CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 한다. 
• 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있다. 프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 그저 순차적을 실행하면 된다. 
• 페이지 테이블 베이스 레지스터(PTBR) : 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다. 
• 페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어난다는 문제가 있다.
  • 해결 : CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다. 
• TLB : 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장. 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장. 
• TLB 히트 : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우. 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다.
• TLB 미스 : 페이지 번호가 TLB에 없을 경우 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근하는 것. 

페이징에서의 주소 변환

- 특정주소에 접근 정보

1. 어떤 페이지 혹은 프레임에 접근하고 싶은지

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

• 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져 있다. 
  • 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보. 
• 논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>.로 변환

페이지 테이블 엔트리

• 페이지 테이블의 각 엔트리, 페이지 테이블의 각각의 행들
• 유효비트
  • 현재 해당 페이지에 접근 가능한지 여부를 알려준다. 현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려주는 비트이다. 
  • 페이지가 메모리에 적재되어 있다면 유효비트가 1, 페이지가 메모리에 적재되어 있지 않다면 유효 비트가 0
  • 페이지 폴트 : CPU가 유효  비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하는 것
  • 페이지 폴트 처리 과정 
    1. CPU는 기존의 작업 내역을 백업한다.
    2. 페이지 폴트 처리 루틴을 실행한다.
    3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해 준다.
    4. 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있게 된다. 
• 보호비트
  • 페이지 보호 기능을 위해 존재하는 비트
  • 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있다. 
  • 세 개의 비트로 구현가능. 읽기를 나타내는 r, 쓰기를 나타내는 w, 실행을 나타내는 x의 조합으로 나타낸다.
• 참조 비트
  • CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다.
  • 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지. 
• 수정 비트(더티 비트)
  • 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다.
  • CPU가 쓰기 작업을 수행한 페이지의 경우 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용은 서로 다른 값을 갖게된다. 수정된 적이 있는 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 한다. 

페이징의 이점 - 쓰기 시 복사

• 부모 프로세스와 동일한 자식 프로세스가 생성되면 자식 프로세스로 하여금 부모 프로세스와 동일한 프레임을 가리킨다. 굳이 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다. 
• 프로세스 간에는 자원을 공유하지 않기 때문에 부모 프로세스 혹은 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제된다. 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리킨다. 

계층적페이징

• 프로세스를 이루는 모든 페이지 테이브 엔트리를 항상 메모리에 유지하지 않을 수 있는 방법. 
• 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식(다단계 페이지 테이블)
• 페이지 테이블을 여러 개의 페이지로 쪼개고, 이 페이지들을 가리키는 페이지 테이블을두는 방식. 
• 페이지 테이블을 계층적으로 구성하면 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없다. 
• CPU가 발생하는 논리 주소가 달라진다.
  • 바깥 페이지 번호에 해당하는 항목은 CPU와 근접한 곳에 위치한 페이지 테이블 엔트리
  • 안쪽 페이지 번호는 첫 번째 페이지 테이블 바깥에 위치한 두 번째 페이지 테이블, 즉 페이지 테이블의 페이지 번호.
    1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지를 찾기
    2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소 얻기

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

- 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조 기억 장치로 내보낼 수 있어야하고, 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야한다. 

요구 페이징

1. CPU가 특정 페이지에 접근하는 명령어를 실행
2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다
3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한디.
5. 다시 처음으로 돌아간다. 

---

• 순수요구 페이징 : 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 하는 것.
• 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 페이지 교체, 프레임 할당을 해결해야한다. 
• 페이지 교체 알고리즘 : 쫓아낼 페이지를 결정하는 방법.

페이지 교체 알고리즘

• 좋은 페이지 교체 알고리즘은 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘이다. 
• FIFO 페이지 교체 알고리즘
  
  • 오래 머물렀다면 나가라
  •  

• 최적 페이지 교체 알고리즘
  
  • 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  •  

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

스래싱과 프레임 할당

• 프로세스가 사용할 수 있는프레임 수가 적어도 페이지 폴트는 자주 발생. 
• 스래싱 : 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
• 스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
• 프레임 할당 방식
  • 균등할당 : 모든 프로세스에 균등하게 프레임을 제공
  • 비례 할당 : 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스 크기가 작으면 프레임을 적게 나눠 주는 방식.
  • 프로세스 실행
    • 작업 집합 모델
      • 작업 집합 : 실행중인 프로세스가 일정 시간 동안 참조한 페이지의 집합. 
    • 페이지 폴트 빈도
      • 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
      • 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.