(CS)프로세스 스케줄링

프로세스 스케줄링

배치 처리 시스템

배치 처리 시스템이란?

• 자동으로 다음 응용 프로그램이 이어서 실행될 수 있도록 하는 시스템
• Application이 등록된 시간 순서대로 실행된다.(순차적인 실행)
• 큐를 생각하면 이해하기 쉽다.
• Application의 실행 시간에 따라 대기시간이 정해진다.
  • 우선도가 낮은 응용프로그램이 실행되고, 우선도가 높은 응용프로그램이 실행되면 우선도가 높음에도 불구하고 앞에 실행된 응용프로그램이 종료될때 까지 대기해야하는 단점이 있다.(대표적인 문제)
• 동시성과 다중사용에도 문제가 많다.
• 위에 여러 문제점을 해결하기 위해 멀티 프로그래밍/시분할 시스템이 등장하게 되었다.

시분할 시스템

시분할 시스템이란?

• 다중 사용자 지원을 위해 컴퓨터 응답 시간을 최소화하는 시스템
• 응용 프로그램이 CPU를 점유하는 시간을 잘게 쪼개어 실행될 수 있도록 하는 시스템

멀티 태스킹

멀티 태스킹이란?

• 단일 CPU에서, 여러 응용 프로그램이 동시에 실행되는 것 처럼 보이도록 하는 시스템

멀티 태스킹과 멀티 프로세싱

• 멀티 태스킹: 단일 CPU에 여러 프로그램을 잘게 쪼개서 동시에 실행되는 것 처럼 보이도록 하는 시스템
• 멀티 프로세싱: 다중 CPU에 하나의 프로그램을 병렬로 실행시켜 실행속도를 극대화시키는 시스템

멀티 프로그래밍

멀티 프로그래밍이란?

• 최대한 CPU를 많이 활용하도록 하는 시스템
  • 시간 대비 CPU활용도를 높이자.
  • 응용 프로그램을 짧은 시간 안에 실행을 완료 시킬 수 있다.
• 응용 프로그램은 온전히 CPU를 쓰기 보다, 다른 작업을 중간에 필요로 하는 경우가 많다.
  • 파일을 읽는 작업 등등
• 중간에 시간이 많이 소요되는 작업이 진행될때 CPU는 해당 응용프로그램 말고, 다른 응용 프로그램을 번갈아 실행하면서 대기시간을 단축시키고 그로 인해 응용 프로그램을 짧은 시간 안에 실행을 완료 시킬 수 있게 된다.

프로세스

프로세스란?

• 실행 중인 프로그램을 프로세스라고 한다.
  • 프로세스: 메모리에 올려저서, 실행 중인 프로그램
  • 프로그램: 어떤 작업을 위해 운영체제 위에서 실행할 수 있는 파일
    • ex: 웹 브라우저, 워드 프로세서, 카카오톡 등
  • 프로세서: 프로세스가 동작될 수 있도록 하는 하드웨어(CPU)
    • 프로세서는 한순간에 하나의 프로세스만 실행 가능
• 프로세스라는 용어는 작업, task, jab이라는 용어와 혼용
• 응용 프로그램 != 프로세스
  • 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있다.
• 하나의 응용 프로그램은 여러 개의 프로세스가 상호작용을 하면서 실행될 수도 있다.

스케줄링

스케줄링이란?

• 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업.
• 대기 시간은 최소화 하고, 최대한 공평하게 처리하는 것을 목적으로 한다.

스케줄러의 종류

• Long-Term Scheduler 장기 스케줄러
• Short-Term Scheduler 단기 스케줄러
• Medium-Term Scheduler 중기 스케줄러

스케줄링 알고리즘

FIFO 스케줄링

• 가장 간단한 스케줄링 알고리즘
• 프로세스 실행 요청 순서에 따라 실행
• 배치 처리 시스템
• FCFS 스케줄러라고 불리기도 한다.
• Queue 자료 구조를 사용해서 구현

최단 작업 우선(SJF) 스케줄링

• 실행 시간이 가장 짧은 프로세스부터 실행시키는 스케줄링 알고리즘

우선순위 기반 스케줄링

• Priority-Based 스케줄러
• 우선순위가 높은 프로세스부터 실행시키는 스케줄링 알고리즘
  • 정적 우선순위: 프로세스마다 우선순위를 미리 지정
  • 동적 우선순위: 스케줄러가 상황에 따라 우선순위를 동적으로 변경

Round Robin 스케줄러

• 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스 사이의 우선순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 방식의 알고리즘

프로세스 상태와 스케줄링

프로세스 상태

• running state: 현재 CPU에서 실행중인 상태
• ready state: CPU에서 실행 대기중인 상태
• block state: 특정 이벤트 발생 대기 상태(I/O 작업)

프로세스 상태에 따른 스케줄링 알고리즘

• Ready State Queue
• Running State Queue
• Block State Queue
• 3가지 상태에 따른 Queue를 각각 만들고, 상태에 따라 각각 Queue에 저장

선점형과 비선점형 스케줄러

선점형 스케줄러란?

• 하나의 프로세스가 다른 프로세스 대신 CPU(프로세서)를 차지할 수 있다.
• 프로세스 running중에 스케줄러가 이를 중단시키고, 다른 프로세스로 교체 가능하다.

