🌞가상메모리의 이해

🌱가상메모리

• OS의 메모리 관리 기술로 제공되는 (실제보다) 큰 가상의 메모리
• 물리적 주소가 아닌 논리적 주소를 가지는 메모리이다.
• 메인 메모리의 제한된 용량과 중첩사용 문제를 해결한다.

🌱가상메모리가 가능한 이유

• 프로세스의 일부만 물리적 메모리에 적재해도 실행이 가능하다.
  -> 프로그램 전체를 동시에 실행하지 않음
  -> 필요시 디스크와 메모리 간에 자동으로 전송

🌱프로세스의 일부만 물리적 메모리에 적재해도 실행 가능한 예

• 오류 처리 코드
  -> 예외 처리, 자주 발생하지 않음
• 배열, 리스트, 테이블 등
  -> 실제로 사용 크기보다 더 크게 정의할 수 있음
• 문서 편집기의 메뉴
  -> 복사하기, 붙이기, 잘라내기, 삽입하기 중 선택한 메뉴를 사용한다.

🌱가상메모리의 장점

1. 다중 프로그래밍으로 프로세서의 사용률과 처리율이 향상된다.
   -> 응답시간이나 반환시간은 향상되지 않음
2. 물리적 메모리 크기 제한 없이 큰 프로그램 실행 가능
3. 프로세스를 새로 적재하거나 스왑할 때 I/O부담 적음
   -> 일부만 적재되므로
4. 프로그래밍이 용이함
   -> 중첩을 고려하여 프로그래밍할 필요가 없으므로

🌱가상메모리의 문제점

1. 시스템 속도 저하
2. 요구된 페이지가 없을 때 처리하는 방안이 필요하다.
   -> 적절한 페이지 교체 알고리즘이 필요하다.

정답

O
O
O
X
X
X
X

---

🌻가상 주소와 물리적 주소의 매핑

• 가상 주소
  -> 실행 중인 프로세스가 참조하는 주소
  -> 논리적 주소
  -> 상대 주소

• 물리적 주소
  -> 메인 메모리의 실제주소
  -> 절대 주소

• 매핑
  -> 동적 주소 변환 : ㅔ모리 참조 동안 가상 주소를 물리적 주소로 변환하는 프로세스
  -> 연속적인 가상 주소가 메인 메모리에서는 불연속적
  -> 매핑 속도 중요 : 느리면 시스템 성능 떨어지고 메모리 사용 효과 낮아짐

🌱가상메모리의 구현 방법 두가지

1. 요구 페이징
2. 요구 세그먼테이션

정답

2^12
2^10
20
12
10

🌞요구페이징

• 실행 중인 프로세스가 요구하는 페이지만 메인 메모리에 적재한다.

• 가상 메모리에서 많이 사용하는 메모리 관리 방법이다.

• 매핑 테이블 유지가 필요하다. -> 동적 주소 변호나

• 지연 스와퍼 lazy swapper로 구현
  -> 프로세스가 요구하는 페이지만 적재하는 스와퍼
  -> Pager라고도함
  -> 지연 기술
  -> 프로세스 전체를 적재하는 스와퍼와 다름

• 장점
  -> 메모리 절약
  -> 다중 프로그래밍 정도 증가
  -> 프로그램 시작 시 I/O절약, 적재 지연 감소, 응답 성능 향상
  -> 물리적 메모리가 부족해도 대용량 프로그램을 실행가능

• 단점
  -> 프로세스 실행 중에 페이지 부재로 지연 발생 : Prepaging을 미리 잘 가져오면 성능 향상 가능
  -> 메모리 관리 복잡 : 페이지 교체 알고리즘 등이 필요
  -> 메모리 액세스 시간 예측이 어려움 : 디스크에서 가져올지도 모름로
  -> 하드웨어 지원이 없을 경우 적용 불가 : 저렴한 시스템에는 없음

🌱쓰기 시 복사(COW)

• 공유 페이지를 수정하려면 복사본을 새로 만든 후 수정
  -> 그 페이지를 공유하는 다른 프로세스들에게 민폐를 안 끼침

• 페이징의 공유 정도를 높이는 최적화 전략

정답

5번

---

🌻페이지부재

🌱페이지부재 처리과정

• 유효 비트가 0인 페이지에 액세스 시도 시 페이지 부재

• Free-frame list : OS가 유지하는 빈 프레임 리스트

