[OS] 02. 프로세스와 스레드 관리

(1) 개요

CPU는 컴퓨터 자원 중 가장 중요한 자원이다.

 

프로세스 스케줄링

• *준비 완료(ready) 상태에 있는 프로세스들 중 어떤 프로세스를 CPU에 할당할 것인가를 결정하는 정책이다.
• CPU의 *처리량(Throughput)최대화와 *반환시간(Turnaround Time)의 최소화를 목표로 한다.

*ready state : Main Memory에 올라와 있지만 CPU를 할당받지 못한 상태

*처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수

*반환시간 : 각 프로세스가 시작해서 끝날 때까지 걸리는 시간

(2) 프로세스 관리

프로세스의 다양한 정의

• 실행(Executing Running)중인 프로그램 = 메모리에 로드된 프로그램
• PCB(Process Control Block)를 지닌 프로그램
• 프로그램 카운터(Program Counter)를 지닌 프로그램

OS의 프로세스 관리 기능

• 사용자 프로세스 및 시스템 프로세스 생성과 삭제
• 프로세스의 일시 중지(suspend)와 재수행(redo)
• 프로세스 스케줄링(어떤 프로세스에 CPU를 할당할 것인가?)
• 프로세스 동기화(2개 이상의 프로세스들 간의 동기화는 어떻게?)
• 프로세스 간 통신(2개 이상의 프로세스들 간의 통신은 어떻게?)
• 교착상태 처리(2개 이상의 프로세스 간에 꽉 막힌 문제는 어떻게?)

(3) 프로세스 구성 요소

프로그램이 실행되기 위해서는 반드시 실행되기 전에 주기억장치(메인 메모리)에 로드 되어야 한다.

• 주기억 장치에 로드된 프로그램 -> 프로세스(Process)

주기억장치에 저장되는 프로세스의 구성 요소

• Code 영역 : 프로그램 코드 자체(CPU가 해석할 수 있는 바이너리 코드 상태), 실행 명령어 코드(집합)
• Data 영역 : 프로그램의 전역 변수(Global variable)나 정적 변수(Static variable)할당
• Stack 영역 : 지역 변수(Local variable)와 함수(메소드) 호출 시 전달되는 인수를 위한 공간
• Heap 영역 : 메모리의 동적 할당을 위한 공간

구성 요소

실행 명령어코드 (코드 영역)

전역변수 / 정적변수 (데이터 영역)

동적 할당 (힙 영역)

. . .

지역변수 / 전달인수 (스택 영역)

 

(4) Process State

• 준비(완료)상태 (Ready State) : CPU 사용이 가능한 상태, 즉 CPU를 할당 받을 수 있는 상태, 혹은 CPU가 프로세스 자신을 처리해 주기를 기다리고 있는 상태이다.
• 실행 상태(Running State) : 프로세스가 CPU를 할당 받아서 사용하고 있는 상태
• 대기 상태(Block State) : 프로세스가 CPU를 양도(반납)하고, 입출력(I/O)을 처리하고 있는 상태

실행 상태에서는 프로세스 처리가 끝날수도, 시간이 다 돼서 돌아갈수도 아니면 입출력할 수도 있는 3가지 기능이 있다.

 

프로세스의 상태 전환

• 준비 상태 -> 실행 상태 (Dispatch)
• 실행 상태 -> 준비 상태 (Timer Runout, 시간이 다 됨)
• 실행 상태 -> 대기 상태 (Block, CPU 반납하고 입출력 수행)
• 대기 상태 -> 준비 상태 (Wakeup , 입출력 완료하고 준비 상태로)

프로세스 스케줄러 내의 Traffic Controller(트래픽 제어기)가 프로세스의 상태를 전환한다.

(5) Process Control Block(PCB)

• 프로세스 제어 블록으로 Process Descriptor(프로세스 설명)라고도 한다.
• 운영체제가 프로세스에 관한 정보를 유지 관리하기 위하여 이용하는 자료구조이다.
• 프로세스에 관련된 정보를 가지고 있는 데이터 구조(테이블 구조)이다.
• 각 Process는 자기만의 PCB를 가지고 있다. 즉, 모든 Process가 PCB를 가지고 있다.
• 프로세스 생성 시에 만들어지고, 수행 완료 시에 삭제된다. 또한 프로세스 스케줄러 내의 Traffic Controller에 의하여 내용이 수정될 수 있다.

구성 형태(PCB에 포함되는 정보)

