-
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. 1, 3
2. 상호 배제, 점유와 대기, 비선점, 원형 대기
3. 다단계 큐 스케줄링, 큐간의 이동, 기아현상
4. 뮤텍스 락은 소유권이 존재하여 하나의 자원이 있는 경우에만 적용 가능하지만 세마포어는 자원이 여러개 있는 경우에도 적용이 가능하다.
뮤텍스 - 메모리 안, 프로세스 내에 동기화, 세마포어 - 파일, 프로세스 사이 동기화