CPU 슀쌀쀄링

2023. 3. 25. 18:46ㆍCS/CS 슀터디

출처: https://choi-geonu.medium.com/%EB%B0%B1%EC%97%94%EB%93%9C-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%93%A4%EC%9D%B4-%EC%95%8C%EC%95%84%EC%95%BC%ED%95%A0-%EB%8F%99%EC%8B%9C%EC%84%B1-4-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-e684331afc77

현대에 듀얎서 PC의 컎퓚팅 성능읎 슝가하고, 읎에 따띌 동시에 여러 프로귞랚을 띄워 사용하는 음읎 잊닀.

욎영첎제 입장에서는 동시닀발적윌로 사용되고 있는 프로섞슀듀에 대핮, 

비록 CPU 윔얎가 하나띌서 한 번에 하나의 프로섞슀 만을 싀행시킬 수 있는 상황음지띌도,

사용자로 하여ꞈ 몚든 프로섞슀듀읎 병렬적윌로 싀행되고 있닀는 착각을 불러음윌킬 수 있얎알 한닀.

만앜 PC륌 통핎 음악을 듀윌멎서 웹서핑을 하는 상황에서,

음악 애플늬쌀읎션읎 싀행되는 동안 검색찜에 타읎핑읎 안된닀멎 읎는 욎영첎제의 역할을 제대로 수행하고 있지 않은 것읎닀.

읎륌 위핎, 욎영첎제는 CPU륌 할당할 작업듀에 대한 슀쌀쀄링을 수행한닀.

닚순히 슀쌀쀄링을 수행시킀는 닚계륌 넘얎, 읎륌 잘 수행할 수 있얎알 한닀.

 

 

슀쌀쀄링의 평가 항목

귞렇닀멎 얎떻게 슀쌀쀄링을 í•Žì•Œ 읎륌 잘 수행했닀고 할 수 있을까?

ì–Žë–€ 슀쌀쀄링 Ʞ법듀읎 졎재하는지 알아볎Ʞ에 앞서,

슀쌀쀄링에서 활용되는 닀양한 평가 항목에 대한 읎핎가 필요하닀. 

대표적읞 슀쌀쀄링의 평가 항목에는 닀음의 요소듀읎 졎재한닀.

  • 반환 시간(turnaround time): 특정 작업읎 작업 목록에 도착하고, 핎당 작업읎 완료될 때까지 소요된 시간
  • 공정성(fairness): 특정 프로섞슀에 치우치지 않고 몚든 프로섞슀에 공정하게 CPU가 할당되는가
  • 응답 시간(response time): 특정 작업읎 작업 목록에 도착하고, 핎당 작업읎 착수될 때까지 소요된 시간

ê·ž 왞에도 CPU 읎용률, 였버헀드 등읎 추가로 졎재하나 핎당 Ꞁ에서는 위 3개에 대핎서만 닀룚고자 한닀.

 

 

슀쌀쀄링 Ʞ법의 분류 Ʞ쀀

슀쌀쀄링 Ʞ법듀은 닀양한 분류 Ʞ쀀을 갖는닀. 간닚히 읎륌 뚌저 소개한 ë’€ 슀쌀쀄링 Ʞ법에는 ì–Žë–€ 것듀읎 졎재하는지 소개하겠닀.

선점형 vs 비선점형

선점읎띌는 말의 의믞는,

읎믞 CPU륌 할당받아 사용하고 있는 특정 작업에 대핮 욎영첎제가 CPU의 제얎권을 가젞올 수 있는지에 대핎서읎닀.

따띌서 비선점형은 반대로 한번 CPU에 작업읎 할당되멎 핎당 작업읎 끝날 때까지 CPU의 제얎권을 욎영첎제가 돌렀받을 수 없는 겜우륌 말한닀.

정적 vs 동적

여Ʞ서 정적곌 동적읎띌는 말의 대상은 각 프로섞슀의 우선순위륌 의믞한닀.

슉 정적 방식에서는 한번 결정된 프로섞슀의 우선순위가 변겜되지 않는 것읎고,  

반대로 동적 방식에서는 한번 결정된 프로섞슀의 우선순위는 읎후 변겜될 수 있닀.

닚음 대Ʞ엎(queue) vs 닀쀑 대Ʞ엎

읎는 말 귞대로 프로섞슀듀의 대Ʞ엎읎 하나읞지 아니멎 여러 개읞지에 대한 여부읎닀.

 

 

슀쌀쀄링 Ʞ법의 종류

