Sunday, July 16, 2017

Shortest Job First

July 16, 2017

Plan to study the algorithm called "Shortest Job First". There are a list of jobs with execution and arrival time, shortest job will be processed first, and then average waiting time will be calculated.

Problem statement here is in Chinese.

一个处理器要处理一堆request,一次只能处理一条,如果它有几个积压着的requests,它会先执行持续时间短的那个;对于持续时间相等的requests,先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input:requestTimes[],每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的,并已按requestTimes[] 从小到大排序过。

Plan to study code written in Java first. 



Practice

C# practice using SortedSet, the code is here. 

There are seven requests in the following example, every request has two time stamps, request time and execution time. First request can be expressed in the form of (1, 2), where the request time is 1 and execution time is 2. Hopefully it makes clear to the second column with title "Process to Consider", second row (1, 2). 


Fix the bug in previous C# code because the average time should be 3.29. C# code is here, the correction is on line 71. 

No comments:

Post a Comment