DEVELOPyo

CPU Scheduling 

CPU를 누구에게 줄것인가, 주고나서 뺏어올 것인가

※ CPU and I/O Bursts in program execution

사용자와의 interaction 이 많은 프로그램일 수록 I/O burst 높다

※ CPU-burst Time의 분포

I/O bound job : I/O 많이 사용, many short CPU bursts

CPU bound job : CPU 많이 사용(계산 위주의 job), few very long CPU bursts.

-> 여러 종류의 job(process)이 섞여 있기 때문에 CPU 스케쥴링이 필요.

※ CPU Scheduler & Dispatcher

- CPU Scheduler :

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다(OS 안에서 처리됨, 별도의 하드웨어나 소프트웨어가 아님)

- Dispatcher :

CPU 제어권을 CPU scheduler 에 의해 선택된 프로세스에게 넘긴다

이 과정을 context switch(문맥 교환)라고 한다

※ CPU 스케쥴링이 필요한 경우

1. Running -> Blocked (ex: I/O 요청하는 시스템 콜) : 자진 반납(nonpreemptive)

2. Terminate : 자진 반납(nonpreemptive)

3. Blocked -> Ready (ex: I/O완료 후 interrupt) : 강제 반납(preemptive)

4. Running -> Ready (ex: 할당시간만료로 timer interrupt) : 강제 반납(preemptive)

Scheduling Criteria

: Performance Index(=Performance Measure, 성능척도)

1. CPU utillization (이용료)

: Keep the CPU as busy as possible (ex: 주방장이 일하는 시간)

2. Throughput (처리량)

: # of processes that complete their execution per time unit

(ex: 얼마나 많은 손님이 다녀갔는가)

3. Turnaround Time (소요시간, 평균시간)

: amount of time to execute a particular process

cpu 처리시간의 총합

(ex: 손님이 와서 식사 하는 시간의 총합(코스요리의 경우 먹고 쉬고 먹고 쉬고를 반복, 먹는 시간의 합))

4. Waiting time (대기 시간)

: amount of time a process has been waiting in the ready queue

(ex: 손님이 와서 기다리는 시간의 총합(코스요리))

5. Response time (응답 시간)

: amount of time it takes from when a request was submitted until the first response is produced, not output

처음으로 응답되는데 까지 걸리는 시간

(ex: 손님이 와서 밑반찬을 네주는데 걸리는 시간)

※

1, 2 는 시스템 입장에서 CPU 성능척도

3, 4, 5 는 process 입장에서의 성능척도

CPU Scheduling 종류

1. FCFS(First-Come First-Served)

프로세스 도착 순서대로 처리(비선점형 nonpreemptive)

※ 문제점

Convoy effect : short process behind long process

앞에 긴 프로세스가 존재하여 뒤에 짧은 프로세스가 처리되지 못하는 현상

2. SJF(Shortest-Job-First)

- 각 프로세스와 다음번 CPU burst time을 가지고 스케쥴링에 활용

- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴

1) Nonpreemptive

CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 뺏기지 않음

2) Preemptive

현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗긴다. 이를 SRTF(Shortest-Remaining-Time-First)라고 부른다.

- SJF is optimal(최적화) : 주어진 프로세스에 대해 minimum average waiting time을 보장

※ CPU Burst Time의 예측

- 다음번 CPU burst time 은 추정(estimate)만 가능

- 과거의 CPU burst time 을 이용해서 추정 (exponential averaging)

CPU Burst Time 예측 공식 정리가 되어있는 곳 : https://darkluster.tistory.com/43

3. Priority Scheduling

- A priority number(integer) is associated with each process

- 가장 높은 우선수위를 가진 프로세스에게 CPU 할당(smallest integer = highest priority)

- SJF 는 일종의 priority scheduling

※ 문제점

Starvation(기아현상)

: low priority processes may never execute. (낮은 우선순위 프로세스가 영원히 CPU를 얻지 못하는 것)

※ 해결책

Aging(노화)

: as time progresses increase the priority of the process (시간이 지나면 우선순위를 올려주는 것)

4. Round Robin(RR)

- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다 (일반적으로 10-100milliseconds)

- 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue와 제일 뒤에 가서 다시 줄을 선다

- n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다 (어떤 프로세스도 (n-1)q time unit 이상을 기다리지 않는다)

※ 장점

1) 응답시간이 빠르다.

2) CPU가 길게 필요하면 길게 기다리고, 짧게 필요하면 짧게 기다린다. (짧은 프로세스는 빨리 나가고 긴 프로세스는 길게(많이) 기다리게 되므로 프로세스의 waiting time 과 turnaround time 이 비례)

