1. 물리 메모리의 한계
1.1 주소 공간과 물리 메모리
32비트 cpu가 액세스 할 수 있는 물리 메모리의 최대 크기 = 2^32 바이트 = 4GB\
- 컴퓨터에 장착된 실제 메모리
- 프로세스가 실행 중 닿을 수 있는 최대 주소 범위 = 프로세스의 주소 공간
1.2 물리 메모리의 크기 한계
- 운영체제는 물리 메모리보다 큰 프로세스를 실행할 수 있는가?
- 운영체제는 여러 프로세스를 합쳐 물리 메모리보다 클 때 이들을 동시에 실행시킬 수 있는가?
2. 가상 메모리 개념
2.1 가상 메모리 개요
가상메모리(virtual memory) 물리 메모리보다 큰 프로세스나 여러 개의 작은 프로세스를 동시에 실행시켜 사용자나 응용프로그램에게 무한대의 메모리가 있다고 느끼도록 하는 메모리 관리 기법
프로세스가 실행되기 위해서는 프로세스의 코드, 데이터, 스택, 힙 등 모든 영역들이 물리 메모리에 적재되어 있어야 한다는 전제를 깸
가상 메모리 기법의 핵심
- 물리 메모리를 디스크 공간으로 확장
- 스와핑(swapping)
가상 메모리 개념
- 물리 메모리 영역을 하드디스크까지 연장하고, 프로세스를 물리 메모리와 하드디스크에 나누어 저장한다
- 프로세스가 실행될 때 프로세스 전체가 물리 메모리에 적재되어 있을 필요는 없다
- 프로세스의 실행에 필요한 부분만 메모리에 적재하고 나머지는 하드 디스크에 저장해두고 실행에 필요할때만 물리 메모리로 이동시킨다
- 물리 메모리에 빈 영역이 부족하면 프로세스를 구분하지 않고 물리메모리 일부분을 하드디스크에 옮겨 빈 영역을 확보한다
- 최대한 많은 프로세스들을 메모리에 적재해 다중프로그래밍 정도를 높여 cpu활용률 + 시스템 처리율을 높인다
- 물리 메모리를 확장하여 사용하는 디스크 영역을 **스왑 영역(swap area)**라고 부른다
- 물리메모리 일부를 디스크로 옮기는 작업 - 스왑 아웃
- 스왑 영역으로부터 물리 메모리로 적재하는 과정 - 스왑 인
- 사용자는 물리 메모리의 크기를 걱정하지 않고 큰 프로그램을 작성할 수 있고 프로그램을 동시에 실행시킬 수 있다
- 운영체제는 프로세스별로 어떤 부분이 물리 메모리에 적재되어 있고 어떤부분이 하드 디스크에 있는지 유지 관리하고 프로세스에게 최소한의 물리 메모리를 할당하여 최대한 많은 프로세스를 실행시킨다
- 가상 메모리는 운영체제마다 구현 방법이 다르다
논리 주소와 가상 주소
프로그램/프로세스 내에서 사용하는 주소 = 논리 주소 , 가상 주소
2.2 가상 메모리 구현
- 요구 페이징(demand paging)
- 페이징 기법을 토대로 프로세스의 일부 페이지들만 메모리에 적재하고 나머지는 하드디스크에 두며, 페이지가 필요할 때 메모리를 할당받고 페이지를 적재시키는 메모리 관리 기법
- 요구페이징 = 페이징 + 스와핑
- 요구 세그먼테이션(demand segmentation)
- 프로세스를 구성하는 일부 세그먼트들만 메모리에 적재해두고 다른 세그먼트가 필요할 때 메모리를 할당받아 세그먼트를 적재하는 메모리 관리 기법
현대 운영체제는 대부분 요구 페이징 기법을 사용한다
2.3 가상 메모리 기법에 대한 의문들
3. 요구 페이징(demand paging)
3.1 요구 페이징 개념
요구 페이징 물리 메모리 크기 한계 극복을 위해 페이징 기법을 기반으로 만들어진 가상 메모리 기법
- 프로세스의 페이지들을 물리 메모리와 하드 디스크에 분산 할당하는 방식
- 현재 실행에 필요한 일부 페이지들만 물리 메모리에 적재하고 나머지는 하드 디스크에 둠으로써 많은 프로세스 실행
- 실행에 필요한 첫 페이지만 물리 메모리에 적재하여 실행, 실행 중 없는 페이지를 참조하게 되었을 때 물리 메모리의 빈 프레임을 할당받고 페이지 적재
요구(demand) : 페이지가 필요할 때 까지 물리 메모리에 적재하지 않다가 페이지가 필요할 때 물리 메모리를 할당받고 디스크에서 읽어 적재시킨다는 의미
3.2 요구 페이징 구성
디스크의 스왑 영역
- 메모리에서 쫓겨난 페이지들이 저장되는 영역
- 시스템 관리자가 위치와 크기 결정
- 리눅스 - 스왑 파티션 사용, 윈도우 - 특정 파일(C:\pagefile.sys) 스왑 영역으로 사용
페이지 테이블
- presence/valid 비트 - 페이지가 메모리에 적재되어 있는지를 나타내는 비트
- 1 : 물리 메모리, 0 : 디스크
- modified/dirty 비트 - 페이지가 메모리에 적재된 후 수정되었는지를 나타내는 비트
- 1 : 해당 페이지가 물리 메모리에 적재된 후 수정됨
- 0 : 수정된 적이 없음, 스왑 영역에 있는 상태
- physical address 필드
- 페이지가 메모리에 적재되어 있는 경우 = 물리 프레임의 번호 기록
- 물리 메모리에 없는 경우 = 디스크 주소(디스크 블록 번호) 기록
페이지 폴트
cpu가 가상 주소를 발생시켜 액세스하려는 페이지가 현재 물리 메모리에 없을 때 페이지 폴트(page fault)라고 한다
페이지 폴트 발생 → 페이지 폴트 핸들러 코드 실행
-
물리 메모리에 서 빈 프레임을 할당받고 요청된 페이지를 하드 디스크에 읽어 적재하고 페이지 테이블 수정
-
빈 프레임이 없는 경우 → 희생 프레임 선택 (페이지 교체 알고리즘 사용)
-
스왑-인(swap-in) : 페이지를 스왑 영역으로부터 프레임에 적재하는 것
-
스왑-아웃(swap-out)/페이지-아웃(page-out) : 프레임에 적재된 페이지를 스왑 영역에 저장하는 것
페이지 히트 : cpu가 발생한 가상 주소 페이지가 메모리 프레임에 있을 때
3.3 페이지 폴트 자세히 알기
mov eax, 10 -- eax 레지스터에 10 저장
mov [11111234], eax -- eax 레지스터 값을 0x1111234 번지에 저장
3.4 요구 페이징 시스템에서 프로세스 실행
- 프로세스의 시작 페이지 적재 - 메모리 프레임 1개 할당 - 실행 파일로부터 프로세스의 실행이 시작될 첫 페이지를 적재한 후 프로세스 실행
- 여러 번의 페이지 폴트를 통해 실행 파일로부터 페이지들 적재 - 실행 초기에는 페이지 폴트가 연이어 발생, 폴트가 발생한 페이지는 실행 파일이나 스왑 영역에 위치
- 메모리가 부족하면 스왑-아웃/스왑-인 - 페이지 100이 들어있는 프레임을 희생 프레임으로 선택
- 스왑-아웃된 페이지 100을 다시 스왑-인
- 수정된 페이지는 스왑 영역에 쓰기
3.5 쓰기 시 복사(COW, copy on write)
완전 복사
- 프로세스는 부모 프로세스에 의해 생성되며 시스템 호출을 통해서만 이루어짐
- fork() : 부모 프로세스의 메모리를 모두 복사하여 자식 프로세스 생성
완전 복사의 비효율성
fork() 시스템 호출이 부모 프로세스와 동일한 크기의 메모리를 할당받고, 부모 프로세스의 메모리를 완전 복사하여 자식 프로세스를 생성해도 곧바로 execlp()를 호출하여 할당받은 메모리를 모두 반환하고 다시 페이지를 적재하기 때문에 비효율적이다.
쓰기 시 복사로 완전 복사 문제 해결
부모 프로세스의 메모리를 복사하지 않고 자식 프로세스가 부모 프로세스의 메모리를 완전히 공유하도록 하고 둘 다 실행되도록 내버려둔다. 그 후 부모든 자식이든 실행 중 메모리 쓰기가 발생하면 그 때 운영체제는 쓰기가 발생한 페이지만 새 프레임을 할당받아 복사한다. 페이지를 읽는 경우에는 복사하지 않는다.
쓰기 시 복사의 장점
- 프로세스 생성시간 절약
- 메모리 절약
3.6 페이지 폴트와 스레싱
페이지 폴트와 디스크 I/O
페이지 폴트가 발생하면 디스크 입출력이 동반된다
- 필요 페이지를 적재하거나 프레임을 비우기 위해 스왑-아웃 시키기 때문
스레싱
페이지 폴트가 계속 발생하여 메모리 프레임에 페이지가 반복적으로 교체되고 디스크 입출력이 심각하게 증가하고 cpu 활용률이 대폭 감소하는 현상
= 빈번한 페이지 폴트로 인한 디스크 입출력 증가 현상 = 디스크 스레싱
스레싱의 원인
- 다중 프로그래밍 정도가 과도한 경우
- 메모리 할당 정책이나 페이지 교체 알고리즘이 잘못되었을 경우
- 컴퓨터 시스템에 설치된 메모리가 절대적으로 작은 경우
- 특정 시간대에 너무 많은 프로세스를 실행한 경우
스래싱 현상 관찰
스레싱을 방치하면 cpu 활용률이 떨어지고 프로세스들의 응답시간이 떨어지며 시스템 처리율이 감소한다.
동시에 실행되는 프로세스의 개수가 늘어날수록 cpu 활용률이 증가함
임계점 M을 넘어갈 때부터 cpu 활용률이 떨어짐
- 상대적으로 각 프로세스에게 할당되는 프레임의 개수가 줄어들고 각 프로세스는 실행에 필요한 페이지들을 모두 메모리에 적재하지 못하게 되어 계속 페이지 폴트가 발생함
- 빈번한 스왑-아웃/스왑-인으로 인해 디스크 입출력이 증가하고 cpu의 대기시간이 늘어 활용률 급감
- → 스레싱이 시작되는 시점
동시에 실행되는 프로세스의 개수가 많음에도 불구하고 오히려 cpu 활용률이 갑자기 떨어질 때 스래싱이 발생하기 시작한 것으로 판단할 수 있다.
스래싱 해결 및 예방
스래싱이 발생한 상태 = 몇 개의 프로세스를 강제로 종료시켜 다중 프로그래밍 정도를 낮추어야 함 스래싱을 예방하기 위해서는 다중 프로그래밍 정도의 시스템 허용치를 낮추어 설정하거나, 컴퓨터의 메모리를 늘리거나, SSD를 사용한다.
- 참조의 지역성과 작업 집합
4.1 프로그램의 실행 특성
페이지폴트를 동반하고 디스크 입출력이 발생함에도 요구 페이징을 사용하는 이유?
- 참조의 지역성
- 작업집합
4.2 참조의 지역성
CPU가 프로그램을 실행하는 동안 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복 참조(액세스)하는 경향이 있는데 이것이 참조의 지역성(locality of reference)이다
- 참조의 지역성은 프로그램이 가지는 기본적인 실행 특성이다
- 프로세스의 실행동안 메모리가 균일하게 참조되지 않고 특정 부분이 집중 참조된다
- 참조의 지역성은 지역성, 지역성의 원리라고도 부른다
- 프로세스는 최근에 참조한 데이터와 코드를 다시 참조하는 경향이 있다
- 경험적 관찰에서 발견한 90/10 규칙은 “프로그램의 코드 10%가 프로그램 전체 실행 시간을 90%를 소비한다”는 규칙이다
참조의 지역성을 이용함으로써
- 현재 실행중인 프로세스가 가까운 미래에 어떤 페이지를 액세스할 것인지 합리적으로 예측 가능
- 현재 메모리에 적재된 페이지 중 가까운 미래에 사용될 페이지가 스왑-아웃되지 않도록 페이지 교체 정책을 폄으로써 시스템 전체의 페이지 폴트 감소
시간 지역성 : 시간면에서 프로그램 내에 지금 참조되는 주소가 다시 참조될 가능성이 큰 특징 공간 지역성 : 공간면에서 지금 참조되는 주소의 주변 번지들이 다시 참조되는 특성
4.3 작업 집합과 페이지 폴트
작업집합
작업집합이란 일정 시간 범위 내에 프로세스가 참조한(액세스한) 페이지들의 집합이다. 그러므로 작업 집합은 현재 프로세스의 실행에 필요한 페이지들의 집합이다.
- 운영체제는 프로세스에게 작업 집합을 적재할 수 있는 정도의 메모리를 할당하고 작업 집합에 포함된 페이지가 스왑-아웃 되지 않도록 관리
- 프로세스 실행 중 갑자기 페이지 폴트가 계속됨 → 프로세스의 작업 집합 페이지를 메모리에 적재하고 있는 과정
페이지 폴트 → 작업 집합 형성
작업 집합 형성 과정
페이지 2, 100, 5, 20 작업 집합 형성
작업 집합과 시간 범위
액세스 횟수에 상관 없이 시간 범위 내 프로세스 실행에 필요한 페이지들은 모두 그 시간 범위의 작업집합 시간 범위가 클수록 작업 집합의 크기도 늘어남
작업 집합 이동
작업 집합 이동 : 프로세스 실행 중 시간에 따라 참조의 지역성이 다른 메모리 영역에서 나타나 작업 집합이 변해가는 것
다중 프로그래밍 시스템에서 스래싱 발생 관측과 예방
스래싱 - 다중 프로그래밍 도입 후 시스템에서 cpu활용률과 작업 처리율이 떨어지는 현상
- 여러 프로세스들에서 작업 집합에 포함된 페이지들이 충분히 메모리에 올라와 있지 않은 경우 스래싱이 발생함
- 각 프로세스에게 작업 집합 페이지들을 수용할 충분한 메모리를 할당하는 알고리즘을 통해 스래싱 예방
4.4 요구 페이징의 필수 알고리즘
요구 페이징의 성능 - 운영체제가 작업 집합에 속한 페이지들을 메모리에 적재한 상태로 프로세스를 실행 가능한지 여부에 달려있음
- 프레임 할당(frame allocation)
- 프로세스에게 할당할 메모리 프레임의 개수를 결정하는 문제
- 프로세스의 작업 집합에 포함된 페이지들을 충분히 수용할만한 개수의 메모리 프레임을 할당하여 페이지 폴트를 줄임
- 페이지 교체(page replacement)
- 페이지 폴트 발생 시 빈 메모리 프레임이 없는 경우 메모리에 적재된 페이지들 중 스왑-아웃시킬 페이지를 선택하는 문제
- 작업 집합에 속하지 않은 페이지를 교체 페이지로 선택해내는 것
5. 프레임 할당
5.1 프레임 할당의 목표
- 프로세스에게 할당할 메모리 프레임의 개수를 결정
- 프로세스의 작업 집합에 포함된 페이지들을 충분히 수용할만한 개수의 메모리 프레임을 할당하여 페이지 폴트를 줄이고 스래싱이 발생하지 않도록 한다
5.2 균등 할당과 비례 할당
균등 할당(equal allocation)
- 프로세스의 크기와 관계 없이 모든 프로세스에게 동일한 개수의 프레임을 할당하는 방법
비례 할당(proportaional allocation)
- 프로세스의 크기에 비례하여 프레임을 할당하는 방법
- 프로세스 크기를 알기 어려움
5.3 프로세스에게 할당할 적정 프레임 수
프로세스에게 할당해줄 프레임의 적정 개수는 작업 집합을 약간 넘나드는 수준이 적합
6. 페이지 교체
6.1 페이지 교체의 정의
페이지 교체란 요청된 페이지가 메모리 프레임에 없고, 페이지를 적재할 빈 프레임도 없는 경우, 메모리 프레임 중 하나를 선택하여 비우고 이곳에 요청된 페이지를 적재하는 과정이다
희생 프레임 : 비우기로 선택한 프레임 희생 페이지 : 희생 프레임에 저장되어 있다가 쫓겨나는 페이지
6.2 페이지 교체의 목표
페이지 교체의 목표는 현재 작업 집합에 포함되지 않거나 가까운 미래에 참조되지 않을 페이지를 희생 페이지로 선택하여 페이지 폴트의 횟수를 줄이는 것이다.
6.3 희생 프레임의 선택 범위
- 지역 교체(local replacement)
- 페이지 적재를 요청한 프로세스에게 할당된 프레임들 중 희생 프레임을 선택하는 방법
- 다른 프로세스에게 할당된 프레임을 건드리지 않아 스래싱이 발생해도 다른 프로세스로 전파되지 않음
- 전역 교체(global replacement)
- 프로세스에 상관없이 전체 메모리 프레임 중 희생 프레임을 선택하는 방법
- 페이지 폴트를 덜 유발시켜 효과적
6.4 페이지 교체 알고리즘
- 최적 교체
- FIFO
- LRU
- CLOCK
6.5 최적 교체 알고리즘
미래에 사용될 가능성이 가장 낮은 페이지를 희생 페이지로 선택
페이지 폴트가 가장 작은 최고 이상적인 방법이지만 각 페이지들이 언제 참조되는지 알아야 구현이 가능하기때문에 실현 불가능함
6.6 FIFO 알고리즘
메모리 프레임에 적재된 페이지들 중 가장 오래된 페이지를 희생 페이지로 선택
각 페이지마다 적재된 시간 정보를 저장하고 적재 시간에 따라 희생 페이지 선택
페이지를 교체할 때마다 모든 페이지들의 적재 시간을 검색하는 것은 부담이 큼
작업 집합을 고려하지 않기 때문에 성능이 낮음
6.7 LRU 알고리즘
참조의 지역성 이용, 프레임에 적재된 페이지들 중 가장 오래전에 참조된 페이지를 희생 페이지로 선택
- 타임스탬프 이용
- 하드웨어 이용, 참조비트 이용
성능은 좋지만 구현 복잡도가 높음 구현에 있어 하드웨어에 대한 지원과 커널 코드의 주기적인 실행도 필요함
6.8 Clock 알고리즘
LRU와 FIFO를 섞은 알고리즘, 2차 기회 알고리즘이라고도 함
메모리 프레임당 1비트의 참조 비트를 사용하고 프레임들을 원형 큐로 만들어 관리 cpu가 페이지를 참조할 때마다 프레임의 참조 비트를 1로 수정
포인터 : 희생 페이지 결정을 위해 검색을 시작하는 원형 큐의 프레임 위치