• 프로세스의 현재 상태(준비, 실행, 대기)
• 프로세스의 고유 id(identifier)
• 프로세스의 우선순위
• 프로세스가 적재된 기억장치의 주소를 가리키는 포인터
• 프로세스에 할당된 자원(장치)등을 가리키는 포인터
• CPU 내에 있는 각종 레지스터의 상태 정보를 저장하기 위한 공간
• 프로그램 카운터(프로세스 내에서 다음에 실행해야 할 명령어의 주소)

※ CPU도 자체적으로 메모리를 일부 가지고 있다 -> Register(입출력 속도가 빠름)

(6) Process Scheduling

목적

1) 공정성 (무한 대기 방지)
2) 처리 능력 최대화 (단위 시간 내에 최대한의 프로세스 수행)
3) 응답 시간의 최소화 (사용자에 대한 빠른 응답)
4) 예측 가능 (동일 프로세스는 거의 같은 비용 및 시간 내에 수행되어야 함)
5) overhead의 최소화 (낭비되는 자원 최소화)
6) 자원 사용의 균형 유지
7) 빠른 응답과 자원 이용 간의 균형 유지 (효과적인 자원 활용 VS 실시간 시스템)
8) 실행의 무한한 지연을 피할 것
9) 우선순위제 실시
10) 즈요 자원들을 차지하고 있는 프로세스에게 우선권 부여
11) 좀 더 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스 제공
12) 시스템의 과중한 부하 감소

이러한 스케줄링의 목적들 간의 상호 충돌이 발생할 수 있어 스케줄링이 복잡해진다.

 

▶ 방식별 분류 ◀

☐ Non Preemptive scheduling

• 하나의 프로세스에 CPU가 할당되면 그 프로세스의 수행이 끝날 때까지 CPU는 그 프로세스로부터 빠져 나올 수 없다.
• 응답 시간 예측이 가능하나 짧은 작업의 프로세스가 긴 작업의 프로세스를 기다리는 경우가 종종 발생하게 된다.
• 일괄 처리 시스템이 이 알고리즘을 써야 한다.

Ex) Priority, FCFS, SJF, HRN

 

☐ Preemptive scheduling

• 하나의 프로세스가 CPU를 차지하고 있을 때 다른 프로세스가 현재 수행 중인 프로세스를 중지시키고 CPU를 차지할 수 있다.
• 우선순위가 높은 프로세스를 먼저 수행할 때 유리하다.
• 실시간 시스템 또는 시분할 시스템에서 빠른 응답 시간이 보장 가능하다.
• 하지만 이전에 수행되던 프로세스의 정보(context)를 별도로 유지 관리해 두어야 하는 오버헤드(부담)가 발생할 수 있고 또는 너무 많은 선점 시에 context switching(문맥 교환)부담도 발생할 수 있다.

Ex) Priority, SRT, Round-Robin, Multilevel Queue/Feedback Queue

1. Priority scheduling

• non preemptive, preemptive 이 두 가지 방식으로 구현이 가능하다.
• 우선순위가 각 프로세스에게 주어지며, CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.
  • 내부적 요인(제한시간, 메모리 요구량, 개방된 파일의 수, etc)과 외부적 요인(프로세스 중요성, 사용 부서 등의 정책적 요인)을 이용하여 우선순위를 할당할 수 있다.
• 그러나 낮은 우선순위의 프로세스들이 CPU를 할당받지 못하는 경우 계속 대기해야 돼서 indefinite blocking(무한 대기) or starvation(기아 현상)이 발생할 수 있다.
• 위의 문제점을 보완하기 위해서 *Aging 기법을 사용해 해결 가능하다.

*Aging기법 : 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 시간이 지남에 따라 점진적으로 증가시킨다.

• 각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순대로 처리하는 방법으로 정적 우선순위 기법과 동적 우선순위 기법이 있다.
  • static priority : 상대적으로 오버헤드는 적으나, 주위 여건의 변화에 적응하지 못하고 우선순위를 바꾸지 않는다.
  • dynamic priority : 필요에 따라 우선순위를 재구성하거나 주변 상황 변화에 잘 적응하지만, 복잡하고 오버헤드가 많아진다.

2. Deadline scheduling

• 작업들이 명시된 시간이나 기한 내에 완료되도록 계획하는 스케줄링이다.
• 실시간 시스템에 유효하게 적용 가능하나, 실제 적용에는 많은 어려움이 있다.
  • 사용자는 사전에 작업이 요구하는 정확한 자원을 제시해야 한다.
  • 다른 사용자 작업에 영향을 미치지 않고 기한부 작업을 수행해야 한다.
  • 기한까지 작업을 끝내기 위하여 자원 배분을 신중히 해야 한다.
  • 많은 수의 기한부 작업이 동시에 실행하는 경우, 스케줄링이 너무 복잡해진다.
  • 기한부 스케줄링에 따른 집중적 자원 운영은 많은 오버헤드를 발생시킨다.

