운영체제 2023-04-03 수업정리

Flow

• Review
• Terminologies
• Basic Concepts

Review

---

Process

• 실행 중인 프로그램
• 실행 중인 프로그램의 상태 정보(PC, pid 등)는 PCB라는 자료구조에 저장한다.
  • PCB : Process Control Block, TCB라고도 한다.
  • Process의 실행 정보를 Context라고 하고, 이를 교체하는 것이 Context-Switching이다.
    • ready -> running
  • Context Switching이 일어나면 Idle time에 의한 오버헤드가 발생한다.

Scheduling

• Job Queue(모든 프로세스), Ready Queue(ready 프로세스), Device queue(I/O 프로세스)
• 각 Queue종류에 따라 Short-term, Long-term, Medium-term scheduler가 존재
• I/O bound process : 실행시간이 긴 편
• CPU boun process : I/O process에 비해 실행시간이 짧은 편

Terminologies

---

Workload

• 프로세스의 작업량, 아래와 같은 가정에서 시작한다.(문제 풀이에 있어서)
  1. 각각의 작업들은 동일한 시간동안 실행된다.
  2. 모든 job들은 동시에 도착한다.
  3. 한번 job을 실행하면, job을 완료할 때까지 실행된다.
  4. CPU bound process에 대해서만 생각한다(I/O는 일단 무시한다.)
  5. 각각의 job의 수행 시간은 알려져 있다.

Scheduler

• 수행되어야 할 job의 동작시점을 정하는 역할을 한다.
  • discrete time으로 끊어서 logic을 수행한다.(이는 scheduler에 따라 다르다.)

Metric

• scheduling의 quality를 바교하는 기준이다.
• turnaround time관점, respond time관점, fairness관점 등 여러 가지가 존재한다.

Burst

• 실행 시간

Basic Concepts

---

Observations

• CPU Burst에 대한 측정을 해보면 고르게 분포되어 있지 않고, 대부분의 작업들이 특정 frequency구간에 모여 있다.
• Scheduling에 있어서는 이러한 특징에 대해 고려해야 한다.
• 그렇다고 특정 Scheduling방법이 옳은 것은 아니다. 이는 Metric에 따라 다르다.

CPU Scheduler

• 일반적으로 CPU scheduling은 아래와 같은 4가지 경우 발생한다.
  1. running to waiting 상태로의 천이
  2. running to ready 상태로의 천이
  3. waiting to ready 상태로의 천이
  4. terminate로의 천이
• 1, 4는 scheduler가 nonpreemptive 방식으로 동작한다.
• 2, 3은 scheduler가 preemptive 방식으로 동작한다.
• 기본적으로 scheduler는 nonpreemptive, preemptive 모두 동작한다.

Preemptive vs Nnpreemptive

• nonpreemptive scheduling방식에서는 어떤 프로세스가 CPU를 점유하면, 해당 프로세스가 CPU제어를 내려놓기 전까지 다른 프로세스는 대기 상태에 머무르게 된다.
• preemptive scheduling은 대기 상태의 프로세스가 실행 중인 프로세스를 밀어내고 "치고 들어가는" 방식이다. 일반적으로 아래와 같은 경우 preemptive scheduling 을 사용한다.
  • 특정 하드웨어(타이머 등)
  • 공유 데이터로의 접근 시도
  • 커널 모드의 preemption
  • curtial OS activity의 interrupt
• preemtive scheduling은 데이터의 read/write에 대해 issue가 발생할 수 있다.
  • 여러 프로세스가 공유 자원을 사용하고 있을 때, read/write동작이 섞여 들어올 때 발생하는 문제이다.
    • 이러한 문제는 critical section등의 해법을 사용한다.
  • scheduling algorithm에서는 고려하지 않는다.(continue at Atomic operation)

Dispatcher

• dispatcher는 scheduler에 의해 선택된 프로세스로 CPU제어를 부여한다.
• 프로세스 실행을 위해 아래와 같은 동작을 수행한다.
  • switching context
  • switching to user mode
  • jumping to the proper location in the user program to restart that program
• 한 프로세스의 실행을 중지하고 다른 프로세스를 실행하는 과정에서 latency가 발생한다.

Scheduling Criteria(기준)

• CPU Utilization
  • 최대한 CPU 사용률을 높여서 성능을 향상시킨다.
• Throughput
  • 단위시간당 실행을 마치는 프로세스의 개수를 증가시킨다.
• Turnaround time
  • 특정 프로세스 실행에 걸리는 시간을 의미한다. 아래와 같이 계산 가능하다.$$T_{turnaround} = T_{completion} - T_{arrival}$$
• Waiting time
  • 프로세스가 ready queue에서 대기하는 시간을 의미한다. 아래와 같이 계산 가능하다.$$T_{waiting} = T_{turnaround} - T_{burst}$$
• Response time
  • process request이후 첫 response까지 걸리는 시간이다. 아래와 같이 계산 가능하다.$$T_{response} = T_{firstrun} - T_{arrival}$$
• Scheduling의 목적은 CPU utilization을 극대화하기 위해서, 즉 cpu busy time을 극대화하기 위해 프로세스 당 실행 시간은 줄이고 대기 시간 역시 줄이는 것이다.
• 평균보다는 minimum time, maximum time에 대한 optimization을 수행한다.
  • 실제로 사용자의 체감은 평균값이 아닌 최댓값, 최솟값에 영향을 받기 때문이다.
• response time에 대한 variance를 줄이는 것이 목적이다. 이는 preemptive scheduling에서의 starvation과 연관이 있다.