# Operation System

## 프로세스 & 스레드 차이점?
- 프로세스는 메모리상에서 실행중인 프로그램이고, 스레드는 프로세스내에서 프로세스가 할당받은 자원을 사용하는 실행의 단위이다.
- 프로세스는 자원을 공유하지 않는데, 스레드는 스택을 제외한 heap과 data, code를 공유한다.
- 스레드에서 스택을 공유하지 않는 이유는 vo나 scope chain등이 저장되어있기에 독립적인 함수 실행을 위해 공유하지 않는 것이다.
- 공유자원에 대해 동기화를 신경써야한다.

## 멀티 스레드와 멀티 프로세스?
### 멀티 스레드
- 각 스레드가 자신이 속한 프로세스의 메모리를 공유하므로 시스템 자원 낭비가 적다.
- 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있다, 동기화 문제가 있다.
### 멀티 프로세스
- 하나의 프로세스가 죽더라도 다른 프로세스는 영향을 끼치지 않고 정상적으로 수행된다.
- 보다 많은 메모리공간과 CPU시간을 차지한다.

### 따라서 대상 시스템의 특징에 따라 적합한 동작 방식을 선택하자.

## 스케줄러
### 문맥교환이란?
- overhead가 발생하는 주요 원인이다.
- 동작 중인 프로세스가 대기를 하면서 해당 프로세스의 상태를 보관하고, 대기하고 있던 다음 순서의 프로세스가 동작하면서 이전에 보관했던 프로세스의 상태를 복구하는 작업이다.
- 만일 비선점일 경우, 프로세스가 i/o 작업으로 대기상태 중일 때 cpu또한 놀 수 있다. cpu가 놀지 않도록 하고, 사용자에게 빠르게 일처리를 제공하기 위한 것이다.
#### 프로세스가 만들어져 시스템에 존재하는 동안 여러가지 사건들에 의해 일련의 상태변화를 거치게 된다.
### 프로세스를 스케줄링하기 위한 queue
- Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합
- Ready Queue: 현재 메모리 내에 있으면서 CPU를 할당받아 실행되기를 기다리는 프로세스의 집합
- Device Queue: Device I/O 작업을 대기하고 있는 프로세스 집합

## CPU 스케줄러
- 프로세스에 CPU를 할당한다.
- 프로세스 상태
- 준비 -> 실행 -> 대기 -> 준비
- Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정한다.

### FCFS(First Come First Served)
- 먼저 온 순서대로 처리
- 비선점형 스케줄링
- 일단 CPU를 할당받으면 cpu burst 가 완료될 때까지 CPU를 반환하지 않는다.
> cpu burst?
> 만약 어떤 프로세스의 CPU burst time이 10초라고 하면, 이 프로세스의 어떤 특정 작업이 완료되기 위해 CPU가 10초동안 프로세스를 작업해줘야한다는 것

- cpu burst시간이 긴 프로세스가 먼저 도달할 경우 효율성이 떨어진다.
### SJF(Shortest-Job-First)
- 다른 프로세스가 먼저 도착했더라도 CPU burst time이 짧은 프로세스에게 먼저 할당해준다.
- 비선점형 스케줄링
- starvation
- 사용 시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없다는 문제점이 있다.

### SRT(Shortest Remaining time First)
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
- 선점형 스케줄링
- 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏긴다.
- starvation

### priority scheduling
- 우선 순위가 가장 높은 프로세스에게 CPU를 할당한다.
- 선점형으로 하면 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
- 비 선점형일 경우 더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.
- startvation
- 실행 준비는 되어있으나 CPU를 사용하지 못하는 프로세스를 CPU가 무기한 대기하는 상태가 있을 수 있다.
- 따라서 아무리 우선 순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주는 방안으로 해결할 수 있다.

### round robin
- 가장 많이 쓰이는 CPU 스케줄링이다.
- 각 프로세스는 동일한 크기의 할당시간을 갖게 된다.
- 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
- RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다.
- Response time이 빨라진다는 장점이 있다.
- 할당시간이 너무 커지게 되면 FCFS와 같아질 수 있고, 너무 잦아지면 잦은 문맥 교환으로 인한 overhead가 발생할 수 있으므로 적당한 시간을 찾는 것이 중요하다.

