운영체제 | CS 지식의 정석

ID

52

status

Public

menu

Computer Science

submenu

tags

Operating System

summary

CS 지식의 정석의 “운영체제” 파트를 공부한 것을 기록합니다.

thumbnail

date

Apr 20, 2024

운영체제와 컴퓨터 시스템의 구조

운영체제

종류

• GUI - Graphical User Interface

• CUI - Charcter User Interface

• OS의 뇌는 커널 (즉 OS가 뭐뭐한다 = 커널이 뭐뭐한다)

• 어떤 프로그램을 SSD에 설치하고 실행시키면 메모리에 올라간다. 이 때 메모리에 올라가면 프로세스가 됌

구조

• 유저프로그램과 하드웨어 사이에 차례대로 인터페이스 - 시스템콜 - 커널의 구조를 가짐

역할

1. CPU 스케줄링과 프로세스 상태관리

2. 메모리 관리

3. 디스크 파일 관리

4. I/O 디바이스 관리

컴퓨터 시스템

구조

• CPU: 인터럽트에 의해 메모리에 존재하는 명령어를 해석해서 실행하는 것

• DMA컨트롤러: CPU의 일을 보조함

• 메모리: 전자회로에서 데이터, 상태 등을 기록하는 장치

• 타이머: 특정 프로그램에서 시간을 다는 역할

• 디바이스 컨트롤러: I/O디바이스들의 작은 CP

• 로컬버퍼: 디바이스에 달려 있는 작은 메모리

CPU

• 구성
• 산술논리연산장치(ALU)
• 산술연산과 논리연산을 하는 회로장치
• 제어장치(CU)
• 프로세스의 조작을 지시하며 명령어들을 읽고 해석하며 데이터 처리를 위한 순서를 결정
• 레지스터
• CPU안에 매우 빠른 임시기억장치

• CPU 순서
• 제어장치가 메모리에 있는 일을 레지스터에 올림
• 레스터에 있는 값을 읽어 ALU보고 계산하라 해서 레지스터 반영
• 레지스터에서 메모리에 다시 옮겨 하드디스크나 SSD에 영구저장

• 인터럽트에 의해 메모리에 존재하는 명령어를 해석해서 실행함

인터럽트

• 역할
• 인터럽트란 어떤 신호가 들어왔을 때 CPU를 잠깐 정지시키는 것
• 우선순위가 높은 프로세스의 발생 등으로 발생
• CPU는 인터럽트가 발생되면 인터럽트 핸들러 함수가 모여 있는 인터럽트 벡터로 가서 인터럽트핸들러함수(ISR, 인터럽트 서비스 루틴)가 실행되며 특정 명령어를 실행

• 종류
• 하드웨어 인터럽트
• I/O 디바이스 등 하드웨어에서 발생하는 인터럽트
• 소프트웨어 인터럽트
• 프로세스에서 발생하는 인터럽트
• 하드웨어 인터럽트보다 우선순위가 높음

시스템 콜

• 정의
• 운영체제가 커널에 접근하기 위한 인터페이스
• 유저 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출할 때 거쳐서 호출함

• 과정
• 가정: 유저프로그램이 I/O 요청을 위한 트랩을 발동했을 때
• 유저 프로그램이 I/O 요청 트랩 발동
• 올바른 I/O 요청인지 확인
• 유저 모드가 시스템콜을 통해 커널모드로 변환
• 이후 커널함수 실행

Modebit

• 시스템콜이 작동될때 modebit을 기반으로 유저모드와 커널모드를 구분

• 1 또는 0의 값을 가지는 플래그 변수

• 1은 유저모드, 0은 커널모드

메모리 계층

• 메모리 계층구조
• 레지스터: CPU 내의 작은 메모리, 휘발성, 속도 가장 빠름, 기억 용량이 가장 적음
• 캐시: CPU내의 L1, L2 캐시를 지칭, 휘발성, 속도 빠름, 기억 용량이 적음
• 주기억장치: RAM, 휘발성, 속도 보통, 기억 용량이 보통
• 보조기억장치: HDD, SSD, 비휘발성, 속도 낮음, 기억 용량이 많음

• 계층 존재 이유
• 더 빠른 접근과 처리 속도 증가
• 비용의 효율성
• 자원의 효율적 사용

가상 메모리와 스와핑 페이지 폴트 그리고 스레싱

가상 메모리(Virtual Memory)

