본문 바로가기

별걸다하는 IT/운영체제 OS

[운영체제 OS] multilevel feedback queue(다단계 피드백 큐) MLFQ 특징, 문제점

[운영체제 완벽 정리 링크 목차]

안녕하세요!! 챕터 5가 반 이상 완료되어 가네요~!! 오늘은 멀티레벨 큐에 이어서 확장된 버전인 멀티레벨피드백큐에 대해서 살펴볼게요!! 

 

이전 포스팅 멀티레벨 큐 ↓

 

[운영체제]Multilevel Queue 다단계큐, 멀티레벨큐

[운영체제(OS) 목차 &책 추천] Multilevel Queue 다단계 큐란? 이 포스팅을 보기전에 RR과 FCFS에 대해서 이해를 하고 오셔야합니다 RR과 FCFS가 무엇인지 잘 모른다면 이전 포스팅을 보고 오시는 것을 추천드려요..

jhnyang.tistory.com

멀티레벨 큐의 단점? 멀티레벨피드백 큐가 나온 이유?

먼저 왜 다단계 피드백 큐가 나오게 됐는지를 이해해야겠죠. 이전 포스팅을 보고 왔다는 전제 하에 설명하도록 할게요!

다단계큐 알고리즘은 각각 프로세스의 중요도에 따라 큐로 나누고 각 큐에서 다른 알고리즘을 적용해 효율을 높일 수 있는 장점이 있죠. 반면에 한 번 해당 큐에 들어가면 프로세스는 다른 큐로 이동되거나 변경되는 것이 거의 불가능하다는 단점이 있어요. 즉 스케줄링 오버헤드가 낮은 대신에 inflexible 유연적이지 못합니다.

 

Unlike multilevel queue scheduling algorithm where processes are permanently assigned to a queue, multilevel feedback queue scheduling allows a process to move between queues.

큐에 영구적으로 할당되는 멀티레벨큐 알고리즘과 다르게 멀티레벨피드백큐 알고리즘은 큐 간의 이동이 허용됩니다.

 

멀티레벨큐는 우선순위 스케줄링에서 언급했던 것처럼, 그냥 우리가 뭐가뭐가 있으면 중요도가 좀 더 높을꺼다 판단해서 우선순위를 높게 줄지 낮게 줄지... 분류할 수 밖에 없어요. 그치만 이건 절대적일 수가 없죠 ㅎㅎ한 예로 대화형 프로세스는 중요한대 그걸 미리 알 수가 없어요. 그냥 저럴 경우 높더라 추측으로 분류할뿐... 그런데 이게 잘못되도 변경할 수 없는 유동적이지 못한 단점이 있습니다.

우리가 앞으로 배울 다단계피드백 큐는 다단계큐 알고리즘과 다르게 프로세스가 큐 사이 이동이 가능해요. 분류되는 방식도 차이가 있고요! 어디 한 번 자세히 살펴볼까요?

 

멀티레벨피드백 큐, 다단계 피드백 큐란?

멀티레벨피드백큐  

사진을 봅시당. 다단계피드백 큐는 5가지 변수에 의해 정의돼요 (프로그램 코드 상)

멀티레벨피드백큐 역시 멀티레벨이라 그런지 여러 개의 큐로 구성되어 있습니다.

또 멀티레벨큐의 확장버전이라 그런지 각 큐마다 스케줄링 알고리즘을 적용할 수 있는 것까지 동일해요.

 

그 다음 세개가 뭘 말하는지 아래 그림을 통해서 쉽게 설명해볼께요

» 작업을 보다 높은 우선순위의 큐로 격상시키는 시기 결정 알고리즘

» 작업을 보다 낮은 우선순위의 큐로 격하시키는 시기 결정 알고리즘

» 프로세스들이 어느 큐에 들어갈 것인가를 결정하는 알고리즘

(작동 방식을 이해하고 나면 뭘 말하는지 알기 쉬워요 ㅎㅎ)

 

다단계피드백 큐 작동 방식

자 어떤게 중요한지 모르니까 일단 시작은 다 똑같이 합니다. 멀티레벨큐가 우선순위에 따라 들어가는 입구가 달랐다면 멀티레벨피드백큐는 모든 프로세스들이 제일 위에 있는 큐로 일단 들어와요.

만약 제일 위에 있는 queue는 RR으로 스케줄링을 하는데 time-quantum을 8로 스케줄링을 해요, 자신의 time quantum을 다 채우지 못한 process는 냅두고 time quantum을 다 채운 프로세스는 그 밑의 레벨에 있는 큐로 들어가게 됩니다. 특징은, 밑에 있는 큐는 타임퀀텀의 크기를 첫 번째 있는 큐의 두 배로 돌려요! 