## 동기화
### Critical section(임계 영역)
- 동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역
### 해결을 위한 기본 조건
- 상호배제(Mutual Exclusion)
- 프로세스 a가 임계영역에서 실행중이라면, 다른 프로세스들은 그들이 가진 임계 영역에서 실행될 수 없다.
- 임계영역에 있지 않는 프로세스가 다른 프로세스의 임계영역 진입을 막아서도 안된다.
- 비어있는 임계영역에 대한 진입은 바로 허용해야한다.
- 특정 프로세스의 진입 시도가 계속 무산되어 starvation을 겪지 않도록 해야한다.
### 해결방안
#### lock
- 하드웨어 기반 해결책으로, 동시에 공유 자원에 접근하는 것을 막기 위해 임계영역에 진입하는 프로세스는 lock을 획득하고 임계영역을 빠져나올 때 lock을 방출함으로써 동시에 접근할 수 없게 한다.
- 멀티프로세서 환경에서는 효율적이지 않다.
#### 세마포어
- 소프트웨어 기반 임계영역 문제를 해결하기 위한 동기화 도구, 직접 키 해제와 공유자원 접근 처리가 필요하다.
- 카운팅 세마포어
- 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용된다.
- 자원을 사용하면 세마포어가 감소되고, 방출하면 세마포어가 증가한다.
- MUTEX(이진 세마포어)
- 임계 영역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되도록 하는 기술이다.
- lock: 현재 임계 영역에 들어갈 권한을 얻어온다. 만약 다른 프로세스가 임계영역을 수행 중이면 종료할 때까지 대기한다.
- unlock: 현재 임계 영역을 모두 사용했음을 알린다. 대기 중인 다른 프로세스가 임계 영역에 진입할 수 있다.
#### 단점
- 세마포어 초기 버전에서 임계 영역에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야하고, cpu시간을 낭비했다.
- 따라서 이를 해결하여 임계 영역에 진입을 시도했지만 실패한 프로세스에 대해 block을 시긴 뒤,임계영역에 자리가 날 대 다시 깨우는 방식을 사용한다.
#### 모니터
- 고급 언어의 설계 구조물로, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태이다.
- 공유 자원에 접근하기 위한 키 획득과 자원 사용후 해제를 모두 처리한다.

## dead lock이란? 그리고 해결방안?
- 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태이다.
- 네가지 조건을 모두 충족할 때 발생한다.
- 상호배제: 한 자원에 대해 여러 프로세스가 동시에 접근할 수 없다.
- 점유대기: 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
- 비선점: 프로세스가 어떤 자원의 사용이 끝날 때까지 그 자원을 빼앗을 수 없다.
- 순환대기: 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있다.이는 비선점과 점유대기 모두 만족해야 성립한다.
- 또한 4가지가 서로 독립적이지는 않다.
### 해결방안
- 교착 상태 발생 조건 중 하나를 제거함으로 써 해결한다. 자원의 낭비가 심하다.
- 은행원 알고리즘
- 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피한다.
- 자원 할당 그래프를 통해 교착 상태를 탐지할 수 있다. 자원을 요청할 때 마다 탐지 알고리즘을 실행하면 오버헤드 발생
- 교착 상태를 일으킨 프로세스를 종료한다.

## 메모리 관리 전략
### 단편화
| `Process A` | free | `Process B` | free | `Process C` |             free             | `Process D` |
| ----------- | ---- | ----------- | ---- | ----------- | :--------------------------------------------------------------------------------------: | ----------- |
- 외부 단편화: 메모리 공간 중 분할 크기자체가 매우 작아서 프로세스들을 수용하지 못한다.
- 내부 단편화: 분할 내에 프로세스를 수용하고 남는 공간.

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

