OS

Operating System 이란 ?

사용자가 컴퓨터를 사용하기 위해 필요한 소프트웨어입니다. 일반적으로 컴퓨터를 사용하면서 실행하는 모든 프로그램들은 운영체제에서 관리하고 제어합니다.

대표적인 운영체제로는 Window, Linux, Mac OSX, iOS 등이 있습니다.

운영체제의 목적

컴퓨터를 효율적으로 사용하기 위한 하드웨어 관리
- CPU, 메모리, 디스크, 키보드, 마우스, 모니터, 네트워크
운영체제의 성능과 컴퓨터의 성능은 비례
사용자에게 편의를 제공

프로세스, 스레드
스케줄링
동기화
IPC 통신

컴퓨터 시스템의 동작 원리

✨ 부팅(Booting)

Processor는 일반적으로 CPU를 말합니다.

Main Memory

ROM : 비휘발성으로 메모리 적게 차지(수 KB)
RAM : 휘발성으로 대부분의 메모리를 차지하며, 실제 프로그램이 할당되는 곳(수 MB ~ 수 GB)

Booting

컴퓨터 전원 켜짐
프로세서에서 ROM에 있는 내용 읽음
POST(Power-On-Self-Test) 프로그램으로 현재 컴퓨터의 상태를 검사
Boot loader가 하드디스크에 저장되어 있는 운영체제를 찾아서 메인 메모리 (RAM)에 가져 옴

커널 (Kernel)
- 운영체제가 수행하는 모든 것이 저장되어 있음
명령어 해석기 (Command interpreter, shell)
- 사용자가 커널에 요청하는 명령어를 해석하여 커널에 요청하고 결과를 출력

✨ 운영체제의 위치

reference

[운영체제(OS)] 1.운영체계란?

Process & Thread

프로그램이란 ?

어떤 작업을 위해 실행할 수 있는 파일

프로세스 vs 스레드 ?

로세스는 자신만의 고유 공간과 자을 할당받아 사용하는 작업의 단위이고, 스레드는 프로세스 내에서 실행되는 흐름의 단위로, 다른 스레드와 프로세스의 자과 공간을 공유하면서 사용합니다.

한 프로세스에는 기본적으로 하나의 쓰레드가 존재한다. 프로세스는 code, data 메모리 공간이 존재하는데, 이는 여러 쓰레드가 공유한다. 이외에도 프로세스의 자원인 file, I/O 등은 여러 쓰레드가 공유하지만, 각 쓰레드가 고유하게 가지고 있는 것은 PC(Program Counter), SP(Stack Pointer), registers, stack 등이 있다.

✨ 프로세스

실행 중인 프로그램
디스크로부터 메모리에 적재되어 CPU의 할당을 받은 작업의 단위
운영체제로부터 시스템 자원을 할당 받음
- CPU 시간
- 운영되기 위한 주소 공간
- Code, Data, Stack, Heap 구로의 독립된 메모리 영역

기본적으로 프로세스마다 최소 1개의 스레드 존재 (메인 스레드)
프로세스는 각각 별도의 메모리 영역(주소 공간)을 할당 받음 (Code, Data, Stack, Heap)
한 프로세스는 다른 프로세스의 변수나 자료구조에 접근할 수 없으며, 이를 위해서는 IPC 통신이 필요
- 파이프, 파일, 소켓 등을 이용한 통신 방법 이용

✨ 프로세스 제어 블록(Process Control Block, PCB)

특정 프로세스에 대한 중요한 정보를 저장하고 있는 커널 내 자료구조
OS는 프로세스 관리를 위해 프로세스의 고유 PCB를 생성

PCB에 저장되는 정보

프로세스 식별자(Process ID, PID) : 프로세스 식별 번호
프로세스 상태 : new, ready, running, waiting, terminated 등의 상태를 저장
프로그램 카운터(Program Counter, PC) : 프로세스가 다음에 실행할 명령어의 주소를 가리킴
CPU 레지스터
CPU 스케줄링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함
입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
어카운팅 정보 : 사용된 CPU 시간, 시간 제한, 계정 번호 등

*아래 또 있음요*

✨ 스레드

프로세스의 실행 단위
한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소 공간이나 자원 공유 가능

스레드는 프로세스 내의 Code, Data, Heap 영역은 다른 스레드와 공유하고 Stack 영역을 따로 할당 받음
스레드는 별도의 레지스터와 스택을 갖고 있으며, 다른 영역을 공유
한 스레드가 프로세스의 자원을 변경하면, 다른 스레드도 그 변경 결과를 즉시 확인 가능

✨ 멀티 프로세스 (Multi Process)

하나의 응용프로그램을 여러 개의 프로세스로 구성,
각 프로세스가 하나의 작업을 처리하도록 하는 것

장점

안전성 : 하나의 프로세스가 죽어도 그 자식 프로세스만 죽는 것 이상으로 다른 영향이 확산되지 않음

단점

Context Switching에서의 오베헤드
- 프로세스 간 공유 메모리 없음
- 캐시 메모리 초기화 등 무거운 작업 진행
프로세스 간 통신 기법 IPC
- 어렵고 복잡함

✨ 멀티 스레드 (Multi Thread)

하나의 응용 프로그램을 여러 개의 스레드로 구성,
각 스레드가 하나의 작업을 처리하도록 하는 것

장점

효율성
- 메모리 공간, 시스템 자원 소모 감소
- 스레드 간 통신시, Heap영역을 통해 데이터를 주고 받으며 통신 방법 간단
- Context switching 시 , 캐시 메모리를 비울 필요가 없어, 비용이 적고 빠름 → ?

단점

자원 공유의 문제(동기화)
하나의 스레드에 문제가 생기면 전체 프로세스에 영향
주의 깊은 설계가 필요, 디버깅 까다로움 → ?

✨ Question

멀티 스레드 vs 멀티 프로세스

멀티 프로세싱 방식은 하나의 프로세스가 죽더라도 다른 프로세스에는 영향을 끼치지 않고 정상적으로 수행된다는 장점이 있지만, 멀티 스레드보다 많은 메모리 공간과 CPU 시간을 차지한다는 단점이 존재합니 다.

반면, 멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 차지하고 Context Switching이 빠르다는 장점이 있지만, 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있다는 점과 동기화 문제를 가지고 있습니다.

이 두 가지는 동시에 여러 작업을 수행한다는 점에서 같지만 적용해야 하는 시스템에 따라 적합/부적합이 구분 됩니다. 따라서 대상 시스템의 특징에 따라 적합한 동작 방식을 선택하고 적용해야 합니다.

