一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1208|回复: 21
收起左侧

[请教] oa2 RoundRobin Schedule 一个概念问题

[复制链接] |试试Instant~ |关注本帖
candy-sweety 发表于 2015-11-13 04:56:59 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Amazon - 内推 - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
如果出现一个任务刚强制结束,一个新任务刚好这个时间来,要怎么处理。 比如说:

arrivals[0,0,2,3]
executetime[5,2,5,6]. visit 1point3acres.com for more.

结果应该是多少。

题目好像说按照在原先array的顺序,但是地里的答案基本没有考虑这一点. 鍥磋鎴戜滑@1point 3 acres


补充内容 (2015-11-13 05:36):
还有一个问题 关于 sjf 的
会不会出现这种情况: arrive_time 是[0,0,1,2] exe_time 是 [3,1,2,4]  这样应该先处理p2吧?但是看地里解答是 直接用p1初始化那个 priority_queue的

本帖被以下淘专辑推荐:

熊亮亮111 发表于 2015-11-16 09:38:51 | 显示全部楼层
raphtao07 发表于 2015-11-13 05:22
嗯,新任务是add不是offer

你好!我不明白 为什么新任务是 add 不是offer呢?这里add 和offer应该没什么区别吧。  求大神讲解一下
回复 支持 1 反对 0

使用道具 举报

raphtao07 发表于 2015-11-13 05:03:28 | 显示全部楼层
是原先array的末尾。不知道你看的哪个版本,这个版本考虑了
class process {. From 1point 3acres bbs
        int arrTime;
        int exeTime;
        process(int arr, int exe) {
                arrTime = arr;. visit 1point3acres.com for more.
                exeTime = exe;
        }
}

public class RoundRobinScheduling {
        public float Solution(int[] Atime, int[] Etime, int q) {
                if (Atime == null || Etime == null || Atime.length != Etime.length)        return 0;
                int length = Atime.length;.1point3acres缃
                Queue<process> queue = new LinkedList<process>();
                int curTime = 0, waitTime = 0;
                int index = 0;
                while (!queue.isEmpty() || index < length) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        if (!queue.isEmpty()) {. 1point 3acres 璁哄潧
                                process cur = queue.poll();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                waitTime += curTime - cur.arrTime;
                                curTime += Math.min(cur.exeTime, q);
                                while (index < length && Atime[index] <= curTime; index++){
                                        queue.offer(new process(Atime[index], Etime[index]));
                                if (cur.exeTime > q)
                                        queue.offer(new process(curTime, cur.exeTime - q));
                                }
                        }
                        else {
                                queue.offer(new process(Atime[index], Etime[index]));
                                curTime = Atime[index++];
                        }. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
                return (float) waitTime / length;. 1point 3acres 璁哄潧
        }.1point3acres缃
}
回复 支持 反对

使用道具 举报

raphtao07 发表于 2015-11-13 05:05:59 | 显示全部楼层
raphtao07 发表于 2015-11-13 05:03
是原先array的末尾。不知道你看的哪个版本,这个版本考虑了
class process {
        int arrTime;

把if (cur.exeTime > q)
      queue.offer(new process(curTime, cur.exeTime - q));
                                }中的offer换成add
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-13 05:13:06 | 显示全部楼层
这题是默认在同一个瞬间新进来的任务是比刚结束该回合的任务有优先权的,所以先让新任务进队列,再把刚结束的任务放队尾就好
回复 支持 反对

使用道具 举报

raphtao07 发表于 2015-11-13 05:22:48 | 显示全部楼层
CSBrogrammer 发表于 2015-11-13 05:13
这题是默认在同一个瞬间新进来的任务是比刚结束该回合的任务有优先权的,所以先让新任务进队列,再把刚结束 ...

嗯,新任务是add不是offer
回复 支持 反对

使用道具 举报

 楼主| candy-sweety 发表于 2015-11-13 05:23:35 | 显示全部楼层
CSBrogrammer 发表于 2015-11-13 05:13
这题是默认在同一个瞬间新进来的任务是比刚结束该回合的任务有优先权的,所以先让新任务进队列,再把刚结束 ...

哦哦好~~谢谢解答。btw SJF 那题也顺便请教一下,如果前两个任务都是0的时间进,也要先执行那个execute时间短的吧?
回复 支持 反对

使用道具 举报

 楼主| candy-sweety 发表于 2015-11-13 05:24:26 | 显示全部楼层
raphtao07 发表于 2015-11-13 05:03
是原先array的末尾。不知道你看的哪个版本,这个版本考虑了. 1point 3acres 璁哄潧
class process {
        int arrTime;

嗯我看的就是这个版本~我的问题楼下解决了~
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-13 05:25:57 | 显示全部楼层
candy-sweety 发表于 2015-11-13 05:23. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
哦哦好~~谢谢解答。btw SJF 那题也顺便请教一下,如果前两个任务都是0的时间进,也要先执行那个execute ...

是滴,sjf的话在heap里的任务永远是执行execution最短的那个. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2015-11-13 05:27):
你就理解为一旦卡牌进场就完全由heap来handle顺序,你就知道每次poll一个任务就行了