| `Process A` | `Process B` | `Process C` | `Process D` |                free                |
| ----------- | ----------- | ----------- | :---------: | ------------------------------------------------------------------------------------------------------------------ |

### 페이징
- 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 관리 방법이다. 외부 단편화와 압축 작업을 해소 하기 위해 생긴 방법론이다.
- 물리 메모리는 frame이라는 고정 크기로 분리되어 있고, 논리 메모리는 페이지라 불리는 고정 크기의 블록으로 분리된다.
- 페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨으로써 외부 단편화를 해결할 수 있다는 장점이 있다.
- 즉, 하나의 프로세스가 사용하는 공간은 여러개의 페이지로 나뉘어서 관리되고, 개별 페이지는 순서에 상관 없이 물리 메모리에 있는 프레임에 매핑 되어 저장된다.
- 그러나 내부 단편화 문제의 비중이 늘어난다.
- 1024B(페이지 크기) * 4 - (프로세스 a가 요구하는 메모리)3172B = 924B
- 924B가 남는다.

### 세그멘테이션

- 논리 메모리와 물리메모리를 같은 크기의 블록이 아닌, 서로 다른 크기의 논리적 단위인 세그먼트로 분할한다. 프로세스를 세그먼트의 집합으로 생각한다.
- 메모리에 할당하는 방법에 대해서는 페이징과 방법이 같다.
- 페이징은 프로세스를 같은 단위로 자르게 되므로 중요한 부분과 중요하지 않은 부분이 같은 페이지 안으로 잘라질 수 있다. 또한 코드 영역 또한 같은 단위로 잘리므로 애매하게 잘려질 확률이 있다. 하지만 세그먼테이션의 방법으로 자르게 되면 코드 영역은 코드 영역으로 잘리게 되고 중요한 세그먼트, 중요하지 않은 세그먼트를 논리적인 내용 측면으로 자를 수 있다.
- 세그먼트는 크기가 고정되어 있지 않고 가변적이다. 크기가 다른 각 세그먼트를 메모리에 두려면 동적 메모리 할당을 해야 한다. 크기가 다른 세그먼트 하나가 swap in이 되었는데 그 크기가 매우 작아서 다른 세그먼트를 수용하지 못할 수 있다. 따라서 외부 단편화가 발생할 수 있다.

## 가상 메모리
- 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법
- 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.
- 불필요하게 프로그램 전체가 메모리에 올라와 있어야하는 게 아니라는 것을 알 수 있다.

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

### 장점
- 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다.
- 프로세스들이 메모리를 공유하는 것을 가능하게하고 프로세스들은 공유 메모리를 통해 통신할 수 있다.
- 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

### 요구 페이징
- 프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략
- 가상 메모리는 보통 페이지로 관리된다.
- 요구 페이징을 사용하는 가상메모리에서는 실행 과정에서 필요해질 때 페이지들이 적재된다. 한번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.
- 프로세스 내의 개별 페이지들은 페이저에 의해 관리된다.
- 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어옮으로써, 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 줄일 수 있다.
- 하지만 해당 페이지 부재에 대해 페이지가 적재될 때까지 해당 프로세스를 대기 상태로 만드는 문맥교환과 디스크와의 입출력 부담이 있다.

### 페이지 교체
- 프로그램 실행시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 페이지 부재가 발생하면 원하는 페이지를 보조저장 장치에서 가져온다.
- 만약 물리 메모리가 모두 사용중인 상황에서 페이지 교체가 이뤄져야 한다.

#### 물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름
1. 디스크에서 필요한 페이지 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
1) 페이지 교체 알고리즘을 통해 희생될 페이지를 고른다.
2) 희생될 페이지를 디스크에 기록하고 관련 페이지 테이블을 수정한다.
3. 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
4. 사용자 프로세스 재시작

### 페이지 교체 알고리즘

#### FIFO 페이지 교체
- 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다.
- 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다.
- 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.
- 페이지를 저장할 수 있는 페이지 프레임 갯수를 늘렸는데 오히려 페이지 부재가 더 많이 발생할 수 있다.