스택을 스레드마다 독립적으로 할당하는 이유는 ?

스택은 함수 호출시 전달되는 인자, 복귀 주소값 및 함수 내에서 선언하는 변수 등을 저장하기 위해 사용되는 메모리 공간입니다.

스택 메모리 공간이 독립적이라는 것은, 독립적인 함수 호출이 가능함을 의미하고 이는 독립적인 실행 흐름이 추가된다는 것입니다. 따라서 스레드의 정의에 따라 독립적인 실행 흐름을 추가하기 위한 최소 조건으로 독립된 스택을 할당하는 것입니다.

PC 레지스터를 스레드마다 독립적으로 할당하는 이유는 ?

PC 값은 스레드가 명령어의 어디까지 수행했는지를 나타냅니다.

스레드는 CPU를 할당받았다가 스케줄러에 의해 다시 선점당합니다. 그렇기 때문에 명령어가 연속적으로 수행되지 못하고 어느 부분까지 수행했는지 기억할 필요가 있어, PC 레지스터를 독립적으로 할당하는 것입니다.

멀티 프로세스 대신 멀티 스레드를 사용하는 이유는 ?

프로그램을 여러 개 키는 것보다 하나의 프로그램 안에서 여러 작업을 해결하는 것이 더욱 효율적
프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리할 수 있다.
Context Switching시, 캐시 메모리를 비울 필요가 없기 때문에 비용이 적고 더 빠름 (스레드는 Stack 영역만 초기화하면 됨)
스레드는 프로세스 내의 메모리를 공유하기 때문에 데이터 전달이 간단하므로 IPC에 비해 비용이 적고 더 빠름 (스레드는 프로세스의 Stack 영역을 제외한 모든 메모리를 공유)

Context Switching이란?

CPU는 한번에 하나의 프로세스만 처리할 수 있음
✨ 다른 프로세스에게 CPU를 할당해 작업을 수행하는 과정을 말합니다
- 여러 프로세스를 처리해야 하는 상황에서 현재 진행중인 Task(프로세스, 스레드)의 상태를 PCB에 저장하고 다음에 진행할 Task의 상태값을 읽어 적용하는 과정

과정
- Task의 대부분 정보는 Register에 저장되고 PCB로 관리
- 현재 실행하고 있는 Task의 PCB 정보를 저장
- 다음 실행할 Task의 PCB 정보를 읽어 Register에 적재하고 CPU가 이전에 진행했던 과정을 연속적으로 수행 가능

Context Switching은 많은 비용이 소모
- Cache 초기화
- Memory mapping 초기화
- 커널은 항상 실행되어야 함
Context Switching의 비용은 프로세스가 스레드보다 더 많이 듬
- 스레드는 Stack 영역을 제외한 모든 메모리를 공유하기 때문에 Context Switching 발생시 Stack 영역만 변경을 진행하면 되기 때문

Thread-safe

멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것

동기화 문제

동기화

한정적인 시스템 자원에 여러 스레드가 동시에 접근해서 사용하면 문제 발생 할 수 있습니다. 이 문제를 방지하기 위해 여러 스레드에게 하나의 자원에 대한 처리 권한을 주거나 순서를 조정하는 기법을 말합니다.

✨ 스레드 동기화

실행 순서의 동기화
: 스레드의 실행 순서를 정의하고, 이 순서를 반드시 따르도록 하는 것
메모리 접근에 대한 동기화
: 메모리 접근에 있어서 동시 접근을 막는 것
(하나의 스레드만 해당 자원에 접근하도록 하는 것)

✨ 동기화 기법

유저 모드의 동기화
- 커널의 힘을 빌리지 않는 동기화 기법
- 성능상 이점이 있으나 기능상의 제한점 존재
임계 구역 기반의 동기화
인터락 함수 기반의 동기화
커널 모드의 동기화
- 커널에서 제공하는 동기화 기능을 이용하는 방법
- 커널 모드로의 변경이 필요하고 이는 성능 저하로 이어지지만, 다양한 기능을 활용할 수 있음
세마포어
뮤텍스
모니터

✨ Q

임계영역이란 ?

뮤텍스와 모니터의 차이는 ?

세마포어와 뮤텍스의 차이는 ?

세마포어(Semaphore) & 뮤텍스(Mutex)

✨ 세마포어란 ?

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있습니다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 하는데, 이를 위해 나온 것이 바로 **'세마포어'**입니다.

세마포어 : 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

✨ 임계 구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 합니다.

✨ 뮤텍스란 ?

임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

상호 배제(Mutual Exclusion)의 약자임

해당 접근을 조율하기 위해 lock과 unlock을 사용합니다.

lock : 현재 임계 구역에 들어갈 권한을 얻어옴 ( 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기 )
unlock : 현재 임계 구역을 모두 사용했음을 알림 ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음 )

✨ 뮤텍스 알고리즘

데커(Dekker) 알고리즘

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

피터슨(Peterson) 알고리즘

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
    }
}

// ------- 임계 구역 ---------

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

제과점(Bakery) 알고리즘

