Agapang

1. 프로세스(Process)
프로세스(Process) = 작업(Job) = 태스크(Task)
: 실행중인 프로그램
: PCB를 가진 프로그램
: 프로세서가 할당되는 실체, 디스패치가 가능한 단위
: 프로시저가 활동중인 것
: 비동기적 행위를 이르키는 주체
: 목적 또는 결과에 따라 발생되는 사건들의 과정
: 운영체제가 관리하는 실행단위

- 프로시저 : 한 프로그램은 여러 개의 작은 프로그램으로 분리될 수 있는데, 이때 분할된 작은 프로그램을 의미, 부 프로그램이라고도 한다
- 비동기적 행위 : 다수의 프로세스가 서로 규칙적이거나 연속적이지 않고 독립적으로 실행되는 것
- 디스패치 : 준비 상태에서 실행 상태로 전이되는 과정

- PCB (Process Control Block) - 프로세스 제어 블록
: 운영체제가 프로세스에 대한 중요한 정보를 저장해 놓는 블록
: 각 프로세스가 생성될 때마다 고유의 PCB가 생성되고, 프로세스가 완료되면 PCB는 제거
- PCB에 저장되어 있는 정보
: 프로세스의 현재상태
: 포인터 - 부모, 자식 프로세스에 대한 포인터, 프로세스가 위치한 메모리에 대한 포인터,     할당된 자원에 대한 포인터
: 프로세스 고유 식별자
: 스케쥴링 및 프로세스 우선순위
: CPU 레지스터 정보 - 누산기, 인덱스 레지스터, 범용 레지스터, PC 등에 대한 정보
: 주기억장치 관리 정보 - 베이스 레지스터, 페이지 테이블에 대한 정보
: 입, 출력 상태 정보
: 계정 정보 - CPU 사용시간, 실제 사용시간, 한정된 시간
: 부모 프로세스와 자식 프로세스도 PCB를 공유하지 않는다

- 프로세스 상태 전이
: 프로세스가 시스템 내에 존재하는 동안 프로세스의 상태가 변하는 것을 의미


- 준비(Ready): 프로세스가 프로세서를 할당 받기 위해 기다리고 있는 상태
- 실행(Run): 준비상태 큐에 있는 프로세스가 할당 받아 실행되는 상태
- 대기(Block): 입출력 처리가 필요하면 현재 실행중인 프로세스가 중단되고 입출력이 완료    될 때 가지 대기하는 상태
: 대기단계가 끝나면 다시 실행단계로 가지 않고 준비단계로 간다
: 할당 받은 시간이 모두 소진되면 작업 중이여도 Time Out후 다시 Dispatch된다.


- 스레드(Thread)
: 프로세스 내에서의 작업 단위
: 하나의 프로세스에 하나의 스레드가 존재하면 단일 스레드
: 하나 이상의 스레드가 존재하면 다중 스레드
: 독립적인 스케쥴링의 최소단위로 프로세스의 역할을 담당
: 경량 프로세스라고도 함
: 스레드는 동일 프로세스 환경에서 서로 독립적인 다중 수행 가능

- 스레드 분류
: 사용자 수준의 스레드 - 사용자가 만든 라이브러리를 이용하여 스레드 운용, 속도는 빠르지만 구현이 어렵다
: 커널 수준의 스레드 - 커널에 의해 스레드 운용, 구현은 쉽지만 속도가 느리다

- 스레드 사용의 장점
: 하나의 프로세스를 여러 개의 스레드로 생성하여 병행성 증진
: 하드웨어, 운영체제의 성능과 응용 프로그램의 처리율을 향상
: 응답 시간 단축
: 프로세스들 간의 통신이 향상


2. 스케줄링
- 스케줄링(Scheduling)
: 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에 할당작업

- 스케줄링의 종류
1. 장기 스케쥴링 : 어떤 프로세스가 시스템 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업, 작업 스케줄링
2. 중기 스케쥴링 : 어떤 프로세스들이 CPU를 할당 받을 것인지 결정하는 작업
3. 단기 스케쥴링 : 프로세스가 실행되기 위해 CPU를 할당 받는 시기와 특정 프로세스를 지정하는 작업 , 프로세스 스케줄링

