2022.06.13 - [컴퓨터 공학/0 +운영체제] - [운영체제] 9. 메모리 관리
[운영체제] 9. 메모리 관리
2022.06.11 - [컴퓨터 공학/0 +운영체제] - [운영체제] 8. Scheduling 기법(2) -유닉스/리눅스 스케줄링 [운영체제] 8. Scheduling 기법(2) -유닉스/리눅스 스케줄링 2022.05.15 - [컴퓨터 공학/0 +운영체제] - [..
howisitgo1ng.tistory.com
지난 포스팅에서는 메모리관리에 대해서 소개 했다.
프로그램이 CPU에서 실행되려면 실행에 당장 필요한 부분이 메모리에 올라와 있어야 한다.!
여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어 사용하는데..
이는 운영체제가 어떤 프로그램에게 어느정도의 메모리를 할당할 것인가 하는 문제에 부딪힌다..!
운영체제는 보통 모든 프로그램들에게 집중적으로 메모리를 할당한 후,
시간이 지나면 메모리를 회수해서
다른 프로그램들에게 다시 집중적으로 메모리를 할당하는 방식을 사용한다.
프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보해야하는 메모리의 크기가 존재하기 때문..!
이번 포스팅에서는 운영체제가 어떤 식으로 프로세스에게 메모리를 할당하는지 알아보자!!
가상 메모리(virtual memory)
프로그램이 실행되기 위해 프로세스의 주소 전체가 메모리에 올라가 있어야한건 아니다.
운영체제는 당장 CPU에서 수행해야 할 부분만 메모리에 올려놓는다. 즉 스왑 아웃과 스왑 인을 반복한다.
때문에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 받지 않게 된다.
그래서 운영체제는 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다.
이렇게 되면 프로그램은 0번지부터 시작하는 자신만의 메모리 주소 공간을 가정할 수 있는데....
이러한 공간은 바로 바로 바로 가상 메모리라고 부른다.!!
정리하면
가상 메모리는 프로세스마다 각각 0번지부터의 주소공간을 갖게 되며,
공간 중 일부는 물리적 메모리에 적재되고, 일부는 스왑영역에 존재한다.
가상메모리 기법
주소 공간을 메모리로 적재하는 단위에 따라
- 요구 페이징
- 요구 세그먼테이션
으로 구현될 수 있다.
요구 페이징(demand paging)
프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라
당장 사용될 페이지만을 올리는 방식
따라서 특정 페이지에 대해서 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.
- 장점
- 메모리 사용량 감소
- 프로세스 전체를 메모리에 올리는데 소모되는 오버헤드 감소
- 물리적 메모리보다 큰 프로그램 실행 가능
e.g)
2박3일간 여행을 갔는데
매 끼니마다 재료를 구입하여 냉장고에 보관하면
냉장고 용량이 작아도 된다.
냉장고: 물리적 메모리
식재료: 프로세스를 구성하는 페이지
냉장고에 식재료 보관: 요청된 페이지를 메모리에 적재
가상메모리 기법에서는 프로세스가 실행 되는 동안 일부 페이지만 메모리에 올라와 있고
나머지 페이지는 디스크의 스왑영역에 존재한다.
따라서 메모리에 있는 페이지, 스왑영역에 있는 페이지를 구분해야 한다.
요구 페이징에서는 유효-무효 비트를 두어 구분한다.(각 프로세스를 구성하는 모든 페이지에 대해 존재한다.)
1. 모든 페이지의 유효-무효 비트가 무효값으로 초기화
2. 메모리에 적재되는 경우 유효 값으로 변경
3. 스왑 아웃인 경우 무효 값으로 변경
4. 스왑 인인 경우 유효 값으로 변경
비트가 무효 값인 경우 처음에 초기화 무효비트로 초기화 했기 때문에
스왑 아웃으로 무효값으로 된 경우가 있고,
해당 페이지를 사용하지 않는 경우라서 무효값인 경우도 있다.
CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 무효값인 경우를
페이지 부재(Page Fault)가 발생했다고 한다..! (쉽게 말해서 요청한 주소가 물리적 메모리에 없는 경우)
요구 페이징의 페이지 부재 처리
https://eunjinii.tistory.com/m/142
[OS] 요구 페이징(Demand Paging)과 관련해 페이지 폴트 인터럽트(Page Fault Interrupt) 발생하는 과정 설명
1. 요구 페이징(Demand Paging) 컴퓨터가 프로그램을 실행할 때, 어느 페이지 블록을 어느 시점에 물리 메모리에 적재해야 하는지 판단해야 한다. 메모리의 용량은 제한적이기 때문이다. 프로세스와
eunjinii.tistory.com
1. CPU가 가상주소 MMU에 요청
2. MMU가 TLB로 가서 가상주소가 캐싱되어 있는지 확인
3. 캐싱되어 있으면, 해당 페이지의 물리 주소로 데이터를 갖고와서 CPU에 보냄
캐싱 안 되어 있으면, 페이지 부재 트랩 발생(page fault trap)
4. valid 비트 확인
5. valid 비트가 1이면, MMU가 해당 페이지의 물리 주소로 데이터를 갖고와서 CPU에 보냄
valid 비트가 0이면, MMU가 OS에 페이지 부재 처리 루틴 호출(CPU 제어권 OS로 변경, 속도 저하)
여기서 부터 페이지 부재 발생 했다고 가정!
6. OS는 해당 페이지를 저장공간에서 갖고온다.(스왑 인)
7. OS는 저장공간에서 가져온 데이터를 메모리의 빈프레임에 올려주고, 페이지 테이블을 업데이트한다.
(무효 값을 유효 값으로: valid bit -> 1,물리 주소 업데이트)
8. OS는 CPU에게 프로세스를 다시 실행하라고 명령
9. 1번 항목 실행
만약 비어있는 프레임이 없다면, 기존에 메모리에 있는 프로세스를 스왑 아웃 시켜야 한다.
스왑아웃 된 상태의 요청된 페이지를 디스크로부터 메모리에 적재하는 것은 오랜 시간이 걸린다.
또한, 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗기고 봉쇄 상태가 된다.
이때는 현재까지 수행되던 CPU레지스터 상태 및 프로그램 카운터값을 프로세스 제어블록에 저장해둠으로써 나중이 이 프로세스가 다시 CPU를 할당받았을 때 정확히 같은 상태에서 다음 명령을 수행할 수 있도록 해야한다.
요구 페이징의 성능
요구 페이징 성능에 가장 큰 영향을 미치는 요소는 바로 페이지 부재의 발생 빈도 이다.
앞선 내용을 보면 페이지 부재 발생시 디스크로 부터 메모리로 읽어오는 오버헤드가 발생하기 때문이다.
즉 페이지 부재가 적게 발생할수록 요구 페이징의 성능을 향상 된다.
요구 페이징의 성능은 요청한 페이지를 참조하는 데 걸리는 유효 접근시간(effective access time)으로 측정한다.
유효 접근시간 = (1 - p) * 메모리 접근시간
+ p * (페이지 부재 발생 처리 오버헤드
+ 메모리에 빈프레임이 없는 경우 스왑 아웃 오버헤드
+ 요청된 페이지의 스왑 인 오버헤드
+ 프로세스의 재시작 오버헤드)
p: 페이지 부재 발생비율(0 <= p <= 1)
페이지 교체(page replacement)
앞서 물리적 메모리에 빈프레임이 존재하지 않을 수 있다고 했다.
그러면 메모리에 올라와 있는 페이지 중 하나를 스왑아웃 시켜야하는데 이것을 페이지 교체라고 한다.
페이지를 교체할 때 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 교체 알고리즘(replacement algorithm)이라고 하는데, 이 알고리즘의 목표는 페이지 부재율을 최소화 하는 것이다.
페이지 교체 해야해... 페이지 부재율을 최소화 하면서..!
페이지 교체 알고리즘의 성능은 주어진 페이지 참조열(page refernce string)에 대해 페이지 부재율을 계산함으로써 평가 할 수 있다.
해당 번호의 페이지가 메모리에 이미 있으면 hit
메모리에 없으면 page fault 라고 한다.
최적 페이지 교체(optimal algorithm, MIN, OTP)
물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 방법
참조열에 따라 진행된다고 했을 때 아래와 같이 진행된다.
이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하므로
실제 시스템에서 사용할 수 있는 알고리즘이 아니다.
이러한 알고리즘을 우리는 오프라인 알고리즘이라고 부른다.
알고리즘을 사용하기 보다는 알고리즘 성능에 대한 상한선을 제공한다.
따라서 새로운 페이지 교체 알고리즘을 설계 했는데, 그 성능이 최적 알고리즘과 유사했다고 한다면....
이는 더이상 그 시스템을 위한 교체 알고리즘의 연구가 필요하지 않음을 시사한다..!(퇴근하자~~~)
선입선출 알고리즘(First In First Out: FIFO)
이 알고리즘은 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.
페이지의 향후 참조 가능성을 고려하지 않고,
물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에
비효율적인 상황이 발생 할 수 있다.
또한 이러한 성질로 인해 물리적 메모리의 공간이 오히려 늘어났음에도 불구하고
오히려 성능은 더 나빠질수 있다.
이러한 현상을 FIFO의 이상현상(FIFO anomaly)라고 부른다.
LRU 알고리즘(Least Recently Used Algorithm)
성능향상을 위해서는 향후 사용될 가능성이 낮은 페이지를 우선적으로 메모리에서 쫓아내는 것이 바람직하다.
메모리 페이지의 참조 성향 중 중요한 한 가지 성질인 시간지역성(temporal locality)을 기억하는가?
시간지역성은 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 말한다.
LRU알고리즘은 이러한 성질을 이용하여 페이지 교체시 가장 오래전에 참조가 이루어진 페이지를 내쫓는다.
LFU 알고리즘(Least Frequency Used Algorithm)
페이지 참조 횟수로 교체시킬 페이지를 결정한다.
페이지 중에서 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재 한다.
성능 향상을 위해서는 최저 참조 횟수를 가진 페이지들 중
상대적으로 더 오래전에 참조된 페이지를 쫓아내도록 구현하는 것이 효율적이다.
LRU보다 구현이 복잡하다.
LFU 알고리즘은 참조횟수를 계산하는 방식에 따라 2가지로 나뉘어 진다.
- Incache-LFU
- 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트
- 쫓겨났다가 다시 올라오면 참조횟수 카운트 1부터 시작(중간 초기화)
- Perfect-LFU
- 총 과거 참조횟수 카운트
- 쫓겨났다가 다시 올라와도 참조횟수 계속 누적
- Incache-LFU보다 오버헤드가 상대적으로 더 큼(참조 기록을 모두 보관하기 때문)
클럭 알고리즘(clock algorithm)
LRU, LFU알고리즘은 페이지의 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 하므로
알고리즘의 운영에 시간적인 오버헤드가 발생한다.
하드웨어적인 지원을 통해 알고리즘의 운영 오버헤드를 줄인 방식이다.
LRU의 근사 시킨 알고리즘으로 NUR또는 NRU알고리즘으로 불린다.
LRU 알고리즘이 가장 오래전에 참조된 페이지를 교체하는 것에 비해
클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다.
교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
하지만, 하드웨어 자원으로 동작하기 때문에 LRU에 비해 페이지 관리가 훨씬 빠르고 효율적으로 이루어진다.
따라서 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.
클럭 알고리즘은 교체할 페이지를 선정하기위해 페이지 프레임들의 참조비트(reference bit)를 순차적으로 조사한다.
- 참조비트가 1인 페이지는 0으로 바꾼다.
- 참조비트가 0인 페이지는 교체한다. 그리고 1로 바꾼다.
시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체하는 것
시곗바늘이 한 바퀴 도는 데 소요되는 시간만큼 페이지를 메모리에 유지시켜둠으로써 페이지 부재율을 줄이도록 설계되었기 때문에
2차 기회 알고리즘이라고도 부른다.
페이지 프레임의 할당
프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지를 결정해야함.
효율적인 메모리 할당 방법이 필요하다..!
- 균등 할당(equal allocation)
- 모든 프로세스에게 페이지 프레임을 균일하게 할당
- 비례 할당(proportional allocation)
- 프로세스의 크기에 비례하여 페이지 프레임을 할당
- 프로세스의 크기가 모두 균일하지 않기 때문
- 우선순위 할당(priority allocation)
- 프로세스의 우선순위에 따라 페이지 프레임을 할당
- 당장 실행되야 할 프로세스와 아닌 것 구분
하지만,,, 할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 우려가 있다..
적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당 해야한다.
각프로세스에 할당되는 페이지 프레임 수를 결정해야하고, 일부 프로세스에게 메모리를 할당하지 않아야 할 수도 있다.
전역교체와 지역교체(global replacement, local replacement)
페이지 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분 할 수 있다.
- 전역 교체
- 모든 페이지 프레임이 교체 대상이 될 수 있다
- 프로세스마다 메모리를 할당하는 것이 아님
- 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법
- 지역 교체
- 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정 가능
- 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 함
스레싱(thrashing)
프로세스가 원할하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당 받아야한다.
최소한의 페이지 프레임을 할당받지 못할 경우 성능상 심각한 문제 발생.. ㅠ0ㅠ
집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율(page fault rate)이 크게 상승해 cpu 이용률이 급격히 떨어질 수 있기 때문이다.
이와 같은 현상을 바로바로바로
스레싱(thrashing)
스레싱 발생 시나리오
1. 운영체제는 cpu의 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적기 때문이라고 판단
준비 큐에 프로세스가 1개라도 있을 경우 cpu는 쉬지않고 일한다. 하지만 준비 큐가 비는 경우 cpu는 논다..!
즉 프로세스가 i/o가 작업을 함으로써 준비 큐가 비는 경우가 발생!!
2. 운영체제는 MPD를 높이게 된다.(cpu 이용률이 낮기 때문..!)
메모리에 올라가는 프로세스 수를 늘린다.
메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍 정도(multi-programming degree: MPD)라고 부른다.
3. MPD가 과도하게 높아지게 되어 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소
각 프로세스는 최소한의 페이지 프레임을 할당받지 못하는 상태가 된다..
그러면 페이지 부재가 발생..!
페이지 부재가 발생하면 디스크 io 작업을 수반하기 때문에 문맥교환을 통해 다른 프로세스에게 cpu가 양도된다.
이때 다른 프로세스 역시 할당받은 메모리 양이 지나치게 적으면 페이지 부재가 발생... ㅠ0ㅠ
그러면 또 다른 프로세스에게 cpu 할당
4. 모든 프로세스가 페이지 부재가 발생하여 시스템은 페이지 부재를 처리하느라 분주해지고, cpu는 놀고 있다.
5. 운영체제는 cpu가 또 놀고있네? 라고 생각해서 MPD를 높인다.(다른 프로세스를 메모리에 또 추가한다.)
6. 프로세스당 할당된 프레임의 수가 더욱 감소하고 페이지 부재는 더 발생
스왑 인, 스왑 아웃을 지속적으로 발생하여, cpu는 또 논다.
이러한 상황을 스레싱이라고 한다..
띠라서 스레싱이 발생하지 않도록 하면서 cpu이용률을 최대한 높일 수 있도록 MPD를 조절하는 것이 매우매우매우 중요하다.!
그래서 워킹셋(working set)과 페이지 부재 빈도 알고리즘(page-falut frequency scheme) 두두둥장!
워킹셋 알고리즘(working set)
프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다.
이러한 경향을 지역성 집합(locality set)이라고 한다.
워킹셋(working set)알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘을 의미한다.
한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋 이라고 정의
워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만
그 프로세스에게 메모리를 할당..!
만약 아닌 경우,
프로세스에게 할당된 페이지 프레임을 모두 반납 시킨 후
그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃!!
이러한 메카니즘으로 MDP를 조절하고 스레싱을 방지함.
워킹셋 알고리즘은 워킹셋 윈도우(working set window)를 사용한다.
페이지가 참조된 시점부터 Δ시간 동안은 메모리에 유지하고, 그 시점이 지나면 메모리에서 지워 버린다.
1. 워킹 셋 크기의 합 > 프레임 수
일부 프로세스를 스왑 아웃, 남은 프로세스의 워킹셋이 메모리에 모두 올라가도록 보장(MPD를 줄이는 효과)
2. 워킹셋 모두 할당 후에도 프레임이 남을 경우
스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋 할당(MPD 증가 효과)
따라서
프로세스의 지역성 집합을 효과적으로 탐지할 수 있는 윈도우 크기 Δ를 결정하는 것이 중요하다..!사진을 보면 워킹셋의 크기는 시간이 지남에 따라 변하게 됨을 알 수 있다.워킹셋 알고리즘은 이처럼 프로세스가 메모리를 많이 필요할 때는 많이 할당하고, 적게 필요 할때는 적게 할당 한다.
워킹셋 알고리즘은 동적인 프레임 할당 기능까지 수행!!
페이지 부재 빈도 알고리즘(page-fault frequency: PFF)
페이지 부재 빈도 알고리즘(page-fault frequency: PFF)은 프로세스의 페이지 부재율을 주기적으로 조사하고
조사 결과에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.
- 부재율이 상한값(upper bound)을 넘을 경우
- 어떤 프로세스의 페이지 부재율이 상한값(upper bound)을 넘게 되면 이 프로세스에 할당 된 프레임수가 부족하다고 판단하여 프로세스에게 프레임을 추가로 더 할당 한다.
- 이때 추가로 할당할 빈 프레임이 없다면 일부 프로세를 스왑 아웃 시켜 메모리에 올라가 있는 프로세스의 수를 조절
- 부재율이 하한값(lower bound)아래로 간 경우
- 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주하여 할당된 프레임 수를 줄인다.
- 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당(스왑 인)함으로써 MPD를 높인다.
'컴퓨터과학 > 0 +운영체제' 카테고리의 다른 글
| 운영체제 핵심 개요 (0) | 2023.09.14 |
|---|---|
| [운영체제] 9. 메모리 관리 (0) | 2022.06.13 |
| [운영체제] 8. Scheduling 기법(2) -유닉스/리눅스 스케줄링 (0) | 2022.06.11 |
| [운영체제] 7. Scheduling 기법 (0) | 2022.05.15 |
| [운영체제] 6. Race Conditions(2) -Semaphores, Mutex and Monitors (0) | 2022.05.03 |