(2) 프로세스 & 스레드 / 스케줄러

 

TL;DR

• 프로세스는 실행 중인 프로그램으로 운영체제로부터 자원을 할당받으며 각 프로세스끼리 독립적이다.
• 스레드는 프로세스 내에서 실행되는 흐름의 단위로 프로세스가 할당받은 자원 내에서 Stack 영역만 따로 갖고 나머지는 공유 자원으로 사용한다.
• Scheduler란? CPU를 효율적으로 사용하기 위한 방법으로, 어떤 프로세스에게 CPU를 줄 지 고른다

 

 

들어가기 전에

운영체제란 HW를 효율적으로 관리하는 소프트웨어로, 시스템 입장에서는 자원 할당자다.

컴퓨터 발전 과정에서

1. 여러 개의 프로그램을 메모리에 올려둘 수 있게 됐고 (bigger and cheaper memory 발전)
2. User interactive 환경이 대두되면서(모니터/키보드 등) I/O bounded job 이 많아졌다.

• CPU를 더욱 효율적으로 사용하기 위한 방법이 모색됐고, 이를 CPU Scheduling 이라고 한다. 운영체제는 kernel data 영역에 각 프로세스를 관리하기 위한 정보인 PCB를 가지고, Scheduling Algorithm에 따라 CPU를 프로세스에 할당한다.
• 이 과정에서 process state, process context, context switch 등의 개념이 나온다.
• Thread는 프로세스 내부에서 CPU를 수행하는 단위로, 동일한 프로세스를 여러개 실행해야할 때, 주소 공간을 공유해 메모리 낭비를 막고 프로세스를 효율적으로 수행하게 하기 위한 기법이다.

 

 

Process

Process 란 실행 중인 프로그램으로 job, task, sequential process 라고도 불린다.

 

👆 Process vs Program

• Program : 파일 시스템 내 실행 파일
• Process : program이 진행되며 바뀌는 register, memory 영역 등을 모두 포함한 개념

 

✅ 프로세스 종류

🔺 데몬 프로세스

• 커널에 의해 실행되며 네트워크의 제어 및 관리 등 시스템을 지원하는 프로세스
• 주기적이고 지속적으로 서비스 요청을 처리하며 백그라운드에서 계속 실행된다.
• 서버 역할을 하는 프로그램들이 해당되고 보통 이름 뒤에 d를 붙인다.

 

🔺 부모 프로세스 (parent process)

• 다른 프로세스를 만드는 프로세스로 PPID(Parent Prcess ID)를 가진다.
• 부팅할 때 실행되는 1번 프로세스를 제외한 프로세스는 모두 부모 프로세스를 가지고 있다.

 

🔺 자식 프로세스 (child process)

• 부모 프로세스에 의해 만들어지는 프로세스로 PID(Process ID)를 가진다.
• 할 일이 끝나면 부모 프로세스에 결과를 돌려주고 종료된다.

 

🔺 고아 프로세스 (orphan process)

• 자식 프로세스가 실행중인데 부모 프로세스가 종료되면 자식 프로세스는 고아 프로세스가 된다.
• 이경우 1번 프로세스가 새로운 부모 프로세스가 되어 고아 프로세스가 작업을 마치고 종료될 수 있도록 돕는다.

 

🔺 좀비 프로세스 (zombie process)

• 자식 프로세스가 실행 종료 후에도 프로세스 테이블 목록에 남아있는 경우이다.
• 이경우 부모 프로세스에게 SIGCHILD 시그널을 보내서 부모 프로세스가 자식 프로세스를 정리하게 하거나, 부모 프로세스 자체를 종료시킨다.

 

 

✅ Process Context

프로그램이 어떤 것을 실행했고, 현재 어느 시점에 있는지 정확하게 규명하기 위한 모든 요소 집합.

크게 세 가지 파트로 나눌 수 있다.

• CPU 수행 상태를 나타내는 하드웨어 문맥 : 현재 시점에 어디까지 실행 됐는가를 확인하는 지표들 Program Counter(PC), 각종 register
• 프로세스의 주소 공간 : 현재 시점에 메모리에 어떤 내용이 들어가 있는가를 확인하는 지표들 Code, Data, Stack
• 커널의 주소 공간 : 운영체제가 현 프로세스를 어떻게 평가하고 있느냐를 확인하는 지표들

 

❓ Code / Data / Stack 에는 어떤 정보가 저장되나요?

 

✅ Process State

프로세스는 상태(State)가 변경되며 수행된다.

 

🔺 New : 프로세스 생성

• System initialization
• 실행 중인 프로세스가 프로세스 생성 시스템 호출 (fork)
• 사용자가 새로운 프로세스 생성하도록 요청
• 배치 작업의 시작

 

