[TIL] Process Scheduling

Program / Process

• Program
  • 하드 디스크 등에 저장 되어 있는 정적인 상태
  • 명령어 리스트를 내용으로 가진 실행 파일
• Process
  • 실행을 위해 메모리에 올라온 동적인 상태
  • 동일한 프로그램으로부터 별도의 실행을 가질 수 있다.
    • 즉, 하나의 프로그램에서 여러개의 프로세스를 가질 수 있다.

 

 

Process의 논리 메모리

• CPU는 프로그램을 하나 또는 여러개의 Process라는 단위로 생성하여 이를 실행한다.

• CPU는 Process 실행을 위해 각각 별도의 논리 메모리를 할당하게 된다.
  • code : 실행 코드를 저장하는 영역
  • data : 전역 변수를 저장하는 영역
  • heap : 동적으로 할당되는 메모리
  • stack : 함수 호출시 임시 데이터 저장 장소

 

 

CPU Scheduler

• ready 상태이지만 현재 running 상태로 전환되지 않은 프로세스들은 ready queue에서 기다리게된다.
• scheduler는 ready queue에서 CPU에서 실행될 프로세스를 선택하는 역할을 한다.

 

 

Dispatcher

• dispatcher는 선택된 프로세스가 CPU에 의해 실행될 수 있도록 만들어주는 역할을 한다.
• 즉, 선택된 프로세스에게 CPU를 할당하는 역할
  • context-switching
  • OS Kernel Mode → USER Mode
  • 실행되어야할 위치로 이동

 

Nonpreemptive Scheduling (비선점)

• 한 프로세스가 CPU를 할당받아 실행중이라면 다른 프로세스들이 CPU를 강제적으로 뺏을 수 없는 방식
• 프로세스가 CPU를 뺏을 수 없기 때문에 context-switching 발생 빈도는 선점형 알고리즘에 비해 적게 발생할 수 있다.
• 하지만 기아현상과 콘보이 효과 같은 것들이 발생할 수 있다는 단점도 존재한다.
• 따라서, CPU burst가 많은 CPU bound program에서 더 유리하게 동작할 수도 있음
• 특징
  • 신사적, 협력적(cooperative), 느린 응답성
  • 오랫동안 CPU를 점유하는 프로세스가 존재할경우 새로운 작업을 수행하는데 걸리는 시간이 길어짐

 

• FCFS (First-come-First-Served)
  • 먼저 도착한 순서대로 처리
  • 콘 보이 효과 → 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스가 처리되는 시간이 길어진다.

 

• SJF (Shortest-Job-First)
  • 프로세스의 다음 CPU Burst가 가장 짧은 프로세스부터 실행
  • 처리시간이 긴 프로세스는 우선순위가 뒤로 밀려 기아 현상이 발생한다.

 

• HRN (Highest Response Ratio Next)
  • 대기 시간과 처리 시간을 고려하여 CPU를 할당하는 기법
  • 우선순위 = (대기시간 + 처리시간) / 처리시간

 

 

Preemptive Scheduling (선점)

• 한 프로세스가 CPU를 할당받아 실행중이더라도 다른 프로세스가 CPU를 할당받을 수 있는 방식
• 즉, CPU에서 프로세스가 실행되고 있다고할지라도 특별한 event가 발생하면 다른 프로세스를 수행시키는 방식
• CPU가 수행하는 프로세스를 동적으로 변경하기때문에 비선점 알고리즘보다 context-switching이 더 자주 발생할 수 있음
• 하지만, 새로운 작업에 대한 응답 시간이 빠르고 기아현상과 콘보이 효과가 발생하지 않는 장점이 있다.
• 특징
  • 적극적, 강제적, 빠른 응답성, 데이터 일관성 문제

 

• SRTF (Shortest-Remaining-Time-First)
  • 남은 CPU burst가 가장 짧은 프로세스부터 실행
  • SJF에 선점형 스케줄링 기법을 추가한 것
  • SJF 처럼 기아 현상이 발생할 수 있음

 

• Round Robin
  • 한 프로세스가 할당 받은 시간동안 작업을 수행하다가 작업을 완료하지 못하면 대기 큐의 맨 뒤로 가서 자기 차례를 기다리는 선점형 스케줄링 기법

 

• Multi-level queue
  • 프로세스들을 그룹화해서 그룹마다 큐를 두는 방식
  • 즉, 여러개의 waiting queue를 두고, 각 Queue에 우선순위를 부여해 우선순위가 높은 Queue에 있는 프로세스에게 CPU를 할당하는 방식