• Zero-fill-on-demand : 프레임을 하랑하기 직전에 0으로 채워 이전 내용을 지운다.

---

🌻페이징 성능

• 페이지 부재 확률을 낮추어야 함

• 유효 액세스 시간을 줄여야함

---

🌻페이지 교체

• 메인 메모리에 있는 페이지를 새로운 페이지로 바꾸는 것
  -> 페이지 부재시 빈 프레임이 없으면 일어난다.

• 빈 프레임이 없으면 희생자를 선택한다.

정답

2번

🌞페이지 교체 알고리즘

1. 선입선출 FIFO
2. 최적OPT
3. 최근 최소 사용LRU
   -> Counter
   -> Stack
4. LRU 근사
   -> Reference bit
   -> Aging
   -> Clock(Second chance)
   -> NRU(Not Recently Used)
   -> Counting : 최소 사용 빈도수(LFU), 최대 사용 빈도수(MFU)
   -> 페이지 버퍼링

🌻선입선출교체 알고리즘

• 오래된 페이지부터 교체한다.

• 각 페이지가 메모리에 적재될 때 선입선출 큐에 삽입한다.

• 큐의 헤드 페이지를 먼저 교체한다.

정답

4 3 2 1 4 3 5 4 3 2 1 5
1 1 1 1 1 1 1 1 1
9번
521

정답

4 3 2 1 4 3 5 4 3 2 1 5
1 1 1 1 1 1 1 1 1 1
10번
3215

• 문제점
  -> 계속 사용되는 오래된 페이지 교체
  -> 벨래디의 변이 : 프레임 수를 늘려도 페이지 부재 수가 증가하는 현상이다.

---

🌻 최적 페이지 교체 알고리즘(OPT)

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체한다.
  -> 페이지 부재 비율이 가장 낮음
  -> 실현 가능성이 희박하다.

---

🌻 최근 최소사용 LRU 교체 알고리즘

• 가장 오랫동안 사용하지 않은 페이지 교체
  -> 시간족으로 거꾸로 찾는 최적 페이지 교체 알고리즘

• 최근에 액세스 한 것은 곧 다시 액세스 할 가능성이 크다
  -> 지역성

• 참조 순서 기억
  -> Counter
  -> Stack

🌱Counter를 이용한 순서 결정 방법

• 논리 클록을 페이지 참조 마다 증가

• MMU는 페이지 참조마다 논리 클록을 페이지 테이블 항목 counter에 복사

• 교체를 위해 검색 필요 : O(n)

🌱Stack을 이용한 순서 결정 방법

• 메모리 참조 마다 페이지 번호를 스택에 push한다.

• Top -> 가장 최근에 사용한 페이지

• Bottom -> 가장 오래전에 사용한 페이지 Victim

• 이미 페이지 번호가 스택에 있을 경우 빼서 push

• 장점 : 교체를 취해 검색을 안해도 돔

• 단점 : Top으로 옮기는 연산이 복잡하다.

---

🌻LRU근사

• LRU문제점 : 너무 많은 작업이나 하드웨어 자원이 필요하다.

• LRU근사 안고리즘
  -> Reference bit
  -> Aging
  -> Clock (Second chance)
  -> NRU (Not Recently Used)
  -> LFU (Least Frequently Used)
  -> MFU (Most Frequently Used)
  -> 페이지 버퍼링

🌱Reference bit algorithm

• 각 페이지의 참조 비트를 참조 때마다 1로 변환
• 참조 비트가 0인 페이지를 교체
• 참조 비트들은 주기적으로 0으로

🌱Reference bit algorithm 개선

• Aging
• Clock(Second Change)
• NRU(Not Recently Used)

🌱Aging algorithm

• 각 페이지 항목에 몇 비트의 참조 비트를 추가한다.
  -> 참조 시 첫 비트를 1로 세트 후 , 모든 페이지의 참조 비트를 right shift한다.
  -> 가작 작은 참조 비트를 희생자로 내몬다.

🌱Clock(Second change) algorithm

• 오래되고 사용하지 않는 페이지를 교체한다.
• FIFO 큐에서 다음 희생자를 선택한다.
• 만약 다음 희생자의 참조 비트가 1이면 0으로 바꾸기만하고 전진한다.

🌱NRU알고리즘

• 최근 사용하지 않았거나 수정하지 않은 페이지를 교체한다.

• NUR라고도 한다.

• 페이지 항목에 두 비트를 추가한다. 참조비트와 수정비트