- 스케줄링의 목적
: 공정성, 처리율 증가, CPU 이용률 증가
: 우선순위 제도, 오버헤드 최소화, 응답 시간 최소화, 반환 시간 최소화
: 대기시간 최소화, 균형 있는 자원의 사용, 무한 연기 회피

- 스케줄링 성능 평가 기준
: CPU 이용률, 처리율 , 반환시간, 대기시간, 응답시간

- 프로세서 스케줄링 기법



1. 비선점(Non-preemptive) 스케줄링 - 일괄 처리 방식에 적합
: 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗을 수 없는 스케줄링 기법
: 모든 프로세스를 공정하게 처리 가능
: 프로세스 응답 시간의 예측이 용이, 일괄 처리 방식에 적합
: 중요한 작업(짧은 시간)이 중요하지 않은 작업(긴 시간)을 기다리는 경우 발생
: 비선점 스케줄링 종류 - FCFS, SJF, HRN, 우선순위 등의 알고리즘

- FCFS(First Come First Service, 선입 선출) = FIFO
: 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법
: 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 그렇지 않은 작업을 기다림

- SJF(Shortest Job First, 단기 작업 우선)
: 준비상태 큐에서 기다리고 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
: 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘

- HRN(Highest Response-ratio Next)
: 실행 시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로, 우선 순위 계산 공식을 이용하여 서비스(실행) 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선 순위를 주어 CPU에 할당
: 우선순위 계산식 = 대기시간 + 서비스 시간 / 서비스 시간 (!)

- 기한부(Deadline)
: 프로세스에게 일정한 시간을 주어 그 시간안에 프로세스를 완료하도록 하는 기법
: 프로세스가 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행
: 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며, 프로세스 실행시 집중적으로 요구되는 자원 관리에 오버헤드가 발생

- 우선순위(Priority)
: 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 가장 높은 프로세스에 CPU를 할당하는 기법
: 우선순위가 동일할 경우 FCFS기법으로 CPU할당
: 가장 낮은 우선순위 프로세스는 무한연기 또는 기아상태가 발생할 수 있다
: 에이징 기법 - 시스템에서 우선 순위가 낮아 무한정 기다리게 되는 경우, 한 번 양보하거나 기다린 시간에 비례하여 우선 수누이를 한 단계씩 높여 자원을 할당하는 기법




2. 선점(Preemptive) 스케줄링 - 대화식 시분할 시스템에 적합
: 하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법
: 우선 순위가 높은 프로세스를 빠르게 처리할 수 있다
: 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용
: 많은 오버헤드를 초래
: 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 블록이 필요
: 선점 스케줄링 종류 - RR(라운드 로빈), SRT, 다단계 큐, 다단계 피드백 큐 등의 알고리즘

- RR(Round Robin)
: FCFS알고리즘을 선점 형태로 변환 한것. 시분할 시스템을 위해 고안
: 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당 받지만 각 프로세스는 시간 할당향 동안만 실행한후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치
: 할당시간이 클수록 FCFS와 같아지고, 할당시간이 적을경우 문맥교환 및 오버헤드 증가

- SRT(Shortest Remaining Time)
: SJF 기법을 선점 형태로 변환한 기법 . 선점 SJF라고도 한다
: 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에 CPU 할당

- 선점 우선 순위
: 비선점 우선순위 기법을 선점 형태로 변경한 것
: 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당

- 다단계 큐(MQ: Multi-level Quene)
: 프로세스를 특정 그룹으로 분류해 그룹에 따라 각기 다른 준비상태 큐를 사용
: 일반적으로 프로세스의 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 준비상태 큐를 상위, 중위, 하위 단계로 배치
: 각 준비상태 큐는 독자적인 스케줄링을 가지고 있고, 각 그룹의 특성에 따라 서로 다른 스케줄링을 사용
: 프로세스가 특정 구룹의 준비상태 큐에 들어갈 경우 다른 큐로 이동할 수 없다.


