一亩三分地论坛

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

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

[系统设计/OOD] 请教一道面试题 -- delay scheduler

[复制链接] |试试Instant~ |关注本帖
echofreshman 发表于 2016-1-4 08:00:26 | 显示全部楼层 |阅读模式

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

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

x
经常在面经里看到要求implement a delay scheduler这道题,就是给一个任务和指定的delay时间,要求把task schedule在指定的时间执行,比如schedule method长这样:Future schedule(int delay_time, Runnable task)。

我对这样的题目感到无从下手,也一直没看到一个比较详细的解题思路,根据目前搜集到的信息,感觉是不是应该这样做:

1.  当拿到一个任务,先把当前的timestamp加上指定的delay_time,形成一个新的timestamp,然后把这个新的timestamp连同task本身存到一个自定义的类里面,比如这个类叫DelayedTask.
2. 维护一个PriorityQueue,把DelayedTask存到PriorityQueue里面,timestamp最小的在栈顶。
3. 用一个loop不停比较栈顶task的timestamp和当前时间,当二者相等时,用ExecutorService来submit Runnable task,从而得到一个Future object,然后返回这个Future object。

这样的作法可行吗?还有就是如果发现 当前时间超过了栈顶task本来plan好要执
行的时间要怎么处理呢?

请大神们不吝赐教,如果有代码分享就更好了。多谢了!
lotustree86 发表于 2016-2-4 16:32:06 | 显示全部楼层
3这一步可以优化一下,不用polling. 你需要一个单独的thread来维护那个队列,调用task. 通过wait, notify来唤醒thread.每次schedule一个新的任务后,call notify唤醒scheduling thread。被唤醒后,查看任务是否到时,如果没有任何任务到时,这wait相应的时间。

具体代码推荐参考Java timer class source code.不复杂。


回复 支持 反对

使用道具 举报

 楼主| echofreshman 发表于 2016-2-5 01:10:56 | 显示全部楼层
lotustree86 发表于 2016-2-4 16:32
3这一步可以优化一下,不用polling. 你需要一个单独的thread来维护那个队列,调用task. 通过wait, notify来 ...

泪流满面,帖子发出这么久终于有好心人回复了。非常感谢点拨,我去看一下sourse code!
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-5 09:22:27 | 显示全部楼层
用java的delayqueue
回复 支持 反对

使用道具 举报

 楼主| echofreshman 发表于 2016-2-5 09:30:23 | 显示全部楼层

嗯,如果是考察对java API了解程度的话,直接说用DelayQueue应该就可以了。不过看之前面经貌似这题是让自己设计一个类似DelayQueue的结构
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-2-5 09:59:07 | 显示全部楼层
那就参考一楼的,他的解法OK
回复 支持 反对

使用道具 举报

 楼主| echofreshman 发表于 2016-2-5 13:16:19 | 显示全部楼层
alen231x 发表于 2016-2-5 09:59
那就参考一楼的,他的解法OK

好的,多谢了!!
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2016-2-14 12:36:59 | 显示全部楼层
lotustree86 发表于 2016-2-4 16:32
3这一步可以优化一下,不用polling. 你需要一个单独的thread来维护那个队列,调用task. 通过wait, notify来 ...

大牛,我java concurrency不熟,想请教下这个地方每次schedule新的任务才去wake notify那个timer thread的话,会不会错过队列顶的任务的delay时间?
回复 支持 反对

使用道具 举报

lotustree86 发表于 2016-2-16 05:42:03 | 显示全部楼层
不会,thread 在call wait 函数的时候可以传waiting time parameter,就设成栈定那个任务的等待时间。这段时间内如果没有新的任务加进来,thread will wake up automatically after the waiting time expired
回复 支持 反对

使用道具 举报

kelong 发表于 2016-2-22 05:47:19 | 显示全部楼层
这种设计题尽量不依赖系统函数。

我觉得一个比较好的办法如下:
1. 每来一个task,define start_time = cur_time + delay
2. 设置一个Heap<task>, 以task.start_time排序,最小的放在top
3. 把当前task加入Heap,set timer = (Heap.top.start_time - cur_time)
4. 当timer到时间激发时,run task = Heap.top; Heap.remove_top; set timer = (Heap.top.start_time - cur_time)

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 02:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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