2023.03.30 - OS술사의 귀환. . . 과 문제의 그놈 MLFQ

안녕하세요, OS술사입니다.

사실 눈치 안보고 모각코 시간에

운영체제가 아닌 연구실 활동을 주로 다루었었는데요

.

.

.

양껏 조롱과 희롱당하고 있는 OS술사의 직책

 

 

일단 도게자 먼저 박겠습니다...

이제부터 OS술사라는 직책에 걸맞는 운영체제 내용을 양껏 담아보도록 하겠습니다.

 

 

특히, 이번주에는 국민대학교 소프트웨어학부 운영체제 수강생이라면

운영체제를 공부 안할레야 안할 수가 없었죠?

 

3월 30일.. 모두가 잡페어 데이로 알고 있지만 사실 운영체제 숏 퀴즈 데이였답니다 와아--

 

 

 

3월 29일 야심한 밤, 에X브리X임을 운영체제로 활활 태우다 못해 황폐해진 그곳..

물음만 가득하고 확신만 없더 그곳..

이미 퀴즈는 끝나긴 했지만 아직 시험은 남아있죠?

 

오늘은 논란의 그 녀석 MLFQ을

페라리 황의 아들 마세라티 허, 그리고 그 마세라티 허의 양아들(허락 안받음) 최지원이 한 번 정리를 해보겠습니다.

 

 

 

知彼知己 百戰不殆

 

적을 알고 나를 알면 그 어떤 싸움도 지지 않는다.

 

오늘 저희가 싸울 놈은 MLFQ인데 적어도 어디서 놀던 놈인지는 알 필요가 있겠죠?

간단하게만 설명을 해보겠습니다.

 

 

MLFQ는 Multi Level Feedback Queue(멀티 레벨 피드백 큐)의 약자로

이전에 다루었던 Scheduling(스케줄링)과 관련된 내용입니다.

 

https://alchemist-of-error.tistory.com/11

2023.03.16 - 망각하고 있던 OS술사의 직책, Scheduling이 무엇인지 알아보자

복습복습!!

 

 

MLFQ가 해결하고자 하는 문제는 반환 시간 그리고 반응 시간입니다.

 

1. 반환 시간을 최적화한다

2. 반응 시간(응답 시간)을 최적화한다

 

이전에 공부했던 내용을 떠올려보면

1번 조건을 만족하는 스케줄링 알고리즘에는 SJF과 STCF가 있었고

2번 조건을 만족하는 스케줄링 알고리즘에는 Round Robin이 있었죠?

 

하지만 SJ와 STCF는 운영체제가 Job의 length를 미리 알 수 없기 때문에 사실상 사용이 불가능하며

RR(Round Robin) 같은 경우에는 반환 시간은 최악에 가까운 성능을 보여줍니다.

 

MLFQ에서는 몇 가지 Rule을 추가해서

각 알고리즘의 단점과 한계점을 보완하고

장점을 쏙쏙 뽑아먹는 스케줄링 기법이라고 생각하시면 됩니다.

 

• 규칙1: 우선순위(A) >우선순위(B), A를 실행
• 규칙2: 우선순위(A) == 우선순위(B), A와 B는 소속된 큐의 타임슬라이스에 의한 RR(Round Robin) 방식으로 실행된다.

MLFQ의 Basic Rules 중 1, 2번입니다.

 

규칙 1에서는 우선순위를 높은 것을 먼저 처리하는 것으로 반환 시간 최적화를 진행하는 것을 볼 수 있으며

규칙 2에서는 우선순위가 동일한 경우에는 RR을 통하여 반응 시간을 최적화하려는 시도를 찾아볼 수 있습니다.

 

???: 아까는 Job Length 몰라서 우선순위 못 정한다면서요.

 

라고 생각하시는 분들이 당연히 있을텐데

MLFQ에서는 우선순위를 정할 수 없다는 문제점을 극복하고자

규칙 3을 통해서 Job이 처음 시스템에 들어왔을 때, 우선순위를 부여하는 방법과

규칙 4을 통하여 우선순위를 관리(강등)하는 규칙을 마련해두었습니다.

 

• 규칙3: 작업이 처음으로 시스템에 들어가면 최상위 큐에 배치된다.
• 규칙4a: 작업이 running 상태동안 time slice 전체를 사용한 경우 우선순위를 한 단계 내린다(1단계 아래의 큐로 이동한다).
• 규칙4b: 작업이 time slice를 모두 사용하기 전에 CPU를 반환한다면 우선순위를 유지한다.

 