※ 할당시간에 따른 차이

q large (할당시간이 길다면) => FCFS

q small (할당시간이 짧다면)=> context switch 오버헤드가 커진다.

Multilevel Queue

Queue가 여러줄이며 우선순위가 높은 큐의 프로세스가 CPU 우선권을 가진다

1) Ready queue를 여러개로 분할

  - foreground (interactive(IO))

  - background(batch - no human interaction)

2) 각 큐는 독립적인 스케쥴링 알고리즘을 가진다

  - foreground - RR (빠른 응답속도)

  - background - FCFS

3) 큐에 대한 스케쥴링 필요

  - Fixed priority scheduling : starvation 문제

  - Time slice : 각 큐에 CPU time을 적절한 비유로 할당한다

    80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

프로세스 처리가 끝나면 바로 나감, 처리가 끝나지 못하면 두번째 큐로 이동, 또 처리가 되지 못했다면 맨 밑의 큐로 이동

처리가 짧은 프로세스에게 우선권을 먼저 준다

※ Multiple-Processor Scheduling

CPU가 여러개인 경우

1) Homogeneous processor 인 경우

- Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가도록

- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 복잡해진다

2) Load sharing

- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

- 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

3) Symmetric Multiprocessing(SMP)

- 각 프로세서가 각자 알아서 스케쥴링 결정

4) Asymmetric multiprocessing

- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

※ Real-Time Scheduling

1) Hard real-time systems : 정해진 시간안에 반드시 끝내도록 스케쥴링

2) Soft real-time computing : 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 한다

3. Thread Scheduling

1) Local Scheduling : User level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread 를 스케쥴할 지 결정

2) Global Scheduling : Kernel level thread 의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread 스케쥴할지 결정 

※ Algoritm Evaluation 알고리즘 평가방법

1) Queueing models

확률 분포로 주어지는 arrival rate와 service rate 등은 통해 각종 performance index 값을 계산

2) Implementation (구현) & Measurement (성능 측정)

실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

3) Simulation (모의 실험)

알고리즘을 모의 프로그램으로 작성 후 trace를 입력하여 결과 비교

※ 이화여자대학교 반효경 교수님의 운영체제 강의 정리

프로세스 생성

1. 부모 프로세스가 자식 프로세스를 생성

   (COW : Copy-On-Write 자식은 부모 자원을 그대로 공유하여 사용하고 있다가 write 발생할 경우 복사 함)

2. 프로세스의 트리 형성

3. 프로세스는 자원을 필요로 함

  - 운영체제로 부터 받는다

  - 부모와 공유한다

4. 자원의 공유

  1) 부모와 자식이 모든 자원을 공유하는 모델

  2) 일부를 공유하는 모델

  3) 전혀 공유하지 않는 모델

5. 수행(Execution)

 - 부모와 자식은 공존하며 수행되는 모델

 - 자식이 종료(terminate)될 때까지 부모가 기다리는(wait) 모델

주소 공간(Address space)

 - 자식은 부모의 공간을 복사한다

 - 자식은 그 공간에 새로운 프로그램을 올린다

ex) UNIX 

  1) fork() 시스템 콜이 새로운 프로세스 생성

    - 부모를 그대로 복사

    - 주소 공간 할당

  2) fork 다음에 이어지는 exec() 시스템 콜을 통해 새로운 프로그램을 메모리에 올린다

프로세스와 관련된 시스템 콜

1. fork() : create a child(copy)

A process is created by the fork() system call.

: creates a new address space that is a duplicate of the caller.

int main() {
   int pid;
   pid = fork();
   if(pid == 0) /* child */
      printf("\n Hello, I am child\n");
   else if (pid > 0) /* parent */
      printf("\n Hello, I am parent\n");
}

fork() 실행시 자식 프로세스가 생겨서 부모 프로세스를 그대로 복제하며

부모 프로세스 Program Counter 도 복제하여, fork() 다음의 if(pid == 0) 라인부터 실행

* 자식 프로세스는 pid = fork(); 이전 라인을 실행하지 못함

2. exec() : overlay new image

A process can execute a different program by the exec() system call.

: replaces the memory image of the caller with a new program.

int main() {
   int pid;
   pid = fork();
   if(pid == 0) { /* child */
      printf("\n Hello, I am child\n");
      execIp("echo", "echo", (char *) 0);
   } else if (pid > 0){ /* parent */
         printf("\n Hello, I am parent\n");
   }
   printf("2");
}

fork() 없이 execIp() 만 사용가능

execIp 를 만나는 순간 새로운 프로그램이 기존 프로그램을 덮어쓰게 되며 echo 가 실행되므로