🌱Counting Agorithms : 각 페이지 항목에 참조 횟수 카운터

1. 최소 사용 빈도수 알고리즘(LFU)
   -> 많이 참조된 후 거의 참조 되지 않는 페이지가 남는 단점
2. 최대 사용 빈도수 알고리즘(MFU)
   -> 빈도수 낮으면 방금 들어와서 앞으로 사용될 확률이 높다고 가정한다.
   -> 계속 많이 사용되는 페이지가 희생자가 되는 단점

🌱페이지 버퍼링

• 빈 프레임들을 항상 유지한다.
  -> 교체된 페이지를 잠시 동안 메인 메모리에 유지한다.
• 교체된 페이지의 리스트 2개로 관리
  -> 수정된 적 없는 페이지, 수정된 페이지(일괄기록)
• 단점
  -> 버퍼링 공간으로 페이징을 위한 공간 감소
• 장점
  -> 신속 페이지 교체
  -> 수정돈 페이지를 디스크에 쓰지 않으므로
  -> 부재 페이지를 디스크가 아닌 메인 메모리에서 가져 오는 경우도 있으므로

🌞프레임 할당 알고리즘

🌱프레임 할당 알고리즘의 필요성

• 각 프로세스에게 적절한 수의 프레임을 할당해야 한다.
  -> 프레임 수가 줄어들면, 페이지 부재 비율 증가하여, 수행 속도가 저하된다.
  -> 성능 저하를 막기 위한 적절한 프레임 수가 존재한다.

🌱고정 프레임 할당 알고리즘

• 균등 할당
  -> 각 프로세스에 같은 개수의 프레임을 할당한다.
  -> 프로세스마다 메모리 필요량이 달라서, 어떤 프로세스는 프레임을 낭비하고, 어떤 프로세스는 빈번한 페이지 부재로 난항을 겪는다.

• 비례할당
  -> 크기 비례할당
  -> 우선순위 비례 할당

🌱각 프로세스에게 할당해야 하는 최소 프레임 수

• 명령어 집합 구조가 결정한다.
  -> 한 명령어가 참조하는 모든 페이지를 수용할 만큼은 필요하다.
  -> 간접 주소 지정박식이면 적어도 3개의 프레임이 필요하다
  -> 명령어의 수행 중 페이지 부재 시 명령어를 다시 시작해야 한다.

🌱각 프로세스에게 할당할 수 있는 최대 프레임 수

• 메인 메모리의 유효 프레임 수

정답

1번

🌞가변프레임 할당 알고리즘

🌻스래싱

• 페이지 교체가 너무 자주 일어나는 현상이다.
  -> 어떤 프로세스가 수행에 보내는 시간보다 페이지 교체에 보내는 시간이 더 길면 스래싱을 하고 있다고 표현을 한다.

• 다중 프로그래밍도가 너무 높으면 스래싱 현상이 발생한다.

• 기타 자원 부족으로 필요한 연산을 수행할 수 없는 상태가 되면 운영체제는 다른 프로세스에서 자원을 회수는 등 방법을 이용하여 자원을 확보한다.

🌱발생원인

• 어떤 프로세스가 실제 사용하는 프레임 수만큼 갖지 못할 경우

• 너무 많은 다중 프로그래밍
  -> 전역 페이지 교체의 경우

1. 새로운 프로세스가 수행 중인 프로세스의 페이지를 빼앗아서 수행을 시작하면 더 많은 페이지 부재가 발생한다.
2. 지속적인 페이지 부재로 서로 프레임을 빼앗기고 뺏는 과정이 지속된다.

• 일부 시스템에서는 프로세서 사용률이 낮으면 다중 프로그래밍 정도를 증가시킨다.
  -> 프로세서의 사용률이 더욱 감소됨

🌱예방

• 프로세스에 적절한 개수의 프레임을 할당한다.

• 작업 집합 모델
  -> 각 프로세스는 그 프로세스 전체가 아니라 작업 집합만 기억장치에 올려도 잘 싱행된다.
  -> 지역성에 근거함

정답

3번

작업집합모델

---

🌻지역성

• 프로세스가 메모리의 동일하거나 가까운 주소를 연속해서 참조하는 현상

• 프로세스가 메모리를 특정 시간동안에는 특정 페이지만 집중적ㅇ로 사용하는 현상이다.

🌱지역성의 종류