• OS에서 사용되는 메모리 관리 기법의 하나

• 실제 이용가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 매우 큰 메모리로 보이게 만드는 것
• 가상주소: MMU와 페이지테이블(page table)에 의해 실제 주소로 변환됨
• 중요) 페이지와 프레임
• 페이지: 가상 메모리를 사용하는 최소 크기 단위
• 프레임: 실제 디스크나 메모리를 사용하는 최소 크기 단위

• 필요성
• 주기억장치의 효율적 관리(스와핑)
• 메모리 관리의 단순화
• 메모리 용량 및 안정성 보장

페이지 테이블

• 가상 메모리는 가상주소와 실제주소가 매핑되어있는 페이지 테이블로 관리되며 이 때 속도 향상을 위해 “캐싱계층인 TLB”를 씀

• 가상주소에서 바로 페이지테이블을 가지 않고 TLB에서 있는지 먼저 확인하고 없다면 페이지테이블로 가서 실제주소를 가져옴

페이지폴트와 스와핑

• 가상메모리는 참조하려는 메모리 영역이 실제 메모리(RAM)에는 데이터가없을 수 있음 → 이 때 페이지 폴트 발생

• 메모리의 당장 사용하지 않는 영역을 하드디스크로 옮기고 하드디스크의 일부분을 “마치 메모리처럼” 불러와 씀 → 이를 “스와핑”이라고 함

• 과정
1. 어떤 명령어가 유효한 가상주소에 접근했으나 해당 페이지가 만약 없다면 트랩이 발생되어 운영체제에 알림
2. 운영체제는 실제 디스크로부터 사용하지 않은 프레임을 찾음
3. 해당 프레임을 실제 메모리에 가져와서 “페이지 교체 알고리즘”을 기반으로 특정 페이지와 교체(스와핑)
4. 페이지 테이블을 갱신시킨 후 해당 명령어를 다시 시작



 

스레싱

• 정의
• 메모리의 페이지 폴트율이 높은 것을 의미
• 발생이유
• 메모리에 너무 많은 프로세스가 동시에 올라가면 스와핑이 많이 일어남
• 페이지폴트가 일어나면 CPU 이용률은 낮아짐
• CPU 이용률이 낮아지면 운용체제는 CPU의 가용성을 높이기 위해 더 많은 프로세스를 메모리에 올림
• 악순환이 반복되어 스레싱이 발생
• 해결방법
• HDD를 사용한다면 SSD로 교체
• 운영체제에서 해결하는 방법은 작업세트와 PFF가 있음
• 작업세트
• 프로세스의 과거 사용이력을 기반으로 많이 사용하는 페이지 집합을 만들어 한꺼번에 미리 메모리에 로드하는 것
• PFF
• page fault frequency
• 페이지 폴트 빈도를 조절하는 방법으로 상한선과 하한선을 만듦
• 상한선에 도달하면 프레임을 늘리고 하한선에 도달하면 프레임을 줄이는 방법



 
 

페이지 교체 알고리즘

• 정의
• 스와핑이 일어날 때 페이지 교체 알고리즘(page replacement algorithm)에 의해 페이지가 교체되게 됨

• 종류
• 오프라인 알고리즘
• 가장 좋은 알고리즘
• 가장 먼 미래에 참조되는 페이지와 현재의 페이지를 바꾸는 LFD(Longest Forward Distance) 알고리즘
• 하지만 미래에 사용되는 프로세스를 우리는 알지 못함 → 따라서 다른 알고리즘과의 성능비교에 대한 상한선
• FIFO
• 가장 먼저 온 페이지부터 교체하는 방법
• LRU
• Least Recently Used
• 최근에 사용되지 않은 페이지를 바꾸는 방법
• 가장 많이 사용하는 알고리즘
• NUR
• Not Used Recently
• 혹은 NRU(Not Recently Used)



• 일명 clock 알고리즘
• 0(참조 되지 않음)과 1(참조 됨)을 가진 비트를 두어서 0을 찾은 순간 해당 페이지를 교체하고, 해당 부분을 1로 바꾸는 알고리즘
• LFU
• Least Frequently Used 알고리즘
• 가장 참조 횟수가 적은 페이지를 교체하는 알고리즘

프로세스와 스레드

프로세스

• 컴퓨터의 메모리에 올라와 실행되고 있는 프로그램

스레드

