Introduction

💡 System 의 자원을 Process/Thread 에게 어떻게 할당할 것인가?

• Assign system resource (CPU, I/O device, etc) to processes/threads to meet system objectives (response time, turnaround time; 프로세스 시작부터 끝까지 총 시간 , throughput; 시간당 처리하는 프로세스 수, or fairness..)
• In practice, these goals often conflict

✔️ CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU에 할당할 프로세스를 고른다
  

✔️ Dispatcher

• CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다
• 이 과정을 Context Switch 라 한다

✔️ CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우다
1. Running 👉 Blocked (ex: I/O 요청하는 System Call)
2. Running 👉 Ready (ex: 할당시간만료로 timer interrupt)
3. Blocked 👉 Ready (ex: I/O 완료후 인터럽트)
4. Terminate

• 1, 4 에서의 스케줄링은 nonpreemptive 비선점
• 나머지는 preemptive 선점

✔️ Scheduling Criteria (Performance Index, 성능 척도)

• CPU utilization 이용률
  • Keep the CPU as busy as possible
• Throughput 처리량
  • of processes that complete their execution per time unit
• Turnaround Time 소요,반환 시간
  • amount of time to execute a particular process
• 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)

---

Scheduler 종류

장기 스케줄러

(or Job scheduler)
✔️ 시작 프로세스 중 어떤 것들을 ready queue 로 보낼지 결정
✔️ 프로세스에 memory(및 각종 자원)을 주는 문제
✔️ degree of Multiprogramming 을 제어
✔️ time sharing system 에는 보통 장기 스케줄러가 없다 (무조건 ready)

단기 스케줄러

(or CPU scheduler)
✔️ 어떤 프로세스를 다음번에 runnning 시킬지 결정
✔️ 프로세스에 CPU를 주는 문제
✔️ 충분히 빨라야 함 (millisecond 단위)

중기 스케줄러

(or Swapper)
✔️ 메모리가 너무 부족할 때, 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄
✔️ 프로세스에게서 memory를 뺏는 문제
✔️ degree of Multiprogramming 을 제어

---

Processor Scheduling

Three types of processor scheduling

✔️ Long-term scheduling (admission scheduler) : 시스템에 입장을 허락할 것이냐

• Decide which jobs/processes to be admitted to the system
  • Contorl the degree of multiprogramming
• Once admitted, a job or user program becomes a process
  • The process may be added to the ready queue for the short-term scheduler or to a queue for the medium-term scheduler in a swapped-out condition

✔️ Mid-term scheduling (swapper) : 메모리로 가져올 것이냐 쫓아낼 것이냐

• Remove a process from main memory and place them on secondary memory, or vice versa Sswap in out process

✔️ Short-term scheduling (dispatcher) : CPU에 할당

• Decide which of the ready, in-memory processes to be executed by the processor following a clock interrupt, IO interrupt, or OS call

• Execute most frequently

• The main objective of short-term scheduling is to allocate processor time to optimize system behaviour

--

Disk Scheduling

✔️ Disk Cache 디스크 섹터의 카피본을 가지고 있고, 디스크 access 없이 제공하는 방법

• Disk Cache is a buffer in main memory for disk sectors
  • Contains a copy of some of the sectors on the disk

✔️ When an I/O request is made for a particular sector, a check is made to determine if the sector is in the disk cache

• If YES 👉 the request is satisfied via the cache
• If NO 👉 the requested sector is read into the disk cache from the disk

✔️ LRU; Least Recently Used

• The most commonly used algorithm
• The block that has not been referenced for the longest time is replaced
• A stack of pointers reference the cache
  • Most recently referenced block is on the top of the stack
  • When a block is referenced or brought into the cache, it is placed on the top of the stack

✔️ LFU; Least Frequently Used

• The block that has experienced the fewest references is replaced
• A counter is associated with each block
• Counter is incremented each tiem block is accessed
• When replacement is required, the block with the smallest count is selected
• Problematic When
  • Certain blocks are referenced relatively infrequently overall, but when they are referenced, there are short intervals of repeated references due to locality, building up high reference counts. After such interval is over, the reference count may br misleading

---

🔗 Reference

[KUOCW] 최린 교수님의 운영체제 강의를 수강하고 정리한 내용입니다. 잘못된 내용이 있다면 댓글로 알려주시면 감사하겠습니다 😊