혼자 공부하는 컴퓨터 구조+운영체제 6주차 (14~15)

2023. 2. 19. 23:47

📃 기본 미션

p.400, 확인 문제 1번 ) 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

보기) 최초 적합, 최적 적합, 최악 적합

(①) : 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
(②) : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
(③) : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

🖍 ) ① : 최초 적합, ② : 최악 적합, ③ : 최적 적합

'14-1 메모리 할당' 을 참고

📃 선택 미션

Ch.14 (14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2414523423'일 때 FIFO, 최적 페이지, LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

🖍 )

3개의 프레임에 각 알고리즘별로 페이지 참조열이 진행되었을때 페이지 폴트는 아래와 같다.

FIFO : 4번

최적페이지 : 2번

LRU 페이지 교체 : 4번

FIFO는 프레임에 먼저 적재된 페이지부터 교체되고

최적페이지 알고리즘은 남은 페이지 참조열 중 사용 빈도가 가장 낮을 페이지를 교체하며

LRU 페이지 교체 알고리즘은 가장 오래 사용되지 않은 페이지를 교체하였다.

1️⃣4️⃣ 가상 메모리

14-1 연속 메모리 할당

✅ 연속 메모리 할당 : 프로세스에게 연속적인 메모리 공간을 할당

스와핑

현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고, 빈 공간에 새 프로세스를 적재하여 실행하는 방식
현재 실행되지 않는 프로세스 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃
스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인

프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 큰 경우에도 동시 실행 가능

메모리 할당

프로세스는 메모리의 빈 공간에 할당되어야 한다 ➡️ 빈 공간이 여러 군데 있을 경우 세 가지 방식으로 할당 가능
최초 적합, 최적 적합, 최악 적합

최초 적합 (first fit)

운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
공간 검색을 최소화 할 수 있고 결국 빠른 할당이 가능

최적 적합(best fit)

운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당하는 방식

최악 적합(worst fit)

운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당

외부 단편화

프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 비효율적인 방식이다
외부 단편화(external fragmentation)이라는 문제가 발생하기 때문
프로세스를 연속적으로 배치하여 수행 중, 먼저 종료되는 프로세스가 발생할 경우 다음과 같다.

비어있는 공간의 총 합은 50MB지만, 50MB 크기의 프로세스를 적재할 수 없다 ➡️ 외부 단편화
외부 단편화 : 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상

외부 단편화 해결

메모리 압축(compaction)
- 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
- 프로세스를 적당히 재배치시켜 흩어져있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
- 빈 공간을 합치는 과정에서 많은 오버헤드가 발생하고, 옮겨지는 프로세스들의 중단 등의 문제가 발생
가상 메모리 기법, 페이징

메모리 압축을 수행하면 내 방에 가구 놓을 공간 마련하듯 공간을 만든다.

14-2 페이징을 통한 가상 메모리 관리

연속 메모리 할당의 두 가지 문제점

외부 단편화
물리 메모리보다 큰 프로세스는 실행 불가

가상 메모리

실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
크게 페이징, 세그멘테이션이 있다.
대부분의 운영체제에선 페이징을 사용한다.

페이징(paging)

외부 단편화는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다.
프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당할 수 있다면 해결
프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자른다.
메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른다.
페이지를 프레임에 할당하는 가상 메모리 관리 기법을 페이징이라 한다.

페이징에서의 스와핑

프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃 한다.
실행에 필요한 페이지들은 메모리로 스왑 인 한다.
프로세스를 실행하기 위해 모든 페이지가 적재될 필요가 없다.
즉, 물리 메모리보다 큰 프로세스도 실행될 수 있다. (페이지 단위로 메모리에 적재되니깐)

페이지 테이블

