💁🏻♂️ 면접을 위한 컴퓨터공학 개념 정리 - [운영체제] 편
🧑🏻💻 공부 자료
1. 운영체제 공룡책 (전공서)
2. 혼공컴운(강민철)
3. 운영체제와 정보기술의 원리(반효경)
4. 깃허브 + 구글링
운영체제 개요
운영체제란
운영체제란 컴퓨터 전체를 진두지휘하는 핵심 프로그램을 말한다.
구체적으로 어떤걸 지휘하느냐. 프로그램들에게 CPU를 어떻게 할당할 것인지 (CPU 스케줄링), 메모리는 어떻게 할당할 것인지 (메모리 관리), 프로세스는 어떻게 실행할 것인지 (프로세스 관리), 파일은 어떻게 관리할 것인지 (파일 관리), 입출력 장치는 어떻게 활용할 것인지 (입출력 관리) 등의 역할을한다.
다시 말해, 실행할 프로그램에 필요한 자원을 할당하고, 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램이 운영체제다.
운영체제는 특별한 프로그램이기 때문에 메모리에서 커널 영역이라는 곳에 따로 적재되어 실행된다. 나머지 프로그램들은 사용자 영역에 적재된다.
UNIX, LINUX, POSIX
유닉스(UNIX) 운영체제는 1969년 벨 연구소에서 최초로 개발된 것으로 이식성(portability)이 좋고, 운영체제 커널의 크기가 작으며, 소스 코드가 공개되었다는 특징이 있다. 유닉스의 등장으로 많은 운영체제들이 영향을 받았다.
리눅스(LINUX) 운영체제는 UNIX의 영향을 받은 Linus(리누스) 라는 사람이 만든 것이다. 이 또한 소스가 공개되었다.
POSIX 는 유닉스 운영체제에 기반을 두는 운영체제 인터페이스다. 리눅스도 POSIX를 준수했다고 볼 수 있다.
macOS, iOS
애플의 macOS 와 iOS 도 유닉스 기반이며, POSIX 규격을 지킨 공식 인증을 받은 운영체제다.
커널 (kernel)
커널 : 운영체제에서 메모리에 올라와 있는 부분, 운영체제의 핵심 부분.
운영체제가 제공하는 모든 부분이 커널은 아니다. 예를들어 GUI 나 CLI 는 커널에 속한 기능은 아니다.
쉘 (shell)
쉘 : 커널과 사용자 프로그램 간에 대화를 가능하게 해주는 명령어 해석기 프로그램.
사용자 프로그램에서 실행시킨 명령어를 해석하여 그 결과를 커널로 보내주는 역할.
쉘의 종류는 다양하나, 리눅스에서는 주로 bash(Bourne-Again Shell)을 사용.
이중 모드와 시스템 콜
운영체제는 프로그램들이 자원에 접근하려고 할 때 오직 자신을 통해서만 접근할 수 있도록 자원을 보호한다.
이 자원의 보호를 이중 모드를 통해 수행한다.
이중 모드 (dual mode)
CPU의 명령어 실행 모드는 2가지로 나눌 수 있다.
- 커널 모드 : 운영체제가 지원하는 함수를 실행할 수 있는 명령어 실행 모드
- 유저 모드 : 운영체제가 지원하는 함수를 실행할 수 없는 명령어 실행 모드
운영체제가 지원하는 함수는 예를들어 fork(), exit(), open(), 하드웨어 접근 메서드 등.
시스템 콜 (system call)
프로그램 실행 중 유저 모드에서 커널 모드로 전환해서 서비스를 요청하는 것.
프로그램이 무언가 하기 위해서 운영체제(system)를 부르는 것(call)이다.
시스템 콜은 소프트웨어 인터럽트의 일종이다.
모든 프로그램은 자신의 독자적인 주소 공간을 가지고 있으며, 프로그램이 함수 호출을 하는 경우, 자신의 주소 공간 내에서 호출이 이루어진다.
하지만 시스템 콜은 자신의 주소 공간을 거스르는 영역에 존재하는 함수(시스템 함수)를 호출하는 것을 말한다.
(= 커널 영역의 코드를 실행하는 것을 말한다)
좀 더 구체적으로 정리하자면,
일반적인 함수 호출은 프로그램 자신의 스택 영역을 사용하는 것임에 비해, 시스템 콜은 커널 영역의 함수 위치로 점프를 하는 방식이다. 그 방식은 바로 인터럽트다. 인터럽트 서비스 루틴 또한 커널 영역에 존재한다.
C언어의 printf(), scanf() 도 내부적으로 시스템 콜을 통해 실행된다.
프로그램에서 시스템 콜을 통해 디스크 파일 입출력이 이루어지는 과정
1) 사용자 프로그램이 유저모드로 CPU 명령을 수행중에 디스크 파일을 읽어와야 하는 경우가 생겼다.
2) 시스템 콜로 커널의 파일 입출력 함수를 호출한다.
3) CPU 는 명령어 사이클을 돌다가 시스템 콜 인터럽트를 발견한다.
4) 플래그 레지스터 내의 인터럽트 플래그 값이 1이라면 인터럽트를 허용한다.
5) CPU의 제어권이 사용자 프로그램에서 운영체제에게 넘겨진다. 프로그램을 멈춘다.
6) 입출력에 맞는 인터럽트 서비스 루틴을 실행한다.
7) 입출력 작업이 끝난 경우 디스크 컨트롤러가 CPU에게 입출력 완료 인터럽트를 보낸다.
8) 완료된 결과를 가지고 다시 멈췄던 프로그램의 다음 명령어부터 수행한다.
프로세스와 스레드
프로세스와 스레드는 모두 작업의 흐름이다.
실행중인 프로그램을 프로세스라고 하고,
프로세스 안에 포함되는 더 작은 단위의 작업 흐름을 스레드라고 한다.
프로세스
실행중인 프로그램을 프로세스라고 한다.
프로세스 특징
1) 기본적으로 프로세스 당 최소 1개의 스레드 (메인 스레드)를 가지고 있다.
2) 각 프로세스는 별도의 주소에서 실행되며 서로 관여하지 않는다.
3) 프로세스끼리 소통을 하려면 IPC 등을 사용해야한다.
4) 코드 / 데이터 / 힙 / 스택 영역을 갖는다.
포그라운드 프로세스 : 사용자가 보는 앞에서 실행되는 프로세스
백그라운드 프로세스 : 사용자가 보지 못하는 뒤편에서 실행되는 프로세스.
백그라운드 프로세스 중, 사용자와 상호작용하지 않고 묵묵히 정해진 일을 수행하는 프로세스를
유닉스 체계의 운영체제에서는 데몬, 윈도우 운영체제에서는 서비스라고 부른다.
PCB
Process Control Block. 프로세스 제어 블록.
운영체제가 프로세스를 다루기 위한 정보들이 담긴 자료구조. 커널 영역에 생성된다.
커널 영역에 생성되는 이유를 생각해보면 당연하다. PCB 는 운영체제를 위해 존재하기 때문에 유저 영역에 생성될 이유가 없다.
PCB의 정보
- PID (Process 고유 ID)
- 레지스터 값 (PC)
- 프로세스 상태
- CPU 스케줄링 정보 (우선순위)
- 메모리 관련 정보
- 베이스 레지스터
- 한계 레지스터
- 페이지 테이블 정보
- TCB (Thread Control Block) 리스트
Context Switch
문맥 교환 : 프로세스 A의 CPU 제어권이 프로세스 B의 CPU 제어권으로 이동하는 것을 말한다.
하나의 프로세스 수행하기 위해 필요한 정보를 문맥 (Context) 라고 한다.
다시 말해, 프로세스 A가 CPU를 사용하며 실행하다가 문맥을 A의 PCB 에 백업해두고, CPU 사용권을 B에게 넘겨 B의 PCB를 불러와서 실행하게 되는 것을 말한다.
심화 1)
같은 프로세스 내의 스레드끼리도 Context Switch가 일어날 수 있다.
그 경우에는 TCB 만 백업해줘도 된다. 이에 대한 내용은 밑에서 다시 정리한다.
심화 2)
Context Switching 시에 프로세스가 바뀌는 것이기 때문에, PCB만 교체되는 것이아니라, TLB의 교체도 일어난다.
Translation Look-aside Buffer(페이지 테이블의 캐시)에 대한 내용은 밑에서 다시 정리한다.
프로세스의 메모리 영역
PCB는 커널영역에 적재되어있는 자료구조다.
그렇다면 프로세스가 사용자 영역에는 어떤 식으로 저장이 되는가.
크게, 코드 / 데이터 / 힙 / 스택 영역으로 나뉜다.
코드 영역
실행할 수 있는 코드, 기계어로 이루어진 명령어 저장
CPU가 실행할 명령어가 담기기에 쓰기가 금지된 구역 (Read-Only)
데이터 영역
전역 변수나 static 변수가 저장되는 영역.
보통 잠깐 썼다가 없앨 데이터가 아닌, 프로그램이 실행되는동안 유지할 데이터를 담는다.
크기가 고정 되어있다.
-코드 영역과 데이터 영역은 크기가 고정되어있다. 그래서 정적 할당 영역이라고도 부른다.
힙 영역
프로그램을 만드는 사용자, 개발자가 직접 할당 할 수 있는 저장 영역.
힙 영역에 메모리 공간을 할당했다면, 언젠가는 해당 공간을 반환을 해야한다.
이 메모리 관리를 제대로 못하면 메모리 누수가 발생할 수 있다.
이를 JVM 에서 편하게 관리해주기도 한다.
스택
매개 변수, 지역 변수가 저장되는 영역.
일반적으로 잠깐 쓰다가 말 데이터들을 저장하는 영역이다.
-코드 영역과 데이터 영역은 크기가 가변적이다. 그래서 동적 할당 영역이라고도 부른다.
-전역 변수 vs 정적 변수
1) (전역 변수의 scope) > (정적 변수의 scope)
2) 초기화 하지 않은 static 변수는 직접 사용하기 전까지 메모리에 올라오지 않는다.
프로세스 상태
생성 (new) : 메모리에 막 적재되어 PCB 를 생성한 상태
준비 (ready) : CPU를 할당받기를 기다리고 있는 상태.
실행 (run) : CPU를 할당받아 실행되고 있는 상태. 실행상태로 바뀌는 과정을 디스패치라고 한다.
할당된 시간을 모두 사용 시 (타이머 인터럽트 발생 시) 준비 상태로 돌아간다.
실행 도중 입출력 장치를 사용하게 되면 입출력 완료 인터럽트를 받을때까지 대기 상태가 된다.
대기 (waiting) : 입출력장치를 사용하는 상태. 끝나면 ready 상태로 간다.
종료 (terminated) : 프로세스 종료. PCB 제거, 메모리에서 제거.
프로세스 계층 구조
윈도우는 프로세스 계층 구조를 사용하지 않지만, macOS, UNIX 는 프로세스를 계층적으로 관리한다.
부모 프로세스
새 프로세스를 생성시켜준 프로세스
자식 프로세스
부모 프로세스에 의해 생성된 프로세스
최초의 프로세스
모든 프로세스 중 가장 위에 있는 프로세스. PID가 1번이다.
최초의 프로세스 예시
macOS : launched
Linux : systemd
Unix : init
프로세스 생성 기법 (macOS의 생성 기법)
1) fork() : 부모 프로세스를 똑같이 복제한다. (PID 값은 다르다)
2) exec() : 새로운 값을 덮어씌운다.
IPC 개념
Inter Process Communication. 프로세스 끼리의 의사소통.
프로세스는 서로 독립적으로 수행되기 때문에 프로세스끼리 데이터를 공유하기 위해서는 IPC라는 데이터 공유 기법을 사용해야한다.
IPC에는 기본적으로 두 가지 모델이 있다.
1) 공유 메모리 (shared memory)
프로세스끼리 공유하는 메모리 영역을 구축하고 데이터를 공유한다.
공유 메모리 영역을 구축할때만 system call이 필요하고, 공유 영역이 구축된 후의 모든 접근은 일반적인 메모리 접근으로 취급되어 커널의 도움이 필요없다.
메모리를 공유하는 것이기 때문에 동기화 작업이 필요하다.
2) 메시지 전달 (message passing)
메시지를 통해서 프로세스끼리 데이터를 교환한다.
동기화 작업이 필요가 없기 때문에 적은 양의 데이터를 교환하는데 유용하다.
메시지 전달은 통상 system call을 사용해서 구현되므로 커널의 간섭 등의 부가적인 시간 소비 작업이 필요하기 때문에, 일반적으로 공유 메모리 모델이 메시지 전달 모델보다 빠르다.
IPC 예시
메시지 전달 기법들이기 때문에 모두 커널을 사용한다.
1) 파이프 (Pipe)
- 두 개의 프로세스를 파이프로 연결해서 한쪽은 데이터를 쓰기만 하고 한쪽은 데이터를 읽기만 한다.
- 1:1 통신이며, 단방향 통신이다.
- 부모-자식 관계를 이룬다.
2) 메시지 큐 (message queue)
- FIFO 자료구조의 큐를 이용해서 메시지를 통해 데이터를 전달한다.
- 파이프는 스트림으로 동작한다면 메시지 큐는 메시지(패킷) 라는 단위로 데이터를 전달한다.
- 양방향 통신이 가능하며 1:1이 아니다. 부모-자식 관계가 아니다.
3) 소켓 (socket)
- 네트워크 상에서 통신하기 위한 기법. 프로세스끼리 소켓 통신하여 IPC 로 사용할 수 있다.
- 같은 컴퓨터가 아닌 다른 컴퓨터의 프로세스끼리도 소통할 수 있다.
- 다른 IPC에 비해 Local이 아닌 Remote로 통신할 수 있다는 특징이 있다.
- 포트번호를 이용해서 통신하려는 상대 프로세스의 소켓을 찾아간다.
스레드
스레드 = 실행의 단위. 프로세스를 구성하는 실행의 단위. CPU 이용의 기본 단위.
스레드는 스레드 ID, 프로그램 카운터 (PC), 레지스터 셋, 스택으로 구성된다.
스레드 특징
1) 스레드는 프로세스 내에서 스택 영역만 따로 할당 받고, 코드 / 데이터 / 힙 영역은 공유한다.
2) 한 프로세스 내의 스레드들은 서로 소통할 수 있다.
3) 별도의 레지스터와 스택을 갖는다.
유저 스레드, 커널 스레드
스레드에는 user level thread 와 kernel level thread 가 있다.
위에서 이야기한 스레드는 유저 프로그램 안에서 생성되는 유저 레벨 스레드다.
#include thread 해서 사용하는 그 스레드.
커널도 프로그램이기 때문에 스레드를 사용한다. 커널 내의 스레드를 커널 레벨 스레드라고 한다.
Window, macOS, Linux 등 현대 운영체제는 모두 커널 스레드를 사용한다.
유저 스레드 특징
-커널 스레드에 비해 오버헤드가 작다.
-동일 프로세스 내 어떤 스레드가 waiting 상태가 된다면 모든 스레드가 멈춘다.
생각해보면 당연한 것이 waiting 상태가 되면 그 프로세스가 멈추기 때문이다.
커널 스레드 특징
-커널이 스레드와 관련된 모든 작업을 관리한다.
-유저 스레드에 비해 오버헤드가 크다.
-동일 프로세스 내 다르 스레드가 waiting 상태가 되더라도 다른 스레드 실행 가능하다.
유저 스레드 - 커널 스레드 매핑
하나의 프로세스는 적어도 하나의 커널 스레드를 가지게 된다.
결국 커널 스레드와 유저 스레드는 어떠한 관계를 맺어야 한다.
이 관계 모델을 다중 스레드 모델이라 하고, 다음과 같은 모델들이 있다.
다대일 / 일대일 / 다대다 모델
TCB
Process Control Block 이 있는 것처럼, Thread Control Block 이 있다.
PCB 는 커널 영역에 생성된다고 했었다.
유저 스레드 TCB는 프로세스 메모리 영역 내부에 생성되고,
커널 스레드 TCB는 커널 영역에 생성된다.
PCB 에서 TCB 리스트를 가리키고, TCB 에서 PCB 를 가리키게 된다.
TCB 저장 정보 : 스레드 ID, 스레드 상태, PCB 포인터, 스케줄링 정보 등.
스레드에서의 Context Switch
보통 TCB는 커널 레벨에서 Context Switch 의 기본 단위가 된다.
같은 프로세스 내의 스위칭에 대해서는 TCB 정보만 저장해도 된다.
하지만 다른 프로세스 간의 스위칭을 할때는 PCB / TCB 정보를 모두 저장해야 한다.
CPU 스케줄링
CPU 스케줄링 : CPU를 할당받고 싶은 프로세스들에게 효율적으로 CPU 자원을 분배하는 방식
I/O bound, CPU bound
프로세스에서 I/O 작업을 하는 것을 I/O burst, CPU 를 이용하는 작업을 CPU burst 라고 한다.
I/O burst 의 비율이 높은 프로세스를 I/O bound process,
CPU burst 의 비율이 높은 프로세스를 CPU bound process 라고 한다.
일반적으로는 I/O bound process 가 CPU bound process 보다 우선순위가 높게 처리되는데, 그 이유는 다음과 같다.
어차피 I/O bound process 는 CPU 를 잠깐만 사용하고 waiting 상태로 접어들거기 때문에, 빨리 CPU 를 할당 시켜줘버리고 다른 프로세스를 처리하는 게 효율적이기 때문이다.
프로세스의 우선순위는 PCB 에 저장된다.
선점형 스케줄링, 비선점형 스케줄링
선점형 스케줄링 (preemptive scheduling)
어떤 프로세스가 CPU를 사용하고 있을 때, 다른 프로세스가 그 사용을 빼앗을 수 있다.
-한 프로세스의 CPU 독점을 막을 수 있다.
-context switch 에 대한 오버헤드가 크다.
비선점형 스케줄링 (non-preemptive scheduling)
어떤 프로세스가 CPU를 사용하고 있을 때, 다른 프로세스가 그 사용을 빼앗을 수 없다.
-한 프로세스가 CPU를 독점할 가능성이 생긴다.
-context switch 에 대한 오버헤드가 작다.
CPU 스케줄러, 디스패처
운영체제에서 CPU 스케줄링 알고리즘이 적혀있는 코드를 CPU 스케줄러라고 한다.
CPU 스케줄러가 어떤 프로세스에게 CPU를 할당시켜줄 것인지 결정하고 나면,
새롭게 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다.
이와 같이 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환결설정을 하는 운영체제의 코드를 디스패처라고 한다. 문맥 교환을 위한 코드.
디스패처는 현재 수행 중이던 프로세스의 context 를 PCB에 저장하고, 새로운 프로세스의 context 를 PCB로부터 복원 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
CPU 스케줄링 알고리즘
프로세스들에 어떤 방식으로 CPU를 할당시켜줄 것인지에 대한 알고리즘.
FCFS
선입선처리 스케줄링 (First Come First Served).
Ready Queue 에 먼저 들어온 프로세스 부터 처리해준다.
Convoy Effect (호위 효과) 를 발생시킬 수 있다.
(Convoy Effect) : 만약 실행시간이 10초가 걸리는 프로세스 A, 1초가 걸리는 프로세스 B가 순서대로 레디큐에 삽입 되었다면 B는 단 1초를 실행하기 위해서 10초를 기다려야 한다. 이런 상황을 호위효과라고 한다.
SJF
최단 작업 우선 스케줄링 (Shortest Job First).
CPU 사용 시간이 짧은 순으로 프로세스를 처리한다.
이론적으로 효율이 좋지만 어떤 프로세스가 얼마나 사용될지 예측하기 어렵다.
Round Robin
FCFS 스케줄링에 타임 퀀텀 (타임 슬라이스)라는 개념을 추가한 스케줄링.
FCFS로 프로세스를 처리하되, 최대 정해진 타임 퀀텀 시간 만큼만 CPU를 할당해준다.
타임 퀀텀 이상으로 CPU가 필요할 경우 남은 작업을 레디 큐의 뒤로 삽입한다.
타임 퀀텀이 너무 작다면 Context Switch 오버헤드를 야기할 수 있고,
타임 퀀텀이 너무 크다면 FCFS와 다를바가 없어져 Convoy Effect를 야기할 수 있다.
Priority
우선순위 스케줄링. 프로세스들에 우선순위를 부여하고, 우선순위 대로 CPU를 할당한다.
다만, 우선순위가 너무 낮은 프로세스는 우선순위가 높은 프로세스들에 가려져 영영 실행이 안되는 경우가 생길 수도 있다. 이를 기아 현상 (starvation)이라고 한다.
그래서 이를 방지하기위해 에이징 (aging) 기법을 사용할 수 있는데, 레디 큐에 들어온지 오래된 프로세스들은 나이를 먹어 우선순위를 높여주는 기법이다.
Multi Level Queue
멀티 레벨 큐 스케줄링. 우선순위 스케줄링의 발전된 형태로, 우선순위별로 레디 큐를 여러 개 두는 방식이다. 큐별로 다른 스케줄링 알고리즘을 사용할 수 있고, 타임 퀀텀도 다르게 설정할 수 있다.
Multi Level Feedback Queue
멀티 레벨 피드백 큐 스케줄링. 멀티 레벨 큐의 발전된 형태다.
멀티 레벨의 큐들끼리 상호작용을 할 수 있게 한다.
처음으로 프로세스를 받아들였다면, 맨 처음엔 가장 높은 우선순위 큐에 삽입되고 타임 퀀텀동안 실행된다. 그러다가 타임 퀀텀이 넘어가면 다음 레벨의 우선순위 큐로 이동된다. 또 넘어가면 다음 큐로 이동된다.
그리고 낮은 우선순위 큐에서 너무 오래 기다리게 된다면 에이징에 의해 우선순위가 다시 높아진다.
이런 방식으로 진행하다보면 CPU를 오래 사용하는 프로세스들은 자동으로 우선순위가 낮아지고, CPU를 적게 사용하는 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝난다.
즉, 멀티 레벨 피드백 큐는 어떤 프로세스의 CPU 이용 시간이 길다면 낮은 우선순위로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위로 이동시킬 수 있는 알고리즘이다.
프로세스 동기화
동기화의 의미
프로세스 동기화란 다음 두 가지를 의미한다.
1) 프로세스가 올바른 실행 순서로 실행되는 것 (실행 순서의 동기화) (순서 제어)
2) Race Condition 이 일어나지 않도록 하는 것 (메모리의 동기화) (공유자원 제어)
Critical Section
임계구역. 프로세스 A와 프로세스 B가 자원을 공유할 때, 동시에 수행되서는 안되는 코드 부분.
Race Condition
경쟁 상태. 임계구역에 동시에 두 개 이상의 프로세스가 침범해서, 예상치 못한 엉뚱한 결과를 낳는 문제.
일반적으로 말하는 동기화 문제다.
Mutex
뮤텍스 : 동기화 문제를 해결하기 위한 대표적 기법 중 하나.
어떤 프로세스가 공유 자원을 사용하게 된다면 공유자원에 lock을 걸어두고, lock이 걸려 있는 동안은 다른 프로세스가 접근 못하게 막는다. 공유 자원의 사용이 끝나면 lock을 해제한다.
뮤텍스의 함수
acquire() : lock이 걸려있지 않다면 공유자원을 획득하고, lock이 걸려있다면 무한 루프를 돌면서 대기한다. 이때 무한정 대기하는 것을 busy waiting 이라고 한다.
release() : 프로세스가 공유자원을 사용한 작업을 마치면, 공유자원에서 빠져나오면서 lock을 unlock 해제한다.
Semaphore
세마포어 : 동기화 문제를 해결하기 위한 대표적 기법 중 하나. 뮤텍스보다 일반화된 방안.
뮤텍스는 공유자원에 접근할 수 있는 프로세스가 단 한개였지만 세마포어는 1개 이상 접근할 수 있다. S라는 정수형 변수만큼 접근을 할 수 있다.
세마포어의 함수
wait() : S > 0 이라면 공유자원을 획득하고 S 값을 1 감소시킨다. S <= 0 이라면 S 값이 0이 될때까지 대기한다. 이때 세마포어는 busy waiting을 하지않고, 그 프로세스의 PCB를 세마포어를 위한 waiting 큐에 삽입한다.
signal() : 프로세스가 공유자원을 사용한 작업을 마치면, 공유자원에서 빠져나오면서 S 값을 1 증가시킨다. 그리고 세마포어 waiting 큐에서 pop을 수행하고 ready 큐로 옮겨준다.
Monitor
모니터 : 동기화 문제를 해결하기 위한 대표적 기법 중 하나. 사용자에게 편리함에 초점을 맞춤.
뮤텍스와 세마포어는 적절하게 함수를 사용해야 하기 때문에 휴먼 에러를 야기할 수 있었다.
모니터는 고급언어에서 제공하는 동기화 해결기법이다.
예를들어 Java의 synchronized 키워드가 있다. 그래서 wait 이나 signal 같은 함수 작성을 해주지 않고 synchronized 키워드만 붙여주면 된다.
모니터 안에는 한 개의 프로세스만 들어갈 수 있고, 모니터에 들어가기 전에는 큐에 삽입이 된다.
Spin lock
스핀 락 : 동기화 해결기법 중 하나. 이름 그대로 누군가 공유자원을 이미 소유하고 있을 때 lock 이 반환될 때까지 빙빙 무한루프를 돌며 확인하면서 기다리는 방법. (= busy waiting)
뮤텍스와 상당히 비슷한데, 중요한 특징은 context switching을 하지 않는 상태로 기다린다는 것이다. 뮤텍스는 무한 루프를 돌다가 context switching이 발생하면 CPU제어권을 넘겨줬는데, 스핀 락은 그러지 않는다.
"조금만 기다리면 되는데 굳이 context switching을 해야하나?"라는 컨셉이다.
멀티코어 CPU에서 사용한다.
데드락
데드락이란
Deadlock = 교착상태. 2개 이상의 프로세스가 서로 공유자원을 할당받기를 기다리고 있어서 그 누구도 일을 하지 못하는 상태.
서로 앞으로 가고싶은 자동차가 꽉막힌 도로의 비유를 많이 든다. 여기서 프로세스는 앞으로 가고싶은 자동차고, 공유자원은 도로가 된다.
식사하는 철학자 문제
Dining philosophers problem.
교착상태를 설명하기 위한 아주 고전적인 비유 상황. 철학자들이 원형 탁자에 앉아있다.
- 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
- 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
- 왼쪽 오른쪽 포크를 모두 집었을때만 식사를 시작한다.
- 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
- 오른쪽 포크를 내려놓았으면 왼쪽 포크를 내려놓는다.
5명의 철학자, 5개의 포크가 있을때, 철학자들 중 그 누구도 식사를 시작하지 못하는 상황이 발생한다.
철학자의 식사 = 프로세스 일처리
포크 = 공유자원
데드락 발생 조건
데드락이 발생하기 위해서는 다음의 4가지 조건을 모두 만족해야한다.
상점비원으로 외운다.
1. 상호 배제
포크 한 개를 철학자 둘이서 함께 사용한다면 데드락은 발생하지 않을 것이다.
한 프로세스가 사용하는 자원을 다른 프로세스가 공유해서 사용할 수 없을 때, 즉 상호 배제 상황이어야 한다.
2. 점유와 대기
철학자가 왼쪽 포크를 들고 있으며, 오른쪽 포크를 집기 위해 기다려야 한다.
한 프로세스가 자신이 쥐고 있는 공유자원을 놓치 않으며 다른 공유자원을 얻기를 기다려야한다.
3. 비선점
철학자 A가 철학자 B가 쥐고 있는 포크를 빼앗아 버린다면 데드락은 발생하지 않을 것이다.
프로세스 A가 공유자원을 점유하고 있다면 다른 프로세스 B가 그 자원을 빼앗을 수 없어야 한다.
4. 원형 대기
탁자가 원형이었기 때문에, 원하는 방향이 사이클을 돌았기 때문에 데드락이 발생했다.
즉, 서로가 서로의 자원을 원하는 원형 대기의 상황이어야 데드락이 발생한다.
데드락 해결 방법
데드락 해결방법에는 크게 예방 / 회피 / 검출 및 회복 / 무시 가 있다.
1) 예방
데드락이 발생하기 위한 4가지 조건 상/점/비/원 중 하나라도 발생하지 않도록 예방하는 것이다.
하지만 그 4가지 조건 중 하나를 제어함으로써 생기는 side effect가 많다.
예를들어 점유와 대기 조건을 예방하기 위해서는
1- 스레드가 실행을 실행하기 전에, 필요한 모든 자원을 한꺼번에 요청하고 한꺼번에 할당받는다
2- 스레드가 자원을 전혀 갖고 있지 않는 경우에만 자원을 요청할 수 있다
이러한 방안들이 있는데, 방안 1번은 프로세스 별 CPU 사용률이 극히 낮아진다는 단점이있고, 2번은 기아 상태를 야기할 수 있다는 단점이 있다.
2) 회피
데드락이 발생하지 않도록 조심해서 자원을 할당해주는 방식이다.
= 안전 상태를 유지하도록 자원을 할당하는 방식이다.
회피를 위한 대표적인 알고리즘으로 은행원 알고리즘이있다.
이는 은행원이 은행에 남아있는 돈의 양을 고려하고, 돈을 빌려줄때는 그 사람이 돈을 갚을 수 있는 능력이 있는지 고려하면서 돈을 빌려주는 원리다.
다시말해, CPU가 프로세스에게 공유 자원을 할당하기 전에는 남아있는 공유 자원의 양을 점검하고, 그 프로세스가 필요로 하는 총 자원의 양을 고려한다.
예를들어, 프로세스 A는 자원을 조금만 할당시켜줘도 바로 모든 작업을 마치고 자원을 반납할 수 있는 상황이라면 A에게 자원을 할당 시켜줄 우선순위가 올라간다.
또 예를들어, 프로세스 A, B, C, D 가 있을 때 B-C-A-D 순으로 자원을 할당시켜준다면 데드락이 발생하지 않는다는 계산 결과가 나왔다고 하자. 그렇다면 B-C-A-D를 안전 순서열이라고 한다.
데드락이 발생할 수 있는 상태를 불안정 상태, 발생하지 않는 상태를 안정 상태라고 한다.
3) 검출 및 회복
데드락이 발생할 수 있다는 것을 인정하고, 발생 후에 데드락 상태를 회복시키는 방식이다.
데드락 발생 여부를 주기적으로 검사하고, 검출되었다면 다음과 같은 방식으로 회복한다.
1- 선점을 통한 회복
2- 프로세스 강제 종료를 통한 회복
1번은 프로세스 한 곳에 자원을 몰아주고 데드락을 해결하는 방식, 2번은 모든 프로세스를 종료시켜버리는 단순 무식한 방식이다.
4) 무시
말그대로 데드락이 발생했을 때 무시해버린다. 문제 발생의 빈도나 심각성에 따라 최대 효율을 요구하는 엔지니어 입장에서는 때때로 이 방식이 적합할때도 있다.
무시를 굳이 거창하게 다른말로 타조 알고리즘이라고 하기도 한다.
메모리 관리
논리주소, 물리주소
논리주소 : 프로세스에서 논리 연산에 사용하는 주소. 실제 메모리 안의 물리적인 주소가 아닌, 가상의 주소.
물리주소 : 실제 메모리의 주소. MMU가 논리주소를 물리주소로 매핑시켜준다.
이 과정을 주소 바인딩(address binding)이라고도 한다.
(물리주소) = (논리주소) + (프로그램 베이스 레지스터)
자세한 내용은 [CS] 컴퓨터 구조 게시글에 정리해뒀다.
스와핑
프로세스 A가 있을 때, A의 전체 부분을 모두 메모리에 올리지 않고, 필요한 일부분만을 메모리에 올릴 수 있다. 그리고 나머지 부분은 보조기억장치의 스왑영역(backing store)에 둔다.
Swap Out : 메모리에서 필요없어진 부분을 스왑영역으로 내보내는 것
Swap In : 메모리에 필요한 부분을 스왑영역에서 들여오는 것
내부 단편화, 외부 단편화
내부 단편화 (internal fragmentation)
메모리 공간을 일정한 크기의 파티션으로 나눴을 때, 들어가는 프로세스가 파티션보다 작아서, 파티션의 공간이 남아 낭비되는 문제.
외부 단편화 (external fragmentation)
C라는 작업의 크기는 70MB이고, 가용공간도 100MB(50MB + 50MB)가 남아있지만, 연속적이지 않아서 메모리에 적재할 수 없는 문제. 가용공간이 불연속적이어서 메모리가 낭비되는 문제.
요약 정리
내부 단편화 = 가용공간 > 프로세스
외부 단편화 = 가용공간 < 프로세스
심화 내용
외부 단편화의 남는 공간에는 새로운 작은 프로세스를 적재할 수 있지만,
내부 단편화의 경우는 이미 그 자리에 프로세스가 할당 된 것으로 간주되기 때문에 새로운 작은 프로세스가 들어갈 수 있는 공간이 있어도 적재할 수 없다.
메모리 할당 방식
메모리 할당 방식은 크게 연속 할당 방식, 불연속 할당 방식으로 나뉜다.
연속할당방식은 하나의 프로세스에 필요한 메모리들은 반드시 연속해서 메모리공간에 위치해야한다.
불연속할당방식은 하나의 프로세스에 필요한 메모리들이 연속해서 메모리공간에 위치하지 않아도 된다.
고정 분할 방식
물리 메모리를 고정된 크기의 파티션으로 나누어 놓고, 그에 맞춰 프로세스를 적재한다.
하나의 분할에는 하나의 프로그램만을 적재할 수 있다.
연속할당 방식 중 하나.
장점
- 원리가 단순하다.
- 시스템 생성 시 미리 주기억장치가 분할되므로 운영체제 오버헤드가 줄어든다.
단점
- 외부 단편화 : 프로세스가 파티션보다 크면 Overlay 기법(프로세스의 필효나 부분만 적재)을 사용해야한다. 그만큼 오버헤드가 발생한다.
- 내부 단편화 : 파티션보다 작은 프로세스가 들어가면 남는 공간에서 내부 단편화가 발생한다.
- 낮은 융통성 : 하나의 분할에 하나의 프로그램만 적재할 수 있기 때문에, 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어있으며, 수행 가능한 프로그램의 크기도 고정되어있어서 가변분할 방식에 비해 융통성이 떨어진다.
가변 분할 방식
메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식.
연속할당 방식 중 하나.
장점
- 가변 분할 방식에서 분할의 크기를 일부러 프로그램보다 크게 설정하지는 않기 때문에 내부 단편화가 생기지는 않는다.
- 고정 분할 방식에 비해서 융통성이 있다.
단점
- 외부 단편화 : 메모리에 존재하는 프로그램이 종료된 자리에 외부 단편화가 발생한다.
- 동적 메모리 할당 문제(dynamic storage-allocation problem)를 고려해야 한다.
동적 메모리 할당 문제
메모리의 가용공간 중 어떤 위치에 프로그램을 적재할 것인지 결정하는 문제.
배치 알고리즘에 의해서 이를 해결한다.
배치 알고리즘 종류
1. 최초 적합 (first-fit)
메모리를 적재할 수 있는 가용공간을 탐색하다가, 최초로 발견한 조건에 맞는 가용 공간에 적재한다.
시간적인 측면에서 효율적이다.
2. 최적 적합 (best-fit)
가용공간을 모두 탐색한 후, 적재할 수 있는 가장 작은 가용공간에 적재한다.
매우 작은 가용공간이 생길 수 있지만 대채로 공간적인 측면에서 효율적이다. 낭비되는 가용공간을 줄인다는 매커니즘.
3. 최악 적합 (worst-fit)
가용공간을 모두 탐색한 후, 적재할 수 있는 가장 큰 가용공간에 적재한다.
나중에 적재하고 남은 가용공간에 다른 프로세스를 적재할 수 있겠다는 매커니즘.
-> 일반적으로 (최초적합, 최적적합) > (최악 적합) 으로 효율적인 것으로 알려져있다.
압축 (compaction)
가변 분할 방식에서 외부 단편화를 해결하기 위한 방법 중 하나로, 빈 가용공간들을 압축해 한 곳으로 모으는 방법.
하지만 메모리 대 이동이 일어나야 하기 때문에 오버헤드가 매우 크다.
-> 그래서 외부 단편화를 해결하기 위한 새로운 해결 방안이 등장했는데, 이것이 오늘날까지도 사용되는 페이징 기법이다.
페이징
프로세스의 논리주소 공간을 페이지라는 고정된 크기로 나누고, 물리주소 공간을 프레임이라는 같은 크기로 나눠서 페이지를 프레임에 할당하는 기법. 불연속 메모리 할당 방식이다.
현대 메모리 관리 기법 중 가장 중요한 개념 중 하나다.
가상 메모리 관리 기법 중 하나. 밑에서 다시 설명하겠지만, 프로세스 중 필요한 일부분만 메모리에 올려서 실행하는 것을 가상 메모리 기법이라고 한다.
페이징의 특징
- 외부단편화 x : 모든 주소공간들을 일정한 크기로 나누고, 불연속으로 할당할 수 있기 때문에 외부단편화가 발생하지 않는다.
- 내부단편화 o : 프로세스의 크기가 항상 페이지 크기의 배수가 될 순 없기 때문에, 마지막 페이지 공간에서 내부 단편화가 발생한다.
- 물리적으로는 불연속적이지만, cpu는 마치 연속적인 것처럼 느껴야 하는데, 이는 페이지 테이블이 있기 때문에 가능하다.
페이지 테이블
논리 주소 단위인 페이지를 물리 주소 단위인 프레임으로 매핑시켜주는 테이블.
<페이지 번호, 오프셋>을 이용 해서 물리 주소를 획득한다.
(물리 주소) = (페이지 번호로 얻은 프레임 시작 주소) + (오프셋)
모든 프로세스는 하나의 페이지 테이블을 가지며, 페이지 테이블은 물리 메모리에 적재된다.
<페이지 테이블 엔트리>
-
유효 비트
현재 해당 페이지에 접근이 가능한지 여부.
페이지가 물리 메모리에 존재하고 있으면 1, 스왑 영역에 존재하고 있으면 0.
유효비트가 0인 페이지에 접근하려는 것을 페이지 폴트 라고 한다. -
보호 비트
0 : 읽기만 가능한 페이지
1 : 읽기 쓰기 가능 페이지 -
참조 비트
CPU가 이 페이지에 접근 한 적이 있는지 여부
0 : 적재 이후 한번 도 읽거나 쓴 적 없는 페이지
1 : 적재 이후 CPU가 읽거나 쓴 페이지
심화 내용
페이징에서는 COW(Copy On Write) 가 일어난다.
프로세스에서 fork()와 exec()을 통해서 자식 프로세스를 만든다는 것을 알고 있다.
하지만 그때마다 페이징 테이블도 복사한다면 비효율적이다.
COW는 이런 상황을 해소시켜준다. 바로 새로운 페이지 테이블을 복사 생성하지 않고 있다가, 진짜로 그 페이지 테이블을 사용할 일이 생길때(write 할 일이 생길 때) 그제서야 페이지 테이블 복사본을 생성한다.
PTBR, PTLR, TLB
-
PTBR
Page Table Base Register. CPU 내의 페이지 테이블 베이스 레지스터.
페이지 테이블이 메모리에 있기 때문에 페이지 테이블의 메모리 위치를 가리키는 레지스터. -
PTLR
Page Table Length Register. 페이지 테이블의 크기를 나타내는 레지스터. -
TLB
Translation Lookaside Buffer. 페이지 테이블의 캐시 메모리.
CPU에서 페이지 테이블을 통해 물리 메모리를 접근하려면, 메모리를 2번 접근해야 한다.
1) CPU에서 메모리의 페이지 테이블 접근.
2) 페이지 테이블로 얻은 페이지, 오프셋으로 다시 한번 메모리의 프레임 접근.
이런 현상을 완화하기 위해서 TLB를 사용한다.-
TLB 히트 : 찾으려는 페이지 번호가 TLB에 있는 경우
-
TLB 미스 : 찾으려는 페이지 번호가 TLB에 없는 경우
context switching 시에 PCB 뿐만 아니라 TLB도 교체가 일어난다.
-
계층적 페이징
페이지 테이블에 계층을 두는 방법.
프로그램의 크기가 매우 클 경우, 페이지 테이블의 크기도 커져서 메모리에 차지하는 공간이 많아지게 된다.
그런 경우, 외부 페이지 테이블과 내부 페이지 테이블을 나눠서 저장한다면 메모리를 아낄 수 있다.
사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블 값을 NULL로 설정해서 메모리를 아낀다.
후에 해당 페이지 테이블을 참조해야하는 경우가 생기면 그때 메모리에 적재한다.
2단계 페이징의 경우, <p1, p2, d> 로 논리주소를 표현한다.
외부 페이지 테이블의 p1 자리에서 내부 페이지 테이블의 위치를 찾아낸다.
그리고 외부 페이지 테이블의 p2에서 프레임의 위치를 찾고, 그 프레임에서 d 만큼 떨어진 곳에서 물리 주소를 얻는다.
메모리 공간을 아낄 수 있다는 장점이 있지만, 그만큼 참조를 여러번 해야하기 때문에 시간적인 사이드 이펙트가 생긴다. 하지만 메모리 공간을 아낌으로 인해 생기는 장점이 훨씬 큰 편이다.
역페이지 테이블
(페이지 -> 프레임) 매핑이 아닌 (페이지 <- 프레임) 매핑을 하는 테이블.
위에서 메모리를 아끼기 위해 계층적 페이지를 사용했었다.
프로세스마다 페이지 테이블을 갖고 있기 때문에, 페이지 테이블들이 메모리에서 차지 하는 공간은 꽤 많다.
그래서 모든 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 대해 공용의 역페이지 테이블을 하나 두는 방법이다.
물리 주소인 프레임에 각 프로세스들의 논리 주소 페이지를 매핑 시키는 방법이다.
역페이지 테이블의 항목은 프로세스 id(pid)와 그 프로세스 내의 논리적 페이지 번호(p)를 가진다.
논리주소는 <pid, p, d> 가 들어온다.
하지만 역페이지 테이블은 주소 변환 요청이 들어왔을 때 pid와 p를 모두 만족하는 곳을 완전탐색해야 하기 때문에 시간적으로 매우 비효율적이다.
공유 페이지
여러 프로세스에 의해 공유되는 코드를 담는 페이지. (shared page)
공유 코드 : 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통적으로 사용될 수 있도록 작성된 코드.
공유 페이지는 물리 메모리에 하나만 적재되어 메모리를 효율적으로 사용할 수 있게 한다.
따라서 다른 프로세스라고 하더라도 공유 페이지의 페이지 번호는 같아야 한다.
이와 반대 되는 페이지로는 private page가 있다.
priavate 페이지는 여러 프로세스에서 공통적으로 사용되지 않는 페이지이며, 다른 프로세스의 어떠한 페이지와 번호가 같을 필요가 없다.
세그먼테이션
프로세스의 주소 공간을 의미 단위의 세그먼트로 나누어 물리 메모리에 올리는 기법.
페이징의 분할 단위인 페이지의 크기는 고정적이었다면, 세그먼트의 크기는 가변적이다.
가상 메모리 관리 기법 중 하나이고, 불연속 메모리 할당 방식이다.
세그먼트는 의미를 가질 수 있는 논리적인 단위로 나눈 것이기 떄문에 크기가 균일하지 않다.
일반적으로는 코드, 데이터, 스택 등의 기능 단위로 세그먼트를 정의한다.
세그먼테이션의 특징
- 내부 단편화 x : 고정된 크기로 분할하는 것이 아니기 때문에 내부 단편화가 발생하지 않는다.
- 보호와 공유의 기능을 수행하기 좋다. 의미있는 단위로 프로그램을 나누기 때문이다.
- 외부 단편화 o : 프로그램이 종료된 뒤 남은 자리에 외부 단편화가 발생할 수 있다.
<세그먼트 번호, 오프셋>으로 논리 주소가 이루어지고, 세그먼트 테이블을 이용해 물리 주소를 찾는다.
세그먼트 테이블
세그먼트 테이블의 각 항목은 기준점(base)과 한계점(limit)을 가지고 있다.
세그먼트 오프셋이 limit을 넘을 경우 배제시킨다.
페이지 테이블이 그랬듯이, 세그먼테이션에서도
STBR(Segment Table Base Register),
SLBR(Segment Table Length Register)가 있다.
context switching 시 세그먼트 테이블도 업데이트한다.
페이지드 세그멘테이션
페이징-세그먼테이션 혼용 기법.
먼저 세그먼테이션과 마찬가지로 프로그램을 의미 있는 단위인 세그먼트로 나눈다.
그 각각의 세그먼트들을 일정한 크기의 페이징의 집합이 되도록 한다.
가상 메모리 기법 중 하나고, 불연속 메모리 할당 기법이다.
페이징 단위로 외부 단편화 문제를 해결하고, 세그먼트 단위로 공유와 보호가 잘 이뤄지게 함으로써 페이징의 약점을 보완한다.
<세그먼트, 오프셋> 으로 논리 주소가 이뤄지고, 오프셋은 상위비트/하위비트로 나눠진다.
상위 비트 - 세그먼트 내의 페이지 번호
하위 비트 - 페이지 내의 오프셋
외부의 세그먼트 테이블, 내부의 페이징 테이블. 2개의 테이블을 사용한다.
세그먼트로 찾아가면 <세그먼트 길이, 페이지 테이블 시작 주소>가 들어있다.
그럼 다시 페이지 테이블을 참조해서 물리 주소를 찾아낸다.
가상 메모리
가상 메모리 기법 : 프로세스의 모든 부분을 메인 메모리에 올리지 않고, 실행하는 데 당장 필요한 일부분만 메인 메모리에 올린 뒤, 나머지는 보조기억장치의 스왑영역에 두는 방법.
메모리에는 일부분만 올렸지만, 마치 전체가 실행되고 있는 것처럼 느끼게 한다.
(가상 메모리 크기) = (메인 메모리 크기) + (하드 디스크 스왑영역 크기)
디맨드 페이징
프로세스를 메모리에 적재할 때 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 demand paging이라고 한다.
디맨드 페이징의 기본적인 양상
1) CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2) 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1인 경우) CPU는 페이지가 적재된 프레임에 접근한다.
3) 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0인 경우 = 스왑 영역에 있는 경우) 페이지 폴트가 발생한다.
4) 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5) 다시 1번을 수행한다.
디맨드 페이징 기법이 잘 작동되려면 다음 두 가지가 중요하다.
1. 페이지 교체
2. 프레임 할당
페이지 교체
메모리의 공간은 한정적이기 때문에, 당장에 필요한 페이지들을 메모리에 적재하기 위해서는 메모리에서 당장 불필요한 페이지들을 스왑 영역으로 내보내야 한다. 이를 페이지 교체라고 한다.
swap out : 메모리 -> 스왑 영역
swap in : 메모리 <- 스왑 영역
페이지 교체 알고리즘 : 메모리에서 어떤 페이지를 내보내야 할지 결정하는 알고리즘.
페이지 폴트 횟수를 줄일수록 좋은 알고리즘이라고 본다.
페이지 교체 알고리즘 종류
1. FIFO
2. SCR
3. Optimal
4. LRU
5. LFU
6. Clock
FIFO
First In First Out. 메모리에 먼저 들어온 페이지부터 스왑아웃시킨다.
앞으로 또 사용될 페이지가 나갈 수도 있기 때문에 비효율적이다.
SCR
Second Chance Replacement Algorithm. FIFO에서 개선된 알고리즘으로, 메모리에 먼저 들어온 페이지부터 스왑아웃 시키되, 한 번의 기회를 더 준다.
먼저 들어왔다는 이유로 일찍 내쫓으면 억울한 상황이 발생한다. 이 페이지가 언제 또 참조될 지 모르기 때문이다.
만약 이번에 나가야 할 페이지의 참조 비트가 1인 경우, 당장 내쫓지 않고 참조 비트를 0으로 반든 뒤 큐의 뒤로 다시 삽입한다. CPU가 한 번 접근한적이 있는 페이지의 경우 한번 더 참조할 가능성이 있기 때문이다.
이번에 나가야 할 페이지의 참조 비트가 0인 경우, 스왑 아웃시킨다.
Optimal
Optimal page replacement algorithm. 최적 페이지 교체 알고리즘.
이론상 가장 좋은 알고리즘으로, 앞으로 가장 적게 참조될 페이지 (사용빈도가 낮을 페이지) 를 스왑아웃 시키는 알고리즘이다.
하지만 앞으로 이 페이지가 얼마나 참조될지 정확히 아는 것은 불가능에 가까워서 이론적인 비교 대상으로 사용한다.
LRU
Least Recently Used. 사용한지 가장 오래된 페이지를 내보낸다.
메모리의 시간 지역성을 활용한 방법이다. 사용된지 오래된 페이지는 앞으로도 사용될 가능성이 없다고 판단해서 스왑 아웃 페이지의 대상으로 삼는다.
LFU
Least Frequently Used. 가장 적게 사용한 페이지를 내보낸다.
페이지 중에서 가장 참조 횟수 (reference count)가 적은 페이지를 내보낸다.
Clock
Clock Algorithm. 클락 알고리즘으로, SCR 을 원형 큐로 구현한 알고리즘이다.
기준점인 클락 핸드가 시계 방향으로 돌아가며 페이지를 가리킨다.
현재 페이지의 유효 비트가 1이라면, 유효 비트를 0으로 교체한 뒤 기회를 주고 다음 페이지로 넘어간다.
현재 페이지의 유효 비트가 0이라면, 그 페이지를 스왑 아웃 시킨다.
지역 교체, 전역 교체
지역 교체 : 페이지 교체 대상을 같은 프로세스 내에서 찾는 것
전역 교체 : 페이지 교체 대상이 같은 프로세스가 아니어도 되고, 메모리 전체 페이지에서 찾는 것
스래싱
Thrashing. 페이지 교체가 너무 자주 일어나서, 프로세스 자체의 일을 수행하는 것보다 페이지 교체를 하는 데 CPU를 더 많이 사용하는 상황.
근본적인 이유는 프로세스에 할당된 프레임 수가 적기 때문이다.
일반적으로 멀티 프로세스에서 동시에 실행하는 프로세스가 많을수록 CPU를 바쁘게 굴리는 것이기 때문에 CPU 사용률이 높아지지만, 어느 임계점을 넘어서면, 프로세스마다 할당해줄 수 있는 프레임 수 자체에 한계가 생기기 때문에 페이지 교체가 너무 많이 일어나서 CPU 사용률이 낮아진다.
스래싱을 방지하는 방법에는 워킹셋 알고리즘과 페이지 폴트 빈도 알고리즘이 있다.
프레임 할당
프로세스 A와 프로세스 B에게 같은 수의 프레임을 할당하는 것은 비효율적일 수 있다. 각 프로세스들이 효율적으로 수행되는 데 필요한 프레임의 수는 서로 다르기 때문이다.
그렇다면 어떤 프로세스에 얼만큼 프레임을 할당하는 것이 좋을까를 고민하는 것이 효율적인 메모리 할당의 핵심이다.
정적 할당 방식 - 프로세스를 실행 하기 전에 미리 프레임 수를 할당하는 방식
동적 할당 방식 - 프로세스 실행 중에 유동적으로 프레임 수를 변경하며 할당하는 방식
정적 할당 방식에는 균등 할당, 비례 할당이 있다.
균등 할당은 말그대로 모든 프로세스에 균일하게 프레임 수를 할당하는 매우 비효율적인 방식.
비례 할당은 프로세스 크기에 비례해서 프레임 수를 할당하는 방식이다. 하지만 프로세스 크기와 필요로 하는 프레임 수가 반드시 비례하지는 않기 때문에 그렇게 효율적이진 않다.
동적 할당 방식에는 워킹셋과 페이지 폴트 빈도를 사용하는 방식이 있다.
워킹셋, 페이지 폴트 빈도
워킹셋
working set = "단위 시간 동안 사용한 페이지 집합".
단위시간에 워킹셋의 수 만큼 유동적으로 프레임 수를 할당해준다.
페이지 폴트 빈도
페이지 폴트가 매우 많이 발생한다 -> 프레임 수가 부족하다 -> 프레임 수를 늘려준다.
페이지 폴트가 매우 적게 발생한다 -> 프레임 수가 넘친다 -> 프레임 수를 줄여준다.
파일 시스템
파일
파일
보조기억장치 (하드디스크 / SSD)에 저장된 관련 정보의 집합. 의미 있고 관련이 있는 정보를 모은 논리적 단위
파일 메타데이터
파일을 이루는 정보. 이름, 파일 형식, 크기, 생성 날짜 등..
파일 연산을 위한 시스템 콜
파일을 다루는 모든 작업은 커널에서 이뤄진다.
운영체제는 파일 CRUD 연산을 위한 시스템 콜을 제공한다.
디렉터리
디렉터리
파일들을 모은 파일. 디렉터리도 일종의 파일이다. 트리 구조를 이룬다.
디렉터리도 마찬가지로 커널에서 CRUD 연산 시스템 콜을 제공한다.
절대 경로와 상대 경로
절대 경로 : 루트 디렉토리부터 시작하는 경로
상대 경로 : 현재 디렉토리부터 시작하는 경로
파일 할당 방법
운영체제는 파일과 디렉터리를 블록(block) 단위로 읽고 쓴다.
파일을 보조기억장치에 할당하는 방법에는 크게 연속 할당과 불연속 할당이 있다.
연속 할당
이름 그대로 연속적인 블록에 파일을 할당하는 방식.
파일에 접근하기 위해서는 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다.
연속 할당이기 때문에 외부 단편화를 야기할 수 있다.
연결 할당
불연속 할당 중 하나. 링크드 리스트와 같은 형태로 파일을 저장한다.
블록 단위로 할당하고, 불연속적으로 파일을 할당할 수 있기 때문에 외부 단편화 문제를 해결한다.
하지만 다음 2가지의 단점이 있다.
1) 반드시 첫 번째 블록부터 차례대로 하나씩 읽어야 한다. 단일 링크드 리스트 형태이기 때문.
2) 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근 할 수가 없다.
그래서 오늘 날에는 연결 할당 방식을 조금 더 개선한 FAT 파일 시스템을 사용한다.
FAT
File Allocation Table. 연결 할당 방식이 링크드 리스트 형태로 파일 할당을 관리 했다면,
FAT 는 테이블 형태로 파일을 할당한다.
테이블에서 각 인덱스마다 다음 차례의 블록의 주소를 저장한다.
개선된 점
1) 반드시 첫 번째 블록부터 읽지 않아도 된다. 임의의 블록부터도 다음 블록을 읽어나갈 수 있다.
2) 하드웨어가 고장이 나도 해당 블록 이후 블록을 접근할 수 있다.
색인 할당
인덱스 블록이라는 핵심 블록을 둔다. 파일의 모든 블록 주소를 하나의 인덱스 블록에 모아 관리한다.
파일 내 임의의 위치에 접근하기 쉽다. 파일의 n번째 데이터 블록에 접근하고 싶다면 인덱스 블록의 n번째 항목이 가리키는 블록에 접근하면 되기 때문이다.
하지만 하나의 인덱스 블록을 가지고는 크기가 큰 파일을 저장하기가 힘들다.
색인 할당을 사용하는 파일 시스템에서는 디렉터리 엔트리에 파일 이름과 더불어 인덱스 블록 주소를 명시해준다.
색인 할당을 기반으로 만든 파일 시스템이 유닉스 파일 시스템이다.
유닉스 파일 시스템 : i-node
색인 할당 방식에서 말했던 핵심 블록(인덱스 블록)을 i-node 라고 부른다.
i-node 에는 파일 속성 정보와 15개의 블록 주소가 저장된다.
저널링 기법
Journal : 저널, 학술지, 일기.
저널링 기법이란 작업 로그를 통해 시스템 크래시가 발생했을 때 빠르게 복구하기 위한 방법.
시스템 크래시
파일 시스템에서 하드웨어 손상이나 오류 발생 시 파일 시스템이 훼손 되는 경우를 말한다.
저널링 기법을 사용하는 파일 시스템에서, 파일 시스템 작업을 하는 순서
1) 작업 직전 로그를 남긴다.
2) 로그를 남긴 후 작업을 수행한다.
3) 작업이 끝났으면 로그를 삭제한다.
작업 도중 시스템 크래시가 발생하여 다시 부팅해야 한다면 파일 시스템 전체를 검사할 필요 없이 로그 영역에 남긴 로그만 검사해도 되기 때문에 효율적이다.
마운트
한 저장 장치의 파일 시스템에서 다른 저장 장치의 파일 시스템에 접근 할 수 있도록 파일 시스템을 편입시키는 작업을 의미한다.
쉽게 말하면, USB 메모리 등 새로운 메모리가 들어올 때, 기존 디렉토리 트리 구조에서 새로운 서브 트리를 이어 붙이는 것을 말한다.
좋은 포스트 감사합니다!