-
Notifications
You must be signed in to change notification settings - Fork 0
학습 기록 | w7 지현
#스와핑 #최초 적합 #최적 적합 #최악 적합 #외부 단편화
- 현재 사용되지 않는 프로세스들을 보조기억장치 일부 영역(스왑 영역, swap space)으로 보내고 : 스왑 아웃, swap-out
- 빈 공간에 새 프로세스를 적재하여 실행 : 스왑 인, swap-in
-
프로세스들이 요구하는 메모리 주소 공간의 크기 > 메모리 크기
→ 프로세스 동시 실행 가능
-
스왑 영역 크기 확인하기 : free, top 명령어
- 프로세스는 메모리의 빈 공간에 할당되어야 한다.
- 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식
-
최초 적합(first-fit)
- 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 프로세스 배치
- 검색 최소화, 빠른 할당
-
최적 적합(best-fit)
- 빈 공간을 모두 검색해 본 후, 적재 가능한 가장 작은 공간에 할당
-
최악 적합(worst-fit)
- 빈 공간을 모두 검색해 본 후, 적재 가능한 가장 큰 공간에 할당
→ 외부 단편화 (external fragmentation) 문제 발생하기 때문
external fragmentation
- 원인 : 프로세스들이 실행되고 종료되길 반복하며 메모리 사이 사이에 빈 공간 발생
- 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
외부 단편화 해결
- 메모리 압축 (compaction)
- 프로세스를 적당히 재배치하여 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
- 단점 : 오버헤드 야기, 프로세스가 해야할 일 중지, 명확한 방법 특정 어려움
- 가상 메모리 기법, 페이징 → 대중적인 방법
#페이징 #페이지 테이블 #PTBR #TLB
- 외부 단편화
- 물리 메모리보다 큰 프로세스 실행 불가
가상 메모리 (virtual memory)
- 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
- 가상 메모리 관리 기법 :
페이징,세그맨테이션
paging
-
메모리의 물리 주소 공간을 프레임(frame) 단위로 자르고
-
프로세스의 논리 주소 공간을 페이지(page) 단위로 자른 뒤
-
각 페이지를 프레임에 할당
-
페이징에서의 스와핑
- 페이지 인, 페이지 아웃
‼ 프로세스를 실행하기 위해 모든 페이지가 적재될 필요는 없다
→ 물리메모리보다 큰 프로세스도 실행될 수 있다!
- 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 알기 어려움
- 불연속적으로 배치되어 있다면 CPU가 순차적으로 실행할 수 없음
- CPU 입장에서 ‘다음에 실행할 명령어 위치’를 찾기 어려움
- (실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치되더라도
- (CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 하는 방법
- 페이지 번호와 프레임 번호를 짝지어주는 일종의 이정표
- 내부 단편화 (internal fragmentation)
- 모든 프로세스가 페이지 크기의 배수가 아님 → 낭비
- 하나의 페이지 크기보다 작은 크기로 내부 단편화 발생
- 적절하게 페이지 크기 설정하는 것이 중요
PTBR
- 프로세스마다 페이지 테이블이 존재하며 메모리에 적재됨
- 각 페이지 테이블은 CPU내의 페이지 테이블 베이스 레지스터(
PTBR; Page Table Base Register) 가 가리킴
TLB
-
페이지 테이블이 메모리에 있으면 메모리 접근 시간이 두배 → TLB(Translation Lookaside Buffer)사용
-
페이지 테이블의 캐시 메모리
-
페이지 테이블의 일부를 가져와 저장
-
TLB 히트
- CPU가 접근하려는 논리 주소가 TLB에 존재 (메모리 접근 1번)
-
TLB 미스
- CPU가 접근하려는 논리 주소가 TLB에 없음 (메모리 접근 2번)
- 특정 주소에 접근하기 위해
- 어떤 페이지/프레임에 접근하고 싶은지
- 접근하려는 주소가 그 페이지/프레임으로부터 얼마나 떨어져 있는지
논리 주소 : 페이지 번호(page number) + 변위(offset)
→ (페이지 테이블)
→ 물리 주소 : 프레임 번호(frame number) + 변위
- 페이지 테이블 각각의 행
- 페이지 번호, 프레임 번호 외의 값
-
유효 비트 (valid bit)
- 현재 해당 페이지에 접근 가능한지 여부
- 메모리 적재 여부
유효비트가 0인 페이지에 접근 →
페이지 폴트(page fault)인터럽트 발생 → 인터럽트 처리 루틴 실행 -
보호 비트 (protection bit)
- 페이지의 보호 기능을 위해 존재
- 읽기/쓰기/실행 권한
-
참조 비트 (reference bit)
- CPU가 이 페이지에 접근한 적이 있는지 여부
-
수정 비트 (modified bit = dirty bit)
- CPU가 이 페이지를 쓴적이 있는지 여부
- 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지 여부를 판단
- 변경된 페이지를 반영
#요구 페이징 #페이지 교체 알고리즘 #스래싱 #프레임 할당
요구 페이징 (demand paging)
- 요구되는 페이지만 적재하는 기법
- 처음부터 모든 페이지를 적재하지 않음
순수 요구 페이징 (pure demand paging)
- 아무 페이지도 적재하지 않고 실행하면 페이지 폴트가 계속 발생. 어느 정도 적재되면 발상 빈도가 떨어짐
- 어떤 페이지를 보조기억장치로 보낼지 결정하는 방법
❓ 좋은 페이지 교체 알고리즘이란?
- 페이지 폴트가 적은 알고리즘
페이지 참조열 (page reference string)
-
CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
2 2 2 4 5 5 5 2 3 9 → 2 4 5 2 3 9
- FIFO 페이지 교체 알고리즘
- 메모리에 가장 먼저 올라온 페이지부터 내보냄
- 장점 : 아이디어와 구현이 간단
- 단점 : 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있음 (먼저 적재되었다고 내쫓아서는 안됨!)
FIFO 페이지 교체 알고리즘 보완
| 참조비트 | 의미 | 내보낼 페이지에 선정될 경우 |
|---|---|---|
| 1 | CPU가 한 번 참조한 적이 있는 페이지 | 한번 더 기회 (참조비트 0으로 초기화 후 적재시간 → 현재시간) |
| 0 | CPU가 참조한 적이 없는 페이지 | 내쫓기 |
-
최적 페이지 교체 알고리즘
- CPU에 의해 참조되는 횟수를 고려
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체
- 장점 : 가장 낮은 페이지 폴트율 보장
- 단점 : 실제 구현이 어려움
→ 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주
-
LRU 페이지 교체 알고리즘
- Least-Recently-Used
- 가장 오랫동안 사용되지 않은 페이지 교체
| 최적 페이지 교체 알고리즘 | 가장 오래 사용되지 않을 페이지 교체 |
|---|---|
| LRU 페이지 교체 알고리즘 | 가장 오래 사용되지 않은 페이지 교체 |
- 나쁜 페이지 교체 알고리즘을 사용
- 프로세스가 사용할 수 있는 프레임 자체가 적음
- 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU이용률)이 저해되는 문제
- 동시 실행되는 프로세스의 수(멀티프로그래밍 정도)를 늘린다고 CPU 이용률이 높아지는 것이 아니다.
❓ 스래싱이 발생되는 이유
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
- 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.
정적 할당 방식 (프로세스 크기와 물리 메모리의 크기만 고려)
- 균등 할당(equal allocation)
- 모든 프로세스들에게 균등하게 프레임을 배분
- 비례 할당(proportional allocation)
- 프로세스의 크기에 비례하여 프레임 배분
동적 할당 방식 (프로세스가 실행하는 과정에서 배분할 프레임 결정)
-
작업 집합 모델 (working set model)
- CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당
- 빈번한 페이지 교체 방지
작업 집합 : 실행 중인 프로세스가 일정 기간 동안 참조한 페이지의 집합
-
페이지 폴트 빈도(PFF; Page-Fault Frequency) 기반 프레임 할당
- 페이지 폴트율에 상한선과 하한선을 정하고 내부 범위 안에서만 프레임을 할당
- 페이지 폴트율 높다 : 너무 적은 프레임 → 더 할당
- 페이지 폴트율 낮다 : 너무 많은 프레임 → 회수
PTBR이 실행되는 프로세스 페이지 테이블을 가리킨다면 하나만 존재?
https://m.blog.naver.com/bycho211/221028200599
-
옳지 않은 것을 모두 구하시요.
- 페이지 테이블 엔트리(PTE)에 담기는 정보 중 유효비트가 0이라면 페이지 폴트가 발생한다.
- 프로세스를 연속적으로 메모리에 할당하면 내부 단편화 문제가 발생한다.
- LRU 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 교체하는 방법이다.
- 프로세스를 실행하기 위해서 모든 페이지가 메모리에 적재될 필요는 없다.
- 페이징에서 주소 변환 시 논리주소와 물리주소의 변위는 동일하다.
-
내부 단편화가 발생하는 이유와 해결 방안을 설명하시오.
-
프레임 할당 방식은 ( A ) 할당 방식과 ( B ) 할당 방식으로 구분된다. A와 B의 특징을 작성하시오.
정답
1. 2, 3
2. 모든 프로세스가 페이지 크기의 배수가 아니므로 하나의 페이지 크기보다 작은 크기로 내부 단편화가 발생한다.
적절하게 페이지 크기를 설정해야 한다.
3. 정적, 동적
정적 할당 방식은 프로세스 크기와 물리 메모리의 크기만 고려하여 할당하며 균등 할당, 비례 할당이 있다.
동적 할당 방식은 프로세스가 실행하는 과정에서 배분할 프레임을 결정하며 작업 집합 모델과 페이지 폴트 빈도를 활용하는 방식이 있다.