• 시간적 지연성
  -> 같은 주소를 가까운 시간 내에 반복해서 참조하는 현상이다.
  -> 순환, 루프, 서브루틴 반복 호출, 스택, 합계에 사용하는 변수이다.

• 공간적 지연성
  -> 근처 주소를 가까운 시간 내에 반복해서 참조하는 현상이다.
  -> 배열 검색, 순차적 코드의 실행, 근처에 관련 변수 선언
  -> 순차적 지역성

---

🌻작업 집합 모델

• 프로세스가 일정시간 동안 필요로 하는 메모리 부분이다.
  -> 작업 집합만 메모리에 있으면 프로세스 실행 가능
  -> 작업 집합은 시간에 따라 점차 변한다.

• 프로세스가 일정시간동안 사용하는 페이지 집합으로 추정

🌱작업집합모델 프레임할당

• 각 프로세스에게 작업 집합 크기 이상의 프레임들을 할당
  -> 새 프로세스는 작업 집합 공간이 있을 때 시작
  -> 프로세스들의 작업 집합 크기 합이 너무 크면 일부 프로세스 중단

🌱작업집합모델 프레임 할당 목표

1. 자주 사용 페이지 집합은 메인 메모리 상주
2. 페이지 부재 최소화
3. 스래싱을 방지
4. 다중 프로그래밍의 정도 최대화
5. 프로세서의 사용률 증가

🌱최적의 작업 집합창 델타티를 설정해야한다.

• 최적의 작업 집합 크기
• 페이지 부재 비율 낮추고, 프레임을 절약한다.

🌱문제점

• 작업 집합 크기와 구성이 시간에 따라 변한다.
• 작업 집합 시작 시 부재 빈도가 높다.
• 과거의 참조가 미래의 참조를 보장하지 않는다.
• 모든 프로세스의 작업 집합 크기를 측정하는 것은 현실적으로 불가능 하다.
  -> 각 프로세스가 참조한 페이지를 시간 순서대로 큐에 관리하는 것이 복잡하다.
• 작업 집합 창의 최적 값이 알려져 있지 않다.
  -> 프로세스의 성격에 따라 다르다

답

4번
2번

---

🌻페이지 부재 비율조절

• 페이지 부재 비율 상한선과 하한선 설정 후 프레임 수 조절
  -> 상한선 : 프레임 수 증가
  -> 하한선 : 프레임 수 감소
  

🌞메모리와 건련된 기타 이슈

🌻전역교체와 지역교체

🌱전역교체

• 메모리의 전체 부분에서 아무거와 교체하는 것이다.

1. 각 프로세스의 실행중 프레임수가 변동된다.
2. 메모리의 활용도 높다.
3. 처리량이 많다.
4. 구현이 쉽다.
5. 각 프로세스의 성능 분석이 용이하지 못하다.
6. 각 프로세스의 페이지 부재 비율 조절이 용이하지 못하다.
7. 대형 시스템들, 리눅스에서 사용한다.

• 전역 교체 알고리즘 에서는 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스의 프레임을 뺏을 수 있다.

• 프레임의 모든 잠금 해제를 고려해야 하며, 교체할 희생자 페이지에서 페이지 테이블 조사가 필요하다.

• 페이지 테이블은 하드웨어로 직접 지원하지 않기 때문에 운영체제는 소프트웨어로 유지관리 해야한다.

• 전역 교체 알고리즘의 문제점은 프로세스가 그 자신의 페이지 부재 비율을 완전히 조절할 수 없다는 것이다.

• 한 프로세스의 페이지 부재 비율은 그 프로세스가 어떠한 프로세스들과 함께 실행되느냐에 따라 영향을 받는다.

• 동일한 프로세스도 그때그때 전혀 다르게 실행될 수 있다.

• 다른 프로세스의 영향을 받기 때문에 실행이 늦거나 빠르게 될 수 있다.

🌱지역교체방법

• 공간적을 비슷한 곳에 할당

• 가장 일반적인 분할 형태는 고정 분할과 작업 집합 모델 기반으로 한 균형 설정 알고리즘이다.

• 시스템 부하 수준이 달라져도 프로세스는 일관된 성능을 보인다.

• 프로세스는 일부 공유 전역 데이터 구조에서 서로 경쟁하지 않고 독립적으로 페이지 부재를 처리한다.

지역보다 전역 교체 알고리즘이 더 좋은 성능을 나타내며 일반적으로 많이 사용한다.