Basic Concepts
To maximize CPU utilization, we need multiprogramming.
CPU 활용도를 극대화하기 위해서는 멀티프로그래밍이 필요합니다.
But, with a single CPU core, only one process can run at a time.
그러나 하나의 CPU 코어로 한 번에 하나의 프로세스만 실행할 수 있습니다.
This requires CPU scheduling.
이 경우 CPU 스케줄링이 필요합니다.
어떤 자원을 누가 언제 어떤 방식으로 사용할지를 결정해주는 것
-> 자원의 효율적인 관리
Observed property of a process
- Process execution consists of a cycle of CPU execution and I/O wait (CPU-I/O burst cycle) and alternates this cycle.
프로세스 실행은 CPU 실행 및 I/O 대기(CPU-I/O 버스트 주기) 사이클로 구성되며 이 사이클을 번갈아 수행합니다.
- CPU burst distribution is generally characterized as exponential, with many short CPU bursts, and a few long CPU bursts.
CPU 버스트 분포는 일반적으로 expensential로 특징지어지며, CPU 버스트가 짧고 CPU 버스트가 길기도 합니다.
Histogram of CPU-burst Times
I/O bound process typically has many short CPU bursts, while a CPU bound process has a few long CPU bursts.
입출력 바운드 프로세스는 일반적으로 짧은 CPU 버스트를 많이 발생시키는 반면 CPU 바운드 프로세스는 긴 CPU 버스트를 몇 개 발생시킨다.
CPU Scheduler
CPU scheduler
- selects a process to run among the processes in memory that are ready to execute
실행할 준비가 된 메모리의 프로세스 중에서 실행할 프로세스를 제외합니다
- allocates the CPU to one of them.
CPU를 둘 중 하나에 할당합니다.
CPU scheduling decisions may take place when a process
- Switches from running to waiting state (i.e., when an I/O is initiated).
- Switches from running to ready state (i.e., when an interrupt occurs).
- Switches from waiting to ready (i.e., when an I/O completes).
- Terminates.
- 실행 상태에서 대기 상태로 전환합니다(즉, I/O가 시작될 때).
- 실행 상태에서 준비 상태(즉, 인터럽트 발생 시)로 전환합니다.
- 대기 상태에서 준비 상태로 전환합니다(즉, I/O가 완료되면).
- 종료됩니다
When scheduling takes place only under 1 and 4, we say that the scheduling scheme is non-preemptive or cooperative.
스케줄링이 1 및 4에서만 수행되는 경우 스케줄링 체계가 비선제적 또는 협력적이라고 합니다.
All other scheduling is preemptive. -> affect OS design !
- Access to shared data, preemption while in kernel mode, etc.
- Virtually all modern Oss use preemptive scheduling algorithms.
Dispatcher
Another component involved in the CPU scheduling function is the dispatcher.
CPU 스케줄링 기능과 관련된 또 다른 구성 요소는 dispatcher입니다.
Dispatcher gives control of the CPU to the process selected by the scheduler
- switching context
- switching to user mode
- jumping to the proper location in the user program to restart that program
- 컨텍스트를 표시합니다
- 사용자 모드로 전환
- 사용자 프로그램의 적절한 위치로 이동하여 해당 프로그램을 다시 시작합니다.
Dispatch latency – time it takes for the dispatcher to stop one process and start another running.
- Should be as fast as possible !
Scheduling Criteria
- CPU utilization keep the CPU as busy as possible.
CPU 활용률은 CPU를 최대한 많이 사용합니다.
- Throughput # of processes that complete their execution per time unit.
Throughput 시간 단위당 실행을 완료하는 프로세스 수.
- Turnaround time amount of time to execute a particular process (from submission to completion).
This is the sum of the periods spent waiting in the ready queue, executing on the CPU, and doing I/O.
특정 프로세스를 실행하는 데 걸리는 시간입니다(제출에서 완료까지).
준비 대기열에서 대기하고 CPU에서 실행하고 I/O를 수행하는 데 소요된 시간의 합계입니다.
- Waiting time amount of time a process has been waiting in the ready queue.
대기 시간 프로세스가 준비 대기열에서 대기하는 시간.
- Response time amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment).
응답 시간 (시간 공유 환경의 경우)이 아니라 요청이 제출된 시점부터 첫 번째 응답이 생성될 때까지 걸리는 시간입니다.
Optimization Criteria
In most cases, CPU scheduler needs to
- Maximize CPU utilization and throughput.
CPU 활용률 및 처리량 극대화
- Minimize turnaround time, waiting time and response time.
turnaround time, 대기 시간 및 응답 시간 최소화
In this case, the average values are optimized.
이 경우 평균값이 최적화됩니다.
However, under some circumstances, optimizing the minimum and maximum values is preferred.
그러나 일부 상황에서는 최소값과 최대값을 최적화하는 것이 선호된다.
For interactive systems, it is more important to minimize the variance in the response time than to minimize the average response time.
대화형 시스템의 경우 평균 반응 시간을 최소화하는 것보다 반응 시간의 분산을 최소화하는 것이 더 중요합니다.