#### 최적 페이지 교체(optimal page replacement)
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체한다.
- 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없으므로 구현이 어렵다.
### LRU 페이지 교체(least-recently-used)
- 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.
### LFU 페이지 교체(least frequently used)
- 참조 횟수가 가장 적은 페이지를 교체한다.
- 어떤 프로세스가 특정 페이지를 집중적으로 사용하다가 다른 기능을 사용하게 되면 더이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다.
### MFU 페이지 교체(most frequently used)
- 많이 참조된 페이지는 충분히 참조가 이루어졌으므로 더이상 참조되지 않을 것이라는 판단에 근거하여 가장 참조가 많이된 페이지를 교체한다.
- 잘 안쓰인다.

# 인터럽트
## 정의
프로그램을 실행하는 도중에 예기치 않은 상황이 발생할 경우 현재 실행 중인 작업을 즉시 중단하고, 발생된 상황을 우선 처리한 후 실행 중이던 작업으로 복귀하여 계속 처리하는 것

지금 수행 중인 일보다 더 중요한 일(ex. 입출력, 우선 순위 연산 등)이 발생하면 그 일을 먼저 처리하고 나서 하던 일을 계속해야한다.

외부/내부 인터럽트는 CPU의 하드웨어 신호에 의해 발생

소프트웨어 인터럽트는 명령어의 수행에 의해 발생

## 외부 인터럽트
입출력 장치, 타이밍 장치, 전원 등 외부적인 요인으로 발생

전원 이상, 기계 착오, 외부 신호, 입출력

## 내부 인터럽트
Trap이라고 부르며, 잘못된 명령이나 데이터를 사용할 때 발생

0으로 나누기가 발생, 오버플로우, 명령어를 잘못 사용한 경우 (Exception)

## 소프트웨어 인터럽트
프로그램 처리 중 명령의 요청에 의해 발생한 것 (SVC 인터럽트)

사용자가 프로그램을 실행시킬 때 발생

소프트웨어 이용 중에 다른 프로세스를 실행시키면 시분할 처리를 위해 자원 할당 동작이 수행된다.

## 인터럽트 발생 처리 과정

주 프로그램이 실행되다가 인터럽트가 발생했다.

현재 수행 중인 프로그램을 멈추고, 상태 레지스터와 PC 등을 스택에 잠시 저장한 뒤에 인터럽트 서비스 루틴으로 간다. (잠시 저장하는 이유는, 인터럽트 서비스 루틴이 끝난 뒤 다시 원래 작업으로 돌아와야 하기 때문)

만약 인터럽트 기능이 없었다면, 컨트롤러는 특정한 어떤 일을 할 시기를 알기 위해 계속 체크를 해야 한다. (이를 폴링(Polling)이라고 한다)

폴링을 하는 시간에는 원래 하던 일에 집중할 수가 없게 되어 많은 기능을 제대로 수행하지 못하는 단점이 있었다.

즉, 컨트롤러가 입력을 받아들이는 방법(우선순위 판별방법)에는 두가지가 있다.

### 폴링 방식
사용자가 명령어를 사용해 입력 핀의 값을 계속 읽어 변화를 알아내는 방식

인터럽트 요청 플래그를 차례로 비교하여 우선순위가 가장 높은 인터럽트 자원을 찾아 이에 맞는 인터럽트 서비스 루틴을 수행한다. (하드웨어에 비해 속도 느림)

### 인터럽트 방식
MCU 자체가 하드웨적으로 변화를 체크하여 변화 시에만 일정한 동작을 하는 방식

- Daisy Chain
- 병렬 우선순위 부여

인터럽트 방식은 하드웨어로 지원을 받아야 하는 제약이 있지만, 폴링에 비해 신속하게 대응하는 것이 가능하다. 따라서 실시간 대응이 필요할 때는 필수적인 기능이다.

즉, 인터럽트는 발생시기를 예측하기 힘든 경우에 컨트롤러가 가장 빠르게 대응할 수 있는 방법이다.