강의지원 게시판

[OS] Nachos 과제 관련 공지 (5/10 17:00 수정 - 마감시간 수정)

O S
작성자
ASL @ KAU ASL @ KAU
작성일
2015-05-07 10:01
조회
2988

Nachos 마감은 1주일 뒤로 미룹니다. (5월 14일 11:00) / 단, 1주일 뒤 미제출 or 진행사항이 부족할 시, 과제 점수 0점에 추가로 시험점수에서까지 감점 처리합니다.

그래도 지금까지 과제 한 내용에 관하여 정리하여 보고서는 5월 7일 20:00까지 제출하시면 됩니다.

코드는 자신이 생각하기에 더 진행된 것이 없다 생각되면 메일로 제출하지 않으셔도 됩니다만, 최소한 자기가 지금까지 조사한 내용에 대한 분석 보고서는 제출해주시기 바랍니다.
(오늘 수업에서 들은 내용 추가하지 말고, 솔직하게 본인이 수업 들어오기 전까지 분석한 내용만 작성하시기 바랍니다.)

 

-오늘 수업에서 설명한 분석 내용

Priority Scheduler문제의 핵심은 PriorityQueue의 자료구조 구현보다는, Priority Scheduling으로 인해 생기는 문제에 대하여 해결하는 것이 핵심입니다.
예를 들면, Low Priority Thread가(상대적으로 Priority가 낮다는 것임) Critical Section에 대한 Lock을 건 상태로 Sleep한다면, High Priority Thread가 해당 Critical Section에 접근하려고 할 경우, Atomicity를 제공하기 위해 일반적으로 Busy Waiting을 하거나, Sleep합니다. 하지만, Priority Scheduling Algorithm에 따라 Low Priority Thread는 자신의 차례를 받기 힘들 것이고, 이로 인해 High Priority Thread가 같이 아무 작업도 못하는 Starvation에 들게 됩니다.
이 때, Low Priority Thread와 High Priority Thread 단 2개만 존재한다면, 쉽게 해결할 수 있으나, (Preemtive한 방식으로 Resource를 강탈하거나, Aging 등으로 인해 Low Priority Thread가 수행되는 경우) 전체 Thread의 갯수가 그 이상일 경우 Scheduling Algorithm에 따라 둘 다 Starvation이 일어날 확률이 높습니다. 이러한 상황의 문제를 어찌 해결하느냐가 이번 과제가 요구하는 바입니다.

PriorityScheduler 파일을 보면 각 ThreadState에 대하여 getPriority로 기본적인 Priority를 알 수 있으나, 위에 언급한 문제 등을 해결하기 위해 Priority가 변경되어야 할 필요가 있습니다. (ex. Priority Inversion, Priority Aging, 등등...) 이러한 이유로 getEffectivePriority에서 기존의 Priority + 상황에 따라 Priority 조정한 결과를 얻어야 합니다.

Aging을 구현하기 위해서, Priority정보에 관한 배열을 두어, 하나씩 밀려나가는(?)방식으로 시도를 해 보았으나, 자료구조의 문제인지 Thread의 갯수가 매우 많아지는 경우에 대하여 해결하지 못하는 문제가 있었습니다.

기존의 Scheduler로 RoundRobinScheduler를 제공하며, Scheduling이 일어나는 TimerInterrupt는 nachos.machine.Timer에서 약 500Tick마다 TimerInterrupt가 실행되며, 현재 수행되고 있던 Thread가 Scheduler를 호출하여, Scheduling 알고리즘에 의해 Thread를 선택하여, 해당 Thread를 마저 수행시키게 하는 방식으로 작동하는 것으로 보입니다.

기본적으로 Priority Scheduling 시나리오에 관한 테스트를 위해 nachos.ag.BasicTestGrader를 기반으로 작성하라고 하였는데, 일단은 nachos 자체가 OS로서 실행되는 것이기 때문에, 지정된 시나리오는 OS가 main으로 하는 동작이 아니라, Autograder로 재현하는 것이 더 맞다고 생각하기 때문에 이쪽 방향을 강요한 것입니다. 본인이 BasicTestGrader를 이용하여 테스트 시나리오를 테스트하기 힘들다면, selfTest 함수 등을 이용하여 재현하셔도 좋습니다. (다만, 주어진 조건을 더 지킨 만큼, AutoGrader쪽에 추가 점수를 줄 예정입니다.)

package nachos.machine; 은 nachos를 구동시키기 위한 기계를 가상머신으로 만든 것이며, 실제 nachos의 Kernel은 nachos.threads.ThreadedKernel으로 동작하며, 그냥 $nachos 명령으로 구동시킬 경우, ThreadedKernel.selfTest() 함수의 내용을 수행합니다. (환경 구축할 때 나왔던 *** thread 0 looped 0 times ....이 여기에서 호출되어 나오는 것입니다.)

 

+ 조교 추가자료 1
http://inst.eecs.berkeley.edu/~cs162/sp14/ (nachos 자체를 개발 & 배포하는 강의) 의 분석에 따르면 PriorityScheduler를 구현하는데 약 125 line정도 추가하면 될 것이라고 언급하였습니다. = 특별하게 새로운 자료구조를 작성하거나 할 필요는 없는 것으로 보입니다.

그리고 위의 Lock 등의 Resource가 Scheduling에 영향을 주는 만큼, Lock에 코드가 더 추가되어야 하는 것으로 보이지만, 해당 부분은 수정하지 않고, Scheduler 자체가 해결해야 하는 것이라고 하고 있습니다. = Lock 등을 수정하는 것은 편법임.

+ 조교 추가자료 2
코드 중간에 보면 Lib.assertTrue(~~~)와 같은 코드가 존재하는 것을 볼 수 있고, 학생들이 제출한 스크린샷 등을 보면 해당 함수 호출되는 부분에서 AssertionFailureError 등으로 실행이 멈추는 상황을 해결하지 못하는 경우가 많이 있습니다.
assertTrue라는 함수는 어떤 상황이 무조건 참이라는 것을 보증해야만 하는 경우에 사용하는 함수로, 안에 argument로 들어온 조건이 참이 아닐 경우에 아예 프로그램(본 과제에서는 nachos 자체)을 종료하는 것입니다.
예를 들면 Scheduler가 다음 Thread를 선택하는 과정에는 어떤 interrupt도 일어나선 안됩니다. (Scheduling 과정에 대한 Atomicity를 보장해줘야 한다고 볼 수 있음) 이런 때에 Lib.assertTrue(Machine.interrupt().disabled()); 과 같은 코드로 모든 인터럽트 핸들링이 꺼져있는지 확인하는 것입니다.

 

참고 자료

첨부파일 (위의 문제 분석 일부에 대한 원문)
www.cs.berkeley.edu/~kubitron/cs162/Nachos/nachos.ppt

P.S. 목요일 실습시간에 nachos 코드로 강의하므로, 과제 마감기한을 앞당깁니다.