[운영체제] 7. Scheduling 기법

2022.05.03 - [컴퓨터 공학/0 +운영체제] - [운영체제] 6. Race Conditions(2) -Semaphores, Mutex and Monitors

[운영체제] 6. Race Conditions(2) -Semaphores, Mutex and Monitors

 

지난 시간에는 Race Condition을 해결하기 위한

뮤텍스, 세마포어, 모니터 등등.. 기법에 대해서 배웠습니다.

이번 포스팅에서는 cpu스케줄링 기법에 대해서 설명하겠습니다..! 🧑‍💻

 

---

 

 

 

우리는 계획을 하고 그 일을 실천하면서 살아가고 있다.

(하지만 살다보면 모든 일은 계획대로 되지않는다라는 것을 알게 된다....🙀)

컴퓨터도 우리와 마찬가지로 모든작업에 대해서 스케줄링한다.

왜 우리는 스케줄을 정하고 일을 하는것일까?

효율적으로 인생을 살기 위해서 아닐까?

마찬가지로 컴퓨터도 효율적으로 작업을 수행하기 위해 스케줄링을 한다.

컴퓨터는 어떻게 스케줄링하는지에 대해서 알아보자~~! 🤩

 

 

 

Scheduling

https://ko.wikipedia.org/wiki/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81_(%EC%BB%B4%ED%93%A8%ED%8C%85) 

스케줄링 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

스케줄링은 무엇인가?

다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법

cpu가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야하는데...

이때 다음 프로세스가 어떤 프로세스를 선택하는 알고리즘을 뜻한다.

알고리즘이란 말은 프로레스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다는 의미...!

 

스케줄링은 적용 시점에 따라 아래 2가지로 분류 할 수 있다.

• preemptive
  • 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 cpu를 강제로 점유하여 실행 할 수 있다.
  • 선점은 프로세스가 cpu를 점유하고 있는 동안 i/o나 인터럽트가 발생한 것도 아니고 모든 작업이 끝내지도 않았는데, 다른 프로세스가 해당 cpu를 강제로 점유 할 수 있다.
• non-preemptive
  • 비선점은 한 프로세스가 한 번 cpu를 점유했다면, i/o(프로세스가 실행->대기로 변경되는 경우)또는 프로세스가 종료될 때 까지 다른 프로세스가 cpu를 점유하지 못하는 것.

 

 

• 스케줄링 시점
  • 프로세스가 생성 될 때
  • 프로세스가 종료 될 때
  • 프로세스 I/O, 세마포어, 또는 다른 무언가로 대기할 때
  • I/O인터럽트 발생 할 때
  • 선점형(preemptive)스케줄링 알고리즘의 경우 클럭 인터럽트가 발생 할 때
    • 수행->대기
    • 수행->준비
    • 대기->준비
    • 수행->종료
• 스케줄링 오버헤드(context switching cost)
  • 모드 변경비용(사용자->커널->사용자)
  • 프로세스 문맥 저장, 복구
  • 메모리 맵 저장 복구
  • CPU 캐쉬 무효화
  • 기타

 

---

 

Scheduling - process behavior

스케줄링에서 프로세스의 두가지 작업행위가 있다.

• a. CPU-bound process
  •  대부분 계산만 한다.
• b. I/O-bound process
  • 대부분 I/O처리만 한다.

기본적으로 I/O bound가 CPU bound보다 우선순위가 높아야 한다.

 

 

---

 

 

Type of Scheduling

https://jhnyang.tistory.com/372

[운영체제OS] 장기스케줄러 vs 중기스케줄러 vs 단기스케줄러에 대해 알아보자! long, medium, short sche

https://kosaf04pyh.tistory.com/191

[운영체제] 프로세스 스케줄러(단기,중기,장기)

 

스케줄러의 종류를 간단하게 요약하면 다음과 같다.

• Long term
  • 메모리에 적재(job scheduler)
    • 10개의 프로세스 중 3개만 메모리에 올려라!
• Medium term
  • 어떤 것을 메모리에서 내려야 하는가를 결정(Swapper, swap in/out)
    • 현재 메모리에 3개를 적재하여 실행하니 cpu가 힘들다... 1개 내려!
• Short term
  • 프로세스에 cpu 할당
    • 메모리에 적재된 2개 중 어떤 것을 실행 할까..?
• I/O Scheduling

 

장기 스케줄러

작업스케줄러라고 부르며 어떤 프로세스를 준비 큐에 삽일 할지 결정하는 역할을 수행한다. 또한, 메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 역할도 수행한다.

