Chapter2-2

프로세스와 스레드 관리 2

프로세스 생성

-      fork( )명령어

n  fork명령어를 실행시키면 프로세스가 하나 더 생긴다.

n  이렇게 생긴 프로세스는 같은 내용이지만 PID가 서로 다르고 독립된 프로세스가 생긴다.

n  fork명령어 전 까지는 앞에 있던 내용과 같지만, 그 뒤로는 독립된 프로세스가 된다.

n  pid = fork ( ) 명령어를 실행시키면 0값은 자식 프로세스가 된다. 부모 프로세스는 0보다 큰 값을 가지게 된다.

 

프로세스 스케줄링

-      CPU 스케줄링 : 어떤 프로세스를 먼저 실행 시킬지 스케줄링

-      프로세스 스케줄링 : CPU에게 서비스 받을 프로세스 스케줄링

 

스케줄링 목적

-      공정해야 함

n  어떤 프로세스에만 치우치지 안아 야함

-      응답 시간 최소화

n  응답 시간이 길면 프로세스를 종료 시킨다.

-      예측 가능

n  다음 프로세스를 어떤 것을 실행 시킬지 알아야함

-      오버헤드의 최소화

n  PCB를 저장하는 시간 + 지금 수행할 PCB로 바꾸는 시간을 줄여 야함

n  부가적으로 드는 일이 오버헤드

n  다른 프로세스로 넘어갈 때 발생하는 시간

-      자원 사용 균형

-      응답과 이용 간의 균형 유지

-      실행의 무한한 지연 X

-      우선순위제 실시

 

프로세스 스케줄링 기준

-      입출력 위주

-      연산 위주

-      일괄 처리형 & batch 형인가

-      대화형인가(I/O위주)

-      인터럽트인가?

 

스케줄링 종류

-      상위 단계 (Job스케줄링 – 중요한 2단계)

n  동시에 프로그램 실행 요청이 들어올 시 그 안에서 순서를 정해 주어야함

-      중간 단계

n  메모리에 올라온 정보를 Queue에 저장

-      하위 단계 (CPU를 건들이는 단계 – 중요한 1단계)

n  Dispatch (Dispatcher)

n  준비 완료 프로세스에게 CPU를 할당할 것인지를 결정

-   하위단계는 CPU에 스케줄링, 상위단계는 Ready Queue 스케줄링

 

방법-환경 별 분류

-      선점/비 선점 스케줄링

n  선점 스케줄링

u  Preemptive : 먼저 CPU를 선점해서 있는 것

u  양아치 같은 사람

u  우선순위가 낮은 프로세스가 실행 중이면 그 프로세스의 자리를 빼앗는다.

n  비 선점 스케줄링

u  이미 다른 프로세스가 CPU를 차지하고 있을 때 그 자리를 차지할 수 없다.

u  우선순위가 높아도 할 수 없다.

-      우선순위 스케줄링

n  우선순위가 높은 프로세스를 먼저 처리

n  정적 우선순위

u  프로세스를 시작해서 큐에 들어오면 우선순위가 정해진다. 그 우선순위는 어떠한 일이 있어도 바뀌지 않는다.

u  대체적으로 모든 프로세스가 여기에 속한다.

n  동적 우선순위

u  상황에 따라 우선순위가 바뀐다.

u  Ageing기법이 동적 우선순위에 속함

l  우선순위가 제일 낮은데 이 프로세스를 실행해야 한다. 그러한 경우에 일정 시간이 지나면 우선순위를 높여준다. 그러면 우선순위가 낮은 프로세스가 높아질 수 있다.

l  무한한 시간을 기다리게 만들 수 없기 때문에 이러한 기법을 사용한다.

-      기한부 스케줄링

n  해당 프로세스가 어떤 시점을 기준으로 그 기준 안에 시행을 하도록 만들어 준다.

n  경성 실시간 시스템

u  데드라인이 급박해서 딱 맞게 처리해야 한다.

n  연성 실시간 시스템

u  데드라인이 급박해도 조금 넉넉하게 처리 한다.

n  정적 스케줄링

u  시작하기 전에 순서가 정해 짐

u  RM(Rate Monotonic) 알고리즘

l  태스크 주기가 짧을수록 더 높은 우선순위를 부여

l  CPU사용율을 계산 했을 때 사용율이 0.779보다 작으면 사용이 가능하다는 것을 알려줌

l  다른 프로세스가 추가되어도 스케줄링이 더 이상 바꿔지지 않는다.

n  동적 스케줄링

u  예측이 잘 안되는 프로세스들을 사용

u  EDF(Earliest-Deadline First) 알고리즘

l  임계 시간이 가장 근접한 태스크를 가장 먼저 수행하는 방식

l  데드라인이 가까운 프로세스를 먼저 우선순위를 붙임

 

-      다중 프로세서 스케줄링

n  여러가지 스케줄링 기법을 함께 사용하는 기법

n  FCFS : First Come First Service

u  비 선점 스케줄링