while(true) {
    
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료

PCB와 Context Switching

✨ Process Management

CPU 프로세스가 여러개일 때, CPU 스케줄링을 통해 관리하는 것을 의미합니다.

이때, CPU는 각 프로세스들이 누군지 알아야 프로세스 관리가 가능한데, 프로세스들의 특징을 갖고 있는 것이 바로 Process Metadata입니다.

Process Metadata

Process ID

Process State

Process Priority

CPU Registers

Owner

CPU Usage

Memeory Usage

메타데이터는 프로세스가 생성되면 PCB(Process Control Block) 이라는 곳에 저장됩니다.

✨ PCB (Process Control Block)

프로세스의 메타데이터들을 저장해 놓는 곳으로 한 PCB 안에는 프로세스의 정보가 담겨있습니다.

정리

프로그램 실행 → 프로세스 생성 → 프로세스 주소 공간에 (코드, 데이터, 스택) 생성

✨ Q

PCB가 왜 필요한가 ?

CPU에서는 프로세스의 상태에 따라 교체작업이 이루어. (interrupt가 발생해서 할당받은 프로세스가 waiting 상태가 되고 다른 프로세스를 running으로 바꿔 올릴 때)

이때, 앞으로 다시 수행할 대기 중인 프로세스에 관한 저장 값을 PCB에 저장해두는 것이다.

PCB는 어떻게 관리되나 ?

Linked List 방식으로 관리함

PCB List Head에 PCB들이 생성될 때마다 붙게 된다. 주소값으로 연결이 이루어져 있는 연결리스트이기 때문에 삽입 삭제가 용이함.

즉, 프로세스가 생성되면 해당 PCB가 생성되고 프로세스 완료시 제거됨

Context Switching

수행 중인 프로세스를 변경할 때, CPU의 레지스터 정보가 변경되는 것을 Context Switching이라고 한다. 즉, CPU가 이전의 프로세스 상태를 PCB에 보관하고, 또 다른 프로세스의 정보를 PCB에 읽어 레지스터에 적재하는 과정

보통 인터럽트가 발생하거나, 실행 중인 CPU 사용 허가시간을 모두 소모하거나, 입출력을 위해 대기해야 하는 경우에 Context Switching이 발생

즉, 프로세스가 Ready → Running, Running → Ready, Running → Waiting처럼 상태 변경 시 발생!

Context Switching의 OverHead란?

프로세스를 수행하다가 입출력 이벤트가 발생해서 대기 상태로 전환시킴 이때, CPU를 그냥 놀게 놔두는 것보다 다른 프로세스를 수행시키는 것이 효율적 즉, CPU에 계속 프로세스를 수행시키도록 하기 위해서 다른 프로세스를 실행시키고 Context Switching 하는 것

CPU가 놀지 않도록 만들고, 사용자에게 빠르게 일처리를 제공해주기 위한 것이다.

인터럽트 (Interrupt)

하드웨어 장치가 CPU에게 어떤 사실을 알려주거나 CPU의 서비스를 요청해야 할 경우, CPU 내에 있는 인터럽트 라인을 세팅하여 인터럽트를 발생
CPU는 매번 프로그램 카운터가 가리고 있는 곳의 명령을 수행한 뒤, 다음 명령을 수행하기 직전에 라인이 세팅되었는지 체크
이를 통해 인터럽트가 발생했으면 CPU는 현재 수행 중이던 프로세스를 멈추고 운영 체제의 인터럽트 처리 루틴으로 이동하여 인터럽트 처리 수행

✨ 인터럽트 종류

하드웨어 인터럽트 : 하드웨어 컨트롤러가 CPU의 서비스를 요처하기 위해 발생시키는 인터럽트
소프트웨어 인터럽트
예외상황
시스템 콜
소프트웨어 인터럽트 발생 과정

✨인터럽트 발생 처리 과정

A프로그램이 CPu를 할당 받고 명령을 수행하고 있는데 인터럽트가 발생하면 A는 현재 수행중인 명령의 위치 저장
그 후 운영 체제 내부 코드인 인터럽트 처리 루틴으로 넘어가서 인터럽트 처리
다시 돌아와 A의 이전 작업 지점부터 수행을 계속함

→ 진행 중이던 A프로세스의 정보는 PCB에 저장. 인터럽트 처리를 모두 마치면 프로그램 A의 PCB에 저장된 주소를 복원시켜 우너래 수행하던 일을 재개

인터럽트 벡터
- 여러가지 인터럽트에 대해 해당 인터럽트 발생시 처리해야 할 루틴의 주소를 보관하고 있는 테이블
- 일종의 함수를 가리키는 포인터
인터럽트 핸들러
- 실제 인터럽트를 처리하기 위한 루틴으로 인터럽트 서비스 루틴
- 운영체제 코들 부분에는 각종 인터럽트 별로 처리해야 할 내용이 이미 프로그램되어 있으며, 이 부분을 인터럽트 서비스루틴 또는 인터럽트 핸들러라고 함

시스템 콜 (System Call)

유저 프로세스에서 운영체제 서비스를 필요로 할 때 이를 받기 위해 사용하는 호출

✨ 커널 모드

프로그램 카운터가 운영체제가 존재하는 부분을 가리키고 있다면, 현재 운영체제의 코드를 수행 중이며, CPU가 커널 모드에서 수행 중이라고 합니다.

✨ 사용자 모드

프로그램 카운터가 사용자 프로그램이 존재하는 메모리 위치를 가리킬 경우, 사용자 프로그램을 수행 중이며 CPU가 사용자 모드에서 수행 중이라고 합니다.

일반 명령 : 메모리에서 자료를 읽어와서 CPU에서 계산하고 결과를 메모리에 쓰는 일련의 명령들
특권명령 : 보안이 필요한 명령으로 입출력 장치, 타이머 등 각종 장치를 접근하는 명령 (커널 모드)
CPU 내에 모드 비트를 두어 두 명령 수행
사용자 프로그램이 디스크의 파일을 접근하거나, 화면에 결과를 출력하는 등의 작업이 필요한 경우가 있다. 하지만, 이러한 작업은 특권 명령의 수행을 필요로함
이와 같은 경우, 사용자 프로그램은 스스로 특권 명령을 수행할 수 없으므로 운영체제에게 특권 명령의 대행을 요청. 이러한 서비스 요청은 시스템 콜이라고 부름 (즉, 특권 명령의 대행을 요청)

✨ 시스템 콜의 유형

프로세스 제어 : 프로세스 특권 모드를 사용해 직접적으로 프로세스 제어가 가능
파일 조작 : 파일을 생성하거나 삭제, 관리 등
장치 관리 : 장치 요구 및 장치 해제, 읽기, 쓰기, 재배치 등
정보 유지 : 시간과 날짜의 설정과 획득, 시스템 자료의 설정과 획득
통신 : 통신 연결의 생성 및 제거, 메시지의 송수신, 상태 정보 전달 등

주요 System call

Process: end(정상 종료), abort(강제 종료), load, execute, create, terminate, get/set, attributes, wait event, signal event
Memory: allocate, free
File: create, delete, open, close, read, write, get/set attributes
Device: request, release, read, write, get/set attributes, attach/detach devices
information: get/set time, get/set system data
Communication: socket, send, receive

교착 상태 (DeadLock)

교착상태란 ?

한정된 자원을 여러 곳에서 사용하려고 할 때, 발생하는 문제로, 프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태입니다

위의 그림처럼 현재 서로 원하는 자원이 상대방에게 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠지게 되는 상황을 DeadLock 이라고 부른다.

✨ 발생하는 경우

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 읻대 프로세스는 대기 상태로 들어감
대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때, '교착 상태' 발생

✨ 발생조건

4가지 조건이 동시에 성립할 때, 발생
4가지 조건 중 하나라도 성립하지 않는다면 교착 상태를 해결할 수 있음

상호 배제(Mutual Exclusion)
- 자원은 한 번에 한 프로세스만이 사용할 수 있음
점유 대기(Hold and Wait)
- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함
비선점 (No Preemption)
- 다른 프로세스에 할당된 자원은 사용이 끝나서 반납할 때까지 강제로 빼앗을 수 없음
순환 대기 (Circular Wait)
- 프로세스의 집합 {P0, P1, ..., Pn}에서 0은 1이 점유한 자원을 대기하고 1은 2가 점유한 자원을 대기하고 Pn은 P0이 점유한 자원을 요구해야 함
- 이처럼 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

✨ 교착 상태 예방

교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법
자원의 낭비가 심함

상호 배제 부정 여러 프로세스가 공유 자원을 사용하도록 한다.
점유 대기 부정 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
비선점 부정 자원 점유 중인 프로세스가 다른 자원을 요구할 때, 점유 중인 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 한다.
순환 대기 부정 자원에 고유한 번호를 할당하고, 번호 순서대로로 자원을 요구하도록 한다.

✨ 교착 상태 회피

교착 상태가 발생하면 피해나가는 방법
은행원 알고리즘
다익스트라가 제안한 방법으로 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래된 기법

프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 검사하여 교착 상태를 회피하는 기법이다.

안정 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기한다.

✨ 교착 상태 회복

교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제함으로써 회복하는 것을 의미

프로세스를 종료하는 방법
- 교착 상태의 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 한 프로세스씩 중지
자원을 선점하는 방법
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법
- 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점

✨ Q

교착상태가 무엇이고, 발생 조건에 대해 설명해주세요.

회피 기법인 은행원 알고리즘이 대해 설명해주세요.

기아 상태를 설명하는 '식사하는 철학자 문제'에 대해 설명해주세요.

CPU 스케줄링

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 합니다. 이때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 CPU Scheduling 알고리즘이라고 합니다. 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는지 결정해야 합니다.

✨ Preemptive vs Non-Preemptive

Preemptive(선점)
- 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생하지 않았음에도 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다.
- 즉, 프로세스가 정상적으로 수행중인 동안 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있다.
Non-Preemptive(비선점)
- 한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.

✨ 선점형 스케줄링

SRT(Shortest Remaining Time) 스케줄링
- 짧은 시간 순서대로 프로세스를 수행한다.
- 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착하면 CPU가 선점된다.
Round Robin 스케줄링
- 시분할 시스템의 성질을 활용한 방법
- 일정 시간을 정하여 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다.
- 그리고 다음 프로세스 역시 같은 시간동안 수행한 후, 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 진행하며, 마지막 프로세스가 끝나면 다시 처음 프로세스로 돌아와서 작업을 반복한다.
- 일정 시간을 Time Quantum(Time Slice)라고 부른다. 일반적으로 10 ~ 100msec 사이의 범위를 갖는다.
- 한 프로세스가 종료되기 전에 time quantum이 끝나면 다른 프로세스에게 CPU를 넘겨주기 때문에 선점형 스케줄링의 대표적인 예시다.
Multi-level Queue 스케줄링
- 프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue(준비 큐)를 여러 개 두며, 각 큐마다 다른 규칙을 지정할 수도 있다.(ex. 우선순위, CPU 시간 등)
- 즉, 준비 큐를 여러 개로 분할해 관리하는 스케줄링 방법이다.
- 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 게 아니라 여러 줄로 선다.
Multi-level feedback Queue 스케줄링
- 기본 개념은 Multi-level Queue와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
- 위 그림에서 모든 프로세스는 가장 위의 큐에서 CPU의 점유를 대기한다. 이 상태로 진행하다가 이 큐에서 기다리는 시간이 너무 오래 걸린다면 아래의 큐로 프로세스를 옮긴다. 이와 같은 방식으로 대기 시간을 조정할 수 있다.
- 만약, 우선순위 순으로 큐를 사용하는 상황에서 우선순위가 낮은 아래의 큐에 있는 프로세스에서 starvation 상태가 발생하면 이를 우선순위가 높은 위의 큐로 옮길 수도 있다.
- 대부분의 상용 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용한다. 프로세스의 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택한다.

✨ 비선점형 스케줄링

FCFS(First Come First Server)
- 준비 큐에 먼저 도착한 프로세스가 먼저 CPU를 점유하는 방식이다.
- CPU를 할당받으면 CPU 버스트가 완료될 때까지 CPU를 반환하지 않으며, 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다.
SJF(Shortest-Job-First)
- 다른 프로세스가 먼저 도착했더라도 CPU 버스트가 짧은 프로세스에게 CPU를 먼저 할당하는 방식이다.
- 선점, 비선점 모두 가능하다.
Priority
- 우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘이다.
- 우선순위는 정수값으로 나타내며, 작은 값이 우선순위가 높다.(Unix/Linux 기준)
- 선점, 비선점 모두 가능하다.

스케줄러의 종류

스케줄러란 ?

프로세스들은 자신이 종료될 때까지 수많은 큐들을 돌아다니는데, OS는 이 큐 안에 있는 프로세스 중 하나를 선택해야 하는 데 이 일을 스케줄러가 담당합니다.

작업 큐(Job Queue)
- 현재 시스템 내의 모든 프로세스의 집합
준비 큐(Ready Queue)
- 현재 메모리 내에 있으면서 CPU를 할당받고 실행되기 위해 기다리는 프로세스의 집합
장치 큐(Device Queue)
- 각각의 장치마다 서비스를 기다리며 줄 서 있는 프로세스의 집합

✨ 장기 스케줄러(Long-term Scheduler)

메모리는 한정되어 있는데 많은 프로세스들이 메모리에 한꺼번에 올라올 경우, 대용량 메모리(디스크)에 임시로 저장
이 Pool(디스크) 내의 저장되어 있는 프로세스 중 어떤 순서로 프로세스를 메모리에 적재할지 결정
메모리와 디스크 사이의 스케줄링을 담당
상대적으로 호출되는 빈도가 적음
즉, 디스크와 같은 저장 장치에 작업들을 저장해 놓고 필요할 때 실행할 작업을 Job Queue에서 꺼내 Ready Queue를 통해서 메인 메모리에 적재
degree of Multiprogramming 제어
- (메모리에 여러 프로그램이 올라가는 것. 즉, 몇 개의 프로그램이 올라갈 것인지를 제어)
프로세스의 상태
- 시작 상태(New) -> 준비 상태(Ready)
- Running(or Ready) -> Terminated

✨ 단기 스케줄러(Short-term Scheduler)

CPU와 메모리 사이의 스케줄링을 담당
장기 스케줄러에 비해 매우 많이 호출
CPU에게 필요한 데이터를 확보해주고 메모리에 있는 프로세스 중 하나를 선택해서 CPU를 할당
즉, Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
Ready Queue에 있는 프로세스 중 먼저 도착한 프로세스에게 CPU를 할당 (=디스페처)
프로세스의 상태 : ready -> running -> waiting -> ready

✨ 중기 스케줄러(Medium-term Scheduler)

시분할 시스템에서 추가로 사용하며, 메모리에 대한 가중을 완화시켜주기 위해 중기 스케줄러 도입
CPU를 차지하기 위한 경쟁이 심해질 때, 우선순위가 낮은 프로세스들을 잠시 제거한 뒤, 나중에 경쟁이 완화되었을 때 다시 디스크에서 메모리로 불러와 중단되었던 지점부터 실행(Swapping)
즉, 프로세스들이 서로 CPU를 차지하려고 경쟁이 심해지면 Swapping 기법을 활용하여 메모리를 관리함으로써 너무 많은 프로그램이 동시에 올라가는 것을 조절
프로세스의 상태 : ready -> suspended

swap out : 메모리에서 디스크로 잠시 나가는 상태

swap in : 디스크에서 메모리로 다시 들어오는 상태

✨ Process state - suspended

Suspended(stopped)

외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다. 프로세스 전부 디스크로 Swap out 됨

Blocked 상태

다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state 로 돌아갈 수 있지만, 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없음

✨ About 중기 스케줄러

✨ Q

장기 스케줄러 vs 단기 스케줄러

동기 vs 비동기

✨ 동기(synchronous : 동시에 일어나는)

동시에 일어난다는 뜻이다. 요청과 그 결과가 동시에 일어난다는 약속이다.
바로 요청을 하면 시간이 얼마가 걸리던지 요청한 자리에서 결과가 주어져야 한다.
요청과 결과가 한 자리에서 동시에 일어난다.
A노드와 B노드 사이의 작업 처리 단위(transaction)를 동시에 맞추겠다.

✨ 비동기(Asynchronous : 동시에 일어나지 않는)

동시에 일어나지 않는다를 의미한다. 요청과 결과가 동시에 일어나지 않을 것이라는 약속이다.
요청한 그 자리에서 결과가 주어지지 않는다.
노드 사이의 작업 처리 단위를 동시에 맞추지 않아도 된다.
동기 방식은 설계가 매우 간단하고 직관적이지만 결과가 주어질 때까지 아무것도 못하고 대기해야 한다는 단점이 있다.
비동기 방식은 동기보다 복잡하지만, 결과가 주어지는데 시간이 걸리더라도 그 시간 동안 다른 작업을 할 수 있으므로 자원을 효율적으로 사용할 수 있다는 장점이 있다.

✨ reference

https://velog.io/@nittre/블로킹-Vs.-논블로킹-동기-Vs.-비동기

메모리

✨ 메인 메모리(main memory)

메인 메모리는 CPU가 직접 접근할 수 있는 기억 장치
프로세스가 실행되려면 프로그램이 메모리에 올라와야 함

주소가 할당된 일련의 바이트들로 구성되어 있음

CPU는 레지스터가 지시하는대로 메모리에 접근하여 다음에 수행할 명령어를 가져옴

명령어 수행 시 메모리에 필요한 데이터가 없으면 해당 데이터를 우선 가져와야 함

이 역할을 하는 것이 바로 MMU

메모리 관리장치(MMU)는 논리 주소를 물리주소로 변환해줌

뿐만 아니라 메모리 보호나 캐시 관리 등 CPU가 메모리에 접근하는 것을 총 관리해주는 하드웨어임

메모리의 공간이 한정적이기 때문에, 사용자에게 더 많은 메모리를 제공하기 위해 '가상 주소'라는 개념이 등장 (가상 주소는 프로그램 상에서 사용자가 보는 주소 공간이라고 보면 됨)

이 가상 주소에서 실제 데이터가 담겨 있는 곳에 접근하기 위해선 빠른 주소 변환이 필요한데, 이를 MMU가 도와주는 것

또한 메인 메모리의 직접 접근은 비효율적이므로, CPU와 메인 메모리 속도를 맞추기 위해 캐시가 존재함

✨ MMU의 메모리 보호

프로세스는 독립적인 메모리 공간을 가져야 되고, 자신의 공간만 접근해야 함

따라서 한 프로세스에게 합법적인 주소 영역을 설정하고, 잘못된 접근이 오면 trap을 발생시키며 보호함

가상메모리

✨ 가상 메모리

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 한다. 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법 이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

✨가상 메모리 개발 배경

실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었다. 또한, 여러 프로그램을 동시에 메모리에 올리기에는 용량의 한계와, 페이지 교체등의 성능 이슈가 발생하게 된다. 또한, 가끔만 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서, 불필요하게 전체의 프로그램이 메모리에 올라와 있어야 하는게 아니라는 것을 알 수 있다

✨ 프로그램의 일부분만 메모리에 올릴 수 있다면...

물리 메모리 크기에 제약받지 않게 된다.
더 많은 프로그램을 동시에 실행할 수 있게 된다. 이에 따라 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

✨ 가상 메모리가 하는 일

가상 메모리는 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것으로 정리할 수 있다. 이로써 작은 메모리를 가지고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공할 수 있다.

✨ 가상 주소 공간

한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간이다. 프로세스가 요구하는 메모리 공간을 가상메모리에서 제공함으로써 현재 직접적으로 필요치 않은 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 물리 메모리를 절약할 수 있다.
예를 들어, 한 프로그램이 실행되며 논리 메모리로 100KB 가 요구되었다고 하자. 하지만 실행까지에 필요한 메모리 공간(Heap영역, Stack 영역, 코드, 데이터)의 합이 40KB 라면, 실제 물리 메모리에는 40KB 만 올라가 있고, 나머지 60KB 만큼은 필요시에 물리메모리에 요구한다고 이해할 수 있겠다.

✨ 프로세스간의 페이지 공유

가상 메모리는...

시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다. 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있다.
프로세스들이 메모리를 공유하는 것을 가능하게 하고, 프로세스들은 공유 메모리를 통해 통신할 수 있다. 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

페이징 vs 세그멘테이션

가상 메모리를 관리하는 기법
가상 메모리는 메모리에 로드된 즉, 실행중인 프로세스가 가상의 공간을 참조하여 마치 커다란 물리 메모리를 갖고 있는 것처럼 사용할 수 있도록 하는 것이다.
간단하게 말해 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이다.

✨ 페이징(Paging)

프로세스의 주소 공간을 동일한(고정된) 사이즈의 페이지 단위로 나누어 물리적 메모리에 불연속적으로 저장하는 방식
외부 단편화와 압축 작업을 해소하기 위함이다.
메모리는 Frame이라는 고정 크기로 분할되고, 프로세스는 Page라 불리는 고정 크기로 분할된다.
하나의 프로세스는 연속적인 동작을 수행하는데, 이를 작은 조각으로 나누어 여기저기 흩어진다면 정상적으로 동작할까?
이처럼 메모리상에서 여러 곳에 흩어진 프로세스를 수행하기 위해 MMU를 통해 논리 주소와 물리 주소를 나누어 사용함으로써 CPU를 속여야 한다.
실제 메모리는 전혀 연속적이지 않는데, CPU는 연속적으로 사용하고 있다는 것을 보장받으며 정상적으로 수행한다.
50byte 크기의 프로세스가 있다고 가정하고, 페이징의 크기는 10byte로 나눈다
프로세스 P1은 5개의 페이지로 나눌 수 있다. 이를 메인 메모리 5곳에 나눠서 할당했다.
CPU는 논리 주소로 프로그램이 설정한대로 연속적인 주소값으로 명령을 내리고 이는 메모리로 가기 전에 각 페이지의 실제 메모리 주소가 저장되어 있는 테이블에서 물리 주소로 변경되어야 한다.
프로세스를 나눈 조각을 Page라 하고, 메모리를 나눈 조각을 Frame이라 한다.
프로세스는 페이지의 집합이고, 메모리는 프레임의 집합이다.
프로세스를 정상적으로 사용하기 위해 MMU의 재배치 레지스터를 여러 개 사용해서 위의 그림과 같이 각 페이지의 실제 주소로 변경해준다. 이러한 여러 개의 재배치 레지스터를 페이지 테이블(Page Table)이라 한다.

✨ 주소 변환(Address Translation)

페이징 기법을 사용하기 위해서는 여러 개로 흩어진 페이지에 CPU가 접근하기 위해서 페이지 테이블을 통해 주소를 변환해야 한다.

논리 주소(Logical Address)

CPU가 접근하는 주소는 2진수로 표현되고 이는 m비트가 있다고 가정하다. 여기서 하위 n비트는 오프셋(offset) 또는 변위(displacement)라고 한다. 그리고 상위 m-n비트는 페이지의 번호에 해당한다. (n = d, m-n = p)
논리주소를 물리주소로 변환하기 위해서 페이지 번호(p)는 페이지 테이블의 인덱스 값이고, p에 해당되는 테이블 내용은 메모리의 프레임 번호이다. 변위(d)는 변하지 않는 값이다. 이 규칙에 대한 예제를 살펴보자.
Page size = 16bytes
Page Table = 5,3,2,8,1,4
논리 주소 50번지는 물리주소 몇 번지인가?

✨ 내부 단편화(Internal Fragment)

내부 단편화는 프로세스 크기가 페이지 크기의 배수가 아닐 경우, 마지막 페이지는 한 프레임(페이지)를 다 채울 수 없어서 발생하는 공간으로 메모리 낭비의 원인이 된다.

예를 들어, 15bytes 크기의 프로세스 p가 있다. 페이지 크기는 4byte로 p를 페이지로 나누면 4,4,4,3의 크기로 총 4개의 페이지가 만들어진다. 마지막 3byte 페이지는 페이지의 크기보다 1byte 작으므로 사용하지 못하고, 이만큼의 메모리 공간이 비게 된다. 이렇게 비어진 공간은 프로세스 p에서도 쓰지 않고, 다른 프로세스에서도 쓰지 못하는 낭비되는 공간이 된다.

아쉽게도 내부 단편화는 해결할 방법이 없다. 하지만, 내부 단편화는 외부 단편화에 비해 낭비되는 메모리 공간은 매우 적다. 내부 단편화의 최대 낭비되는 크기는 page size - 1이 된다. (외부 단편화는 최대 전체 메모리의 1/3이 낭비된다고 한다.) 이는 무시할 정도로 작은 크기이다.

✨ 보호(Protection)

모든 주소는 페이지 테이블을 경유하므로, 테이블을 이용해서 보호 기능을 수행할 수 있다. 대표적으로 페이지 테이블마다 r(read), w(write), x(execute) 비트를 두어, 해당 비트가 켜져있을 때, 그 수행이 가능하도록 한다.

페이지 테이블에 r,w,x 비트를 추가한 모습이다. 만약, 1번 페이지 엔트리처럼 쓰기 비트가 꺼져있는 페이지에 쓰기 작업을 시도하면 CPU에 인터럽트가 발생하여 ISR(Interrupt Service Routine)에서 강제로 해당 프로세스를 종료시킨다.

공유는 메모리 낭비를 방지하기 위함이다. 같은 프로그램을 쓰는 복수 개의 프로세스가 있다면, 프로세스의 메모리는 code+data+stack 영역으로 나뉘는데 프로그램이 같다면 code 영역은 같을 것이다.

그러므로 하나의 code 영역을 복수 개의 프로세스가 공유하여 메모리 낭비를 줄이는 것이다. 단, code가 공유되려면 code가 변하지 않는 프로그램이어야 한다. 이를 non-self-modifying code = reentrant code(재진입 가능 코드) = puer code 라고 한다.

✨ 세그멘테이션(Segmentation)

프로세스를 서로 크기가 다른 논리적인 블록 단위인 '세그먼트(Segment)'로 분할하고 메모리에 배치하는 것을 말하며, 각 세그먼트의 크기는 일정하지 않다.
프로세스를 Code + Data + Stack 영역으로 나누는 것 역시 세그멘테이션의 모습이다. 물론, code, data, stack 각각 내부에서 더 작은 세그먼트로 나눌 수도 있다.
세그먼트를 메모리에 할당할 때는 페이지를 할당하는 것과 동일하다. 하지만, 테이블은 조금 다르다. 세그먼테이션을 위한 테이블은 세그먼트 테이블이라고 한다.
세그먼트 테이블은 세그먼트 번호와 시작 주소, 세그먼트 크기를 엔트리로 갖는다.
세그먼트에서 주소변환 역시, 페이징과 유사하다. 한 가지 주의할 점은 세그먼트의 크기는 일정하지 않기 때문에, 테이블에 limit 정보가 주어진다. 그리고 CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해서 해당 프로세스를 강제로 종료시킨다.

✨ 세그먼테이션에서 보호와 공유

먼저, 결론부터 말하면 페이징보다 세그먼테이션에서의 보호와 공유는 더 효율적이다.

보호에서는 세그먼테이션 역시 r,w,x 비트를 테이블에 추가하는데, 세그먼테이션은 논리적으로 나누기 때문에 해당 비트를 설정하기 매우 간단하고 안전하다. 페이징은 code+data+stack 영역이 있을 때, 이를 일정한 크기로 나누므로 두 가지 영역이 섞일 수 있다. 그러면 비트를 설정하기가 매우 까다롭다.

공유에서도 마찬가지다. 페이징에서는 code 영역을 나눈다해도 다른 영역이 포함될 확률이 매우 높다. 하지만, 세그먼테이션은 정확히 code 영역만을 나누기 때문에 더 효율적으로 공유를 수행할 수 있다.

✨ 세그먼테이션과 페이징

세그먼테이션은 페이징과 유사하고 보호와 공유 측면에서는 더 나은 성능을 보여주었지만, 현재 대부분은 페이징 기법을 사용한다. 그 이유는 세그먼테이션에는 치명적인 단점이 존재하기 때문이다.

메모리 할당을 처음 시작할 때, 다중 프로그래밍에서의 문제는 크기가 서로 다른 프로세스로 인해 여러 크기의 hole이 발생한다. 이로 인해 어느 hole에 프로세스를 할당하는 것에 대한 최적화 알고리즘이 존재하지 않고, 외부 단편화로 인해 메모리 낭비가 크다고 했었다.

세그먼테이션도 똑같은 문제점이 발생한다. 왜냐하면 세그먼테이션은 논리적인 단위로 나누기 때문에 세그먼트의 크기가 다양하다. 이로 인해 다양한 크기의 hole이 발생하므로 같은 문제가 발생한다.

결론적으로 세그먼테이션은 보호와 공유에서 효율적이고, 페이징은 외부 단편화 문제를 해결할 수 있다. 그러므로 이 두가지를 합쳐서 사용하는 방법이 나왔다. 두 장점을 합치기 위해서는 세그먼트를 페이징 기법으로 나누는 것이다. (Paged Segmentation)

하지만, 이 역시 단점이 존재한다. 세그먼트와 페이지가 동시에 존재하기 때문에 주소 변환도 두번해야 한다. 즉, CPU에서 세그먼트 테이블에서 주소 변환을 하고, 그 다음 페이지 테이블에서 또 주소 변환을 해야 한다.

페이지 교체 알고리즘

✨ 메모리 과할당(over allocating)

실제 메모리의 사이즈보다 더 큰 사이즈의 메모리를 프로세스에 할당한 상황

페이지 기법과 같은 메모리 관리 기법은 사용자가 눈치 채지 못하도록 눈속임을 통해 메모리를 할당해줌 (가상 메모리를 이용해서)

과할당 상황에 대해서 사용자를 속인 것을 들킬만한 상황이 존재함

프로세스 실행 도중 페이지 폴트 발생
페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
메모리의 빈 프레임에 페이지를 올려야 하는데, 모든 메모리가 사용중이라 빈 프레임이 없음

이러한 과할당을 해결하기 위해선, 빈 프레임을 확보할 수 있어야 함

메모리에 올라와 있는 한 프로세스를 종료시켜 빈 프레임을 얻음
프로세스 하나를 swap out하고, 이 공간을 빈 프레임으로 활용

swapping 기법을 통해 공간을 바꿔치기하는 2번 방법과는 달리 1번은 사용자에게 페이징 시스템을 들킬 가능성이 매우 높아서 하면 안됨

(페이징 기법은 사용자 모르게 시스템 능률을 높이기 위해 선택한 일이므로 들키지 않게 처리해야한다)

따라서, 2번과 같은 해결책을 통해 페이지 교체가 이루어져야 함

✨ 페이지 교체

메모리 과할당이 발생했을 때, 프로세스 하나를 swap out해서 빈 프레임을 확보하는 것

프로세스 실행 도중 페이지 부재 발생
페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
메모리에 빈 프레임이 있는지 확인
빈 프레임이 있으면 해당 프레임을 사용
빈 프레임이 없으면, victim 프레임을 선정해 디스크에 기록하고 페이지 테이블을 업데이트함
빈 프레임에 페이지 폴트가 발생한 페이지를 올리고, 페이지 테이블 업데이트

페이지 교체가 이루어지면 아무일이 없던것 처럼 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야 함

이때, 아무일도 일어나지 않은 것처럼 하려면, 페이지 교체 당시 오버헤드를 최대한 줄여야 함

✨ 오버헤드를 감소시키는 해결법

이처럼 빈 프레임이 없는 상황에서 victim 프레임을 비울 때와 원하는 페이지를 프레임으로 올릴 때 두 번의 디스크 접근이 이루어짐

페이지 교체가 많이 이루어지면, 이처럼 입출력 연산이 많이 발생하게 되면서 오버헤드 문제가 발생함

방법1

변경비트를 모든 페이지마다 둬서, victim 페이지가 정해지면 해당 페이지의 비트를 확인

해당 비트가 set 상태면? → 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 뜻 (즉, 페이지가 메모리 올라온 이후 한번이라도 수정이 일어났던 것. 따라서 이건 디스크에 기록해야함)

bit가 clear 상태라면? → 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황 (즉, 디스크와 내용이 같아서 기록할 필요가 없음)

비트를 활용해 디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대 절반으로 감소시키는 방법임

방법2

페이지 교체 알고리즘을 상황에 따라 잘 선택해야 함

현재 상황에서 페이지 폴트를 발생할 확률을 최대한 줄여줄 수 있는 교체 알고리즘을 사용

FIFO

OPT

LRU

캐시의 지역성

✨ 캐시 메모리

주기억장치에 저장된 내용의 일부를 임시로 저장해두는 기억장치
CPU와 주기억장치의 속도 차이로 성능 저하를 방지하기 위한 방법

CPU가 이미 봤던걸 다시 재접근할 때, 메모리 참조 및 인출 과정에 대한 비용을 줄이기 위해 캐시에 저장해둔 데이터를 활용한다

캐시는 플리플롭 소자로 구성되어 SRAM으로 되어있어서 DRAM보다 빠른 장점을 지님

✨ CPU와 기억장치의 상호작용

CPU에서 주소를 전달 → 캐시 기억장치에 명령이 존재하는지 확인

(존재) Hit

해당 명령어를 CPU로 전송 → 완료

(비존재) Miss

명령어를 갖고 주기억장치로 접근 → 해당 명령어를 가진 데이터 인출 → 해당 명령어 데이터를 캐시에 저장 → 해당 명령어를 CPU로 전송 → 완료

이처럼 캐시를 잘 활용한다면 비용을 많이 줄일 수 있음

따라서 CPU가 어떤 데이터를 원할지 어느정도 예측할 수 있어야 함

(캐시에 많이 활용되는 쓸모 있는 정보가 들어있어야 성능이 높아짐)

적중률을 극대화시키기 위해 사용되는 것이 바로 지역성의 원리

✨ 지역성

기억 장치 내의 정보를 균일하게 액세스 하는 것이 아니라 한 순간에 특정부분을 집중적으로 참조하는 특성

지역성의 종류는 시간과 공간으로 나누어짐

시간 지역성 : 최근에 참조된 주소의 내용은 곧 다음에도 참조되는 특성

공간 지역성 : 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

✨ 캐싱 라인

빈번하게 사용되는 데이터들을 캐시에 저장했더라도, 내가 필요한 데이터를 캐시에서 찾을 때 모든 데이터를 순회하는 것은 시간 낭비다.

즉, 캐시에 목적 데이터가 저장되어있을 때 바로 접근하여 출력할 수 있어야 캐시 활용이 의미있어짐

따라서 캐시에 데이터를 저장할 시, 자료구조를 활용해 묶어서 저장하는데 이를 캐싱 라인이라고 부른다.

즉, 캐시에 저장하는 데이터에 데이터의 메모리 주소를 함께 저장하면서 빠르게 원하는 정보를 찾을 수 있음 (set이나 map 등을 활용)

단편화

✨ 외부 단편화(external fragmentation)

프로그램의 크기보다 분할의 크기가 작은 경우, 해당 분할이 비어있음에도 불구하고 프로그램을 적재하지 못하기 때문에 발생하는 메모리 공간을 말한다.
어떤 프로그램에도 배당되지 않은 빈 공간임에도 현재 상태에서 사용될 수 없는 작은 분할이다.

✨ 내부 단편화(internal fragmentation)

프로그램의 크기보다 분할의 크기가 큰 경우, 해당 분할에 프로그램을 적재하고 남는 메모리 공간을 말한다.
즉, 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각이다.
ex) 메모리 자유 분할 공간이 10,000B가 있고 프로세스 A가 9,999B를 사용하게 되면 2B가 남게 된다. 이러한 현상을 내부 단편화라 한다.