• 프로세스 내 작업의 흐름

• 종류
• 싱글스레드 프로세스
• 멀티스레드 프로세스

프로세스와 스레드 차이

1. 프로세스: 코드, 데이터, 스택, 힙 메모리 영역을 기반으로 작업 스레드: 프로세스 내의 스택 메모리를 제외한 다른 메모리 영역을 프로세스 내의 다른 스레들과 공유하기 때문에 메모리적 이점이 있음

2. 프로세스끼리 통신을 하기 위해서는 IPC를 사용해야하지만, 스레드는 서로 격리되어있지 않으므로 그냥 통신 가능(빠름)

3. 프로세스는 문제가 생겨도 다른 프로세스에 영향을 끼치지 않음 스레드는 문제가 생기면 다른 스레드에 영향을 끼쳐 스레드로 이루어져 있는 프로세스에 영향을 줌

4. 프로세스는 생성과 종료에 더 많은 시간이 듦 스레드는 더 적은 시간이 듦

프로그램의 컴파일 과정

• 프로그램은 컴파일러가 컴파일 과정을 거쳐 컴퓨터가 이해할 수 있는 기계어로 번역되어 실행될 수 있는 파일이 된 것을 의미

• 과정
1. 전처리
• 소스코드의 주석제거, #include 등 헤더파일을 병합하고 매크로를 치환
2. 컴파일러
• 오류처리, 코드 최적화 작업을 하여 어셈블리어로 변환
3. 어셈블러
• 어셈블리어는 목적코드(object code)로 변환됨
4. 링커
• 프로그램 내 있는 라이브러리 함수 등과 결합해 실행파일이 만들어짐

프로세스의 메모리 구조

• 위에서부터 스택, 힙, 데이터 영역(BSS segment, Data segment), 코드 영역으로 나누어짐

• 스택은 위 주소부터 할당되고 힙은 아래 주소부터 할당

• 스택
• 지역변수, 매개변수, 함수가 저장되고 컴파일 시에 크기가 결정됨. 함수가 함수를 호출 하는 등에 따라 런타임시에도 크기가 변경됨(동적인 특징)

• 힙
• 동적 할당할 때 사용되며 런타임 시 크기가 결정됨(동적인 특징)

• 데이터 영역
• BSS영역과 Data 영역으로 나뉘고 정적할당에 관한 부분을 담당(정적인 특징)

• 코드 영역
• 소스코드 들어감(정적인 특징)
 

정적 할당

• 컴파일단계에서 메모리를 할당하는 것

• BSS segement와 Data segment, Code/Text segment로 나뉘어서 저장됨

• BSS segment는 전역변수, static, const로 선언되어있는 변수 중 0으로 초기화 또는 초기화가 어떠한 값으로도 되어 있지 않은 변수들이 이 메모리 영역에 할당됨

• Data segment는 전역변수, static, const로 선언되어있는 변수 중 0이 아닌 값으로 초기화된 변수가 이 메모리 영역에 할당됨

동적 할당

• 런타임단계에서 메모리를 할당받는 것이며 Stack과 Heap으로 나눠짐

• Stack
• 지역변수, 매개변수, 실행되는 함수에 의해 늘어나거나 줄어드는 메모리 영역

• Heap
• 동적으로 할당되는 변수들을 담음
• malloc(), free() 함수를 통해 관리함
 

PCB와 컨텍스트 스위칭

PCB

• 정의
• Process Control Block
• 운영체제에서 관리하는 프로세스에 대한 메타데이터를 저장한 데이터 블록
• 커널 스택에 저장되며 각 프로세스가 생성될 때마다 고유의 PCB가 생성되고 프로세스가 종료되면 PCB는 제거

• 구조
• 프로세스 상태: 대기중, 실행 중 등 프로세스의 상태
• 프로세스 번호(PID): 각 프로세스의 고유 식별 번호(프로세스 ID)
• 프로그램 카운터(PC): 이 프로세스에 대해 실행될 다음 명령의 주소에 대한 포인터.
• 레지스터: 레지스터관련 정보
• 메모리 제한: 프로세스의 메모리 관련정보
• 열린 파일 정보: 프로세스를 위해 열린 파일 목록들



 
 

컨텍스트 스위칭

• 정의
• PCB를 기반으로 프로세스의 상태를 저장하고 다시 복원시키는 과정
• 프로세스가 종료되거나 인터럽트에 의해 발생