방식(Real-Time System Scheduling)

• Static Sheduling : 시스템에 의해 실행되는 작업 집합이 미리 정의되어 있는 경우
  Ex) Rate Monotonic(RM) Algorithm : 대표적인 정적 스케줄링 방식으로, 작업 주기가 짧을수록 더 높은 우선순위를 부여한다.
• Dynamic Scheduling : 작업의 발생 시간이나 특성을 미리 예측할 수 없을 경우에 유용하며, 보장된 주기의 시간 내에 서비스를 보장한다.
  Ex) Earliest-Deadline First(EDF) Algorithm : 대표적인 동적 스케줄링 방식으로, 임계 시간이 가장 근접한 태스크를 가장 먼저 수행하는 방식이다.

3. Multiple Processor scheduling

프로세서들(CPU)의 형태가 동일한 동질 시스템 또는 서로 다른 이질 시스템이 존재한다.

 

이질 시스템

• 각 프로세서는 자신의 프로세스를 위한 Ready Queue가 각각 있으며 자신만의 스케줄링 알고리즘을 가지게 된다.

동질 시스템

• 프로세서(CPU)들이 동질일 경우 load balancing(로드 밸런싱)을 수행해야 한다.
• 동질 시스템에서의 두 가지 스케줄링 방식
  • 각 프로세서(CPU)가 스스로 스케줄링하며, 공동 준비 큐를 조사하여 실행할 프로세스를 선택한다.
  • 한 프로세서가 다른 프로세서를 위한 스케줄러로서 지정되어 master slave structure(주종 구조)를 구성한다.

*이질 : CPU가 다른 것

*동질 : 하나의 Queue에 여러 개의 CPU가 연결된 것

4. First Come First Served(FCFS) scheduling

• non preemptive 방식으로 구현하고 가장 간단한 스케줄링 알고리즘이다.
• 프로세스들이 준비 상태의 큐에 도착한 순서에 따라 CPU를 할당 받는다.
• 다른 알고리즘에 비해 작업 완료시간을 예측하기가 용이하지만, 특정 프로세스에 대하여 빠른 응답 시간 보장이 안 된다.
• 긴 작업이나 중요하지 않은 작업이 짧은 작업이나 중요한 작업을 오랫 동안 기다리게 할 수 있다.
  • convoy effect(호위 효과) : 먼저 도착한 프로세스가 CPU에서 수행되는 버스트 시간이 매우 길면, 그 다음 도착한 프로세스가 첫번째 프로세스가 끝날 때까지 매우 긴 시간을 기다리게 되는 현상

• *평균 대기 시간과 *평균 반환 시간을 Gantt chart(간트 차트)를 이용해 성능 평가를 하면 비효율적이라는 것을 확인할 수 있다. 그래서 잘 사용하지 않는다.

*평균 대기 시간 : 큐에서부터 CPU로 받기 직전의 시간, CPU를 받기 위해서 대기하는 시간

*평균 반환 시간 : 프로세스가 완전히 끝나는 시간

5. Shortest Job First(SJF) scheduling

• non preemptive 방법으로 구현하고, 프로세스 중에서 수행시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링이다.
• FCFS를 보완한 것으로 보다 평균 대기시간을 감소시킨다.
• 문제점은 수행될 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데 이 정보를 얻기가 어렵다.
  • 사용자가 제공하는 정보에 의존하고, 부정확한 정보나 거짓 정보의 위험이 존재한다.

6. Shortest Remaining Time(SRT) scheduling

• preemptive 방법으로 구현하고, SJF방법에 선점 방식을 도입한 것이다.
• 새로 도착한 프로세스를 포함하여 처리가 완료되는 데 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다.
  • 실행중인 프로세스라도 남은 처리시간이 더 짧다고 판단되는 프로세스가 큐에 들어오면 언제라도 실행중인 프로세스가 선점된다.
  • 수행중인 각각의 작업들에 대한 실행시간을 추적 보유해야 한다.(overhead)
• SRT는 도착시간이 필요함.

계산할 때 복잡하므로 표를 작성해서 평균 대기 시간과 평균 반환시간을 구한다.

7. Round-Robin scheduling