✨ 압축(Compaction)

외부 단편화를 해소하기 위해 프로세스가 사용하는 공간들을 한쪽으로 몰아, 자유 공간을 확보하는 방법론이다.
단점 : 작업 효율이 좋지 않다.

✨ Swapping

메모리에 올라온 프로세스의 주소 공간 전체를 디스크의 스왑 영역으로 일시적으로 내려놓는 것이다. 메모리 공간을 확보하면 이후에 다른 프로세스의 메모리를 불러 들일 수 있다.
주의할 점은 프로세스가 종료되어 주소 공간을 디스크로 내쫓는 것이 아니라 특정한 이유로 수행중인 프로세스의 주소공간을 일시적으로 메모리에서 디스크로 내려놓은 것을 의미한다.
- 스왑인 : 디스크 -> 메모리
- 스왑 아웃 : 메모리 -> 디스크

✨ 연속 할당 방식

각각의 프로세스를 물리적 메모리의 연속적인 공간에 올리는 방식
1. 고정 분할 방식
  - 물리적 메모리를 주어진 개수만큼의 영구적인 분할로 미리 나누고 각 분할에 하나의 프로세스를 적재하여 실행시키는 방식
  - 단편화 문제 발생
2. 가변 분할 방식
  - 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식
  - 외부 단편화 발생