• 컨텍스트 스위칭의 비용
• 유후시간의 발생
• 컨텍스트 스위칭을 할 때마다 유후시간이 생겨서 CPU의 가용성이 떨어지는 비용이 발생함
• 캐시미스
• 프로세스가 가지고 있는 메모리 주소가 그대로 있으면 잘못된 주소 변환이 생기므로 캐시클리어 과정이 무조건 일어나게되고 이 때문에 캐시미스가 발생함

프로세스 상태

• 생성 상태
• 프로세스가 생성된 상태를 의미
• fork() 또는 exec() 함수를 통해 프로세스가 생성된 상태 → 이때 PCB가 할당
• fork()
• 부모 프로세스의 주소 공간을 그대로 복사하며, 새로운 자식 프로세스를 생성하는 함수
• 주소 공간만 복사하고 부모 프로세스의 비동기 작업 등을 상속하지 않음
• exec()
• 새롭게 프로세스를 생성하는 함수

• 대기 상태
• 처음 프로세스가 생성된 이후 메모리 공간이 충분하면 메모리를 할당받고 아니면 아닌 상태로 준비큐에 들어가서 대기중인 상태를 말함

• 대기 중단 상태
• 준비큐가 꽉찬 상태, 메모리 부족으로 일시 중단된 상태

• 실행 상태
• CPU 소유권과 메모리를 할당받고 인스트럭션을 수행 중인 상태

• 중단 상태
• 어떤 이벤트가 발생한 이후 기다리며 프로세스가 차단된 상태

• 일시 중단 상태
• 중단된 상태에서 프로세스가 실행되려고 했지만 메모리 부족으로 일시 중단된 상태

• 종료 상태
• 프로세스 실행이 완료되어 해당 프로세스에 대한 자원을 반납하며 PCB가 삭제되는 상태
• 부모 프로세스가 자식 프로세스를 강제적으로 종료시켜 비자발적 종료(abort)로 종료되는 것도 있음

멀티프로세싱과 멀티스레딩

멀티프로세싱

• 여러 개의 프로세스

• 두 가지 이상의 일을 수행할 수 있는 것

• 특정 프로세스 중 일부에 문제가 발생되더라도 다른 프로세스에 영향을 미치지 않으며 격리성과 신뢰성이 높음

멀티스레딩

• 프로세스 내 작업을 멀티스레드로 처리하는 기법

• 스레드끼리 서로 자원을 공유하고 프로세스보다는 가벼워서 효율성이 높음

• 한 스레드에 문제가 생기면 다른 스레드에도 영향을 끼쳐 프로세스에 영향을 줄 수 있음

IPC

• Inter-Process Communication

• 프로세스끼리 데이터를 주고받고 공유 데이터를 관리하는 메커니즘

• 종류
• 공유 메모리
• 여러 프로세스가 서로 통신할 수 있도록 메모리를 공유하는 것
• 메모리 자체를 공유해 불필요한 데이터 복사의 오버헤드가 발생하지 않아 가장 빠름
• 같은 메모리 영역을 여러 프로세스가 공유하기 때문에 동기화 필요
• IPC 중에서 가장 빠른 통신 방법



• 파일
• 디스크에 저장된 데이터를 기반으로 통신하는 것을 의미
• 소켓
• 네트워크 인터페이스(TCP, UDP, HTTP 등)를 기반으로 통신하는 것을 의미
• 파이프
• 익명파이프
• 프로세스 사이에 FIFO 기반의 통신채널을 만들어 통신



• 단방향 통신 → 양방향 통신 하려면 2개의 익명 파이프 필요



• 부모, 자식 프로세스 간에만 사용 가능하고 다른 네트워크상에서는 사용 X
• 명명파이프
• 익명 파이프의 확장된 개념
• 부모, 자식 뿐만 아니라 다른 네트워크 상에서도 통신 가능
• 보통 서버, 클라이언트용 파이프를 구분해서 동작



• 메세지 큐
• 메세지를 큐 자료구조 형태로 관리하는 버퍼를 만들어 통신
• 동작 과정
1. 프로세스가 메세지를 보내거나 받기 전에 큐를 초기화
2. 보내는 프로세스(sender)의 메세지는 큐에 복사되어 받는 프로세스(receiver)에 전달



 

공유 자원과 경쟁상태 그리고 임계영역

