3. Processes - Process scheduling

1. Process Scheduling

Scheduling : 컴퓨터 시스템에서 여러 작업 중에서 어떤 작업을 우선순위에 따라 선택하여 실행할지 결정하는 작업 (다음을 선택하는것)

 

Process scheduling : CPU에서 실행할 프로세스 선택

• 각 프로세서에서 한 번에 하나의 프로세스만 실행할 수 있다
• 다른 프로세스는 기다려야 한다.

scheduling 목표

• cpu 활용성을 최대한 높여주는것
• 유저가 프로그램과 상호작용 하게 할수있는것

 

2. Scheduling Queue

Scheduling queue : 운영체제에서 프로세스들을 저장하는 자료구조 

• 종류 : Ready queue, job queue, device queue
• 어떻게 구현 ? linked list 로 대부분 만든다.

PCB in Linux

C Structure task_struct ( = PCB를 나타내는 리눅스성의 structure)

pid_t pid; /* process identifier */

long state; /* state of the process */

unsigned int time_slice /* scheduling information */

struct task_struct *parent; /* this process’s parent */

struct list_head children; /* this process’s children */

struct files_struct *files; /* list of open files */

struct mm_struct *mm; /* address space of this process */

 

각 queue는 일반적으로 linked list of PCBs로 표시된다.

linked list of PCBs

 

3.Queueing Diagram

Representation of process scheduling

하나의 프로세스가 생성되어 실행되면서, 그 수명 주기 동안 다양한 스케줄링 큐에서 작업을 처리하게 된다

4.Schedulers

스케줄러가 큐에서 프로세스를 선택할 때 어떤 방식으로 선택하는가?

• Long-term scheduler (job scheduler)
• Short-term scheduler (CPU scheduler)

 

Short-term scheduler (CPU scheduler)

 

Short-term scheduler

• 자주 실행된다(최소 100msec에 한 번).
• Scheduling time은 매우 짧아야 한다.

 

Long-term scheduler (job scheduler)

Long-term scheduler

• Degree of multiprogramming 제어
  • 시스템이 안정 상태에 있을 때, 생성된 프로세스의 평균 수 == 종료된 프로세스의 평균 수 같아진다!
• 덜 자주 실행된다
  • 프로세스가 시스템을 떠날 때만 실행됨
• I/O-bound and CPU-bound processes를 적절하게 혼합해서 사용해라!

 

 

• 일부 프로그램에서는 long-term scheduler가 없거나 최소일수 있다.
  • Ex) UNIX, Windows
• 일부 Time-sharing system에 medium-term scheduler(레디 큐 -> 잡큐 로 돌려보냄) 가 있다.
  • 메모리에서 프로세스를 제거하여 멀티프로그래밍의 정도를 줄임

 

5.Context Switch

실행 중인 프로세스를 전환하려면 상황에 맞는 스위치가 필요하다.

• Save state (context) of current process (PCB) (현재 프로세스(PCB)의 상태(컨텍스트) 저장)
• Restore state (context) of the next process (다음 프로세스의 상태(컨텍스트) 복원)

Context switch : 운영체제에서 여러 프로세스를 실행하기 위해 CPU가 현재 실행중인 프로세스의 상태(context)를 저장하고, 다음 실행할 프로세스의 상태를 불러오는 과정

 

“Context” includes

• Register contents
• OS specific data

 

When to switch?

• Multitasking
• Interrupt handling

Context switching 에는 상당한 overhead가 필요하다. (overhead: 이동 과정에서 발생하는 추가적인 처리 비용)

그러면 어떻게 overhead를 줄일수있을까?

1. Time Slice의 조절

2. 다중 큐(Multi-Level Queue) 구성

3. 프로세스의 수 조절

4. 캐시 활용

 

context-switching 을 위한 H/W지원

• H/W switching
• 빠른 switching을 위한 여러 register 세트