补充内容 (2015-11-13 05:29):
额为什么是卡牌?(因为把任务看成卡牌的话会很有意思。。。有点当年游戏王的感觉呵呵呵)
回复 支持 反对

使用道具 举报

 楼主| candy-sweety 发表于 2015-11-13 05:31:01 | 显示全部楼层
CSBrogrammer 发表于 2015-11-13 05:25
是滴,sjf的话在heap里的任务永远是执行execution最短的那个

补充内容 (2015-11-13 05:27):

嗯 我意思~会不会出现这种情况: arrive_time 是[0,0,1,2] exe_time 是 [3,1,2,4]  这样应该先处理p2吧?但是看地里解答是 直接用p1初始化那个 priority_queue的
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-13 05:36:28 | 显示全部楼层
candy-sweety 发表于 2015-11-13 05:31
嗯 我意思~会不会出现这种情况: arrive_time 是[0,0,1,2] exe_time 是 [3,1,2,4]  这样应该 ...

我没看地里的代码,但是priority queue的初始化不需要element的,你把comparator设置好然后在每个iteration开始就先check arrive time把小于当前clock的任务都放进heap里后再poll就好. from: 1point3acres.com/bbs

补充内容 (2015-11-13 05:37):
是的,应该先处理p2
回复 支持 反对

使用道具 举报

 楼主| candy-sweety 发表于 2015-11-13 05:38:22 | 显示全部楼层
CSBrogrammer 发表于 2015-11-13 05:36
我没看地里的代码,但是priority queue的初始化不需要element的,你把comparator设置好然后在每个iterati ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
嗯好,所以像刚刚的情况,就应该先处理p2 对吧?不过testcase比较少可能不会出现前两个都是0的情况
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-13 05:41:18 | 显示全部楼层
candy-sweety 发表于 2015-11-13 05:38. 1point3acres.com/bbs
嗯好,所以像刚刚的情况,就应该先处理p2 对吧?不过testcase比较少可能不会出现前两个都是0的情况
. Waral 鍗氬鏈夋洿澶氭枃绔,
嗯,即使出现你也知道怎么handle了不是
回复 支持 反对

使用道具 举报

 楼主| candy-sweety 发表于 2015-11-13 05:46:55 | 显示全部楼层
CSBrogrammer 发表于 2015-11-13 05:41. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
嗯,即使出现你也知道怎么handle了不是

然后我又想到了一个 case
arrive time [0,0,2,3]
exe time [2, 5, 3, 4]

这样的话 p1刚结束p3刚好进来 , 这时候先处理 p3 还是 p2 呀?
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-13 06:15:33 | 显示全部楼层
candy-sweety 发表于 2015-11-13 05:46
然后我又想到了一个 case
arrive time [0,0,2,3]
exe time [2, 5, 3, 4]

p3,因为此时p3已经进来了,你就把每一秒和下一秒之间都看成是有一个延迟就好了
回复 支持 反对

使用道具 举报

coolthluo 发表于 2015-11-13 10:50:18 | 显示全部楼层
如何处理 [0,0] [2,1] 的情况呢,用priority queue的话
回复 支持 反对

使用道具 举报

 楼主| candy-sweety 发表于 2015-11-13 12:17:12 | 显示全部楼层
coolthluo 发表于 2015-11-13 10:50
如何处理 [0,0] [2,1] 的情况呢,用priority queue的话

应该是0.5  具体你看楼上的讨论哈~
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-13 12:34:44 | 显示全部楼层
coolthluo 发表于 2015-11-13 10:50
如何处理 [0,0] [2,1] 的情况呢,用priority queue的话

这个是0。。。因为nobody is waiting. from: 1point3acres.com/bbs

补充内容 (2015-11-13 12:37):.鐣欏璁哄潧-涓浜-涓夊垎鍦
噢不好意思,是0.5呵呵呵
回复 支持 反对

使用道具 举报

raphtao07 发表于 2015-11-16 10:43:45 | 显示全部楼层
熊亮亮111 发表于 2015-11-16 09:38
你好!我不明白 为什么新任务是 add 不是offer呢?这里add 和offer应该没什么区别吧。  求大神讲解一下

是我记错了,确实没区别
回复 支持 反对

使用道具 举报

dwy189 发表于 2015-11-16 11:21:29 | 显示全部楼层
这一题除了二楼贴的解法外有没有更好的解法呢? 二楼的时间复杂度是怎么样的? 谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 20:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表