운영체제 7주차

---

 

1. 입출력 요청이나 자식 프로세스가 종료되기를 기다림 → 시스템 콜을 호출해서 운영체제가 호출되고 운영체제는 실행상태인 프로세스를 대기 상태(waiting)로 전환. 프로세스가 대기 상태로 바뀌었으므로 운영체제는 스케줄링 결정

2. 실행 상태(running)에서 준비 상태(ready) 상태로 전환될 때(인터럽트 발생) → e.g. 타이머나 입출력 장치에서 입출력이 종료되었을 때 → 인터럽트가 발생했으므로 운영체제가 개입하고 운영체제는 실행 중인 프로세스를 무조건 ready로 바꾸고 새로운 프로세스를 선택(스케줄링 결정)

3. 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때 → 입출력 OR 어떤 이벤트가 종료(e.g. 자식 프로세가 종료됐다 ⇒ exit 시스템 콜) → 인터럽트 → 운영체제 개입 → 운영체제는 새로운 프로세스 스케줄링 결정

4. 종료할 때 → exit 시스템 콜 실행됨 → 운영체제 실행 → 운영체제는 새로운 프로세스 실행

 

• 선점(preemptive)
  • 인터럽트가 발생하면서 CPU를 사용하던 프로세스가 CPU를 뺐김. 즉 프로세스는 CPU를 빼았기고 싶지 않은데도 CPU를 빼았기는 경우 (e.g. 입출력이 끝날 때 인터럽트가 발생하면 CPU 빼았김)
    • Timer Interrupt: 할당 시간 만료로 CPU를 강제로 빼았고 다른 프로세스에게 넘겨줘야 한다.
    • Device Controller의 I/O 완료 Interrupt: I/O 요청 작업을 마쳤으므로 해당 프로세스를 ready queue에 대기시켜줘야 한다.
  • 비선점 (nonpreemptive)
    • 일단 CPU가 한 프로세스에 할당되면, 프로세스가 CPU를 반환할 때까지(빼았기지 않고) CPU를 사용함. (여기서는 CPU를 예를 들었지만, 모든 컴퓨터 자원을 의미한다. 컴퓨터 자원이 비단 CPU만 있지는 않다)
      • I/O Interrupt: CPU가 어떠한 프로세스에 할당되어 있다가 I/O 요청이 들어오면 그 프로세스에게 CPU를 넘겨줘야 한다.
      • Terminate: 프로세스가 일을 모두 마치고 종료가 되면 CPU를 다른 프로세스에게 넘겨줘야 한다.

대표적인 5개의 스케줄링 기준(criteria)

<시스템 입장에서의 성능 척도>

1) CPU 사용률(utilization): 단위 시간당 CPU 사용시간의 비율 (1 ~ 100%, CPU 사용시간 / 단위시간(단위시간은 정하기 나름 1초, 1분, 1시간...))

2) 처리량(Throughput): 단위시간당 완료된 프로세스의 개수

<프로세스 입장에서의 성능 척도>

3) 반환 시간(Turnaround time): 특정 프로세스를 실행하는데 걸린 총 시간

4) 대기 시간 (Waiting time): 프로세스가 준비 큐에서 대기하면서 기다린 시간의 합, 즉 ready 큐에서 CPU 할당을 기다리는 시간의 총합. 무슨 말이냐면 준비 상태에서 실행 상태로 갔다가 다시 준비 상태로 갈 수도 있기에, 여러 번 준비 큐에서 기다리는 시간의 총합

5) 응답 시간(Response time): 작업을 요청한 후 첫 번째 응답이 나올 때까지의 시간 (응답이 시작되는 데까지 걸린 시간이며 응답을 출력하는 데 걸리는 시간이 아님 ⇒ 예를 들어 모니터에 100개의 글자를 출력하는 프로세스라면 100개의 문자를 모두 출력하는 시간이 아니라 1개의 문자를 출력하는 데까지 걸린 시간을 말한다.)

운영체제의 CPU 스케줄러는 ① CPU 이용률을 최대화하고 ② 처리량을 최대화하고 ③ 반환 시간을 최소화하고 ④ 대기 시간을 최소화하고 ⑤ 응답시간을 최소화해야 하지만 현실적으로 이 5가지 목표를 동시에 달성하는 건 불가능하므로 응용 분야에 따라서 적절한 목표를 정해야 한다(e.g. 대화식 시스템에서(문자를 입력하면 모니터에 출력)는 평균 응답시간을 최소화하고 응답시간의 변동폭을 줄이는 걸 최소화해야 한다)

 

 

대표적인 CPU 스케줄링 알고리즘

 

 

 

 

1. FCFS(먼저 요청한 것을 먼저 서비스, 선착순 스케줄링 알고리즘)

