[OS] Process Management, CPU scheduling

 

 

 

 

프로그램 : 하드디스크에 실행되지 않고 내장되어 있음

프로세스 : 프로그램이 메인 메모리에서 실행되고 있음

 cpu는 프로세서와 소통하고 cpu의 시간을 나눠준다.

 

 

 

 

multi processing system

new → ready → running →wating → ready → running → teminated

time sharing system

new → ready → running →wating → ready → running → teminated

time expired가 추가되어 일정 시간이 지나면 강제로 다른 프로그램으로 스위칭된다.

 

 

 

 

PCB (Process Control Block) = Task Control Block

 

PCB는 os 안에 process management 안에 있으며 프로세서에 대한 모든 정보를 담고 있다.

1 프로세서 당 1 PCB를 가지고 있다. 

PC : 다음에 몇 번지 실행할 것인지

레지스터 : time expired 되거나 waiting 상태가 끝나면 다시 돌아와야 하기 때문에 PCB에 레지스터 값 기록해야 한다.

MMU info : 각 프로세서의 base, limit 값

processor ID : 프로세서마다 번호를 붙임

list of open file : 현재 사용하고 있는 파일정보

PCB는 프로세서의 상태에 대한 정보를 담고 있다. 

 

 

 

Queue

 

세 종류의 큐는 os 내부 process management에 존재한다.

 

Job queue

- Job scheduler → 줄서서 대기하고 있는 프로그램 중 어떤 것을 먼저 메인메모리로 올릴지 결정하는 프로그램

- Long - term scheduler → 한 프로그램이 끝날 때까지 기다려야 하므로 몇 분 간격으로 일어남

 

Ready queue

- CPU scheduler → 줄서서 대기하고 있는 프로세서 중 어떤 것을 먼저 CPU로 올릴 지 결정하는 프로그램

- Short - term scheduler → 한 작업이 종료되면 CPU를 누구에게 매핑할 지 결정해야 하고 스위칭이 빨리 일어나야 함

                                       → 가장 중요한 스케줄링 

 

Device queue

- Device scheduler → 줄서서 대기하고 있는 프로세서 중 어떤 것을 먼저 device로 올릴 지 결정하는 프로그램

 

컴퓨터 프로세서는 큐 내부에 줄을 서서 기다린다.

하드디스크에 있던 프로그램들이 메인메모리로 올라가 CPU의 서비스를 받으려면 순서대로 기다려야 한다.

 

 

 

 

 

 

 

Multiprogramming

 

메인메모리에 여러 개의 프로세서를 올리는 것을 말한다.

Degree : 메인 메모리에 프로세서가 몇 개 올라와 있는지를 나타냄

• I / O bound : 주로 I/O작업.
• CPU bound process : 주로 CPU 자주 사용하는 작업
• job scheduler는 cpu와 i / o를 사용하는 작업을 한 쪽에 치우치지 않고 적절히 mix해야 한다.
• medium - term schduler → swapping → 메인메모리를 살펴보고 사용하지 않는 어떤 프로세서를 내보낼 지 결정(swap out)
•  & Backing store에 있는 어느 프로세서를 메인메모리로 가져올 지 결정(swap in)
• context switching (문맥전환)
  • Scheduler → ready Queue에서 대기하고 있는 프로세서 중 어떤 것을 먼저 내보낼 것인지 결정
  • Dispatcher → 스케줄러가 선택한 프로세서를 실행하기 위해 여러 상태 / 레지스터 값을 바꿔줌
  • Context switching overhead → cpu는 1개, 프로세서는 여러 개이므로 한 순간에  하나의 프로세서만 컨트롤

 

 

 

메인메모리에 프로그램 A,B,C가 올라와 있는 상태이다. 프로그램 B가 실행되던 중 잠시 사용이 멈춘다면 메인 메모리에 올라와 있기만 한 상태이므로 B를 하드디스크로 swap out하고, 프로그램 A나 C를 실행하거나 다음 프로세서를 메인메모리로 올린다. 

 

 

 

 

cpu스케줄러는 ready queue에서 대기하고 있는 프로세서 중 어떤 것을 먼저 내보낼 것인지를 결정한다.

Dispatcher는 스케줄러가 선택한 프로세서를 실행하기 위해 여러 상태 / 레지스터 값을 바꾸어준다.

ex) P1 → P2라면

P1의 현재 상태(PC값, 스택포인터, 레지스터, MMU, base, limit값)을 전부 os의 process management에 있는 PCB1에 저장해야 한다.

∵ P2로 갔다가 다시 P1의 현재상태로 복귀할 때 필요한 값들이므로

P2의 저장된 값을 복원(restore)하면 CPU는 P2의 코드를 돌림

 

∴ 프로세서 넘어갈 때마다 store, restore를 반복 → Context 위치가 자주, 빠르게 넘어가게 되면 overhead 횟수가 증가 →  low-level의 어셈블리어를 사용해 효율적으로 코드를 짜야할 필요성

 

 

 

 

 

 

 

CPU scheduling

 

Preemptive = 선점

cpu가 어떤 프로세스를 막 실행하고 있고 프로세서가 끝난 상황이 아닌데, 이 프로세서를 강제로 쫓아내고 새로운 게 들어갈 수 있는 스케줄링 방식

Non-preemptive  = 비선점 

cpu가 어떤 프로세서를 막 실행하고 있고 프로세서가 끝난 상황이 아닌데, 새로운 스케줄링이 절대 일어나지 않는 방식

 

scheduling criteria