✨ 불연속 할당 방식

하나의 프로세스를 물리적 메모리의 여러 영역에 분산하여 적재하는 방식
1. 페이징
  - 프로세스를 동일한 크기의 페이지로 나눈다.
  - 내부 단편화 문제
2. 세그멘테이션
  - 프로세스를 서로 다른 크기의 논리적 블록 단위인 세그멘테이션으로 나눈다.
  - 외부 단편화 문제

파일 시스템

컴퓨터에서 파일이나 자료를 쉽게 발견할 수 있도록, 유지 및 관리하는 방법이다.

저장매체에는 수많은 파일이 있기 때문에, 이런 파일들을 관리하는 방법을 말한다.

✨ 특징

커널 영역에서 동작
파일 CRUD 기능을 원활히 수행하기 위한 목적
계층적 디렉터리 구조를 가짐
디스크 파티션 별로 하나씩 둘 수 있음

✨ 역할

파일 관리
보조 저장소 관리
파일 무결성 메커니즘
접근 방법 제공

✨ 개발 목적

하드디스크와 메인 메모리 속도차를 줄이기 위함
파일 관리
하드디스크 용량 효율적 이용

✨ 구조

메타 영역 : 데이터 영역에 기록된 파일의 이름, 위치, 크기, 시간정보, 삭제유무 등의 파일 정보
데이터 영역 : 파일의 데이터