슀쌀쀄링 Ʞ법에는 닀음의 Ʞ법듀읎 졎재한닀.

  • FCFS 슀쌀쀄링
  • SJF 슀쌀쀄링
  • STCF 슀쌀쀄링
  • RR 슀쌀쀄링
  • MLFQ 슀쌀쀄링
  • CFS 슀쌀쀄링

 

FCFS 슀쌀쀄링(FIFO)

First Come First Served의 앜자로, 의믞 귞대로 뚌저 듀얎옚 작업 순서대로 작업을 수행시킀는 것을 말한닀.

핎당 방식은 뚌저 듀얎옚 작업읎 끝날 때까지 닀륞 작업을 시작하지 않는 비선점형 슀쌀쀄링읎고,

프로섞슀 간 우선순위가 변하지 않는 정적 슀쌀쀄링읎며, 닚음 대Ʞ엎 슀쌀쀄링읎닀.

뚌저 듀얎옚 작업을 최우선윌로 수행하는 것은 얌핏볎Ʞ에는 타당핎 볎읎고 공정성의 잡멎에서도 묞제가 없얎 볎읎지만,

만앜 뚌저 듀얎옚 작업읎 닀륞 작업에 비핎 곌도하게 덩치가 큰 겜우 묞제가 될 수 있닀.

CPU 슀쌀쀄링의 ꎀ점에서 공정성읎란 ê²°êµ­ 몚든 프로섞슀듀읎 비슷한 수쀀윌로 CPU륌 사용할 수 있는 것읎Ʞ 때묞에, 

뚌저 듀얎옚 작업읎 닀륞 작업에 비핎 덩치의 찚읎가 졎재한닀멎 뒀에 듀얎옚 작업은 CPU륌 거의 할당받지 못할 수도 있닀.

읎러한 상황을 Convoy Effect띌고 하는데

핎당 상황에서는 반환 시간곌 응답 시간의 잡멎에서도 성능을 볎장하Ʞ가 얎렵닀.

따띌서 핎당 방식은 닚순하고 구현하Ʞ 쉜닀는 장점읎 있음에도 잘 사용되지 않는 방식읎닀.

 

SJF 슀쌀쀄링

Shortest Job First의 앜자로, 말 귞대로 가장 짧은 작업을 뚌저 수행하는 것을 의믞한닀.

핎당 방식은 닚음 대Ʞ엎로 구현된닀.

또한 핎당 방식은 음반적윌로 비선점형윌로 구현되며,

프로섞슀의 우선순위가 각 프로섞슀의 CPU 사용 시간(CPU burst time)에 대한 예잡치로 결정되는 동적 슀쌀쀄링 Ʞ법읎닀.

SJF 슀쌀쀄링은 몚든 작업읎 동시에 대Ʞ엎에 듀얎였는 상황에서는 응답 시간, 공정성의 평가 Ʞ쀀 상 최적의 Ʞ법읎지만,

현싀의 상황은 귞렇지 ì•Šë‹€. 

따띌서 뚌저 덩치가 큰 작업읎 듀얎옚 뒀에, 순찚적윌로 짧은 작업읎 듀얎옚닀멎

FCFS 슀쌀쀄링에서 발생했던 Convoy Effect가 동음하게 발생한닀.

또한 각 작업의 CPU burst time을 정확하게 예잡할 수 없닀는 묞제점도 졎재한닀.

 

STCF 슀쌀쀄링

Shortest Time-to-Completion First의 앜자로,

현재 대Ʞ엎에 졎재하는 ìž‘ì—…ë“€ 쀑 완료까지 잔여 시간읎 가장 짧은 작업을 우선윌로 수행시킚닀.

핎당 방식을 위핎서는 특정 프로섞슀가 싀행되는 와쀑에도 얞제든지 잔여 시간읎 가장 짧은 작업윌로 대첎될 수 있얎알 하Ʞ 때묞에

선점 방식의 슀쌀쀄링윌로 구현핎알 한닀.

또한 작업의 우선순위가 싀시간윌로 변겜될 수 있는 동적 슀쌀쀄링읎멎서 닚음 대Ʞ엎을 갖는 슀쌀쀄링읎닀.

핎당 방식은 SJF 슀쌀쀄링곌 달늬, 몚든 작업읎 동시에 대Ʞ엎에 포핚되지 않더띌도,

반환 시간곌 공정성 만을 고렀했을 때는 정말 훌륭한 방식읎닀.

하지만 응답 시간을 고렀했을 때는 읎알Ʞ가 달띌진닀.

잔여 시간읎 상대적윌로 ꞎ 작업듀은 CPU륌 점유하Ʞ 위핎서는 였랜 대Ʞ 시간을 가젞알 하고,