• preemptive 방법으로 구현하고, 시분할 시스템을 위하여 고안된 선점 스케줄링 방식이다.
• 각 프로세스는 순서대로 같은 크기의 CPU 시간을 할당 받으며, 할당 시간 내에 완료되지 못하면 준비 큐의 가장 뒤로 보내진다.
  • CPU time quantum(할당 시간)의 크기는 보통 10에서 100ms 사이다.

• 할당 시간이 너무 큰 경우 : FCFS 방식과 똑같이 동작한다. (한번의 CPU 할당에 프로세스가 완료된다.)
• 할당 시간이 너무 작은 경우 : context switching을 위한 overhead가 크게 발생하고, 결과적으로 대부분의 시간이 CPU를 할당하는데 소모된다.

• CPU 할당시간에 따른 문맥 교환 (Context Switching) 횟수
  • CPU 할당시간이 각각 11ms, 8ms, 2ms로 결정되는 경우

8. Multilevel Queue scheduling

• preepmtive방법으로 구현하고, 다단계 큐 스케줄링 알고리즘은 프로세스들을 위한 준비 큐를 다수의 별개 큐로 구분하여 스케줄링한다.
• 기억장치의 요구량이나 프로세스의 우선순위 혹은 프로세스의 유형과 같은 프로세스의 특성에 근거해 프로세스들은 해당 큐에 진입하게 된다.
  • 각 큐는 자신의 스케줄링 알고리즘을 가지고 있는데, 예를 들어 대화형 작업을 위한 큐는 라운드 로빈 스케줄링 알고리즘을 적용하고, 일괄처리 작업을 위한 큐는 FCFC 스케줄링 알고리즘을 적용한다.
• 일괄처리 작업이 실행 중일 지라도 상위 단계 큐에 작업이 들어오면 일괄처리 작업은 상위 단계 프로세스 작업에 의하여 CPU를 선점당한다.

9. Multilevel Feedback Queue scheduling

• preemptive방법으로 구현하고, 프로세스들은 CPU의 사용시간에 따라 입출력 위주와 CPU위주 프로세스로 구분되는데 이를 기준으로 서로 다른 CPU 할당시간을 부여할 필요가 있다.
• 새로운 프로세스는 Queueing network의 단계1큐에 추가되어, 그 프로세는 FCFS에 의하여 CPU를 할당 받는다.(높은 우선 순위 배정)
• 프로세스가 끝나기 전에 할당된 시간이 만료되거나 입출력 등으로 인하여 CPU를 양도한다면 그 프로세스는 그 다음 하위 단계의 큐로 이동되어 순서를 기다린다.
• 마지막 단계의 큐에서는 그 프로세스가 완료될 때까지 round-robin 방식으로 스케줄링 된다.

스케줄링 기준

• 짧은 작업에 유리
• 효율적인 입출력 장치 이용을 위하여 입출력 위주 프로세스에 우선권 제공
• 가능한 한 빨리 작업의 특성을 알고 그에 맞게 스케줄링을 변경
• 대부분의 다단계 피드백 체계에서는 프로세스가 하위 단계의 큐로 옮겨갈수록 주어지는 CPU 할당 시간을 크게 설정한다.

---

10. High Response ratio Next(HRN) scheduling

• non preemptive방법으로 구현하고, 일단 한 작업이 CPU를 차지하면 그 작업은 완성될 때 까지 실행된다.
• SJF 스케줄링의 문제점인 긴 작업과 짧은 작업간의 지나친 불평등을 보완한 기법으로, 우선순위 계산식에서 시스템 응답시간이 클수록 우선순위가 높아진다.
• 우선순위(시스템 응답시간) = (대기시간 + 버스트 시간) / 버스트 시간
• 짧은 작업이나 대기 시간이 큰 작업일수록 우선순위가 높아진다.
• Aging의 구현 방법

Thread

프로세스와 쓰레드의 관계

Thread 특징

• 각 쓰레드는 서로 독립적으로 수행된다
• 프로세스 내에 여러 개의 쓰레드가 존재한다.
• 프로세스 내에 메모리를 쓰레드들이 공유하여 사용 가능하다.
• 쓰레드는 프로세스의 일부분이기 때문에 프로세스의 자원들을 공유하지만, 그 자신의 처리 시간과 스택, 레지스터들이 할당된다.
• 프로세스 간의 전환 속도보다 쓰레드 간의 전환 속도가 더 빠르다.
• 쓰레드의 실행/종료 순서는 예측 할 수 없다.(두 개 이상의 쓰레드가 공유 변수 사용 시 문제 발생 위험)
• 쓰레드는 서로 독립적이지만, 한 쓰레드가 취한 행동은 프로세스에 있는 다른 쓰레드에 영향을 미친다.