장기스케줄러는 수십초 또는 수분 단위로 가끔씩 호출되기 때문에 상대적으로 속도가 느린것이 허용된다.

과거에는 적은양의 메모리를 많은 프로세스들에게 할당 하면서 프로세스당 메모리 보유량이 적어져 장기스케줄러가 이를 조절하는 역할을 수행했지만, 현대의 운영체제에서는 프로세스가 시작되면 장기 스케줄러 없이 바로 그 프로세스에 메모리를 할당하여 준비큐에 넣어준다.

 

중기 스케줄러

너무 많은 프로세스에게 메모리를 할당하여 시스템성능이 저하되는 경우를 해결하기위해 등장한 스케줄러

메모리에 적재된 프로세스의 수를 동적으로 조절한다.

• swap out
  • 메모리에 많은 수의 프로세스가 적재되어 프로세스 당 보유하고 있는 메모리가 극도로 적어지게 되면, I/O가 수시로 발생하여 시스템의 성능이 크게 저하된다. 이때 메모리에 올라와 있는 프로세스 중 일부를 메모리 통째로 빼앗아 그 내용을 디스크 스왑영역에 저장한다.
• swap in
  • 반대로 메모리에 여유가 생기면 스왑영역에 있는 프로세스를 다시 적재한다. 

 

단기 스케줄러

cpu스케줄러라고 불리며, 준비 상태의 프로세스 중 어떤 프로세스를 다음번에 실행 상태로 만들지 결정한다.

시분할 시스템에서 타이머 인터럽트가 발생하면 단기스케줄러가 호출된다.

일반적으로 스케줄러라 함은 단기 스케줄러를 의미한다.

미리 정해진 스케줄링 알고리즘에 따라 cpu를 할당 할 프로세스를 선택한다.

매우 비번하게 호출 되기 때문에 수행속도가 매우 빨라야한다.

 

---

 

728x90

 

Categories of Scheduling Algorithms

https://hyunah030.tistory.com/4

[운영체제] CPU 스케줄러 - FCFS, SJF, SRT, RR, Priority Scheduling

크게 시스템에 따라 3가지로 나눌 수 있다.

• Batch System
• Interactive System
• Real time Sytem

 

그렇다면 시스템별 스케줄링 알고리즘의 목적은 무엇일까?

• All system
  • Fairness
    • CPU를 모든 프로세스가 공평하게 점유
  • No Startvation(Policy enforcement)
    • 각각의 프로세스들이 오랜시간동안 CPU를 할당받지 못하는 상황이 없도록 한다.
  • Balance
    • 모든 시스템이 바쁘게 실행 중 인지
• Batch system
  • throughput(처리량)
    • CPU가 단위 시간당 처리하는 프로세스 갯수
  • Turnaround time(반환시간)
    • 프로세스가 시작해서 끝날때 까지 걸리는 시간
  • CPU Utilization(CPU 사용률)
    • 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• Interactive system
  • response time(응답 시간)
    • 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간
  • proportionality
    • 사용자의 기대를 만족시키는 정도
• Real-time system
  • meeting daealines
    • 데이터 손실 방지
  • predictability
    • 멀티미디어 시스템의 풀질 저하 방지

 

---

 

Batch System

Batch System 스케줄링에는 4가지 알고리즘이 존재한다.

• 비선점
  • FCFS(First-come First-served)
    
    • 먼저 자원 사용을 요청한 프로세스에게 자원 할당
    • CPU스케줄링, 디스크 스케줄링에 사용
  • SJF(Shortest Job First)
    • 소요시간이 짧은 프로세스에게 자원을 먼저 할당(평균 대기 시간을 최소화 하기 위함)
    • 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 양보되어 기아상태가 발생 할 수도 있음
  • HRRN(Highest Response Ratio Next)
    • 프로세스 처리의 우선 순위를 CPU처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정
• 선점
  • SRT(Shortest reamaing time)
    • shortest job first를 preemptive으로 변경한 알고리즘
    • 현재 작업 중인 프로세스를 중단시키고 새로 들어온 프로세스의 처리를 시작.

 

FCFS(First Come First Start)

선입 선처리 스케줄링은 먼저 자원 사용을 요청한 프로세스에게 자원을 할당해 주는 방식의 스케줄링 알고리즘이다.

전체 프로세스의 turnaround time을 구해보자.

turnaroud time = waiting time + service time

waiting time = 3 + 6 + 4 + 5 = 18

turnaroud time = 18 + 2 = 20

 

 

SJF(Shortest Job First)

작업시간 Service Time이 작은 프로세스부터 먼저 실행한다.

waiting time을 최소하 하기위해 사용하는 방식이다.​

