스케줄링
CPU가 작업을 분배하는 방법
Last updated
CPU가 작업을 분배하는 방법
Last updated
프로세스가 생선된 후 모든 상태 변화를 조정해주는 일을 한다. CPU와 시스템 자원을 어떻게 배정할지 결정한다
🔴 고수준 스케줄링 가장 큰 틀에서 이뤄지는 스케줄링이다. 시스템의 전체 작업 수를 조절해주며, 작업을 받아 들이거나 거부한다.
시스템의 전체 작업수는 멀티 프로그래밍 정도 이다
🟠 저수준 스케줄링 가장 작은 틀에서 이뤄지는 스케줄링이다. 프로세스에 CPU를 할당하거나, 프로세스 상태를 상태로 바꿀지 결정한다.
🟡 중간수준 스케줄링 프로세스를 활성화 할지 말지 결정하여 전체 프로세스의 수를 조절하는 방식이다. 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
모든 프로세스가 공평하게 작업하는 것 이다. 자원을 골고루 배분하고 안정적으로 작동하도록 해야된다.
🔴 공평성 : 모든 프로세스는 공평하게 자원을 배정받아야 하며, 특정 프로세스가 배제되어서는 안된다 🟠 효율성 : 시스템 자원이 유휴시간 없이 사용되도록 스케줄링 하고, 유휴 자원을 사용하는 프로세스는 우선권을 가진다. 🟡 안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 보호한다. 🟢 확장성 : 프로세스가 증가해도 안정적으로 작동해야 한다 🔵 반응 시간 보장 : 응답이 없는 경우 시스템이 멈춘것으로 가정하기 때문에, 적절한 시간 안에 프로세스의 요구에 반응해야 한다. 🟣 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다
🔴 선점형 : CPU를 운영체제가 강제로 뺏을 수 있는 방식 🟠 비선점형 : CPU를 빼앗을 수 없는 방식
선점형 스케줄링은 운영체제가 필요하다고 판단 되면, 실행 상태에 있는 프로세스의 작업을 중단 시키고 새로운 작업을 시작할 수 있다.
비선점형 스케줄링은 프로세스가 종료& 자발적 대기 전까지는 실행된다. 그러나 CPU 사용시간이 긴 프로세스 떄문에 시스템의 처리율이 떨어질 수 있다.
프로세스는 커널프로세스와 일반 프로세스로 나뉘어 진다. 이때 스케줄러에 할당되는 우선순위는 커널 프로세스가 일반 프로세스 보다 높다.
CPU 집중 & 입출력 집중
프로세스는 준비, 실행, 대기를 거쳐 완료 된다. CPU를 할당받아 실행하는 작업을 CPU 버스트, 입출력 작업을 I/O 버스트 라고 부른다.
🔴 CPU 집중 프로세스 : 수학 연산과 같이 CPU를 많이 사용하는 프로세스를 말한다. 🟠 입출력 집중 프로세스 : 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스이다.
전면&후면 프로세스
🔴 전면 프로세스 : 사용자에게 입력을 받아와야 하는 프로세스 🟠 후면 프로세스 : 사용자의 응답이 필요하지 않으면 프로세스
프로세스의 중요도는 PCB에 표시된다. CPU 스케줄러는 PCB를 뒤져서 가장 높은 순위의 프로세스에 CPU를 할당 한다.
🔴 고정 우선순위 방식 : 프로세스가 끝날 때 까지 바뀌지 않는 방식이다. 🟠 변동 우선순위 방식 : 프로세스 생성 시 부여받은 우선순위가 중간에 변하는 방식이다.
대기상태는 입출력이 완료되기를 기다리는 프로세스가 모여있는 곳 이다. 같은 장치의 입출력을 기다리는 프로세스의 PCB는 동일한 입출력 큐에 모여 있게 된다.
준비큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기큐는 여러개의 PCB를 동시에 꺼내 준비 상태로 옮긴다. 입출력이 동시에 끝나는 경우에 여러 인터럽트가 한번에 처리되는데, 이떄 인터럽트 벡터를 사용한다.
선점형 알고리즘과 비선점형 알고리즘이 있다. ** 비선점형은 최근에 거의 사용되지 않는다 **
알고리즘을 선택할 때 에는, 평가 기준이 있어야 한다.
🔴 CPU 사용률 : CPU가 사용된 시간을 측정하는 방법이다. 🟠 처리량 : 단위 시간당 작업을 마친 프로세스의 수다. 🟡 대기 시간 : 실제 작업이 이뤄지기 전 까지 대기 시간이다. 🟢 응답 시간 : 프로세스 시작 후 첫번째 출력&반응 까지 걸리는 시간이다. 🔵 반환 시간 : 프로세스가 생성된 후 종료되어 자원을 반환 할 때 까지 걸리는 시간이다.
성능은 평균 대기시간 ( $모든 프로세스의 대기시간\over 프로세스수$ ) 을 본다
준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다. (FIFO) 단일큐 이며, 프로세스가 끝나야 다음 프로세스를 실행할 수 있다.
처리시간이 긴 프로세스가 CPU를 오래동안 차지하는 걸 콘보이 효과 라고 한다.
실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다. 작은 작업을 먼저 실행하기 때문에 효율성이 좋아진다.
이런 장점에도 불구하고 sjf 스케줄링을 사용하지 못하는 이유
🔴 운영체제가 종료시간을 예측하기 힘들다 🟠 공평하지 못하다
최고 응답률 우선 스케줄링이다. 프로세스 실행 시간을 기준으로 하여 가장 적은 시간을 사용하는 프로세스에게 우선권을 주어준다.
우선순위 = $대기시간 + 사용시간 \over CPU사용시간$
순환 순서 방식이다. 한 프로세스가 할당받은 시간동안 작업을 진행하다 끝나지 않으면 맨뒤로 가서 차례를 기다리는 방식이다. 자신의 타임슬라이스 만큼 CPU를 사용할 수 있게된다.
SJF 와 라운드 로빈을 혼합한 방식으로 최소 잔류시간 우선 스케줄링 이라고 한다. 남아있는 잔여 시간이 가장 적은 프로세스를 우선적으로 선택한다. 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 한다.
프로세스의 중요도에 따라 우선순위를 갖는데 우선순위를 반영한 알고리즘이다.
🔴 SJF 스케줄링 : 작업 시간이 짧은 프로세스에 높은 우선순위 🟠 HRN 스케줄링 : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여한다. 🟡 SRT 스케줄링 : 남은 시간이 짧은 프로세스에 높은 우선순위를 부여한다. 🟢 고정 우선순위 알고리즘 : 한번 우선순위를 부여받으면 종료될때 까지 우선순위가 고정된다 🔵 변동 우선순위 알고리즘 : 일정 시간마다 우선순위가 변한다.
다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것 만으로 우선순위가 결정된다.
우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식이다.
우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다. CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아 가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
프로세스가 CPU를 한 번씩 할당 받아 실행될 때 마다 프로세스의 우선순위를 낮춤으로써, 낲은 프로세스의 실행이 연기되는 문제가 완화된다.
우선순위가 낮을수록 CPU의 타임슬라이스가 크다.
시스템을 보호하는 데 매우 중요한 작업이다. 입출력이 완료되면 이벤트를 발생시켜 CPU에게 알려주는 작업이다.
실행중인 명령어로 발생하는 동기적 인터럽트& 실행 중인 명령어와 무관하게 발생하는 비동기적 인터럽트이다.
인터럽트 발생시 인터럽트 번호와 번호가 붙어있는 함수의 쌍으로 이루어져 있다. 각각의 인터럽트에는 고유 번호 IRQ 가 있다. 인터럽트는 한순간에 동시에 발생하는 인터럽트 벡터로 발생한다.