✨ 접근 방법

순차 접근(Sequential Access)
가장 간단한 접근 방법으로, 대부분 연산은 read와 write
직접 접근(Direct Access)
특별한 순서없이, 빠르게 레코드를 read, write 가능
기타 접근
직접 접근 파일에 기반하여 색인 구축

✨ 디렉터리와 디스크 구조

1단계 디렉터리

가장 간단한 구조

파일들은 서로 유일한 이름을 가짐. 서로 다른 사용자라도 같은 이름 사용 불가

2단계 디렉터리

사용자에게 개별적인 디렉터리 만들어줌

UFD : 자신만의 사용자 파일 디렉터리
MFD : 사용자의 이름과 계정번호로 색인되어 있는 디렉터리

트리 구조 디렉터리
2단계 구조 확장된 다단계 트리 구조
한 비트를 활용하여, 일반 파일(0)인지 디렉터리 파일(1) 구분
그래프 구조 디렉터리
순환이 발생하지 않도록 하위 디렉터리가 아닌 파일에 대한 링크만 허용하거나, 가비지 컬렉션을 이용해 전체 파일 시스템을 순회하고 접근 가능한 모든 것을 표시
링크가 있으면 우회하여 순환을 피할 수 있음

IPC(Inter Process Communication)

프로세스는 독립적으로 실행된다. 이는 다른 프로세스에게 영향을 받지 않는다는 뜻이기도 하다. (스레드는 프로세스 안에서 자원을 공유하므로 영향을 받는다.)
이처럼 독립적인 공간을 가진 프로세스간 통신에 사용되는 기법이 IPC 통신이다.
프로세스는 커널이 제공하는 IPC 설비를 이용해 프로세스간 통신을 할 수 있게 된다.

PreviousWeb NextNetwork

Last updated 2 years ago