※ 프로세스는 CPU burst와 I/O burst가 서로 왔다갔다 하면서 실행된다. CPU burst는 CPU 명령을 실행하는 것을 말하고(running state) I/O burst는 I/O를 요청한 다음 기다리는 시간임(waiting state). 만약 어떤 프로세스의 CPU burst time이 10초라고 하면, 이프로세스의 어떤 특정 작업이 완료되기 위해서는 CPU가 10초 동안 이 프로세스를 작업해줘야 한다는 의미이다. 그 다음 I/O burst가 왔다는 것은 10초 동안 이 작업을 한 후에, 키보드로부터 입력을 받는 작업이 뒤따라온다든가, 어떤 I/O 작업이 수행되어야 다음 CPU가 작업을 할 수 있다는 것을 의미한다.

프로세스가 3개가 있고 burst time은 각각 24ms, 3ms, 3ms 라고 가정하자. 프로세스의 도착순서: P1, P2, P3 라는 의미는 ready queue에 연결된 순서를 의미한다.

 

프로세스 도착순서를 바꾼다면?

위 템플릿에서 보는 것처럼 프로세스 도착순서만 바꾸어도 평균 대기시간이 매우 단축된다. 즉 짧은 프로세스를 먼저 처리하면 평균 대기시간이 좋아진다

• FCFS는 선착순으로 프로세스를 처리하게 되니, Convoy effect라는 문제가 발생한다.

• 입출력 같은 특정 이벤트가 발생하기 전까지는 CPU를 반납하지 않으므로 시분할 시스템(time sharing, 설정 타이머 주기로 CPU를 빼앗음)을 사용할 수 없다!!

 

CPU 시간이 짧은 것을 먼저 처리 (FCFS 보안)

※ CPU 버스크 크기 비교 ⇒ CPU 사용 시간을 운영체제가 사전에 알고 있다고 가정

 

1. P1이 도착시간이 가장 빠르므로 P1이 실행이 된다.

2. 비선점식이므로 P1은 7초의 실행시간을 보장받는다. P1의 실행이 끝나고(비선점이므로) 이미 나머지 프로세스가 다 준비 큐에 도착을 했으므로 Burst time(실행 시간)을 보고 가장 짧은 실행시간을 가진 프로세스 P3를 실행시킨다.

3. 준비큐에 남아 있는 P2와 P4의 실행시간이 같기 때문에 이런 경우에는 준비 큐에 먼저 도착한 프로세스를 실행시킨다.

 

 

※ 선점식 SJF는 Shortest-Remaining-Time-First(SRTF)라고도 함

1. 우선 P1이 가장 먼저 도착했으므로 P1을 먼저 실행시킨다.

2. 2초에 P2가 도착하면, 즉 새로 도착한 프로세스가 있으면 도착한 프로세스의 CPU 시간과 현재 실행 중인 프로세스의 남은 CPU 시간을 비교해서 더 짧은 CPU 시간을 가진 프로세스를 실행시킨다. P1의 남은 CPU 시간은 5초이고 P2의 CPU 시간은 4이므로 P2를 실행시킨다.

3. 4초에 P3가 도착하면 다시 P3과 P2를 비교해 더 짧은 CPU 시간을 가진 P3를 실행시킨다.

4. 5초에 P3가 종료되고 동시에 P4가 도착했으므로 남아있는 프로세스 중에 남아있는 CPU 시간이 가장 작은 프로세스를 실행시킨다. (새로 도착하는 프로세스가 없는 상태에서 현재 실행중인 프로세스가 종료되면 남아 있는 프로세스 중에 CPU 시간이 가장 작은 프로세스를 실행시킨다)

 

비선점식과 선점식을 비교했을 때, 평균 대기 시간을 기준으로 선점식이 더 나은 퍼포먼스를 보인다!! 하지만 위 비교의 기본 전제는 CPU 실행 시간을 안다는 것이었는데, 현실에서는 어떤 프로세스의 CPU 실행시간을 사전에 알기란 사실상 불가능하다. 그러면 SJF를 쓸 수는 없느냐? 라고 묻는 다면 정확하게는 아니지만

CPU 버스트 크기(

CPU 실행 시간)를 대략적으로 예측하는 방법을 사용한다.

 

 

• tn = n번째 CPU 시간(운영체제가 어떤 프로세스를 실행하고 이 프로세스를 준비나 대기 상태로 바꿀 때, 그 때마다 PCB에 시간을 기록한다. CPU 시간 = 대기나 준비 상태에 들어간 시간 - 처음 CPU 할당했을 때 시간)

• 다음 프로세스 CPU 시간 예측(아직 실행되지 않아서 알 수가 없으므로 예측)

 

위 그래프를 보면 처음 예측은 많이 빗나갔으나 점차 실제 실행값에 근사하고 있음을 알 수 있음.

 

FCFS, SRTF 예제