• Unix 에서는 fork 시스템 콜을 통해 프로세스를 생성한다. fork 통해 부모 프로세스의 주소 공간을 복사한 후, exec을 통해 새로운 ㅍ로그램을 실행시킨다.
• 그러나 리눅스 계열의 운영체제에서는 바로 주소 공간을 복사하지 않고, 우선 실행하다가 부모 프로세스와 자식 프로세스의 내용이 달라지는 순간 카피해서 주소 공간을 할당한다. 이런 방식을 copy-on-write(COW)라고 부른다.

 

🔺 Running : 프로세스가 CPU 잡고 instructino 수행 중

• running -> waiting(blocked) : I/O 등 오래 걸리는 작업 때문에 자진해서 CPU를 내놓는 경우
• running -> ready : timer interrupt 걸려 CPU 빼앗김

 

🔺 Ready : 프로세스가 CPU 기다리는 상태 ( 메모리 등 다른 조건 모두 만족하고)

스케줄러에 의해 CPU 할당 받으면 당장 instruction을 수행할 수 있는 상태

 

🔺 Waiting(Bolcked) : 프로세스가 CPU 수행할 수 없는 상태

CPU 주어져도 당장 instruction 수행할 수 없는 상태

blocked -> ready : Process 자신이 요청한 event(예: I/O)가 만족될 때 상태 변화

 

🔺 Terminated : 프로세스 종료

프로세스의 세계는 자식 프로세스가 먼저 종료되어야 부모 프로세스가 종료되는, 단계적 종료가 일어난다. 따라서 자식이 종료될 때는 부모 프로세스에 알린다.

1. 자발적 종료
   • (main 끝나서 return 한다던가)
   • exit 시스템 콜 수행
2. 비 자발적 종료
   • Fatal Error 로 인한 강제 종료 (segment fault, nonexistent memory 등..)
   • 다른 프로세스에 의한 종료 (kiil)

 

🔺 Suspended : 외부(스케줄러)에서 프로세스를 정지해둔 상태

외부(스케줄러)에서 Resume 해주어야 Ready 상태가 됨.

 

🔺 Monitor mode Running : 운영체제가 실행 중인 상태

Kernel model 라고 말하지 운영체제가 running 한다고 말하지는 않는다.

 

---

Thread

• 프로세스 내부에 CPU를 수행하는 단위로, lightweight process라고 부른다.
• 동일한 일을 하는 프로세스를 여러 개 실행할 때, 프로세스를 여러 개 만들면 주소공간이 낭비되기 때문에 주소 공간을 하나만 두고(공유할 수 있는 자원은 공유) 실행하는 방식이다.

 

✅ Thread 장점

• CPU 관련 정보들 (PC, registers)만 Thread 별로 가지고 있기 때문에, 메모리가 절약된다.
  -> Stack 영역만 따로 갖고 나머지는 공유 자원으로 사용
• Creating & Switching 모든 면에서 프로세스보다 Thread가 빠르고 오버헤드도 적다.
• CPU가 여러개인 컴퓨터에서는 Thread를 활용해 병렬성을 높일 수 있다.

 

✅  Thread 구현

🔺 User Threads

커널이 Thread 의 존재를 알지 못하며, 사용자 공간에 Thread를 위치시킨다.

• Thread를 지원하지 않는 OS 에서도 구현될 수 있고,
• Thread 생성, 전환 등에 kernel 도움이 필요 없어 10-100배 정도 빠르다. (function call 사용)
• Customized Scheduling Algorithm 사용이 가능하다.
• 그러나 OS가 Thread 존재를 모르기 때문에 clock interrupt 를 할 수 없어 무한루프 발생 등 오류 발생 시 thread 스케줄링이 어렵다.
• 하나의 Thread가 오류로 인해 죽거나 block 되는 경우, 전체 Process가 죽거나 block 된다.
• Thread 관리는 라이브러리로 제공한다.

 

🔺 Kernel Threads

커널이 Thread 의 존재를 알고, 그 관리를 OS가 Thread table을 만들어 한다.

• OS가 Thread를 알기 때문에 스케줄링이 가능하다.
• Thread 생성, 전환 등에 system call 이 사용되므로 오버헤드가 크다.

 

---

 

Scheduler

• CPU Scheduler 는 CPU를 사용하는 프로세스가 전환되는 것에 관여한다.
• CPU를 효율적으로 사용하기 위한 방법으로, 어떤 프로세스에게 CPU를 줄 지 고른다.
  • 프로그램의 실행은 CPU를 연속적으로 사용하는 단계(CPU burst)와 I/O를 사용하는 단계(I/O burst)로 이루어져 있다.
  • Interactive job들은 I/O burst가 잦기 때문에, 사용자가 오래 기다리지 않게 하기 위해 CPU 스케줄링이 꼭 필요하다.
