SJF( Shortest Job First ) 스케줄링 구현관련 문의 (python)
조회수 1913회
SJF 스케줄링을 효과적으로 구현해놓은 샘플코드를 찾던중에 다음과 같은 코드를 발견했습니다.
Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
위 코드를 Python으로 다음과 같이 구현해보았습니다.
class Schedule():
def __init__(self, name, at, bt):
self.name = name
self.at = at
self.bt = bt
self.ct = 0
def __repr__(self):
return '\t'.join([self.name, str(self.at), str(self.bt), str(self.ct)]) + '\n'
def solution(processes):
pro = []
for p in processes:
pro.append(Schedule(p[0], p[1], p[2]))
pro.sort(key=lambda x: (x.at, x.bt))
pro[0].ct = pro[0].bt + pro[0].at
for j in range(1, len(processes)):
ab = pro[j-1].ct
# partial sorting 부분
waitings = list(filter(lambda x: x.at < ab, pro[j:]))
pro[j:j+len(waitings)] = sorted(waitings, key=lambda x: x.bt)
# partial sortings 부분
if pro[j-1].ct < pro[j].at:
pro[j].ct = pro[j-1].ct + pro[j].bt + pro[j].at - pro[j-1].ct
else:
pro[j].ct = pro[j-1].ct + pro[j].bt
return pro
print(solution([['A', 0, 4], ['B', 3, 2], ['C', 5, 6], ['D', 4, 6], ['E', 5, 7]]))
# 코드 실행하기로 실행되도록 수정함. -------------------------------V
위 코드에서 제가 " partial sorting" 이라고 표현해놓은 부분을 좀더 pythonic 하게 구현할 수는 없을지요? 위 링크에 있는 C++ 코드가 좀더 간결하고 한 눈에 이해하기 좋아보여서 파이썬도 이런 방법이 가능할지 알고 싶습니다.
bool compare2(schedule a,schedule b)
{
return a.bt < b.bt && a.at <= ab;
}
/* main( ) 에서 호출방법 */
sort(pro+i,pro+n,compare2);
업데이트 : 아래 질문은 다른곳에서 힌트를 얻어서 일단 취소합니다.
추가 질문 :
위와 같은 기능을 지원하는 SJF 스케줄링을 python의 heapq를 사용하여 효과적으로 구현할 수 있을지요? SJF를 heap을 이용해서 구현할 수 있다는 내용을 어디서 본 것 같은데, 효과적으로 적용할 수 있는 방법은 잘 생각이 나지 않네요... ( 위의 경우와 같이 프로세스의 arrival time이 모두 같지 않고 변경되는 경우에 적용할 수 있는 방법입니다.)
댓글 입력