• 공유 자원
• shared resource
• 시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 모니터, 프린터, 메모리, 파일, 데이터 등의 자원이나 변수를 의미

• 경쟁 상태
• race condition
• 공유 자원을 둘 이상의 프로세스 또는 스레드가 동시에 읽거나 쓰는 상황을 말함
• 동시에 접근을 시도할 때의 타이밍이 예상되는 결과 값에 영향을 줄 수 있는 상태
• 경쟁 상태를 잘 해결하지 못하면 데이터 정합성, 무결성을 지키지 못함
• 데이터 정합성
• data consistency
• 예상되는 데이터의 값과 다른 것
• ex) 읽을 때 0원 이어야 하는데 1000원인 것
• 데이터 무결성
• data integrity
• 어떠한 규칙을 위반하면 안되는 것
• 은행에서 0원인데 출금하는 것

• 임계 영역
• critical section
• 둘 이상의 프로세스 또는 스레드가 공유자원에 접근할 때 순서 등의 이유로 결과가 달라지는 코드영역을 뜻함
• 이 영역은 한번에 둘 이상의 프로세스나 스레드가 들어갈 수 없게 설계

뮤텍스, 세마포어, 모니터

경쟁상태를 해결하는 대표적인 3가지 방법 상호배제, 한정대기, 진행의 융통성의 조건을 만족시키며 경쟁상태를 해결

• 상호 배제
• mutual exclusion
• 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없음

• 한정 대기
• bounded waiting
• 특정 프로세스가 임계영역 진입을 요청한 후 해당 요청이 승인되기 전까지 다른 프로세스가 임계영역에 진입하는 횟수를 제한하는 것
• 이를 통해 특정 프로세스가 영원히 임계 영역에 들어가지 못하게 하는 것을 방지

• 진행의 융통성
• progress
• 만약 어떠한 프로세스도 임계영역을 사용하지 않는다면 임계영역 외부의 어떠한 프로세스도 들어갈 수 있음
• 이 때 프로세스끼리 서로 방해하지 않음

• 뮤텍스(mutex)
• 공유 자원을 lock()을 통해 잠금설정하고 사용한 후에 unlock()을 통해 잠금해제가 되는 객체 lock을 기반으로 경쟁상태 해결
• 잠금이 설정되면 다른 프로세스나 스레드는 잠긴 코드 영역에 접근 불가, 해제는 그와 반대
• 한번에 하나의 프로세스만 임계영역에 존재
• ex) 변기가 1개인 화장실

• 세마포어(semaphore)
• 일반화된 뮤텍스
• 간단한 정수 S(현재 쓸 수 있는 공유자원의 수)와 두 가지 함수(wait(), signal())로 공유 자원에 대한 접근 처리
• wait()은 S를 1씩 감소 → 감소시키다 만약 S가 음수가 된다면 공유자원을 쓸 수 없기 때문에 프로세스는 차단되며 대기열에 프로세스를 집어넣음
• signal()은 S를 1씩 증가 → 공유자원을 프로세스가 다 쓴 상태. 이 때 만약 S가 0 이하라면 대기열에 있던 프로세스가 동작
• wait()은 P()라고도 하고 signal()은 V()라고도 함
• 이를 통해 여러 프로세스가 동시에 임계영역에 접근 가능
• 종류
• 바이너리 세마포어
• 0과 1의 두 가지 값만 가질 수 있는 세마포어
• 구현의 유사성으로 인해 뮤텍스는 바이너리 세마포어라고 할 수 있지만 뮤텍스는 잠금을 기반으로 상호배제가 일어나는 ‘잠금 메커니즘’을 사용했고, 세마포어는 신호를 기반으로 상호 배제가 일어나는 ‘신호 메커니즘’을 사용
• 카운팅 세마포어
• 여러 개의 값을 가질 수 있는 세마포어
• ex) 5명의 사용자만이 로그인하여 들어갈 수 있는 게임

• 모니터(monitor)
• 둘 이상의 스레드나 프로세스가 공유 자원에 안전하게 접근할 수 있도록 공유자원을 숨기고 해당 접근에 대해 인터페이스만 제공하는 객체
• 이를 통해 공유자원에 대한 작업들을 순차적으로 처리
• 모니터는 세마포어보다 구현하기 쉽고 한번에 하나의 프로세스만 공유자원에 접근 가능. 따라서 상호배제가 자동. 인터베이스를 기반으로 구축
• 세마포어는 모니터보다 구현하기 어렵고 한번에 여러개의 프로세스가 공유자원에 접근. 따라서 상호배제를 명시적으로 구현해야함. 또한 정수변수를 기반으로 구축

