CPU 스케줄링

스케줄링 알고리즘

I/O bound job과 CPU bound job이 섞여 있기 때문에 스케줄링이 필요하다.

성능 척도

시스템 입장에서 성능 척도

• CPU utilization(이용률)
  전체 시간 중에서 CPU가 놀지 않고 일한 시간의 비율

• throughput(처리량)
  주어진 시간 동안에 몇개의 일을 처리했는가

프로그램 입장에서 성능 척도

• turnaround time(소요시간, 반환시간)
  CPU를 쓰기위해 기다리고 쓰러 들어와서 다 쓰고 나갈 때 까지 걸린 총 시간
  특정 프로세스를 실행하는 총 시간이 아니라 CPU버스트와 I/O버스트를 반복할 때 CPU를 쓰러 들어와서 I/O를 하러 나갈 때 까지의 시간이다.

• waiting time(대기 시간)
  CPU를 쓰려고 레디큐에서 기다리는 시간

• response time(응답 시간)
  레디큐에 들어와서 처음으로 CPU를 얻기 까지 걸린 시간

preemptive스케줄링에서 CPU를 얻었다 뺏겼다를 반복할 때 반복된 대기시간을 다 합친것이 waiting time이다.
response time은 최초의 CPU를 얻기 까지의 시간이다.

FCFS(First Come First Served)

먼저 들어온 것을 먼저 처리
CPU를 길게 쓰는 작업이 먼저 처리되면 평균 waiting time이 길어진다.
긴 작업 뒤에 짧은 작업이 있는 것을 convoy effect라고 한다.

SJF(shortest job first)

CPU버스트가 짧은 프로그램에 CPU를 주는 스케줄링
평균 대기 시간이 가장 짧게 된다.

nonpreemptive스케줄링에서는 CPU를 짧게 쓰는 프로세스에 CPU를 줬는데 그 보다 더 짧게 쓰는 프로세스가 들어와도 CPU를 뺏지 않는다.
preemptive스케줄링에서는 CPU를 줬더라도 더 짧은 프로세스가 들어오면 CPU를 뺏어준다.

preemptive방식이 평균 대기 시간이 더 짧다.
다만 CPU를 길게 쓰는 프로세스는 영원히 CPU를 받지 못할 수도 있다. 이것을 starvation문제 라고 한다.
그리고 CPU사용시간을 미리 알 수가 없고 과거의 CPU버스트 시간을 보고 추측해야 한다.

priority scheduling

우선순위가 가장 높은 프로세스에 CPU를 준다.

현재 우선순위가 가장 높은 프로세스에 CPU를 줬는데 그 보다 더 높은 우선순위의 프로세스가 들어왔을 때 CPU를 뺏지 않으면 nonpreemptive, 뺏으면 preemptive이다.
preemptive에서는 우선순위가 낮은 프로세스가 CPU를 얻지 못할 수도 있다.
이 스타베이션문제를 해결하기 위해 우선순위가 낮더라도 오래 기다리면 우선순위를 조금씩 높여주게 되는데 이것을 aging기법이라 한다.

SJF는 일종의 priority scheduling이다.

round robin

CPU를 줄 때 동일한 크기의 할당 시간을 세팅해서 주고 그 시간이 끝나면 타이머 인터럽트에 의해 CPU를 빼앗겨 레디 큐에서 기다리게 된다.

CPU를 돌아가며 조금씩 줬다 뺏었다 하기 때문에 응답 시간이 빠르다.

할당 시간을 지나치게 크게 잡으면 FCFS처럼 되고
지나치게 짧게 잡으면 문맥 교환 오버헤드가 커진다.

multilevel queue

레디 큐를 여러 개로 분할한다.

foreground 큐 - interactive한 일
background 큐 - batch(사용자와 상호작용이 없는)한 일

foreground는 사용자와 상호작용을 하기 때문에 round robin사용
background는 CPU만 오래 사용하고 응답 시간이 빠르다고 좋을게 없기 때문에 문맥 교환 오버헤드를 줄이기 위해 FCFS사용

큐에 대한 스케줄링이 필요한데
우선순위를 강하게 설정하면 우선순위가 높은 큐가 비었을 때만 우선순위가 낮은 큐의 프로세스에 CPU를 주게 되니 스타베이션이 발생할 수 있다.
스타베이션을 막기 위해 각 큐에 CPU시간을 적절한 비율로 할당한다.

multilevel feedback queue

프로세스가 다른 큐로 이동이 가능하다.
에이징을 이 방식으로 구현할 수 있다.

보통은 처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 넣는다. 그리고 CPU할당 시간을 짧게 준다.
아래 큐로 갈수록 round robin의 할당시간을 길게 준다.
제일 아래 큐는 FCFS를 쓴다.
할당시간 안에 처리를 하지 못하면 아래 큐로 강등되는 것을 반복한다.

이렇게 하면 CPU사용시간이 짧은 프로세스에 우선순위를 더 많이 주게 되고
CPU사용시간이 긴 프로세스는 우선순위를 낮추게 된다.
그리고 CPU사용시간 예측이 필요없다.

real time scheduling

hard real time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야한다.
soft real time task는 일반 프로세스에 비해 높은 우선순위를 갖도록 해야한다.

thread scheduling

• local scheduling
  user level thread는 운영체제가 스레드의 존재를 모르는 상태이고 사용자 프로세스가 직접 스레드를 관리한다.

• global scheduling
  kernel level thread는 운영체제가 스레드의 존재를 알고있고 프로세스 스케줄링 하듯이 어떤 스레드를 스케줄할지 결정한다.

process synchronization

여러 주체가 하나의 데이터를 동시에 접근하려고 할 때 원치않는 결과를 얻을 수 있다.

공유 데이터(x = 2)에 프로세스1이 접근하고 그 후에 프로세스2가 접근해서
프로세스1에서 x = x + 1;을 해서 리턴하고
프로세스2에서 x = x - 1;을 해서 리턴하면
공유 데이터의 x는 2가 아니라 1이 된다.

여기서 x = x + 1; x = x - 1; 이 부분을 critical section이라 한다.

race condition

여러 프로세스들이 동시에 공유 데이터를 접근하는 상황.