2023.08.13 - [컴퓨터 공학/운영체제] - [혼공컴운] chapter.13 교착 상태
[혼공컴운] chapter.13 교착 상태
2023.08.13 - [컴퓨터 공학/운영체제] - [혼공컴운] chapter.12 프로세스 동기화 [혼공컴운] chapter.12 프로세스 동기화 2023.07.29 - [컴퓨터 공학/운영체제] - [혼공컴운] chapter.11 CPU 스케줄링 [혼공컴운] chapte
zinistic.tistory.com
14-1 연속 메모리 할당
- 스와핑(swapping)
: 오랫동안 사용되지 않은 프로세스들을 임시로 보조기억장치의 일부 영역에 쫓아내고, 쫓아내서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식.- 스왑 영역(swap space): 프로세스들이 쫓겨나 저장되는 영역. 보조기억장치의 일부에 해당.
- 스왑 아웃(swap-out): 현재 실행되지 않는 프로세스가 메모리(RAM)에서 스왑 영역으로 옮겨지는 것.
- 스왑 인(swap-in): 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것.
→ 스와핑을 이용하여 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시에 실행 가능하다.
- 메모리 할당
- 최초 적합(first fit): 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방법.
* 검색 최소화, 빠른 할당 가능. - 최적 적합(best fit): 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식.
- 최악 적합(worst fit): 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 배치하는 방법.
- 최초 적합(first fit): 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방법.
- 외부 단편화(external fragmentation): 여러 프로세스들이 실행되고 종료되면서 메모리 사이에 생기는 작은 공간으로 인해서 생기는 메모리 낭비 현상.
* 빈 공간의 총합이 프로세스를 적재할 수 있는 충분한 공간이어도 그 공간이 프로세스를 적재하기 충분하지 않은 크기로 분할되어 있다면 그 프로세스를 적재할 수 없음.
- 외부 단편화 해결 방법
- 압축(compaction)
: 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법.
* 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기한다는 단점이 있음.
- 압축(compaction)
- 외부 단편화 해결 방법
14-2 페이징을 통한 가상 메모리 관리
- 가상 메모리(virtual memory): 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게하는 기술.
- 페이징(paging)
: 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame) 이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 기법.
- 페이징 시스템에서 스와핑
: 페이징에서 스와핑 사용 가능. 프로세스 단위가 아닌 페이지 단위로 스왑 인/아웃.
- 페이지 아웃(page out): 페이징 시스템에서 스왑 아웃
- 페이지 인(page in): 페이징 시스템에서 스왑 인
→ 프로세스 전체가 메모리에 적재될 필요 없음. 필요하지 않은 페이지는 보조기억장치 스왑 영역에 저장됨.
- 페이징 시스템에서 스와핑
- 페이지 테이블(page table)
: 프로세스가 물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 하는 것. 페이지 번호와 프레임 번호를 짝지어주는 역할을 함.
페이지 테이블의 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있다.
* 페이징 시스템은 외부 단편화 문제를 해결할 수 있지만, 내부 단편화 문제를 야기할 수 있음.
→ 프로세스 크기가 페이지 크기의 배수가 아닐 수 있음.
- 페이지 테이블 베이스 레지스터(PTBR: page table base register)
: 각 프로세스의 페이지 테이블이 적재된 주소를 저장하는 레지스터. CPU 내에 존재함.
* 실행되는 프로세스가 변경되면 PTBR이 가리키는 주소 또한 변경됨.
- TLB(Transiation Lookaside Buffer)
: CPU는 페이지 테이블에 접근한 후 프레임에 다시 접근하여 총 두번의 메모리 접근이 필요한데, 이와 같은 문제를 막기 위한 페이지 테이블의 캐시 메모리. 일반적으로 MMU 내에 존재함.
* 캐시 메모리 역할을 수행하기 위하여 페이지 테이블의 일부를 저장함.
- TLB 히트: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우
- TLB 미스: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 없을 경우
- TLB(Transiation Lookaside Buffer)
- 페이징에서의 주소 변환
- 페이지 번호: 접근하고자 하는 페이지 번호.
- 변위: 프레임의 시작 번지로부터 얼만큼 떨어져 있는지의 정보.
* 페이징 주소 변환 예시
< 5번 페이지, 변위 2 라는 논리 주소에 접근 >
→ 페이지 테이블을 통해 5번 페이지의 프레임 찾기.
→ 5번 페이지는 1번 프레임에 존재.
→ 1번 프레임의 시작 주소에 변위 2를 더한 값에 접근. 즉 10번지에 접근함.
- 페이지 테이블 엔트리(PTE: page table entry)
: 페이지 테이블의 각각의 행들을 말함.
< 페이지 테이블 엔트리에 있는 정보>- 유효 비트(vaild bit): 현재 해당 페이지에 접근 가능한지 여부를 알려주는 비트.
* 현재 페이지가 메모리에 적재(1)되어 있는지, 보조기억장치에 적재(0)되어 있는지 알려주는 비트이다.
* 페이지 폴트(page fault): 유효 비트가 0인 (즉, 보조기억장치에 적재되어 있는)페이지에 접근하려고 할때 발생하는 예외.
< 페이지 폴트를 처리하는 과정 >
- CPU 기존 작업 내용 백업
- 페이지 폴트 처리 루틴 실행.
- 원하는 페이지 메모리에 적재 후 유효 비트 1로 변경
- CPU는 해당 페이지에 접근 가능.
- 보호 비트(protection bit): 페이지 보호 기능을 위한 비트. 읽기 모드와 읽기/쓰기 모드를 구분함.
- 보호 비트가 0 일 경우: 읽기만 가능.
- 보호 비트가 1 일 경우: 읽기/쓰기 모두 가능.
* 보호 비트를 세 개의 비트로 자세한 구현 가능
=> 읽기(Read)비트 r / 쓰기(Write)비트 w / 실행(eXecute) 비트 x
ex) 보호비트가 100일 경우
=> 읽기 가능. 쓰기 불가능. 실행 불가능. - 참조 비트(reference bit): CPU가 해당 페이지에 접근한 적이 있는지 여부를 나타냄.
접근한 적이 있다면 1, 접근한 적이 없다면 0. - 수정 비트(modified bit): 해당 페이지에 데이터의 수정 여부를 나타냄. 더티 비트(dirty bit)라고도 함.
변경된 적이 있다면 1, 변경된 적이 없다면 0.
* 수정 비트가 필요한 이유
: 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지, 할 필요가 없는지 판단하기 위함.
- 유효 비트(vaild bit): 현재 해당 페이지에 접근 가능한지 여부를 알려주는 비트.
- 쓰기 시 복사(copy on write)
: fork 시스템 호출로 생긴 복사본(자식 프로세스)가 쓰기 작업을 할 시에 별도의 공간으로 복제.
→ 운영체제에서 fork 시스템 호출 시에 부모 프로세스의 복사본이 자식 프로세서로 만들어지는 과정에서 복사본을 메모리를 할당하지 않고 부모 프로세스와 동일한 프레임을 가리키게 함으로서 시간과 자원을 절약할 수 있음. 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제됨. - 계층적 페이징(hierarchical paging)
: 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식.
프로세스의 페이지 테이블을 여러 개의 페이지로 자르고, 이 페이지들을 가리키는 페이지 테이블을 두는 방식.
* outer 페이지 테이블: 페이지를 가리키는 페이지 테이블. 항상 메모리에 유지해야 함.
* 계층적 페이징 시스템에서의 주소 변환 과정
1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지 찾기.
2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더하여 물리 주소 얻기.
14-3 페이지 교체와 프레임 할당
- 요구 페이징(demand paging)
: 프로세스를 메모리에 적재할 때 필요한 페이지만을 메모리에 적재하는 기법.
* 순수 요구 페이징(pure demand paging): 어떠한 페이지도 메모리에 적재하지 않은 채로 실행하여 메모리에 적재하는 기법.
- 페이지 참조열(page reference string): CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열.
→ 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않음 - 페이지 교체 알고리즘
- FIFO 페이지 교체 알고리즘
: 페이지 폴트 발생 시 메모리에 가장 먼저 적재된 페이지부터 내쫓는 방식. - 2차 기회 페이지 교체 알고리즘
: 기본적으로 FIFO 페이지 교체 알고리즘의 규칙을 따르되, 방출 대상 페이지의 참조 비트가 1 이라면 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정. - 최적 페이지 교체 알고리즘
: 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘.
* 앞으로의 사용 빈도를 알기는 현실적으로 어렵기 때문에 다른 알고리즘을 평가하는데 사용. - LRU 페이지 교체 알고리즘
: 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘.
- FIFO 페이지 교체 알고리즘
★ 페이지 참조열이 2 3 1 3 5 2 3 4 2 3 일 때 여러 알고리즘의 페이지 교체 예시 ★
< FIFO 페이지 교체 알고리즘 >
→ 페이지 폴트 4번 발생.
< 최적 페이지 교체 알고리즘 >
→ 페이지 폴트 2번 발생.
* 페이지 참조열을 참고해서 미래에 어떤 페이지가 쓰이지 않을지를 알아내 해당하는 페이지를 스왑 아웃하는 알고리즘.
< LRU 페이지 교체 알고리즘 >
→ 페이지 폴트 3번 발생.
* 페이지 참조열을 참고해서 과거에 어떤 페이지가 오랫동안 쓰이지 않았는지를 알아내 해당하는 페이지를 스왑 아웃 하는 알고리즘.
- 스래싱
: 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 CPU 이용률이 낮아지는 문제.
- 멀티프로그래밍의 정도(degree of multiprogramming): 메모리에서 동시 실행되는 프로세스의 수
→ 동시 실행되는 프로세스가 많아질수록 CPU 이용률도 비례해서 커지지만 동시에 실행되는 프로세스가 필요 이상으로 많아질 경우 CPU 이용률도 낮아짐.
- 프레임 할당 방식
- 균등 할당(equal allocation): 모든 프로세스에 균등하게 프레임을 제공하는 방식. 정적 할당 방식.
ex) 세 프로세스에 300 프레임을 할당한다면 각 프로세스에 100 프레임씩 할당하는 방식. - 비례 할당(proportional allocation): 프레임 할당 비율을 프로세스 크기에 비례해 할당하는 방식.
프로세스 크기가 크면 프레임을 많이 할당하고, 프로세스 크기가 작으면 프레임을 적게 할당. 정적 할당 방식. - 작업 집합 모델(working set model): 작업 집합을 참고하여 그 크기만큼 프레임을 할당하는 방식.
* 작업 집합(working set): 프로세스가 일정 기간 동안 참조한 페이지의 집합.
→ 운영체제는 작업 집합의 크기만큼만 프레임을 할당.
* 작업 집합 구하기
→ 프로세스가 참조한 페이지, 일정 시간 간격이 주어지면 작업 집합을 구할 수 있다.
특정 시간에서의 필요한 프레임의 개수를 구할 수 있음. - 페이지 폴트 빈도(PFF:Page-Fault Frequency): 페이지 폴트율에 상한선과 하한선을 정하고, 이 범위 내로 프레임을 할당하는 방식.
* 페이지 폴트율 高 => 적은 프레임을 갖고 있음.
* 페이지 폴트율 低 => 많은 프레임을 갖고 있음.
→ 너무 많지도 적지도 않은 프레임을 할당하게 하는 방식.
- 균등 할당(equal allocation): 모든 프로세스에 균등하게 프레임을 제공하는 방식. 정적 할당 방식.
* 오류 지적은 환영입니다.^^ *
'컴퓨터 공학 > 운영체제' 카테고리의 다른 글
| [혼공컴운] chapter.14~15 확인문제 (1) | 2023.08.21 |
|---|---|
| [혼공컴운] chapter.15 파일 시스템 (1) | 2023.08.20 |
| [혼공컴운] chapter.12~13 확인문제 (1) | 2023.08.13 |
| [혼공컴운] chapter.13 교착 상태 (0) | 2023.08.13 |
| [혼공컴운] chapter.12 프로세스 동기화 (1) | 2023.08.13 |