프로세스가 메모리에 불연속적으로 배치되는 페이징 기법에선 CPU가 ‘다음에 실행할 명령어 위치’를 찾기 어려워진다.
(실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치되더라도
(CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 하는 방법
페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표 (프로세스마다 존재해서 짝지어 주는 이정표)
물리적으로는 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보임
CPU는 그저 논리 주소를 순차적으로 실행하면 될 뿐이다.

내부 단편화

페이지 크기가 10KB, 프로세스 크기가 108KB일 경우
2KB 만큼의 내부 단편화가 발생할 수 있다.
하나의 페이지 크기보다 더 작은 크기로 발생하는 메모리 낭비

PTBR

프로세스마다 페이지 테이블이 있다.
각 페이지 테이블은 CPU 내의 프로세스 테이블 베이스 레지스터(PTBR)가 가리킨다.

TLB

페이지 테이블이 메모리에 위치하면 프로세스 실행과정에서 메모리에 접근하는 시간이 두 배가 된다.
메모리에 접근하는 시간을 줄이기 위해 CPU 옆에 (일반적으로 MMU내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 일부를 가져와 저장하는 캐시 메모리를 이용한다.
CPU가 접근하려는 논리 주소가 TLB에 있다면 ➡️ TLB 히트 : 메모리 접근을 한 번한다.
CPU가 접근하려는 논리 주소가 TLB에 없다면 ➡️ TLB 미스 : 메모리 접근을 두 번 한다.

페이징에서의 주소 변환

특정 주소에 접근하고자 할때 필요한 정보
1. 어떤 페이지/프레임에 접근하고 싶은지에 대한 정보
2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지에 대한 정보
페이징 시스템에서의 논리 주소 : 페이지 번호(pgae number)와 변위(offset)로 이루어져있다.
<페이지 번호, 변위> 는 페이지 테이블을 거쳐 <프레임 번호, 변위>로 변환된다.
변위는 동일하다.

페이지 테이블 엔트리

페이지 테이블의 각각의 행 : 페이지 테이블 엔트리(PTE)
페이지 번호, 프레임 정보 외에 담기는 정보가 존재
유효 비트 : 현재 해당 페이지에 접근 가능한지 여부를 나타내는 비트 정보 (메모리에 적재되어 있는지 여부를 알려준다.)
유효 비트가 0인 페이지에 접근하려 할 경우 페이지 폴트(page fault)라는 인터럽트가 발생한다.
보호 비트 : 페이지 보호 기능을 위해 존재하는 비트
보호 비트를 읽기, 쓰기, 실행으로 권한을 나누어 저장할 수 있다.
참조 비트 : CPU가 이 페이지에 접근한 적이 있는지 여부를 나타내는 비트
수정 비트(=dirty bit) : CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부를 알려준다.
수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없느지를 판단하기 위해 존재한다.

14-3 페이지 교체와 프레임 할당

요구 페이징

처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
요구되는 페이지만 적재하는 기법
아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행하는 경우 ‘요구 페이징의 기본적인 양상’에 따라 페이지 폴트가 지속적으로 발생하게 되고, 점차적으로 페이지 폴트 발생 빈도가 떨어지게 된다. 이를 순수 요구 페이징(pure demand paging) 기법이라고 한다.

요구 페이징의 기본적인 양상

CPU가 특정 페이지에 접근하는 명령어를 실행한다.
해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다.
페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
다시 1번을 수행한다.

요구 페이징 시스템이 안정적으로 작동하기 위해 해결해야 할 묹

페이지 교체
프레임 할당

페이지 교체 알고리즘

요구 페이징 기법으로 페이지들을 적재하다보면 메모리가 가득 차게 되며, 스와핑을 수행하게 된다.
페이지 스와핑에서 스왑 아웃(페이지 아웃)을 수행할 페이지를 결정하는 방법을 페이지 교체 알고리즘이라 한다.
일반적으로 페이지 폴트가 적은 알고리즘을 좋은 페이지 교체 알고리즘이라 한다.
페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있다.

✅ 페이지 참조열(page reference string)
- CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
2223555337 의 페이지를 참조했다고 가정할 경우 23537이 페이지 참조열이 된다.

FIFO 페이지 교체 알고리즘

가장 단순한 방식
메모리에 가장 먼저 올라온 페이지부터 내쫒는 방식
아래 그림에서 페이지 교체시에 발생하는 페이지 폴트만 고려 (순수 페이지 폴트는 생략)

아이디어와 구현은 간단하지만 마냥 좋지는 않다. ➡️ 프로그램 실행 내내 사용될 페이지가 메모리에 먼저 적재되었다고 교체 당할 수 있다.

FIFO 페이지 교체 알고리즘 - 보완책

2차 기회(second-chance) 페이지 교체 알고리즘
참조 비트 1 : CPU가 한 번 참조한 적이 있는 페이지
참조 비트 0 : CPU가 참조한 적이 없는 페이지
참조 비트를 활용하여 FIFO 페이지 교체 알고리즘을 수행한다.
내쫒으려는 대상 페이지의 참조 비트가 1일 경우 당장 내쫒지 않고 참조 비트를 0으로 만든 뒤, 현재 시간을 적재시간으로 수정한다.
CPU가 접근한 적이 있을 경우 한 번의 기회를 더 주는 셈
메모리에 가장 오래 머무른 페이지의 참조 비트가 0일 경우 오래되었으면서 사용되지 않은 페이지므로 교체대상이 된다.

최적 페이지 교체 알고리즘

CPU에 의해 참조되는 횟수를 고려
메모리에 오래 남아야할 페이지는 자주 사용될 페이지
메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
앞으로의 사용 빈도가 가장 낮을 페이지를 교체하는 알고리즘

FIFO 페이지 교체 알고리즘 보타 페이지 폴트가 적어졌다
가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
실제 구현이 어렵다 ➡️ 사용되지 않을 페이지를 예측하는 일 🤯
다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주

LRU(Least-Recently-Used) 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 예측의 어려움으로 구현이 어렵지만
LRU 페이지 교체 알고리즘은 ‘가장 오래 사용되지 않은 페이지’를 교체하는 것으로 구현이 가능하다.
최근 사용되지 않은 페이지는 앞으로도 사용되지 않지 않을까? 라는 아이디어에서 출발한다.

기타 페이지 교체 알고리즘

LRU 페이지 교체 알고리즘의 파생 알고리즘들이 존재한다.

스레싱

페이지 폴트가 자주 발생하는 이유는 근본적으로 ‘프로세스가 사용할 수 있는 프레임 자체가 적어서’ 이다.
결국 프레임이 부족하면 페이지 폴트가 자주 발생하고 결과적으로 CPU의 이용률이 떨어진다.
프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률이 저해되는 문제)를 스레싱이라 한다.
동시 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 높아지는 것이 아니다. (스레싱 발생)

스레싱이 발생하는 근본적인 이유로는 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적적한 프레임을 할당해주어야 한다.

균등 할당(equal allocation)

가장 단순한 할당 방식
모든 프로세스들에게 균등하게 프레임을 할당하는 방식
프로세스별 크기가 다르기 때문에 합리적이지 않다.

비례 할당(proportional allocation)

프로세스의 크기를 고려한 할당 방식
프로세스의 크기에 비례하여 프레임을 할당한다.
프로세스의 크기와 요구되는 프레임 수는 일치하지 않기 때문에 결국 실행해봐야 필요한 프레임 수를 알게 된다.

✅ 정적 할당 방식 : 프로세스의 실행과정을 고려하지 않고 프로세스의 크기나 물리 메모리의 크기 같은 고정된 값을 이용한 할당 방식 (균등 할당, 비례 할당)

작업 집합 모델

프로세스가 실행하는 과정에서 배분할 프레임을 결정
스레싱이 발생하는 이유가 빈번한 페이지 교체 때문이니 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하는 아이디어

작업 집합

프로세스가 참조한 페이지
시간 간격

페이지 폴트 빈도 기반 프레임 할당

프로세스가 실행하는 과정에서 배분할 프레임 결정
두 개의 가정에서 생겨난 아이디어
1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
2. 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
페이지 폴트율에 대해 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

✅ 동적 할당 방식 : 프로세스가 실행하는 과정을 통해서 프레임을 할당하는 방식 (작업 집합 모델, 페이지 폴트 빈도 기반 프레임 할당)

1️⃣5️⃣ 파일 시스템

15-1 파일과 디렉터리

파일 시스템(file system)

파일과 디렉터리를 관리하는 운영체제 내의 프로그램
파일과 디렉터리를 다루어 주는 프로그램
한 컴퓨터 내에 여러 파일 시스템을 이용할 수도 있다.

파일과 디렉터리

보조기억장치의 데이터 덩어리

파일

보조기억장치에 저장된 관련 정보의 집합
의미 있고 관련 있는 정보를 모은 논리적 단위
파일을 이루는 정보 = 파일을 실행하기 위한 정보 + 부가 정보(= 속성, 메타 데이터)

파일의 속성

유형 : 운영체제가 인식하는 파일의 종류, 파일 유형을 알리기 위해 가장 흔히 사용하는 방식이 파일 이름 뒤에 붙는 확장자

파일 연산을 위한 시스템 호출

파일을 다루는 모든 작업은 운영체제에 의해 이뤄진다.
파일을 다루기 위해 운영체제는 파일 연산을 위한 시스템 호출을 제공한다.

파일 생성
파일 삭제
파일 열기
파일 닫기
파일 읽기
파일 쓰기

디렉터리

윈도우에서는 폴더(folder)라고 부른다.
과거 운영체제에서는 하나의 디렉터리만 존재 : 1단계 디렉터리
최근 운영체제는 대부분 여러 계층으로 파일 및 폴더를 관리하는 트리 구조 디렉터리 - 최상위 디렉터리(루트 디렉터리, /), 서브 디렉터리가 존재한다.

경로

디렉터리를 이용해서 파일/디렉터리의 위치, 나아가 이름까지 특정 지을 수 있는 정보
절대 경로와 상대 경로가 존재
절대 경로 : 루트 디렉터리에서 자기 자신까지 이르는 고유한 경로
상대 경로 : 현재 디렉터리부터 자기 자신까지 이르는 경로

✅ 같은 디렉터리에는 동일한 이름의 파일이 존재할 수 없지만, 서로 다른 디렉터리에는 동일한 이름의 파일이 존재할 수 있다.

디렉터리 엔트리

사실 많은 운영체제에서는 디렉터리를 그저 ‘특별한 형태의 파일’로 간주한다.
디렉터리는 그저 ‘포함된 정보가 조금 특별한 파일’이다.
파일의 내부에는 파일과 관련된 정보들이 있다면,
디렉터리의 내부에는 해당 디렉터리에 담겨 있는 대상과 관련된 정보들이 담겨 있다. (보통 테이블 형태로 구성)
디렉터리 엔트리에 담기는 정보는 디렉터리에 포함된 대상의 이름, 그 대상이 보조기억장치 내에 저장된 위치(를 유추할 수 있는 정보)가 있다.

디렉터리 엔트리에 파일 속성을 명시하는 경우도 있다.

15-2 파일 시스템

파티셔닝(partitioning)

저장 장치의 논리적인 영역을 구획하는 작업
파티셔닝 작업을 통해 나누어진 영역 하나하나를 파티션(partition)이라 한다.

포매팅(formatting)

저장 장치를 삭제하는 것 ➡️ 정확한 표현이 아님
파일 시스템을 설정하여 어떤 방식으로 파일을 관리할지 결정, 새로운 데이터를 쓸 준비하는 작업
USB 포매팅시 파일 시스템을 골라 포매팅 한다. 즉 파일 시스템은 포매팅할 때 결정된다.
파일 시스템에는 여러 종류가 있고, 파티션마다 다른 파일 시스템을 설정할 수도 있다.

✅ 포매팅까지 완료하여 파일 시스템을 설정하였다면, 파일과 디렉터리 생성이 가능해진다.

파일 할당 방법

포매팅까지 끝난 하드 디스크에 파일 저장하기
운영체제는 파일/디렉터리를 블록 단위로 읽고 쓴다.
하나의 파일이 보조기억장치에 저장될 때에는 여러 블록에 걸쳐 저장된다.
파일을 보조기억장치에 할당하는 두 가지 방법 : 연속 할당, 불연속 할당
불연속 할당은 연결 할당과 색인 할당으로 나누어진다.

✅ 하드 디스크의 가장 작은 저장 단위는 섹터이지만 보통 블록 단위로 읽고 쓴다.

연속 할당

이름 그대로 보조기억장치 내 연속적인 블록에 파일 할당
연속된 파일에 접근하기 위해 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다.
디렉터리 엔트리 : 파일 이름 & 첫번째 블록 주소 & 블록 단위 길이 명시

구현이 단순하다는 장점이 있지만 외부 단편화를 야기할 수 있다.

불연속 할당 - 연결 할당

각 블록의 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당
파일을 이루는 데이터 블록을 연결 리스트로 관리
불연속 할당의 일종 : 파일이 여러 블록에 흩어져 저장되어도 무방
디렉터리 엔트리 : 파일 이름 & 첫번째 블록 주소 & 블록 단위의 길이

외부 단편화 문제를 해결하지만 단점이 존재
1. 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 한다. 즉 임의접근 속도가 느리다.
2. 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없다.

불연속 할당 - 색인 할당

파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아 관리하는 방식
파일 내 임의의 위치에 접근하기 용이하다.
디렉터리 엔트리 : 파일 이름 & 색인 블록 주소

FAT 파일 시스템

연결 할당 기반 파일 시스템
연결 할당의 단점을 보완한 파일 시스템이다.
파일 할당 테이블(FAT, File Allocation Table)에 각 블록에 포함된 다음 블록 주소를 한데 모아 관리한다.
FAT가 메모리에 캐시될 수 있기 때문에 캐시될 경우 느린 임의 접근 속도를 개선할 수 있다.
디렉터리 엔트리에는 파일의 속성까지 같이 명시된다.

유닉스 파일 시스템

색인 할당 기반 파일 시스템
색인 블록을 i-node 라고 부른다.
i-node 에는 파일 속성 정보와 열다섯 개의 블록 주소가 저장될 수 있다.
i-node의 크기보다 큰 블록의 파일을 저장하기 위해서 유닉스 파일 시스템은 다음과 같이 해결한다.
1. 블록 주소 중 열두 개에는 직접 블록 주소를 저장한다. (직접 블록 : 파일 데이터가 저장된 블록)
2. 1번으로 충분하지 않다면 13번째 주소에 단일 간접 블록 주소를 저장한다. (단일 간접 블록 : 파일 데이터를 저장한 블록 주소가 저장된 블록)
3. 2번으로 충분하지 않다면 14번째 주소에 이중 간접 블록 주소를 저장한다. (이중 간접 블록 : 단일 간접 블록들의 주소를 저장하는 블록)
4. 3번으로 충분하지 않다면 15번째 주소에 삼중 간접 블록 주소 저장 (삼중 간접 블록 : 이중 간접 블록들의 주소를 저장하는 블록)

'혼공컴운' 카테고리의 다른 글

혼자 공부하는 컴퓨터 구조+운영체제 5주차 (12~13) (0)	2023.02.12
혼자 공부하는 컴퓨터 구조+운영체제 4주차 (9~11) (0)	2023.02.05
혼자 공부하는 컴퓨터 구조+운영체제 3주차 (6~8) (0)	2023.01.24
혼자 공부하는 컴퓨터 구조+운영체제 2주차 (4~5) (0)	2023.01.15
혼자 공부하는 컴퓨터 구조+운영체제 1주차 (1~3) (0)	2023.01.08

고밍고밍의 연습장