읎는 읎믞 위에서 얞꞉한 몚든 슀쌀쀄링 방식에서도 동음하게 발생하는 묞제읎닀.

따띌서 응답 시간 ꎀ점에서는 읎믞 소개된 슀쌀쀄링 방식듀은 몚두 좋은 방식은 아니닀.

 

RR 슀쌀쀄링

Round-Robin의 앜자로,

핎당 방식은 사전에 타임 퀀텀 값읎띌고 불늬는 시간 값을 섀정한 후 몚든 대Ʞ엎 낮 프로섞슀듀에 대핮 

타임 퀀텀만큌씩만 CPU륌 점유하게 하는 방식을 사용한닀.

대Ʞ엎 낮 졎재하는 몚든 작업듀읎 타임 권텀 값만큌 한 번씩 수행되고 나멎,

위에서 얞꞉한 곌정을 계속핎서 수행한닀.

위와 같읎 동작하는 핎당 방식의 특성상 선점형읎며 정적읎고, 닚음 대Ʞ엎 슀쌀쀄링읎닀.

핎당 방식은 공정성의 잡멎에서 볎았을 때 정말 훌륭한 방식읎닀.

또한 응답 시간의 잡멎에서도, 위에서 읎믞 얞꞉한 슀쌀쀄링 방식듀에 비핎 훚씬 나은 방식읎닀.

닀만, 반환 시간의 잡멎에서 볎았을 때는 거의 최악읎닀.

음반적윌로 공정성을 우선시하는 방식에서는 반환 시간곌 같은 평가 척도는 나쁘게 나올 수밖에 없Ʞ 때묞에 발생하는 당연한 결곌읎닀.

핎당 방식은 또한 타임 퀀텀 값을 얎떻게 섀정하느냐에 따띌서 성능읎 달띌진닀.

만앜 타임 퀀텀 값을 상대적윌로 작게 가젞간닀멎, 평균 응답 시간은 더욱 좋아질 것읎닀.

닀만 타임 퀀텀 값읎 너묎 작아지게 되멎, 윘텍슀튞 슀위칭읎 너묎 자죌 발생하여 성능 상 좋지 못한 결곌륌 얻을 수 있닀. 

따띌서 띌욎드로빈 방식에서는 핎당 trade-off륌 고렀하여 적절한 타임 퀀텀 값을 섀정하는 것읎 쀑요하닀.

핎당 방식은 앞서 얞꞉했듯읎 반환 시간의 잡멎에서 귞늬 좋지 못한 슀쌀쀄링 방식읎지만, 싀제로는 많읎 쓰읎는 방식읎닀. 

ê·ž 읎유로는, 

현대의 컎퓚터에서 응답 시간은 가장 첎감읎 잘되는 성능 지표 쀑 하나띌는 점곌

말 귞대로 상대적윌로 반환 시간읎 안 좋은 것읎지 컎퓚팅 Ʞ술의 발전윌로 절대적윌로는 ê·ž 찚읎가 믞믞하닀는 점읎 있닀. 

 

MLFQ 슀쌀쀄링

출처: https://www.geeksforgeeks.org/difference-between-multilevel-queue-mlq-and-multi-level-feedback-queue-mlfq-cpu-scheduling-algorithms/

Multi-level Feedback Queue의 앜자로,

핎당 방식은 각 작업의 CPU burst time을 예잡하Ʞ 얎렵닀는 한계 속에서 응답 시간곌 반환 시간을 최적화하Ʞ 위핎 등장한 방식읎닀.

읎늄에서 알 수 있듯읎, 닀쀑 대Ʞ엎을 사용하는 방식읞데 읎때 각 대Ʞ엎은 하나의 우선 순위륌 의믞한닀.

슉, 우선 순위 별로 대Ʞ엎읎 졎재하는 것읎닀.

읎 때 우선순위는 정적윌로 ì •í•Žì ž 있는 것읎 아닌,

처음 작업읎 듀얎왔을 때는 높은 우선순위륌 갖고 있닀가 싀행읎 됚에 따띌 점찚 우선순위가 낮아지는 방식을 채택한닀.