u  도착한 순서데로 서비스를 해 줌

u  호위 효과

l  앞에 있는 프로세스가 매우 길 때 다음 프로세스는 그냥 기다린다.

l  앞에 어떤 프로세스가 있느냐 에 따라 시간이 달라짐

u  세 프로세스의 평균 반환 시간(Turnaround Time), 평균 대기 시간(Waiting Time)은?

l  도착 시간이 없으면 거의 동시에 도착

l  P1 = 21, P2 = 3, P3 = 6

l  1,2,3순서일 경우

n  P1이 21의 시간을 차지

n  P2는 3의 시간을 차지

n  P3은 6의 시간을 차지

u  => 네모난 차트로 그리면 Gantt Chart가 된다.

n  평균 반환 시간 = (21 + 24 + 30) / 3 = 25

n  평균 대기 시간 = (0 + 21 + 24) / 3 = 15

u  => 도착 순서가 1 -> 2 -> 3일 때라고 한다.

l  2,1,3의 순서일 경우

n  평균 반환 시간 = (3 + 24 + 30) / 3 = 19

n  평균 대기 시간 = (0 + 3 + 24) / 3 = 9

l  2,3,1의 순서일 경우

n  P2(0~3) -> P3(3~9) -> P1(9~30)

l  Burst Time가 적은 것부터 수행해야 반환 시간과 대기 시간이 짧아진다.

u  먼저 도착한 프로세스가 CPU에서 수행되는 Burst Time이 매우 길면, 그 다음 도착한 프로세스가 첫 번째 프로세스가 끝날 때까지 매우 긴 시간을 기다리게 되는 것

 

n  SJF(Shortest Job First) 방식

u  Burst Time이 짧은 것을 먼저 수행

u  비 선점 방식

u  P1 = 7, P2 = 8, P3 = 3, P4 = 6

u  먼저 들어와도 낮은 것 먼저 수행

u  SJF : 3 -> 4 -> 1 -> 2

l  0~3, 3~9, 9~16, 16~24

l  TA : (16 + 24 + 3 + 9) /4 = 13

l  W : (9 + 16 + 0 + 3)/4 = 7

u  FCFS : 1 -> 2 -> 3 -> 4

l  TA : (7 + 15 + 18 + 24)/4 = 16

l  W : (0 + 7 + 15 + 18)/4 = 10

n  우선순위 스케줄링

u  우선순위대로 서비스 해 준다.

u  비 선점 스케줄링

u  다른 조건이 없을 때, 우선순위가 같은 경우 먼저 온 프로세스부터 서비스 한다.

 

n  Round-Robin 스케줄링

u  선점 스케줄링 방식

u  CPU할당 시간이 정해준다. 그 시간이 지나면 CPU를 놓고 나온다.

u  Time Quantum을 정하는 것이 중요 함 (CPU 할당 시간)

u  절대적으로 시스템이 도와주지 못하면 할 수 없다.

l  문맥 교환이 이루어 져야 한다.

l  A상태를 저장하고 B상태로 바뀌는 것

u  CPU주변 장치들이 함께 빨라져야 가능하다.

u  오버 헤드

l  Time Quantum이 길어지면 FCFS와 같아진다.

l  Time Quantum이 짧아지면 문맥 교환 만 하다가 끝나게 된다.

u  80%정도는 I/O중심의 인터럽트에 사용

l  Ex) P1 = 7, P2 = 8, P3 = 3, P4 = 6

l  Time Quantum = 1

n  1-2-3-4-1-2-3-4-1-2-3-4-1-2-4-1-2-4-1-2-4-1-2-2

n  같은 프로세스는 문맥 교환 횟수에 포함 된다면 문맥 교환은 : 23

n  같은 프로세스는 문맥 교환 횟수에 포함 되지 않는다면 문맥 교환은 : 24

l  Time Quantum = 2

n  1-1-2-2-3-3-4-4-1-1-2-2-3-4-4-1-1-2-2-4-4-1-2-2

u  시분할 시스템에서 사용

 

n  SRT(Shortest Remaining Time) 스케줄링

u  처리 시간이 짧은 프로세스부터 시작

u  SJF 기법에 선점 방식 도입

n  다단계 큐(Multilevel Queue) 스케줄링

u  Ready Queue에서 뽑아서 스케줄을 한다.

u  처음에는 어차피 I/O인터럽트가 발생하기 때문에 FCFS를 그냥 사용한다.

u  뒤로 갈수록 RR방식의 스케줄링을 사용한다.

l  뒤로 갈수록 길어지는 프로그램

u  전면 작업 프로세스 / 후면 작업 프로세스

l  전면 : I/O, FCFS스케줄링 (I/O는 알아서 빠져 나옴)

l  후면 : 연산, RR스케줄링

n  HRN 스케줄링

u  SJF의 불평등을 어느정도 보완한 기법

u  값이 가장 큰 순서대로 수행

u  보통 대기시간이 높은 프로세스가 우선순위가 높아 진다.