- 다단계 피드백 큐(MFQ)
: 다단계 큐와 달리 다른 준비단계의 큐로 이동할 수 있게 개선한 기법
: 각 준비상태 큐마다 시간 할당량을 부여하고 완료 못하면 다음 단계의 준비큐로 이동
: 상위 단계 일수록 우선순위가 높고 시간 할당량은 적다
: 낮은 우선순위에서 너무 오래기다린 프로세스를 기준으로 높은 우선 순위를 할당
: 하위 단계 프로세스가 실행중이더라도 상위 단계 프로세스가 들어오면 상위 단계에 CPU를 할당하고, 마지막 단계 큐에서는 작업이 완료도리 때까지 RR기법 사용




3. 병행 프로세스와 상호 배제
- 병행 프로세스(Concurrent Process)
: 두 개 이상의 프로세스들이 동시에 존재하며 실행 상태에 있는 것을 의미
: 다중 처리 시스템이나 분산 처리 시스템에서 중요한 개념으로 사용

- 임계 구역(Critical Section)
: 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로세스만 자원을 사용하도록 지정된 공유 자원을 의미
: 임계 구역은 하나의 프로세스만 접근 가능
: 특정 프로세스가 독점할 수 없으며, 임계 영역에서 수행 중인 프로세스는 인터럽트 불가능
: 공유자원 - CPU, 메모리, 디스크, 입출력장치, 버퍼 등

- 상호 배제(Mutual Exclusion)
: 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법
: 임계 구역을 유지하는 기법
: 소프트웨어적 구현 방법
 - 두개의 프로세스 기준: 데커 알고리즘, 피터슨 알고리즘
 - 여러 개의 프로세스 기준: Lamport의 빵집 알고리즘
: 하드웨어적 구현 방법
 - Tast & Set 기법, Swap 명령어 기법

- 동기화 기법(Synchronization)
: 두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 것. 상호 배제의 한 형태

- 세마포어(Semaphore)
: '신호기', '깃발'을 뜻하며, 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행유도
: 다익스트라가 제안, P와 V라는 두개의 연산에 의해서 동기화가 유지, 상호 배제의 원리를 보장
: S는 P와 V연산으로만 접근 가능한 세마포어 변수로, 공유 자원의 개수를 나타내며 0과 1 또는 0과 양의 값을 가질 수 있다

- 모니터(Monitor)
: 동기화를 구현하기 위한 특수 프로그램 기법으로 특정 공유 자원을 프로세스에게 할당하는 데 필요한 데이터와 이를 처리하는 프로시저로 구성
: 자료 추상화와 정보 은폐 개념을 기초로 하며, 공유 자원을 할당하기 위한 병행성 구조로 이루어짐
: 모니터 내의 공유 자원을 사용하려면 반드시 모니터의 진입부를 호출해야한다
: 외부의 프로시저는 직접 엑세스할 수 없다.
: 모니터의 경계에서 상호 배제가 시행된다
: 모니터에는 한 순간에 하나의 프로세스만 진입하여 자원을 사용
: Wait 와 Signal 연산이 사용



4. 교착상태(Dead Lock)
- 교착상태
: 상호 배제에 의해 나타나는 문제점, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미

- 교착상태 발생의 필요 충분 조건
1. 상호 배제(Mutual Exclusion)
: 한번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다
2. 점유와 대기(Host and Wait)
: 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다
3. 비선점(Non-preemption)
: 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없어야 한다
4. 환형 대기(Circular Wait)
: 공유 자원을 사용하기 위해 대기하는 프로세스들이 원 형태로 구성되어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구


- 교착상태 해결 방법
1. 예방 기법(Prevention)
: 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법
: 교착상태 발생의 4가지 조건중 하나를 제거함으로써 수행, 자원의 낭비가 가장 심한 기법
: 상호 배제 부정, 점유 및 대기 부정, 비선점 부정, 환형 대기 부정

2. 회피 기법(Avoidance)
: 교착상태가 발생할 가능성을 배제하지 않고, 적절히 피해나가는 방법
: 주로 은행원 알고리즘을 사용
: 은행원 알고리즘 - 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전 상태, 교착 상태가 발생할 수 있는 상태를 불완전 상태라고 한다.

3. 발견 기법(Detection)
: 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미

4. 회복 기법(Recovery)
: 교착 상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미


* 버퍼링 - 보조 기억장치 이용
* 스풀링 - 주 기억장치 이용