Assignment 2 - Parallel processing

Assignment 2 - Parallel processing

이번 과제는 저번처럼 이미 짜여진 코드를 수정하여 더 효율적이게 바꾸는 것이라 코드만 이해하고 넘어가보도록 하겠다.

저번 Assignment 1 - Process package의 확장판이라고 볼 수 있는 과제였다. 위의 설명과 같이 n개의 threads를 통해 m개의 업무를 처리하는 과정이며 ti 는 m개의 업무 중 i번째 업무의 처리시간을 의미한다.

Input format :
n m
t1 t2 t3 ... ti ti+1 ti+2 ...

Output format :
index(thread) time(start at)
index(thread) time(start at)
index(thread) time(start at)
...

 바로 예시를 들어 이해를 하자면 Sample 1에서 보여 주듯 thread의 갯수(n)는 2개, 업무의 갯수(m)은 5개이며 각 업무의 처리시간은 1, 2, 3, 4, 5초가 되겠다. 이에 대한 출력은 각 thread에서 업무에 착수한 시각들을 내보내야 하므로, 0번째 thread가 0초에 착수하고 1번째 thread가 0초에 착수하여 처리를 시작한다. 이후 1초가 되면 0번째 thread에서 업무는 완료되어 다음 프로세스를 착수하게 되어 0번째 thread에서 1초에 착수하는 것을 출력하게 된다.
 다음 예시인 Sample 2는 더 간단한데 n은 4, m은 20이고 이에 대한 각 처리시간들이 모두 1초이다. 따라서 4개의 threads가 동시에 착수하여 끝내고 다시 착수하고 끝내고를 반복하는 모습을 보여주게 된다.

# python3
class JobQueue:
    def read_data(self):
        self.num_workers, m = map(int, input().split())
        self.jobs = list(map(int, input().split()))
        assert m == len(self.jobs)

    def write_response(self):
        for i in range(len(self.jobs)):
          print(self.assigned_workers[i], self.start_times[i]) 

    def assign_jobs(self):
        # TODO: replace this code with a faster algorithm.        self.assigned_workers = [None] * len(self.jobs)
        self.start_times = [None] * len(self.jobs)
        next_free_time = [0] * self.num_workers
        for i in range(len(self.jobs)):
          next_worker = 0          for j in range(self.num_workers):
            if next_free_time[j] < next_free_time[next_worker]:
              next_worker = j
          self.assigned_workers[i] = next_worker
          self.start_times[i] = next_free_time[next_worker]
          next_free_time[next_worker] += self.jobs[i]

    def solve(self):
        self.read_data()
        self.assign_jobs()
        self.write_response()


if __name__ == '__main__':
    job_queue = JobQueue()
    job_queue.solve()

위의 과제내용에 대한 코드이다. 제출자는 더 빠른 알고리즘을 원했지만 딱히 변경은 하지 않겠다. JobQueue 클래스를 선언하고 read_data를 통해 입력값들에 대한 인자들을 정리하며, write_response를 통해 업무들을 처리한 정보에 대해 하나씩 출력해준다. assign_jobs는 각 부여된 업무들을 빈 thread에 어떻게 할당할지에 대한 알고리즘이며 solve를 통해 이들을 정리해준다.