교착 상태(deadlock)

• 정의
• 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태
• 각 프로세스는 서로가 원하는 자원을 유지한채 다른 프로세스의 자원을 얻기를 기다림
• 원인
• 상호 배제
• 주어진 시간 내에 하나의 프로세스만 자원을 독점 가능 → 다른 프로세스들은 접근 불가능
• 점유 대기
• 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하며 대기하는 상태
• 비선점
• 다른 프로세스의 자원을 강제적으로 가져올 수 없음
• 환형 대기
• 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황
• 해결 방법
1. 자원을 할당할 때 애초에 조건이 성립되지 않도록 설계
2. 교착 상태 가능성이 없을 때만 자원 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당가능 여부를 파악하는 ‘은행원 알고리즘’ 사용
3. 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지움
4. 교착 상태는 매우 드물게 일어나서 이를 처리하는 비용이 더 큼 → 따라서 현대 운영체제는 교착 상태가 발생하면 사용자가 작업을 종료하는 방법을 채택함

CPU 스케줄링 알고리즘

• CPU는 스케줄링 알고리즘을 통해 효율적으로 어떤 프로세스를 선택함. 여기서 효율적이란
• CPU 사용률이 높은가?
• 단위 시간당 작업을 마친 프로세스의 수(처리량)가 높은가?
• 작업을 요청한 프로세스가 작업을 시작하기 전 대기하는 시간은 짧은가?

• 비선점형(non-preemptive)
• 정의
• 프로세스가 스스로 CPU 소유권을 포기하는 방식
• 강제로 프로세스를 중지하지 않음
• 컨텍스트 스위칭으로 인한 부하가 적음
• 종류
• FCFS
• First Come, First Served
• 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
• 단점: 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convey effect)이 발생



• SJF
• Shortest Job First
• 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
• 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어날 수 있음
• 평균 대기 시간이 가장 짧음
• 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용



• 우선순위
• Starvation이 일어나는 SJF 스케줄링에서 오래된 작업일수록 우선순위를 높이는 방법(aging)을 통해 단점을 보완한 알고리즘
• 여기서 우선순위란 작업의 시간, 프로세스의 메모리 요구사항, 열린 파일 수, 평균 CPU 사용량 등을 고려해서 설정
• 우선순위 알고리즘은 앞서 설명한 SJF+우선순위를 말하는 것 뿐만 아니라 FCFS를 활용하여 만들기도 하며 선점형, 비선점형적인 우선순위 스케줄링 알고리즘을 말함

• 선점형(preemptive)
• 정의
• 현재 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 강제로 다른 프로세스에 CPU 소유권을 할당할 수도 있는 방식
• 현대 운영체제가 쓰는 방식
• 종류
• 라운드 로빈(RR, Round Robin)
• 현대 컴퓨터가 쓰는 스케줄링 방법, 단순한 선점형 알고리즘
• 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 가는 알고리즘
• 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커짐
• 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아짐
• 로드밸런서에서 트래픽 분산 알고리즘으로 쓰임





• SRF(혹은 SRTF)
• Shortest Remaining Time First
• 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘
• 다단계큐
• 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 RR이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것
• 큐 간의 프로세스 이동이 안돼서 스케줄링 부담이 적지만 유연성이 떨어짐
• Starvation 현상이 발생할 수도 있음

캐시

• 정의
• 데이터를 미리 복사해 놓는 임시 저장소
• 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리
• 캐시는 자주 사용하는 데이터를 기반으로 설정해야 함 → 지역성을 기반으로 설정
• 시간 지역성(Temporal Locality)
• 최근 사용한 데이터에 다시 접근하려는 특성
• 공간 지역성(Spatial Locality)
• 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성
• 캐시는 우리가 사용하는 서비스 내부에서도 많이 찾아볼 수 있음
• DB에서의 redis 데이터베이스를 캐시계층으로 둔 사례



• 웹서버 앞단에 nginx 서버를 캐시계층으로 둔 사례

• 캐시히트
• 캐시에서 원하는 데이터를 찾은 것