마지막 큐는 백그라운드 프로세스가 보통 그랬듯이 대게 FCFS로 처리됩니다.

 

왜 피드백?

일단 multilevel queue인데 queue에 서로 feedback이 있죠? 그래서 이걸 multilevel feedback queue라 합니다. 그런데 이거의 의미가 뭔지 생각해 봅시다.

일단 시작은 다 똑같은 데로 들어왔는데 자신의 time quantum을 다 채운 애는밑으로 내려가고 자신의 time quantum을 다 채우지 못한 애는 그냥 원래대로 들어가요. 자신의 time quantum을 다 채운 거랑 다 못 채운거랑 의미는 뭘까요?

 

왜 이렇게 하느냐,

이 특징은 바로 CPU burst와 중요도의 상관관계를 사람들이 발견한데서 있습니다.

보통 사용자와 interactive하지 않은, background의 프로세스는 CPU burst가 매우 크다는 특징을 이용한거죠.

 

자, 여러분 사양이 엄청 큰 게임을 다운로드 한다고 생각해봐요, 그 게임 다운로드 하는데 적어도 30분은 기다려야 한다고 합시다. 그럼 우리는 이거 그냥 백그라운드로 돌려놓고 인터넷서칭을 하죠, 즉 바로바로 처리해야할 일은 인터넷 서칭이 됩니다. 만약 게임다운로드 하는 동안 나는 아무것도 할 수 없다면 답답하고 짜증날테니까요 ㅎㅎㅎ

이렇게 게임 다운로드처럼 CPU를 계속 써야하는, CPU burst가 큰 프로세스를 우선순위가 낮다고 판별하는 겁니다. 그리고 나와 상호작용할 가능성이 높은 프로세스, 내 입출력을 필요로 하는(마우스 클릭이라던지 키보드 타이핑이라던지) 이런 애들은 CPU처리가 I/O작업이랑 번갈아가며 일어나므로 CPU burst가 작다는 특징을 기져요 그리고 이를 우선순위가 높구나! 이런 특징을 활용한 것이 멀티레벨피드백 큐인겁니다 ㅎㅎ알겠죵?

 

time quantum을 다채웠다는것은 CPU burst process일 가능성이 높죠 그래서 한번 더 밑으로 내려보는겁니다. 16으로 했더니 그걸 또 다 채웠어!! 아 그럼 이거는 CPU bound process구나! 그러니까 아예 밑으로 내려가서 CPU bound process들은 사용자하고 대화형으로 동작하는 것이 아니니까 context switching을 안하고 그냥 개를 쭉 수행시켜주는 것이 유리하겠죠? 그러니까 FCFS로 그냥 하는겁니다.

즉 다음 단계로 넘어갈 수록 CPU burst가 크다는 거니까 우선순위가 점점 낮아진다! 이런 룰이 되는거예요

 

우째보면 같은 말 반복인데, I/O bound process들은 사용자하고 대화형으로 동작하잖아요. 그러니까 개네들을 먼저 수행시켜줘야지 CPU bound process는 사용자들을 기다리지도 않아요 ㅎㅎ (예시 든 것처럼)

interactive process는 계속 대화형으로 해야하니까 이 멀티레벨피드백 방식은 대화형 프로세스의 우선순위를 높이는 스케줄링의 방법이겠죠.

그런데 아까 우리 multilevel queue는 대화형 프로세스이다 아니다 하는 것을 미리 알고 들어왔는데, 그걸 사실은 알 수가 없어요. 그러니까 이 방법으로 대화형 프로세스 인지 아닌지를 이 time quantum의 크기로 스케줄링을 해주는 방법이고 이 multilevel feedback queue가 우리 고전적으로 사용했던 아주 고전적인 방법입니다.

물론 지금은 우선순위라고 하는 개념이 도입되서 더 좋은 방법이 수행돼죠 ㅎㅎ(우선순위 +RR 전 포스팅에서 다뤄서 아시죠?) ㅎㅎ실제로 솔라리스2.6 TS(time sharing) 스케줄러가 이 알고리즘을 적용했다네요 ㅎㅎ

 

멀티레벨피드백큐의 문제점?

자꾸 인터렉티브한 즉 우선순위가 높은 프로세스가 들어오면 큐0만 주구장창 수행되고 낮은 우선순위 애들은 밀리는 starvation문제가 발생합니다. (앞 스케줄링 알고리즘에서 하두 많이해서 다들 예측했을 것 같은 로직 ㅎㅎ)

 

해결방안? solution

이럴 경우 우선순위 스케줄링에서 언급했던 aging 방식을 도압해서 해결할 수 있습니다.