• cpu utilization(cpu이용률) → cpu가 놀지 않고 얼마나 부지런히 일하는가
• throughput(처리율) → 단위 시간 당 몇 개의 작업을 처리하는가. 시간 당 처리하는 작업이 많을 수록 throughput 증가
• turnaround time(반환시간) → 작업이 메인메모리로 들어가 종료되고 나올 때까지 걸리는 시간 짧을수록 좋다.
• waiting time(대기시간) → cpu의 서비스를 받기 위해 ready queue에서 얼마나 대기했는가
• response time(응답시간) →  처음 응답이 나올 때까지 걸리는 시간. 주로 대화형 컴퓨터의 척도로 사용된다.

 

preemtive 스케줄링 & time schduling system x

Preemtive 스케줄링에서 Time sharing system이 아닌 경우, 병원에 환자가 의사의 진료를 받기 위해 대기하는 것처럼 ready queue에서 대기하다 cpu에서 수행되고 다시 device queue로 갔다가 i/o를 수행하는 과정을 거쳐 종료된다.

단 응급환자가 온 경우 원래 진료받던 환자는 대기실로 쫓겨나게 된다. 

Preemtive 스케줄링 & Time sharing system

Preemtive 스케줄링에서 Time sharing sytstem인 경우 일정 시간이 지나면 다음 프로세서로 넘어가야 한다.

 

 

 

 

 

 

CPU schduling algorithms

 

1. First - Come, First - Served → 먼저 온 것 먼저 수행

 

• P1 → P2 → P3 순

P1(0-24)

P2(24-27)

P3(27-30)

average wating time = ( 0 + 24 + 27 ) / 3 = 17

• P3 → P2 →P1 순

P3(0-3)

P2(3-6)

P3(6-30)

average wating time = (3 + 6 + 0) / 3 = 3

 

위는 실행시간순서가 아닌 fcfs순으로 수행했을 때이고 아래는 수행시간이 짧은 순으로 수행한 경우이다.

위의 경우가 averaging time이 오래걸리므로, fcfs가 항상 효율적이라고 할 수는 없다.

 

2. Shortest - Job - First → 작업시간이 짧은 것 먼저 서비스

P4(0-3)

P1(3-9)

P3(9-16)

P2(16-24)

 

averaging wating time = (3 + 16 + 9 + 0) / 4 = 7

 

수행시간이 짧은 프로세서순으로 정렬해 averaging타임을 계산하면 효율적으로 cpu를 스케줄링할 수 있다.

하지만 각 프로세서를 실행해봐야 알기 때문에 비현실적이며, 미래의 cpu 사용시간에 대한 예측이 필요하다.

 

3. Priority Scheduling → 우선순위가 높은 것 먼저 서비스

낮은 우선순위는 높은 우선권을 갖는다.

우선순위를 매기는 기준은 다양하다. → time limit가 짧은 것, 메모리를 적게 차지하는 것, i/o가 길고 cpu수행시간이 짧은 것

P2(0-1)

P5(1-6)

P1(6-16)

P3(16-18)

P4(18-19)

average wating time = (6 + 0 + 16 + 18 + 1) / 5 = 8.2

외부에서 ready queue로 프로세서가 계속 유입되는데, 기존에 대기하던 프로세서보다 새로 들어오는 프로세서의 우선순위가 더 높다면 오래 기다렸다 해도 선택될수 없는 starvation 현상이 일어날 수 있다.

따라서 aging기법으로 starvation 현상을 막을 수 있다. aging은 os가 ready queue를 주기적으로 조사해 오래 기다릴수록 우선순위를 높이는 방식이다.

 

4. Round - Robin → 빙글빙글 돌면서 순서대로 서비스

time sharing system이다.

time quantum을 두어, 한 프로세서가 아직 완전히 끝나지 않았음에도 불구하고 time quantum이 지나면 자동으로 다음 프로세서로 넘어가는 방식이다.

Process	Burst time(msec)
P1	24
P2	3
P3	3

time quantum이 4ms일 때

P1(0-4)

P2(4-7)

P3(7-10)

P1(10-30)

P1을 4ms만큼 실행하고 바로 P2,P3를 끝마친 후 남은 시간동안 P1을 수행해 끝낸다.

averaging wating time = (6 + 4 + 7) / 4 = 5.66

 

time quantum의 사이즈에 굉장히 의존적이다. 

△→ ∞ : FCFS와 유사

△ → 0 : processor sharing와 유사 → 스위칭이 워낙 빈번하게 일어나기 때문에 여러 개의 프로세서가 동시에 수행되는 것처럼 보이는 효과 발생 → overhead 증가

 

5. Multilevel Queue → 큐를 여러 개 둠

각각 다른 역할을 하는 큐를 여러 개 두고, 큐에 우선순위를 두어 그룹에 따라 각각 다른 스케줄링을 진행하는 방식이다.

 

6. Multilevel Feedback Queue → 큐를 여러 개 둠

각각 다른 역할을 하는 큐를 여러 개 두고, 프로세서가 너무 많은 cpu time 사용 시 다른 큐로 들어갈 수 있도록 feedback회로를 추가하는 방식이다. starvation를 대비해 우선순위 높은 큐로 이동할 수 있다.

 

 

 

 

 

 

Process Creation

프로세스는 프로세스에 의해 만들어진다. → parent process가 child process를 생성하는 과정이 반복되 프로세스 트리 구성함

프로세스 트리

PID : 프로세스에 번호 붙임 

fork() : 부모 프로세스 복사

exec() : 실행파일을 메모리로 가져오기

exit() : 프로세스 종료 → 프로세스가 가졌던 모든 자원은 os에 반환