핎당 방식은 닀음의 규칙에 따띌 슀쌀쀄링을 수행한닀.

  1. 우선순위가 가장 높은 큐에 졎재하는 작업부터 싀행
  2. 특정 큐에 여러 개의 작업읎 졎재한닀멎, 읎는 RR 방식윌로 슀쌀쀄링
  3. 새로욎 작업읎 듀얎였멎 읎륌 우선순위가 가장 높은 큐에 배치
  4. 특정 작업읎 타임 퀀텀을 몚두 소진하지 못한 채 CPU륌 반환할 겜우엔 êž°ì¡Ž 큐에 귞대로 두고, 타임 퀀텀을 몚두 소진한 겜우에는 한닚계 낮은 큐로 읎동
  5. 사전에 섀정핎둔 Ʞ간읎 지날 겜우 몚든 큐의 작업을 최상위 큐로 읎동(Aging)

읎륌 통핎 MLFQ는 우선순위륌 고렀하멎서도 작업듀의 응답, 반환 시간을 최적화한닀. 

또한 낮은 우선순위의 작업듀읎 êž°ì•„ 상태에 빠지는 것을 고렀하여 Aging Ʞ법을 추가적윌로 적용하여 읎륌 핎결했닀.

핎당 방식은 선점형, 동적, 닀쀑 대Ʞ엎 슀쌀쀄링윌로 볌 수 있닀.

핎당 방식은 구현에 난읎도가 있는 방식읎지만

싀시간윌로 응답을 수행핎알하는 대화형 작업(ex. 킀볎드 입력)에 대핮 나쁘지 않은 성능을 볎읎고,

덩치가 큰 작업듀읎 지속적윌로 CPU륌 할당받을 수 있게 한닀는 점에서 

많은 욎영첎제에서 채택하는 방식읎닀. 특히, Windows 욎영첎제에서 읎륌 Ʞ볞 슀쌀쀄러로 사용한닀.

 

CFS 슀쌀쀄링

출처: https://www.linuxjournal.com/node/10267

Completely Fair Scheduler의 앜자로, 읎늄에서 알 수 있듯읎 핎당 슀쌀쀄링 방식은 공정성을 최우선 목표로 잡는닀.

읎륌 위핎 핎당 방식에서는 sched_latency와 min_granularity띌는 두 변수륌 뚌저 섀정한닀.

음반적윌로 두 값은 각각 48ms와 6ms륌 ê°–êž° 때묞에 읎륌 Ʞ쀀윌로 섀명하겠닀.

여Ʞ에서 sched_latency는 현재 대Ʞ엎에 졎재하는 몚든 작업듀읎 공유하는 하나의 사읎큎 죌Ʞ읎닀.

만앜 대Ʞ엎 낮 프로섞슀가 4개 졎재한닀멎, 48ms륌 4로 나눠 각각 12ms씩 할당받는닀.

읎제 각 작업은 12ms씩 수행하게 되고, 각 작업읎 갖는 vruntime읎띌는 변수에 싀행 시간을 쌓는 식윌로 작동한닀.

읎 때 닀음 수행할 작업은 vruntime읎 가장 작은 작업을 선택하게 된닀.

만앜 대Ʞ엎 낮 프로섞슀가 굉장히 많은 상황에서는, 각 작업읎 할당 받는 시간읎 굉장히 짧을 것읎닀. 또한 컚텍슀튞 슀위칭읎 더 자죌 발생하여 성능 상 묞제가 발생할 수 있닀.

읎륌 위핎 졎재하는 것읎 min_granularity 값읞데, 각 작업에 할당되는 시간읎 핎당 값볎닀 작아지더띌도 슀쌀쀄러는 묎조걎 min_granularity 값 만큌은 작업을 수행시킚닀. 

CFS가 공정성을 최우선 목표로 잡Ʞ는 하나, 귞렇닀고 성능읎 귞렇게 나쁘지만은 ì•Šë‹€.

CFS 방식에서는 성능을 위핎 작업듀을 Red-Black 튞늬륌 통핎 ꎀ늬하는데, 읎륌 통핎 연결 늬슀튞로 작업듀을 ꎀ늬하는 닀륞 방식곌 비교하여 핎당 분알에서 더 나은 성능을 얻을 수 있었닀. 특히 연결 늬슀튞 방식에 비핎, 확장성읎 더 뛰얎나닀.

CFS는 위와 같은 특징듀을 통핎 확장성곌 성능을 얎느정도 볎장할 수 있었고, 읎에 늬눅슀에서 Ʞ볞 섀정윌로 쓰읎는 슀쌀쀄러읎닀. 

(nice 조정을 통한 프로섞슀 간 할당 시간 가쀑치 조정은 Ꞁ읎 너묎 Ꞟ얎진 탓에 닀룚지 ì•Šê² ë‹€.)

 

 

 

ì°žì¡°

OSTEP(Operating System Three Easy Pieces), 2015 - Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau 

 

'CS > CS 슀터디' 칎테고늬의 닀륞 Ꞁ