FCFS를 적용한 (a)에 비하여 SJF를 적용한 (b)의 waiting time이 감소함을 알수 있다.

 

 

SRT(Shortest Remaining Time)

최단 잔여시간을 우선으로 하는 스케줄링

진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep시키고 짧은 프로세스를 먼저 할당 한다.

-> 짧은 작업이 계속 밀려오면 긴 작업은 우선순위에 밀려 처리를 못한다....(Starvation)

단기 스케줄링 보다는 장기 스케줄링에 유리함

선점형 SJR라고도 불린다.

B프로세스가 C프로세스에 밀려 B프로세스는 sleep되고 C프로세스가 진행됨을 알수 있다.

 

 

HRRN(Highest Response Ratio Next)

최상 응답 비율 순서 스케줄링은 프로세스 처리의 우선 순위를 CPU처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정하는 스케줄링 알고리즘이다.

ratio = (대기시간 + 실행시간)/실행시간

ratio가 큰 프로세스부터 먼저 실행한다.

SJF 스케줄링의 문제점을 보완하여 대기시간이 길어지는 프로세스가 우선순위에 밀려 처리되지 못하는것을 방지한다.

 

 

 

---

 

Interactive system

Interactive system은 응답성이 중요함.

-> 프로세스를 번갈아 가면서 실행...!! 😜

https://velog.io/@jewelrykim/Scheduling-Policy-%EC%9D%98-%EB%B0%9C%EC%A0%84-%EA%B3%BC%EC%A0%95%EA%B3%BC-%EC%9E%A5%EB%8B%A8%EC%A0%90-1Round-Robin-%EA%B9%8C%EC%A7%80

Scheduling Policy 의 발전 과정과 장단점 1(Round Robin 까지)

 

•  선점
  • Round Robin(라운드 로빈)
    • 시분할 시스템을 위해 설계
    • 프로세스들 사이에 우선순위를 두지 않음
    • 순서대로 시간 단위로 CPU를 할당
  • Priority(우선순위)
    • 우선순위가 높은 프로세스에 CPU를 우선 할당
    • 우선순위가 같을 경우, FCFS와 다를게 없음(비선점, 선점 둘다 사용)
  • Multilevel queues(다단계 큐)
    • 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에 우선순위를 부여
    • 각각의 큐에 다른 스케줄링 알고리즘 적용 가능
  • Shortest process Next
    • SJF의 inrteractive 버전
    • Exponential Average를 통해서 프로세스 할당
      • 운영체제는 프로세스 실행 시간을 알 수 없기 때문에 프로세스 과거 실행시간 이력을 참고
  • Guaranteed
    • 프로세스마다 cpu시간의 1/n씩 나누어서 할당
  • Lottery
    • 프로세스에게 복권을 나누어 주어 당첨된 프로세스에게 cpu를 할당
    • 할당 복권을 갯수로 프로세스 실행 수 조절 가능
  • Fair-share(공정 공유)
    • 프로세스의 특성이나 중요도에 따라

 

 

반응형

 

 

RR(Round Robin)

http://wiki.hash.kr/index.php/%EB%9D%BC%EC%9A%B4%EB%93%9C_%EB%A1%9C%EB%B9%88

라운드 로빈 - 해시넷

 

시분할 시스템을 위해 설계된 선점형 스케줄링이다.

모든 프로세스가 같은 우선순위를 가지고 time slice를 기반으로 스케줄링한다.

 

시간 할당량 안에 프로세스가 작업을 마치지 못하면 문맥교환이 일어난다.

일반적으로 우선순위가 높은 프로세스는 time slice를 길게주고

우선순위가 낮은 프로세스는 time slice는 작게 준다.

 

시간 단위 동안(time quantum) 수행한 프로세스는 준비 큐의 끝으로 밀려난다.(블록상태가 된다.)

문맥 전환의 오버헤드가 크지만, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리함.

 

Virtual Round-Robin

일반적으로 I/O를 요구하는 프로세스는 time quantum을 다 소비를 못한다.

그런 프로세스를 Auxiliary Queue에 보관한다.(Auxiliary Queue는 Ready Queue보다 우선순위가 높다.)

반대로 CPU Burst 요구하는 프로세스는 time quantum을 다 소비한다.

이러한 불공평을 해결하기 위해 Virtual Round-Robin 제안했다..! 🤩

Virtual Round-Robin

검정 글씨는 일반적인 라운드 로빈

빨간 글씨는 가상 라운드 로빈 방식에서 추가된 것

1. 도착한 프로세스는 준비 큐로 진입