비선점형 스케줄러란?

• 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU(프로세서)를 사용할 수 없다.
• 프로세스가 자발적으로 blocking 상태로 들어가거나, 실행이 끝났을 때만 다른 프로세스로 교체가 가능하다.

인터럽트

인터럽트란?

• CPU가 프로그램을 실행하고 있을때, 입출력 하트웨어 등의 장치나 또는 예외상황이 발생하여 처리가 필요할 경우 CPU에 알려서 처리하는 기술

인터럽트가 필요한 이유?

이미지 출처: https://www.fun-coding.org/interrupt.html

• 선점형 스케줄러에서 다른 프로세스로 교체하기 위해 지금 실행중인 프로세스를 중단시킨다.
  • 현재 진행중인 프로세스를 중단시키기 위해서는 스케줄러 코드가 실행되어야한다.
• 이때 사용하는 것이 인터럽트다.
• 예외 상황 핸들링
  • 입출력 하드웨어의 등의 장치 문제 또는 예외상황이 발생할 경우 CPU에 알려줘야 처리가 가능하다.

인터럽트 처리 예

• CPU가 프로그램을 실행하고 있을때
  • 입출력 하드웨어 등의 장치 이슈 발생
    • 파일처리가 끝났다는 것을 운영체제에 알려주기
    • 운영체제는 해당 프로세스를 block state에서 실행 대기 상태로 프로세스 상태를 변경
  • 예외 상황이 발생
    • 0으로 나누는 계산이 발생해서, 예외 발생을 운영체제에 알려주기
    • 운영체제가 해당 프로세스 실행 중시/에러 표시

class Test {
    public static void main(String[] args) {
        System.out.println("인터럽트 테스트");
        int a;
        int b = 0;
        a = 100 / b;
        System.out.println(a);
    }
}

• 인터럽트 테스트 문구는 정상적으로 출력
• 컴파일 단계에서 100 / 0 부분에서 문제가 있는지 알 수가 없다.
• 프로그램이 실행되고 100 / 0 부분에서 예외가 발생하면서, 프로그램이 종료된다.
  • Exception in thread “main” java.lang.ArithmeticException: / by zero at Test.main(Test.java:6)

인터럽트의 종류

• 타이머 인터럽트
  • 선점형 스케줄러를 처리하기 위해 필요
  • 하드웨어로 부터 일정 시간마다 타이머 인터럽트를 운영체제에 알려준다.
  • 일정 시간마다 프로세스의 교체를 위해 필요
• 입출력(IO) 인터럽트
  • 키보드, 마우스 등등 입출력 하드웨어 장치로부터 신호를 받았을때 처리하는 인터럽트

내부 인터럽트(소프트웨어 인터럽트)

• 주로 프로그램 내부에서 잘못된 명령 또는 잘못된 데이터 사용 시 발생
  • 0으로 나누었을때
  • Overflow/Underflow가 발생할때
  • 잘못된 명령 또는 허용되지 않는 공간 접근 시

외부 인터럽트(하드웨어 인터럽트)

• 주로 하드웨어에서 발생되는 이벤트
  • 전원 이상
  • 기계 문제
  • 키보드 등 IO관련 이벤트
  • Timer 이벤트

프로세스와 컨텍스트 스위칭

PCB

• 프로세스가 실행중인 상태를 캡쳐/구조화하여 저장
• 저장되는 내용
  • Process ID
  • Register값 (SP, PC)
  • Scheduling Info (Process State)
  • Memory Info (메모리 사이즈 Limit)
  • 등등

컨텍스트 스위칭(문맥 교환)

이미지 출처: https://www.fun-coding.org/contextswitching.html

• 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태를 보관하고 새로운 프로세스의 상태를 적재하는 작업
• 이전 프로세스의 상태를 보관하는 곳이 바로 PCB이다.
• 운영체제에 따라 PCB를 저장하는 위치는 달라질 수 있다.
• 디스패치: ready상태의 프로세스를 running상태로 변경하는 것
• 컨텍스트 스위칭은 굉장히 빠른 속도로 이루어진다.

프로세스간 커뮤니케이션(IPC)

• 원칙적으로는 프로세스간 접근이 허용되지 않는다.

IPC란?

• 프로세스간 통신 방법을 제공한다.

프로세스간 통신이 왜 필요할까?

• 성능을 높이기 위해 여러 프로세스를 만들어서 동시 실행
• 위와 같은 작업을 하기 위해 프로세스의 상태를 확인 및 데이터 송수신이 필요
• 예를 들어 fork() 시스템 콜이 있다.
  • fork() 함수로(C언어) 프로세스 자신을 복사해서 새로운 프로세스로 만들 수 있다.
  • 프로세스를 fork()해서 여러 프로세스를 동시에 실행 시킬 수 있다.
  • CPU의 코어개수 만큼 프로세스를 동시에 실행 가능(병렬처리)
  • 각 프로세스에서 처리한 데이터를 모아서 결과를 반환해야 하므로, 프로세스간 통신이 필요하다.

---

Reference

[10분 테코톡] 👩‍💻👨‍💻 쪼밀리와 오구의 Process vs Thread

운영체제란?

스케줄러의 종류