MLFQ에서는 일단 새로운 작업이 도착한 경우에 가장 높은 우선순위를 부여하고(가장 높은 레벨의 큐에 배치하고)

time slice를 기준으로 삼아 우선순위를 유지, 강등하는 것으로 관리합니다.

 

???: 음음.. 그래 일리가 있구만.. 이 정도면 쓸만한데?

하. 지. 만.

규칙 4a와 규칙 4b만으로는 해결할 수 없던 문제들이 몇 가지 발견되기 시작하였는데요

첫 번째 문제는 starvation(굶주림)

두 번째는 문제는 game the scheduler 입니다.

---

그렇다면 먼저 starvation 문제가 무엇인지 같이 보시죠.

MLFQ는 규칙 1에 의거하여 레벨이 높은 큐가 다 돌기 전까지 낮은 레벨의 큐는 돌지 않습니다.

따라서, 우선순위가 낮은 작업들은 새로운 작업들이 계속해서 들어오는 경우 CPU를 얻을 수 없죠!

특히 하단 그림의 왼쪽을 보게 되면 대화형 Job이 들어온 경우에는 Q0에 머물고 있는 작업은 실행되지 않습니다.

 

이를 해결하기 위해서 MLFQ에서는 boosting과 관련된 규칙을 추가로 정의합니다.

boosting은 S라는 일정 주기(Period)마다 모든 작업을 최상위 큐에 재배치하는 역할을 수행합니다.

이로 인하여 앞서 말했던 굶주림 문제를 해결하며

S라는 Period는 어떤 상황에 어떻게 코드를 작성한 지에 따라 유동적으로 바뀌게 됩니다. 

Starvation (좌) / Boosting을 통한 문제 해결 (우)

 

• 규칙5: 주기 S가 지나면, 시스템 내부에 있는 모든 작업은 가장 높은 큐에 재배치한다.

Boosting과 관련된 규칙도 이렇게 새로 만들어지게 되었습니다.

그런데 운영체제 퀴즈에서는 얘를 고려하면 문제 난이도가 더블링돼서 나오지 않았습니다

---

다음으로는 두 번째 문제였던 game the sheduled에 대하여 알아보겠습니다.

.

.

.

.

이는 앞서 설명한 MLFQ의 규칙 4b의 헛점을 적절히 악용한 문제점입니다.

바로 스케줄러가 어떻게 설계가 되어 있는지 아는 사람들이 time slice를 다 소진하기 바로 직전..!

yiled()와 같이 짧은 시간이 소요되는 시스템 콜을 불러 스스로 Blocked 시키고 우선순위를 계속 유지하는 것입니다.

 

세상에는 개새끼천재가 많아서 발생한 문제를 해결하기 위하여 규칙 4a와 규칙 4b를 리뉴얼하게 됩니다.

• 규칙4: 작업이 지정된 단계에서 배정받은 시간(allotment time)을 소진하면(IO 발생, Yield() 호출 등으로 CPU를 포기한 횟수와 상관없이) 작업의 우선순위는 감소한다(즉 한 단계 아래 큐로 이동한다).

 allotment(배정 시간)을 기준으로 강등 규칙을 다시 만드는 것으로 의도적인 시스템 콜을 호출하는 꼼수는 막히게 되었죠.

 

game the scheduled (좌) / 규칙 4 변경 -> 해결 (우)

 

 

그리고 이게 그 말 많았던 문제의 문제인데

다음 포스팅은 해당 부분에 대한 풀이와 Short Quiz에 대한 풀이를 같이 적어보려고 합니다.

 

사실 문제 풀이를 기대하셨을 수도 있을 거 같은데

지금의 저는 우매함의 봉우리에 올라서 1주 동안 하산한 뒤에 다시 돌아오도록 하겠습니다~~

 

+

 

보현님께서 해당 문제 풀이를 하셨다고 합니다. ㅁㄱㅂ~

아래 글에서 확인해보세요~!~!

https://alchemist-of-error.tistory.com/19

23.03.30 - [PLAYLIST] 내가 보려고 만들었다🥰 도입부부터 찢은 운체 모음💥

 

 

모각코 담당자님 앞으로 OS 글 많이 올리겠습니다 그동안 인내해주셔서 감사합니다 ;)