2. 준비 큐에 있는 프로세스는 FCFS방식으로 스케줄링

3. 실행 중이던 프로세스 시간 할당량이 만료되면 다시 준비큐로 들어가 대기

4. 프로세스가 입출력을 요구 했다면, 입출력이 완료 될때 까지 입출력 큐로 들어가 대기

5. 입출력이 완료 되면 보조 큐에 진입(FSCF Queue)

6. 다음번 프로세스를 고르는 시점에서 스케줄러는 보조큐에서 대기중인 프로세스를 준비 큐보다 먼저 실행(실행 시 저번 실행 때 못채우고 반납한 시간 만큼만 실행)

 

 

Priority Scheduling

https://wonit.tistory.com/108

[운영체제] 17. 우선순위 스케줄링(Priority 스케줄링) 알고리즘

 

준비큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여

우선순위가 높은 프로세스를 cpu에 할당하는 방식

일반적으로 우선순위가 동알한 프로세스가 준비 큐로 들어오게 되면 FIFO로 스케줄링을 한다.

 

 

 

Multilevel feedback queue(MLFQ)

https://velog.io/@jewelrykim/%EB%A9%80%ED%8B%B0-%EB%A0%88%EB%B2%A8-%ED%94%BC%EB%93%9C%EB%B0%B1-%ED%81%90%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%EC%8A%A4%EC%BC%80%EC%A5%B4%EB%A7%81

멀티 레벨 피드백 큐(우선순위 스케쥴링)

https://lipcoder.tistory.com/62

2-4장. 스케줄링 : 멀티 레벨 피드백 큐(MLFQ)

 

SJF나 STCF(Shortest Time Complete First)같은 알고리즘은 작업의 실행 시간이 필요하지만,

운영체제에서는 실행 시간 정보를 미리 알 수 없다....

하지만 개발자들은 대화형 시스템은 빠른 시스템이라는 느낌을 주고 싶었기 때문에 여러가지 연구를 한다.

그래서 앞서 나온 RR을 생각했지만, RR은 응답시간은 단축시키지만 반환시간은 거의 최악이었다.

정보없이 스케줄링 + 응답시간

이 두마리 토끼를 잡기 위해 MLFQ 등장! (많은 스케줄링 

 

 

여러개의 큐로 구성되어 있고 각각 큐마다 다른 우선순위 배정

MLFQ의 핵심은 우선순위를 정하는 방식이다.

각 작업의 특성에 따라 동적으로 우선순위를 부여한다.(고정된 우선순위를 부여하는 것이 아니다.)

규칙1: priority(A) >  priority(B) 이면 A 실행
규칙2: priority(A) = priority(B) 이면 A, B는 RR으로 실행
규칙3: 작업이 시스템에 진입하면 가장 높은 우선순위 큐에 놓여진다.
규칙4: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다.(한단계 아래 큐로 이동)
규칙5: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
규칙6: 일정시간 동안 실행이 안되면 우선순위를 상승시킨다.(기아 방지)

 

 

Short Process Next

SJF의 interactive version

실행시간이 짧은 프로세스를 먼저 실행(대기시간 감소)

마찬가지로 운영체제는 프로세스 실행시간을 알수 없다....

그래서 과거 프로세스의 실행 시간을 참고하여 결정!!

근데,,  그냥 참고하면 문제가 생기기 때문에

위와 같은 식을 사용하여 계산한다.(a는 가중치)

Exponential Average = 마지막 실행시간 + 그 전Exponential Average

 

 

🏛Guarnateed Scheduling

공평하게 프로세스의 CPU할당 시간을 나누어 준다.(1/n)

리눅스의 Fair Scheduling과 비슷

 

 

🎟Lottery Scheduling

프로세스마다 복권을 나누어 주고 당첨된 프로세스르 할당.

장점으로 사용자가 프로세스 실행비율을 정할 수 있다.

e.g)

100개의 복권을 A,B,C 프로세스에 나누어준다.

A는 20개, B는 30개, C는 50개

여기서 당첨된 프로세스를 실행

 

 

Fair-share Scheduling(리눅스)

연결된 프로세스 수와는 관계 없이 cpu를 공정하게 할당한다.

 

그룹별로 계산.

 

 

 

Scheduling Mechanism VS Policy

유닉스, 리눅스를 개발 할 때 다양한 원칙이 있다.

1. 스케줄링 메커니즘과 정책을 구분해야한다.

2. 커널은 스케줄링 메커니즘을 제공해야한다.

3. 커널 알고리즘 또는 사용자의 프로세스는 스케줄링 정책을 결정할 수 있다.