[프로그래머스] (Swift) 디스크컨트롤러 (Lv.3) (feat. 운영체제의 SFJ 스케줄링 알고리즘)

🟠 TIL - 오늘은 무엇을 배웠나요!

📝 운영체제의 SFJ 알고리즘 (최소 작업 우선 스케줄링)

최소 작업 우선 스케줄링 이란, 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행시간이 가장 짧은 작업에 할당하는 방법

• 항상 실행시간이 짧은 것부터 처리하기 때문에, 평균 대기시간이 줄어든다.

해당 문제는 비선점 스케줄링 방식이다. 비선점 SFJ 스케줄링 방법을 살펴보자.

https://wonit.tistory.com/104

• p1은 전에 아무 프로세스가 없기 때문에 바로 실행한다.
• p1의 실행 시간이 1일때, 2일때, 3일때, 4일때 각각 p2, p3, p4, p5가 들어온다.
• 각각의 프로세스 실행 시간을 비교하여 가장 짧은 프로세스 p4를 인지하고 p4를 실행 시킨다.
• p4의 실행이 끝나고 나서 그 다음의 실행 시간이 짧은 p3를 실행시킨다.
• p3의 실행이 끝나고 그 다음 실행 시간이 짧은 p5를 실행 시킨다.
• p5의 실행이 끝나고 그 다음 실행 시간이 짧은 p2를 실행 시킨다.

이런 방식으로 진행되며, 아래 문제와 동일한 방식이다. 그대로 코드로 구현하면 되는 문제였다. (나는 말이 장황하게 되어있고, SFJ를 몰랐어서 문제를 이해하는데 조금 걸렸다 ㅠㅠ 역시 운영체제 중요해...✨)

https://wonit.tistory.com/104

https://wonit.tistory.com/104

💡 반환시간 = 위 차트에 실행 순서에 따른 실행 시간 + 대기시간
💡 대기시간 = 반환시간 - 실행시간

 

이렇게 결과가 나오게 된다.

이제 선점 스케쥴링 방식을 간단하게 알아보자.

https://wonit.tistory.com/104

• p1은 아무 프로세스가 없기 때문에 바로 실행된다.
• 시간이 흐르고 실행 시간이 1일때 p2가 들어오는데, p2의 실행 시간(28)보다 p1의 실행 시간(10-1=9)가 더 짧기 때문에 계속 진행한다.
• 또 시간이 흐르고 실행 시간 2일 때 p3가 들어오는데 p1의 실행 시간(10-2=8)보다 p3의 실행 시간(6)이 더 짧기 때문에 p1의 실행을 잠시 중단하고 p3를 실행시킨다.
• 시간이 흐르고 실행 시간 3일때 p4가 들어오는데 p3의 실행 시간(6-1=5)보다 p4의 실행 시간(4)가 더 짧기 때문에 p3를 잠시 중단시키고 p4를 실행 시킨다.
• 시간이 흐르고 실행 시간이 4일 때 p5가 들어오는데, p4의 실행 시간(4-1=3) 보다 p5의 실행 시간(14)이 길기 때문에 p4를 그대로 유지시킨다.
• 시간이 흐르고 실행 시간이 7일 때 p4의 실행을 끝내고 그 다음으로 짧은 p3를 실행시킨다.
• (반복)

결국엔 이러한 간트차트가 나온다.

 

🟠 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42627 

프로그래머스

 

 

🟠 문제 풀이

사실 처음에 보고 '힙'알고리즘을 사용하라고 해서 조금 헤맸다. 힙은 스위프트에서 지원하지 않기 때문에 어떻게 구현해야할지 막막했고, 도대체 이게 왜 ... 힙을 사용해야하는지 몰랐다 ㅠㅠ (SFJ알고리즘을 몰랐다,,)

힙을 사용해야하는 이유는, python을 예를 들면, heap 에 저장하면, 작은 순서대로 heap 내부에 정렬이 되고, heappop을 하게 되면 자동으로 가장 작은 수가 Pop된다고 한다.

해당 문제는, '작업 소요 시간'이 작은 순서대로 처리하는 것이 핵심이었으므로, 힙을 사용하면 된다고 언급된 것이다.

그럼 왜 작업소요시간이 작은 순서대로 처리해야하는가?

소요시간이 짧은 순서대로 진행하게되면, 평균 대기시간이 줄어들기 때문이라고 한다. 이는 위에 TIL 파트에서 더 자세한 설명이 될 것이다.

그래서 문제는 아래와 같이 풀었다. 스위프트에서는 힙이 없으므로 정렬을 잘 해주는게 포인트였다. 그리고 더불어서, 끝나는 시간은 항상달라지는데, 시작시간 가능 시간은 항상 같다. 그래서 '시작시간이 빠른 순서대로', '시작시간이 같다면 소요시간이 작은순서대로' 정렬해주었다.

1. 두번의 정렬 과정을 거친다.
2. 그리고 현재시점을 저장할 변수 now, 대기시간과 소요시간을 모두 합친 결과를 담을 totalTime 변수를 만들었다.
3. 정렬된 jobs 배열에서 remove 하면서 진행할 것이기 때문에 (python에서는 heappop) jobs배열이 아예 없어질때까지 반복하기위해서 while문을 사용한다.
4. 그 안에서 for문을 이용해서 내부에서 당장 더할 수 있는 작업들을 찾을 것이다.
5. check라는 변수는, 작업을 마친 시간 now가, 작업 요청시간보다 작을 경우에 필요해서 넣었다. check 가 true로 바뀌지 않는다면,현재 요쳥된 작업을 시작할 시간이 아직 되지 않았다는 뜻이므로, now에 +1 씩 해준다.

위 과정을 생각하는데 조금 시간이 걸렸다. 그래서 아이패드로 차근차근 그려나가면서 문제를 풀었다. (사실 인터넷도 조금 참고;; )

 

🟠 정답코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/디스크컨트롤러/main.swift

GitHub - deslog/Algorithm: ✨ 백준, 프로그래머스 Swift 문제풀이 ✨

import Foundation

var jobs = [[0, 3], [1, 9], [2, 6]]
// return 9
func solution(_ jobs:[[Int]]) -> Int {
    var sortedJobs = jobs.sorted(by: { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $1[0] })
    sortedJobs.sort(by: { $0[1] == $1[1] ? $0[0] < $1[0] : $0[1] < $1[1] })
    var now = 0
    var totalTime = 0

    while !sortedJobs.isEmpty {
        var check = false
        for i in 0..<sortedJobs.count {
            if sortedJobs[i][0] <= now {
                now += sortedJobs[i][1]
                totalTime += now - sortedJobs[i][0]
                sortedJobs.remove(at: i)
                check = true
                break
            }
        }
        // for문안에다가 넣어서 시간 한참걸렸네 ㅠㅠ 
        if !check {
            now += 1
        }
    }

    return totalTime / jobs.count
}