printf("2"); 는 실행 될 수 없음

3. wait() : sleep until child is done

프로세스 A가 wait() 시스템 콜을 호출하면

1) 커널은 child가 종료될 때까지 프로세스 A를 sleep 시킨다 (block 상태)

2) child process 가 종료되면 커널은 프로세스 A를 깨운다 (ready 상태)

: 자식이 종료(terminate)될 때까지 부모가 기다리는(wait) 모델

main {
   int childPID;
   childPID = fork();
   if(childPID == 0){
     <code for child process>    
   } else {
      wait();
   }
}

fork 로 자식 프로세스 생성

wait() 으로 부모프로세스가 sleep,

자식 프로세스가 CPU를 얻어서 자식 프로세스의 코드(code for child process)가 실행 된 후(끝난 후)

부모 프로세스가 깨어난다.

4. exit() : frees all the resources, notify parent

프로세스의 종료

1. 자발적 종료

   1) 마지막 statement 수행 후 exit() 시스템 콜을 통해

   2) 프로그램에 명시적으로 적어주지 안하도 main 함수가 리턴되는 위치에 컴파일러가 넣어준다

2. 비자발적 종료

   1) 부모 프로세스가 자식 프로세스를 강제로 종료시킨다

     - 자식 프로세스가 한계치를 넘어선 자원을 요청할 때

     - 자식에게 할당된 task가 더 이상 필요하지 않을 때

   2) 키보드로 kill, break 등을 친 경우

   3) 부모가 종료하는 경우

     - 부모 프로세스가 종료하기 전에 자식들이 먼저 종료된다

프로세스 종료

1. 프로세스가 마지막 명령을 수행한 후 운영체제에게 이를 알려준다(exit)

 - 자식이 부모에게 output data를 보낸다 (via wait)

 - 프로세스의 각종 자원들이 운영체제에게 반납된다

2. 부모 프로세스가 자식의 수행을 종료시킴 (abort)

 1) 자식이 할당 자원의 한계치를 넘어설 때

 2) 자식에게 할당된 테스크가 더 이상 필요하지 않을 때

 3) 부모가 종료(exit)해야하는 경우

   - 운영체제는 부모 프로세스가 종료하는 경우 자식이 더 이상 수행되도록 두지 않는다

   - 딸려있는 모든 자식을 종료시킨 후 부모를 죽이는 단계적인 종료

프로세스 간 협력

1. 독립적 프로세스(Independent process)

  : 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을

    미치지 못한다

2. 협력 프로세스(Cooperating process)

  : 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음

3. 프로세스 간 협력 메커니즘(IPC : Interprocess Communication)

1) 메시지를 전달하는 방법

- message passing : 커널을 통해 메시지 전달. 프로세스 사이에 공유 변수를 사용하지 않고 통신하는 시스템

a. Direct Communication : 통신하려는 프로세스의 이름을 명시적으로 표시 

b. Indirect Communication : mailbox(또는 port)를 통해 메시지 간접 전달

2) 주소 공간을 공유하는 방법

- shared memory : 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 shared memory 메커니즘이 있음

※ thread : thread는 사실상 하나의 프로세스이므로 프로세스 간 협력으로 보기는 어렵지만 동일한 process를 구성하는 thread들 간에는 주소 공간을 공유하므로 협력이 가능

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Thread

프로세스(heavyweight process) 내부에 CPU 수행 단위가 여러개 존재하는 것

CPU를 수행하는 단위

"A thread (or lightweight process is a basic unit of CPU utilication"

[Process 정보를 담고 있는 Process Control Block]

[PCB 내에서의 Thread]

data, code 등 메모리 공유가 가능한 자원은 최대한 공유(※ 공유하는 부분은 Task 라 칭함)하며,

CPU 수행과 관련된 Program Counter, registers, Stack 영역은 별도로 가진다. 

Thread 사용시 기대 효과

1) 다중 스레드로 구성된 태스크 구조에서는 하나의 서버 스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행(running)되어 빠른 처리 가능.

2) 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율(throughput)과 성능을 얻을 수 있다

3) 병렬성을 높일 수 있다(CPU가 여러개인 컴퓨터인 경우)

Thread 사용시 장점

- Responsiveness " if one thread is blocked, another thread continues

- Resource Sharing : n threads can share binary code, data, resource of the process

- Economy : creating & CPU switching thread rather than a process (overhead)

- Utilization of MP(Multi Processor) Architectures : each thread may be running in parallel on a different processor

Thread 구현 방식

- Kernel Threads (supported by kernel)

- User Threads (supported by library)

- Real-time Threads

※ 이화여대 반효경 교수님의 운영체제 강의내용 정리