• 캐시미스
• 캐시에서 원하는 데이터를 찾지 못한 것
• 캐시미스가 일어나면 메모리로 가서 원하는 데이터를 레지스터에 등록

• 캐시매핑
• 종류
• 직접매핑(직접 사상)
• 연관매핑(연관 사상)
• 집합-연관매핑(집합-연관 사상)

• 직접매핑(Direct Mapping)
• “직접 블록별 매핑을 하다”
• 메모리의 특정 블록은 특정 캐시 라인에만 매핑할 수 있는 것을 말함

• 연관매핑(Associative Mapping)
• “자유로이 연관 매핑을 하다”
• 순서를 일치시키지 않고 관련 있는 캐시와 메모리를 매핑하며 메모리의 컨텐츠가 캐시의 어느 위치에도 올라갈 수 있는 방법
• 스와핑이 덜 일어나겠지만 캐시의 모든 블록을 탐색해야 해서 속도가 직접매핑보다 느림

• 집합-연관매핑(Set Associate Mapping)
• 집합을 나누고(정해진 집합을 만들다 - 직접매핑) 해당 집합에는 bd만 같으면 들어올 수 있게 하는데 이 때 어떤 블럭에도 들어올 수 있게 하는 것
• 따라서 모든 블럭을 찾을 필요 없이 특정 블럭을 찾게 해 탐색비용을 낮춘 직접매핑의 장점과 스와핑을 완화시키는 연관매핑의 장점을 모두 지님

메모리 할당

• 정의
• 프로그램에 필요한 메모리를 할당할 때 시작 메모리 위치, 메모리 할당 크기를 기반으로 할당

• 종류
• 연속 할당
• 불연속 할당

• 연속 할당(Contiguous Memory Allocation)
• 메모리에 ‘연속적’으로 공간을 할당하는 것
• 사용 가능한 메모리 공간이 같은 위치에 함께 있음. 즉, 메모리 파티션이 전체 메모리 공간에 여기저기서 분산되어 있지 않음



• 고정분할방식과 가변분할방식으로 나뉨



• 고정분할방식(Fixed Partition Allocation)
• 메모리를 미리 같은 크기로 분할해서 할당하는 방법 → 내부단편화(Internal Fragmentation)가 발생



• 프로그램이 필요한 공간보다 더 많은 메모리가 할당되어 내부적으로 조각이 많이 생기는 것을 의미
• 추후에 프로그램에 필요한 메모리를 할당하지 못하는 현상 발생
• 가변분할방식(Variable Partition Allocation)
• 프로그램에 필요한만큼 동적으로 할당하는 방법
• 외부단편화가 발생할 수 있음



• 가변분할방식은 최초적합, 최적적합, 최악적합이 있음
• 최초적합(first fit) : 위쪽이나 아래쪽부터 시작해 홀을 찾으면 바로 할당합니다.
• 최적적합(best fit) : 필요한 메모리 크기 이상인 공간 중 가장 작은 홀부터 할당합니다.
• 최악적합(worst fit) : 프로세스의 크기와 가장 많이 차이가 나는 홀에 할당합니다.

• 불연속할당(Non-contiguous Memory Allocation)
• 정의
• 메모리를 연속적으로 할당하지 않는 방법
• 현대 운영체제가 쓰는 방법
• 종류
• 페이징
• 세그멘테이션
• 페이지드 세그멘테이션
• 페이징(Memory Paging)
• 동일한 크기(보통 4kb)의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당 → 홀의 크기가 균일하지 않은 문제가 없어지지만 주소 변환을 페이지별로 해야해서 주소변환이 복잡해짐
• 외부단편화가 해결되지만 내부단편화가 생길 수 있음



• 세그멘테이션(Memory Segmentation)
• 페이지 단위가 아닌 의미 단위인 세그먼트(segment)로 나누는 방식
• 프로세스는 코드, 데이터, 스택, 힙으로 나누어져서 메모리가 할당되는데 코드와 데이터 또는 코드와 스택 등으로 나눌 수도 있으며 함수 단위로 나눌 수도 있음을 의미함
• 공유와 보안 측면에서 좋지만 홀 크기가 균일하지 않게 됨
• 내부단편화가 해결될 수 있지만 외부단편화가 일어날 수 있음



• 페이지드 세그멘테이션(Paged Segmentation)
• 세그멘테이션으로 나누되 해당 세그멘테이션을 동일한 크기의 페이지로 나누는 방법