• CPU Scheduler가 프로세스를 고르면, Dispatcher가 CPU제어권을 선택된 프로세스에게 넘기고, 이 과정을 Context Switch라고 한다.
  • nonpreemptive (자진 반납) 예) I/O 시스템콜, Terminate
  • preemptive(강제로 빼앗음) 예) CPU 할당 시간 만료(timer interrupt)

 

👆 CPU Scheduler는 별도의 하드웨어인가? 아니면 프로그램인가?

운영체제 안에 스케줄러 코드가 있고 이걸 CPU Scheduler라고 부르는 것 뿐이다.

 

🔺 Context Switch

CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정으로, 운영체제는 다음을 수행한다.

• CPU를 사용하던 프로세스 A가 system call 또는 interrupt 발생으로 CPU를 넘겨야 할 때
• CPU를 내어주는 프로세스 A의 상태를 A의 PCB에 기록하고,
• CPU를 새롭게 얻는 프로세스 B의 상태를 B의 PCB에서 읽어온다.

하지만 system call이나 interrupt 발생 시 반드시 context switch가 일어나지는 않는다. system call이나 interrupt 발생 시 프로세스 A에서 운영체제로 CPU가 넘어갔다가, 바로 프로세스 A에게 CPU를 넘겨줄 수도 있다. 이런 경우는 context switch라고 부르지 않는다. 즉 context switch는 운영체제가 다른 프로세스로 CPU를 넘길 때만 일어난다.

 

 

✅ Scheduler 종류

🔺 장기 스케줄러 Job scheduler

• 시작 프로세스 중 어떤 것을 ready queue에 보낼지 결정한다.
• 즉, 프로세스에게 memory를 주는 문제를 다룬다.
• 메모리에 올라가 있는 프로세스의 수를 제어한다. (Degree of Multiprogramming)

=> 지금은 프로세스 시작되면 곧바로 메모리에 올리고, 중기 스케줄러를 통해 프로그램의 수를 제어한다.

 

🔺 중기 스케줄러 Swapper

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다.
• 즉, 프로세스에게 memory를 빼앗는 문제를 다룬다.

 

🔺 단기 스케줄러 CPU Scheduler

• 어떤 프로세스를 다음에 running 시킬지 결정한다.
• 즉, 프로세스에게 CPU를 주는 문제를 다룬다. (Millisencond 단위로 이루어진다.)

 

✅ Scheduler Algorithm

• 스케줄링 알고리즘은 어떤 시스템이냐에 따라 다른 목적을 갖게 된다.
• 대부분은 CPU의 효율성에 중점이 있으나 interactive system의 경우 응답 속도에, real-time system의 경우 deadline 지키는 것에 중점을 둔다.

 

🔺 FCFS (First-Come-First-Service)

• 비선점 스케줄링 알고리즘 (Non-preemptive)
• 먼저 도착한 프로세스를 먼저 처리하는 방식
• 구현하기 쉽지만 효율이 떨어진다.
• 무조건 도착한 순서대로 프로세스를 처리해야 하므로 Convey Effect가 발생할 수 있음
  : 실행 시간이 긴 프로세스가 실행시간이 짧으 프로세스보다 앞에 있는 경우 기다리는 시간이 길어진다.

🔺 SJF (Shortest-Job-First)

• 비선점 스케줄링 알고리즘 (Non-preemptive)
• 실행시간(CPU 점유시간)이 짧은 순서대로 프로세스를 처리하는 방식
• 평균 대기 시간을 최소화하고, 많은 프로세스들에게 빠른 응답 시간을 제공할 수 있음
• 그러나 실행시간이 긴 프로세스는 계속 자원 할당을 받지 못해 Starvation(기아 현상)이 발생
• 실제 구현할 때는, CPU 사용시간을 예측하기 어렵다는 점과 모든 Job이 동시에 들어오지 않기 때문에 실제 optional 하게 선택할 수 없다는 점에서 문제가 있다.

🔺 SRTF (Shortest-Remaining-Time-First)

• 비선점 스케줄링 방식인 SJF를 선점 형태로 변경한 방식 (Preemptive)
• 사전에 실행시간이 알려진다고 할 때, 남은 실행 시간이 짧은 작업을 선택한다.
• 잔여 실행시간을 계속 추적하는 과정에서 Context Switching Overhead가 발생
• 구현 및 사용이 비현실적으로 어려움