a process that waits too long in a lower-priority queue may be moved to a higher priority queue.

낮은 우선순위 큐에서 너무 오래 기다리는 프로세스들을 높은 우선순위 큐에 다시 갖다놓는거죠 ㅎㅎ

 

멀티레벨 피드백 큐 VS 멀티레벨 큐

이 알고리즘은 실제 구현하기 엄청 복잡해요 근데 굳이 피드백큐 알고리즘을 사용하는 이유는 뭘까요?

서두에 문제점 제시한 거랑 좀 겹치긴 한데,, 뭐 반복은 할수록 좋으니까요 ㅎㅎ

복잡한데 왜 쓰냐?

잘 정리된 캡처본이예요 ㅎㅎ

1. 유연성이 뛰어나!

2. SJF알고리즘처럼 turnaround시간에 최적화되어있습니다. 타임 퀀텀을 보고 우선순위를 예측하고 변경하잖아요 즉 이런 방법은 더 짧은 프로세스가 먼저 돌게 해주니까 turnaround의 평균 시간을 줄일 수 있습니다.

3. 또한 인터렉티브한 프로세스가 앞에 오니까 response time은 당연히 짧겠죠?

이런 장점때문에 복잡한데도 불구하고 썼다합니다.

 

내 글 보기전엔 이해안됐지만 내 포스팅 보고나면 이해될 정리 글 (헤헤)

- 입출력 위주와 CPU 위주인 프로세스 특성에 따라 서로 다른 타임 슬라이스를 부여한다.

- 새로운 프로그램이 들어오면 높은 우선순위를 할당해주어 단계 1에서 즉시 수행하고 점차 낮은 우선순위를 부여하며 단계가 n쯤 되는 나중에는 그 작업이 완료될 때까지 라운드 로빈으로 순환한다. (결국 RR로빈도 높은 퀀텀을 부여하면 FCFS 특징을 띄는거 아시죠?)

- Multi Level Feedback Queue는 FCFS와 Round Robin을 모두 사용하므로 Hybrid 스케줄링 기법이다.

오늘은 여기까지입니다 나름 쉽게 설명하려고 이번에도 노력했는데 도움이 됐는지요?ㅎㅎㅎ

다음 포스팅에서 또 봐요 공감 & 댓글 & 광고 보답은 글을 작성하는데 힘이 됩니다!

 

  • ㅇㅇ 2020.05.10 20:23

    님의 깊은 지식에 감탄하고 같니다

  • 컴공과학생 2020.05.23 04:01

    딱딱한 어투도 아니고 강의때 놓친부분 항상 와서 체크하고 가다가 감사해서 이렇게 댓글 남깁니다. 적게 일하고 많이버세요 진짜 ㅠ

  • 학생 2020.12.21 13:14

    이런 알고리즘이 있다는 것도 몰랐네요. 구현은 어렵다하셨지만 알고리즘의 구조와 개발의도는 정말 참신하네요. 특히 백그라운드 프로세스와 대화형 프로세스를 간단히 구분할 수 있어서 좋네요. 덕분에 즐겁게 공부하고 있습니다!! 감사합니다!

  • +컴공 2021.04.29 16:03

    설명이...대박이시네요 바로 이해됬어요

  • 대박.. 2021.06.22 17:10

    좋은 글 감사드립니다!!
    궁금한 점이 있어서 여쭤봅니다!

    MFQS 와 Priority + RR 의 차이점이 궁금한데요,
    Priority 는 우선순위를 내부적 외부적으로 모두 선택이 가능하고,
    MFQS 는 내부적으로 저렇게 적혀 있는 식으로만 우선순위를 정하는 것이 차이점이라고 보면 될까요??

    Priority + RR 이 좀 더 상위 개념 또는 추가 기능이 있는 알고리즘인가 해서 여쭤봅니다!!
    읽어주셔서 감사합니다!

  • ㄷㄹㄷㄷ 2021.07.05 16:02

    MFQ의 경우, OS 책에서는
    "어떤 프로세스가 지정된 시간 보다 CPU너무 많이 사용하면 더 낮은 우선순위 큐로 이동
    마지막 큐에서는 이전 큐가 모두 비었을 때 FIFO방식으로 처리"
    라고 써져있는데

    "모든 프로세스들이 제일 위에있는 큐로 들어간다. 만약 제일 위의 queue RR으로 스케줄링 시간을 8로 스케줄링, 다 못 채운 프로세스 냅두고 다 채운 프로세스 다음 레벨의 큐로 들어감" 이 부분에서 다 못 채운 프로세스들이 다음 레벨의 큐로 가는 것 아닌가요?