1. 운영체제와 컴퓨터
1.1 운영체제의 역할과 구조
운영체제의 역할
- CPU 스케줄링과 프로세스 관리
- 메모리 관리
- 디스크 파일 관리
- I/O 디바이스 관리
운영체제의 구조
시스템콜
유저 프로그램(응용 프로그램)이 운영체제의 서비스를 받기 위해 커널 함수를 호출할 때 사용.
시스템콜을 받으면 유저 모드에서 커널 모드로 변환. 커널에 접근하여 명령 수행.
커널
운영체제의 핵심 부분.
시스템콜 인터페이스를 제공하며 보안, 메모리, 프로세스, 파일 시스템, I/O 디바이스, I/O 요청 관리 등 운영체제의 중추적인 역할
modebit
0 또는 1의 값을 가지는 플래그 변수.
시스템콜이 작동될 때 modebit을 참고해서 유저 모드와 커널 모드를 구분.
커널 모드: 0
유저 모드: 1
드라이버
하드웨어를 제어하기 위한 소프트웨어
1.2 컴퓨터의 요소
CPU
산술논리연산장치(ALU, Arithmetic Logic Unit), 제어장치(CU, Contorl Unit), 레지스터로 구성.
인터럽트에 의해 메모리에 존재하는 명령어를 해석해서 실행하는 단순 반복 장치.
산술논리연산장치
아래 기능을 수행하는 디지털 회로.
- 덧셈, 뺄셈 같은 두 숫자의 산술 연산
- 배타적 논리합, 논리곱 같은 논리 연산
제어 장치
- 입출력 장치 간 통신을 제어
- 명령어를 읽고, 해석
- 데이터 처리를 위한 순서를 결정
레지스터
CPU와 직접 연결된, CPU 내부의 매우 빠른 임시기억장치.
메모리에 비해 속도는 아득히 빠르고, 공간은 몹시 협소하다.
인터럽트
어떤 신호가 들어왔을 때 CPU를 잠시 정지시키는 것.
하드웨어 인터럽트: I/O 디바이스의 연결 등으로 발생
소프트웨어 인터럽트: 트랩이라고도 한다. 수를 0으로 나누는 연산 등의 프로세스 오류로 발생한다. (이때 프로세스가 시스템콜을 호출)
DMA 컨트롤러
I/O 디바이스가 메모리에 직접 접근할 수 있도록 하는 하드웨어 장치. 보조 일꾼.
하나의 작업을 CPU와 DMA 컨트롤러가 동시에 하는 것을 방지.
메모리
전자회로에서 데이터나 상태, 명령어 등을 기록하는 장치.
보통 RAM(Random Access Memory)을 일컬어 메모리라고 한다.
타이머
특정 프로그램에 시간 제한을 다는 역할.
시간이 종료되면 CPU에 인터럽트.
디바이스 컨트롤러
I/O 디바이스에 붙어있는 작은 CPU.
로컬 버퍼는 각 디바이스의 데이터를 임시 저장하는 작은 메모리
2. 메모리
2.1 메모리 계층
- 레지스터: CPU 안에 있는 작은 메모리
- 캐시: L1, L2 캐시를 지칭. L3 캐시도 있음.
- 주기억장치: RAM을 지칭.
- 보조기억장치: HDD, SSD를 지칭. 얘만 비휘발성.
캐시
데이터를 미리 복사해 놓는 임시 저장소.
저장 장치 간에 속도 차이에 따른 병목 현상을 줄이기 위함.
예) 메모리와 CPU 사이에 존재하는 레지스터. 이런 것을 캐싱 계층이라고 함.
캐싱 계층을 두지 않고 캐시를 직접 설정하려면, 어떤 것을 캐시로 할지 근거가 필요하다.
근거는 지역성에 기반한다.
지역성
시간 지역성 temporal locality
최근 사용한 데이터에 다시 접근하려는 특성
e.g.) counter 변수
공간 지역성 spatial locality
최근 접근한 데이터 혹은 그와 가까운 공간에 접근하는 특성.
e.g.) 특정 배열을 순차적으로 모두 탐색.
캐시히트 & 캐시미스
캐시에서 원하는 데이터를 찾았다면 캐시히트,
해당 데이터가 캐시에 없다면 주 메모리로 가서 데이터를 찾아오는 것을 캐시미스.
캐시히트는 CPU 내부 버스를 기반으로 가까운 캐시에서 데이터를 가져오므로 빠르다.
캐시미스는 CPU 바깥의 시스템 버스를 통한다. 느리다.
캐시매핑
캐시가 히트되기 위해 매핑하는 방법.
레지스터와 주 메모리 간에 데이터를 주고 받을 때를 기반.
- 직접 매핑: 메모리 1 ~ 100 / 캐시 1 ~ 10이라면, 1 : 1~10, 2 : 11~20 이런식으로 매핑. 처리가 빠르고 충돌 잦다.
- 연관 매핑: 순서 상관 없이 관련 있는 캐시와 메모리를 매핑. 충돌 적고 모든 블록을 탐색해야 해서 느리다.
- 집합 연관 매핑: 위 2개를 합침. 순서는 일치시키지만 블록화하여 덩어리로 매핑. 덩어리 내에서는 연관 매핑.
웹 브라우저의 캐시
쿠키
만료기한이 있는 키-값 저장소. 4KB.
same site 옵션을 strict로 설정하지 않을 경우 다른 도메인에서 요청했을 때 자동 전송.
보통 서버에서 만료기한을 정함.
로컬 스토리지
만료기한이 없는 키-값 저장소. 5MB.
웹브라우저를 닫아도 유지.
HTML 5 이상.
세션 스토리지
만료기한이 없는 키-값 저장소. 5MB.
탭 단위로 세션 스토리지를 생성. 탭을 닫을 때 해당 데이터 삭제.
HTML 5 이상.
2.2 메모리 관리
2.2.1 가상 메모리 virtual memory
실제로 이용 가능한 메모리 자원을 추상화하여, 사용자에게 매우 큰 메모리로 보이게 만드는 것.
- 가상 주소 logical address: 사용자에게 주어진 주소
- 실제 주소 physical address: 실제 메모리 상에 있는 주소
가상 주소는 메모리 관리 장치(MMU)에 의해 실제 주소로 자동 변환된다.
가상 메모리는 가상 주소와 실제 주소가 매핑된 '페이지 테이블'로 관리된다.
이때 속도 향상을 위해 주소 변환을 위한 캐시인 TLB를 사용한다.
2.2.2 스와핑 swapping
페이지 폴트가 발생했을 때, 당장 사용하지 않는 영역을 하드디스크로 옮기고,
하드 디스크의 일부를 마치 메모리처럼 불러와 쓰는 것을 스와핑이라고 함.
페이지 폴트
가상 메모리에는 존재하지만 실제 메모리인 RAM에는 현재 없는 데이터를 접근하는 경우.
2.2.3 스레싱 thrashing
정의
메모리의 페이지 폴트율이 높은 것을 의미한다.
이는 컴퓨터의 심각한 성능 저하를 초래한다.
원인
스레싱은 메모리에 너무 많은 프로세스가 동시에 올라가게 되면 스와핑이 많이 일어나게 되면서 발생한다.
페이즈 폴트는 CPU 이용률 저하로 이어진다.
CPU 이용률이 낮아지면 운영체제는 가용성을 높이기 위해 더 많은 프로세스를 메모리에 올린다. -> 악순환 -> 스레싱
해결방법
물리적인 방법
- HDD를 SSD로 교체한다.
- 메모리를 늘린다.
논리적인 방법
작업 세트 working set
프로세스의 지역성을 통해 결정된 페이지의 집합을 만들어서 미리 메모리에 로드.
상・하한선으로 페이지 폴트 빈도를 조절.
상한선에 도달하면 프레임을 늘리고, 하한선에 도달하면 프레임을 줄인다.
2.2.4 메모리 할당
메모리에 프로그램을 할당할 때 시작 메모리 위치, 메모리의 할당 크기를 기반으로 할당한다.
이것을 결정하는 방법론.
연속 할당
고정 분할 방식 fixed partition allocation
메모리를 미리 나누어 관리하는 방식.
융퉁성이 없고, 내부 단편화가 발생한다.
가변 분할 방식 variable partition allocation
매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용한다.
외부 단편화가 발생한다.
최초 적합(first fit), 최적 적합(best fit), 최악 적합(worst fit)이 있다.
불연속 할당
페이징 Paging
동일한 크기의 페이지 단위(보통 4KB)로 나누어 메모리의 서로 다른 위치에 프로세스를 할당.
빈 공간의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡.
세그멘테이션 segmentation
페이지 단위가 아닌 의미 단위인 세그먼트로 나누는 방식.
프로세스를 이루는 메모리를 코드 / 데이터 / 코드 내 함수 단위 등으로 나눈다.
공유와 보안 측면에서 장점. 빈 공간의 크기가 균일하지 않은 단점.
페이지드 세그멘테이션 paged segmentation
프로그램을 의미 단위인 세그먼트로 나누고, 다시 그것을 임의가 아닌 동일 크기의 페이지 단위로 나누는 것.
2.2.5 페이지 교체 알고리즘
오프라인 알고리즘
먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾼다.
미래는 알 수 없다. 꿈 같은 것이다.
FIFO
가장 먼저 적재된 페이지를 가장 먼저 교체하는 것.
LRU (Least Recently Used)
참조한 지 가장 오랜 시간이 지난 페이지를 교체하는 것.
NUR (Not Used Recently)
일명 Clock 알고리즘.
0과 1을 가진 비트를 둔다. 1은 최근 참조 / 0은 참조되지 않음.
시계 방향으로 돌면서 0을 찾고, 그 순간 해당 프로세스로 교체하고 1로 방문 처리를 한다.
LFU (Least Frequently Used)
가장 참조 횟수가 적은 페이지를 교체.
3. 프로세스와 스레드
프로세스
컴퓨터에서 실행되고 있는 프로그램.
CPU 스케줄링의 대상이 되는 작업(task)이라는 용어와 거의 같은 의미로 쓰임.
프로그램 -> 메모리 -> 프로그램의 인스턴스화 -> 프로세스 -> CPU 스케줄러에 따라 CPU가 프로세스를 실행.
스레드
프로세스 내 작업의 흐름.
3.1 프로세스와 컴파일 과정
전처리
소스 코드의 주석 제거.
#include 등 헤더 파일 병합하여 매크로를 치환.
컴파일러
오류 처리, 코드 최적화 -> 어셈블리어로 변환
어셈블러
어셈블리어는 어셈블러를 통해 목적 코드(object code)로 변환.
*.o의 확장자. (운영체제 by 운영체제)
링커
프로그램 내에 있는 라이브러리 함수 또는 다른 파일들과 목적 코드를 결합하여 실행 파일 생성.
*.exe, *.out 등의 확장자.
라이브러리
정적 라이브러리
프로그램 빌드 시 라이브러리가 제공하는 모든 코드를 실행 파일에 넣음.
외부 의존도 낮음. 코드 중복 등 메모리 효율 낮음.
동적 라이브러리
프로그램 실행 시 필요할 때만 DLL이는 함수 정보를 참조하여 라이브러리를 사용.
외부 의존도 높음. 메모리 효율 높음.
3.2 프로세스의 상태
생성 상태
프로세스가 생성된 상태.
이때 PCB가 할당.
대기 상태
메모리 공간이 충분하면 메모리를 할당 받고, 아니면 할당받지 못한 상태로 대기(대기 중단 상태).
CPU 스케줄러로부터 CPU 소유권이 넘어오기를 기다리는 상태.
실행 상태
CPU 소유권과 메모리를 할당 받고, 인스트럭션을 수행 중인 상태.
CPU burst가 일어났다고도 표현.
중단 상태
어떤 이벤트(인터럽트)가 발생하여 프로세스가 차단된 상태.
중단된 상태에서 프로세스를 실행하려고 했지만 메모리가 부족하면 일시 중단 상태.
3.3 메모리 상의 프로세스 구조
스택
스택은 동적 할당(런타임 단계에서 메모리를 할당받는 것)이 된다.
지역 변수, 매개변수, 돌아오는 주소 등 실행되는 함수에 의해 가변적인 메모리 영역이다.
재귀 함수를 호출하는 경우 새로운 스택 프레임이 매번 사용되기 때문에,
함수 내의 변수 집합이 해당 함수의 다른 인스턴스 변수를 방해하지 않는다.
힙
동적으로 할당되는 변수를 담는다.
malloc(), free() 함수를 통해 관리할 수 있다.
e.g.) 동적으로 관리되는 자료구조
데이터와 코드 영역
정적 할당(컴파일 단게에서 메모리를 할당)되는 영역이다.
데이터 영역은 BSS segement, Data segment, code/text segment로 나뉜다.
BSS segment는 전역 변수 또는 초기화 되지 않은 변수가 할당된다.
Data segment는 전역 변수 또는 초기화 된 변수가 할당된다.
Code segment는 프로그램의 코드가 할당된다.
3.4 프로세스 제어 블록 PCB
정의
PCB(Process Control Block)는 하나의 프로세스에 대한 메타데이터 저장소를 말한다.
중요한 정보이기에 일반 사용자가 접근할 수 없도록 커널 스택의 가장 앞부분에서 관리된다.
프로그램 실행 -> 프로세스 생성 -> 프로세스 구조에 따라 주소값이 메모리가 할당 -> 해당 프로세스의 메타데이터는 PCB에 저장.
구조
- 프로세스 ID
- 프로세스 스케줄링 상태
- 프로세스 권한
- 프로그램 카운터
- CPU 레지스터
- CPU 스케줄링 정보
- 계정 정보
- I/O 상태 정보
컨텍스트 스위칭 context switching
문맥 교환이라고도 한다.
PCB를 기반으로 프로세스의 상태를 저장하고 로드하는 과정.
CPU는 코어 하나당 단 한 개의 프로세스를 구동할 수 있다.
많은 프로세스가 동시에 구동되는 것처럼 보이는 이유는, 몹시 빠른 속도로 프로세스 간의 컨텍스트 스위칭이 이루어지고 있기 때문이다.
컨텍스트 스위칭이 일어날 때 캐시 미스가 발생하면 고스란히 비용이 된다.
작업하고 있지 않는 유휴 시간(idle time)도 비용이다.
스레드에서의 컨텍스트 스위칭
후술하겠지만 스레드는 스택 영역을 제외한 나머지 메모리를 공유한다.
따라서 프로세스 단위에서보다, 스레드 단위의 컨텍스트 스위칭이 비용도 적고, 시간도 적게 소요된다.
3.5 멀티프로세싱
정의
여러 개의 프로세스를 통해 동시에 일을 병렬 수행하는 것. (컨텍스트 스위칭을 통해)
하나의 프로세스에 문제가 발생해도 다른 프로세스를 이용할 수 있어 신뢰성이 높다.
IPC (Inter Process Communication)
프로세스끼리 데이터를 주고 받고, 공유 데이터를 관리하는 메커니즘.
클라이언트가 데이터를 요청하고, 서버가 응답하는 것 또한 IPC의 예이다.
(스택을 제외한) 메모리가 완전히 공유되는 스레드보다는 속도가 떨어진다.
종류로는 공유 메모리, 파일, 소켓, 익명 파이프, 명명 파이프, 메시지 큐가 있다.
공유 메모리 shared memory
여러 프로세스에게 동일한 메모리 블록에 대한 접근 권한을 부여.
매개체를 통하지 않고, 메모리 자체를 공유하기 때문에 오버헤드가 발생하지 않아 IPC 방식 중에서 가장 빠르다.
동기화가 필수적이다. 충돌 방지해야 하니까.
파일
디스크에 저장된 데이터 또는 파일 서버에서 제공한 데이터
소켓
네트워크 인터페이스를 통해, 동일한 컴퓨터의 다른 프로세스 / 네트워크의 다른 컴퓨터로 전송하는 데이터.
TCP, UDP.
익명 파이프 unnamed pipe
프로세스 간에 FIFO 방식으로 읽히는 임시 공간인 파이프를 기반으로 데이터를 주고 받음.
단방향의 읽기 전용, 쓰기 전용 파이프로 작동.
명명된 파이프 named pipe
파이프 서버와 하나 이상의 파이프 클라이언트 간의 통신을 위한 단방향 / 양방향 파이프.
이것은 파이프가 아니다 Ceci n'est pas une pipe
르네 마그리트의 유명한 작품이다.
메시지 큐
메시지를 큐로 관리하는 것.
커널에서 전역적으로 관리하므로 다른 IPC 방식에 비해 사용이 직관적이다.
공유 메모리의 복잡한 동기화 구현의 대안이 되기도 한다.
3.6 스레드와 멀티스레딩
스레드
프로세스의 실행 가능한 가장 작은 단위.
프로세스는 여러 개의 스레드를 가질 수 있다.
프로세스와 달리 스레드 간에 코드, 데이터, 힙 영역을 공유한다.
멀티스레딩
프로세스 내 작업을 여러 개의 스레드로 처리하는 기법.
스레드끼리 자원을 공유하기 때문에 효율성이 높다.
한 스레드에 문제가 생기면 다른 스레드에 영향을 끼칠 수도 있다.
독립적으로 실행될 수도 있다.
3.7 공유 자원과 임계 영역
공유 자원 shared resource
시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 자원이나 변수.
모니터, 프린터, 메모리, 파일, 데이터 등.
공유 자원을 두 개 이상의 프로세스가 동시에 읽거나 쓰는 상황을 경쟁 상태(race condition)이라고 함.
임계 영역 critical section
경쟁 상태일 때 결과가 달라지는 코드 영역.
없는 게 좋다.
해결하기 위한 방법은 뮤텍스, 세마포어, 모니터가 있다.
이들은 다음의 조건을 만족한다.
- 상호 배제: 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없다.
- 한정 대기: 특정 프로세스가 영원히 임계 영역에 들어가지 못 해서는 안 된다.
- 융통성: 어떠한 프로세스도 임게 영역을 사용하지 않는다면, 영역 외부의 프로세스가 들어갈 수 있다.
마치 공용 화장실처럼 A가 들어가면 잠그고(Lock), B의 접근을 막는 것과 유사하다.
B는 기다리다가 A가 나오면 이용한다.
뮤텍스 mutex
프로세스나 스레드가 공유 자원을 사용할 때 lock()으로 잠금한다.
사용이 종료되면 unlock()으로 잠금을 해제한다.
세마포어 semaphore
정수 값과 두 가지 함수 wait()과 signal()로 공유 자원에 대한 접근을 처리한다.
함수의 실행 타이밍은 뮤텍스와 유사하다.
- wait: 프로세스나 스레드가 공유 자원에 접근 -> wait() -> 나머지는 기다려
- signal: 공유 자원 해제 -> signal() -> 다음 프로세스로 순서를 넘겨줌
바이너리 세마포어 binary semaphore
0과 1만 가질 수 있는 세마포어.
뮤텍스와 유사하지만 뮤텍스는 잠금 메커니즘을, 바이너리 세마포어는 신호 메커니즘을 기반으로 동작한다는 차이가 있다.
카운팅 세마포어 counting semaphore
여러 개의 값을 가질 수 있는 세마포어.
여러 자원에 대한 접근을 제어.
모니터 monitor
둘 이상의 프로세스나 스레드가 안전하게 접근할 수 있도록, 공유 자원을 숨기고 해당 접근에 대해 인터페이스만 제공.
모니터큐를 통해 공유 자원에 대한 작업을 순차 처리.
3.8 교착 상태 deadlock
정의
두 개 이상의 프로세스가 서로가 가진 자원을 기다리며 중단된 상태.
원인
- 상호 배제: 한 프로세스가 자원을 독점. 나머지는 접근 불가.
- 점유 대기: 특정 프로세스가 점유한 자원을 다른 프로세스가 요청 중인 상태.
- 비선점
- 환형 대기: A는 B의 자원을 요구, B는 A의 자원을 요구, ...
해결 방법
- 자원을 할당할 때 교착상태의 조건이 성립되지 않도록 설계.
- 교착 상태 가능성이 없을 때만 자원 할당. 요청 자원의 최대치를 가정하고 할당 여부를 파악 (== 은행원 알고리즘)
- 교착 상태가 발생하면 사이클을 찾고, 관련 프로세스를 하나씩 kill
- 교착 상태는 매우 드물게 발생. 매우 해결하기 어려움. -> 강제 종료.
4. CPU 스케줄링 알고리즘
정의
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라,
프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.
이 알고리즘은 다음의 목표를 갖는다.
- CPU 이용률은 높게
- 주어진 시간에 많은 일을 할 수 있게
- 준비 큐ready queue에 잇는 프로세스는 적게
- 응답 시간은 짧게
4.1 비선점형
프로세스가 CPU 소유권을 스스로 포기.
강제로 프로세스를 중지하지 않음.
컨텍스트 스위칭으로 인한 오버헤드가 적다.
FCFS (First Come, First Served)
먼저 온 것, 먼저 처리.
준비 큐에서 오래 기다리는 현상(convoy effect)가 발생하는 단점.
SJF (Shortest Job First)
실행 시간이 가장 짧은 프로세스 먼저 실행.
긴 시간을 갖는 프로세스의 경우 기아starvation 문제가 있다.
실행 시간을 미리 알 수 없으므로 과거 실행 시간을 토대로 추측한다.
평균 대기 시간이 가장 짧다.
우선순위 or HRN (Highest Response-ratio Next)
기아 문제를 해결하기 위해 오래된 작업일수록 우선 순위를 높이는 방식.
실행 시간이 짧거나, 대기 시간이 길수록 우선 순위가 높아진다.
계산식: (대기 시간 + 서비스 시간) / 서비스 시간
4.2 선점형
현대 운영체제가 쓰는 방식.
알고리즘에 의해 특정 프로세스에 인터럽트를 발생시켜 강제 중단하고, 다른 프로세스 CPU 할당.
라운드 로빈 RR, Round Robin
가장 많이 사용되는 선점형 알고리즘.
특정 시간 단위(time slice, time quantum)를 설정하여,
각 프로세스가 단위 시간 내에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘.
N개의 프로세스가 q의 시간 단위로 동작한다고 했을 때, 반드시 (N - 1) * q 시간 내에 자기 차례가 온다.
q가 커지면 FCFS처럼 동작한다.
q가 작으면 컨텍스트 스위칭이 잦아져 오버헤드가 커진다.
로드밸런서에서 트래픽 분산 알고리즘으로도 사용된다.
SRF (Shortest Remaing time First)
SJF의 선점형 버전.
다단계 큐
우선순위에 따른 여러 개의 준비 큐를 사용한다.
각 큐마다 다른 알고리즘(RR, FCFS, ...)을 적용한다.
우선순위가 높은 큐에 있는 프로세스는, 하위 큐의 프로세스에 대하여 절대적인 우선순위를 갖는다.
큐 간에는 프로세스 이동이 불가하다.
스케줄링 부담이 적지만 유연성이 떨어진다.
다단계 피드백 큐
각 단계의 큐마다 서로 다른 CPU 시간 할당량을 갖는다.
우선순위가 높은 큐일수록 할당량이 적다.
최초 할당 시간 내에 프로세스를 완료하지 못 하면,
하위 우선순위 큐로 내려간다.
상위 큐는 FCFS, 하위 큐는 RR로 동작한다.
참고
면접을 위한 CS 전공지식 노트, 주홍철
'CS > 운영체제' 카테고리의 다른 글
| [운영체제] 혼공컴운 50분 강의 요약 (0) | 2024.05.01 |
|---|---|
| [운영체제] 용어 사전 (0) | 2024.03.05 |
| [운영체제] 32비트, 64비트, x86, x64 (0) | 2024.02.05 |