🔺 RR (Round Robin)

• 선점 스케줄링 알고리즘 (Preemptive)
• 자원 사용 제한 시간(Time Quantum)을 두고 먼저 도착한 순서대로 프로세스를 처리하는 방식
• 프로세스는 할당된 시간이 지나면 자원을 반납해야함 (특정 프로세스의 독점 방지 ⇒ 공정함)
• Time Quantum의 크기 설정이 성능의 중요한 역할을 한다.
  시간이 길면 응답의 질이 떨어지고, 시간이 짧으면 문맥 교환으로 인한 오버헤드가 커진다.

🔺 Priority Scheudling

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 방식 (정수로 표현하고, 작은 숫자가 우선순위가 높음)
• 선점 스케줄링에선 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 선점
• 비선점 스케줄링에선 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣음
• 높은 우선순위 프로세스가 CPU를 계속 할당받아 우선순위가 낮은 프로세스는 무한정 연기되는 Starvation(기아 현상) 발생할 수 있다.

🔺 Muti-level Queue (MLQ)

• 작업별 별도의 Ready Queue를 두어 프로세스를 처리하는 방식 (최초의 배정된 큐를 벗어날 수 없고, 각각의 큐에 자신만의 스케줄링 기법을 사용함)
• 큐 사이에는 우선 순위 기반의 스케줄링을 사용한다.
• 그러나 여러 개의 큐를 관리해야 하므로 스케줄링 overhead가 발생할 수 있다.
• 우선순위가 낮은 큐는 기아 현상이 발생할 수 있다.
  이를 해결하기 위해 각 큐에 CPU time을 적절한 비율로 할당할 수 있다.

🔺 Multilevel Feedback Queue

• 프로세스의 큐간 이동이 허용된 MLQ
• 각 큐마다 시간 할당량을 다르게 배정하고, 다른 스케줄링 방식을 사용한다.
  -> 중요한 프로세스는 타임 퀀텀을 짧게, 덜 중요한건 타임 퀀텀을 길게
  -> I/O bounded job은 RR 방식을, CPU job은 FCFS 방식을 사용
• I/O-bounded 프로세스들을 상위 단계의 큐로, Compute-bounded 프로세스를 하위 단계의 큐로 이동시켜 우선순위를 높임
• 대기 시간이 지정된 시간을 초과한 프로세스들을 에이징 기법을 통해 상위 단계의 큐로 이동 (Starvation 방지 및 응답 속도 높이기)

 

 

➕ Scheduling Algorithm Evaluation

• Queueing models : 이론적으로 프로세스의 arrive rate과 service rate을 계산
• Implementation & Measurement : 실제 시스템에 알고리즘을 구현하여 성능 측정
• Simulation : 모의 프로그램으로 작성해 trace(예제)를 입력해 결과 비교

 

 

✅ Multi-processor Scheduling

CPU를 여러개 갖는 경우 아래 두 가지 방법으로 스케줄링 할 수 있다.

 

🔺 싱글 큐 스케줄링 (SQMS)

SQMS는 단순하지만 캐시 선호도 문제와 lock에 의한 오버헤드 문제가 있다.

• 하나의 큐에 작업들을 넣어서 처리하는 방식으로 싱글 프로세서에서 쓰던 스케줄러를 그대로 사용한다.
• 스케줄러가 여러 CPU에서 잘 작동하는지 확인하기 위해 lock을 사용하면서 오버헤드가 발생한다.
• 모든 CPU가 하나의 큐에서 작업을 가져오기 때문에 작업이 여러 개의 CPU 사이를 왔다갔다 하게 되면서 성능이 나빠진다. (캐시 선호도 적용이 안되는 프로세스가 존재할 수 있다.)
  -> SQMS 구현체는 대부분 캐시 선호도를 보존하기 위한 알고리즘을 추가로 가지고 있다.

 

🔺 멀티 큐 스케줄링 (MQMS)

MQMS는 확장성이 뛰어나고 캐시 선호도를 잘 처리하지만 load imbalance 문제가 발생한다.

• CPU가 각각 하나 또는 그 이상의 큐를 가지고, 각 큐는 RR 등 특정 스케줄링 방법을 사용한다.
• 작업이 시스템에 들어오면 heuristic에 따라 하나의 큐에만 배치되고, 각 CPU 별로 독립적으로 스케줄링이 된다. 
• 올바르지 못한 스케줄링으로 특정 CPU가 쉬고 있는 문제가 발생할 수 있다. (load imbalance)
  -> 사용 중인 CPU의 작업을 쉬는 CPU로 옮기는 migration 을 통해 해결할 수 있다.