x*****0
发帖数: 452 | 1 Assume in a system, users will register a callback function with system and
that callback function will be called when an event is triggered
but if the event is already triggered, the user will synchronously call
the callback function
For example
suppose user i registers cb i at time Ti,
and the event happens at time Te
and assume that T1 < T2 < T3 <...< Tm < Te < Tm+1 < ... < Tn
at time Te, cb1..cbm will be called
cbm+1 .. cbn will be called synchronously
implement two APIs: void register_cb (cb), and void event_trigger()
上面是原题的描述，我简单的概括一下：
设计一个system，里面有一个task queue和两个function。
1’ trigger。这个function运行并清空task queue中所有的tasks。
2‘ addTask。在trigger之前把task加入task queue，在trigger之后直接运行task。
----------------------------------------------------------------------------
---
单线程下当然好做:
class TriggerTask {
Queue q;
boolean triggered = false;
addTask(Task t) {
if (triggered == true) {
t.invoke();
}
else {
q.offer(t);
}
}
triggerTask() {
triggered = true;
while (!q.isEmpty()） {
q.poll().invoke();
}
}
----------------------------------------------------------------------------
---
follow up: 如果在多线程环境下呢？因为没有找到更多的关于这个follow up的描述，
我只能自己猜测了。
现在有两个线程，一个负责register, 一个负责trigger。当register第m个task时，假
设此时is_triggered==0（没有触发），程序运行到q.append(cb)，但是还没加入到队
列，这个时候这个线程下CPU，另一个负责trigger的线程上了CPU，并且一直把所有在
queue中的callback都调用了，然后才下CPU。此时负责register的线程重新获得CPU，
继续未完成的工作，把Tm(task m)加入queue，然后这个线程接着在CPU上运行，因为此
时is_triggered变成true了，所以后续register的task，会被直接call。那么就产生问
题了。这个Tm(task m) 没有被call，还在queue里呆着呢！
大家觉得呢，follow up可以按照上面这样理解吗？或者还有其它的理解。
如果按照上面来理解的话，那么怎么来解呢？
这是版上给出的解答：
class TriggerTask {
Queue q;
boolean triggered = false;
Lock lock = new Lock();
addTask(Task t) {
lock.lock();
if (triggered == true) {
lock.unlock()
t.invoke();
}
else {
q.offer(t);
lock.unlock();
}
}
triggerTask() {
triggered = true;
lock.lock();
lock.unlock();
while (!q.isEmpty()） {
q.poll().invoke();
}
}
不明白在triggerTask()中为什么：
lock.lock();
lock.unlock();
大家可以帮忙说说吗？
reference:
http://www.mitbbs.com/article_t1/JobHunting/32908907_0_1.html
http://www.mitbbs.com/article_t/JobHunting/32702941.html |
x*****0
发帖数: 452 | |
l******s
发帖数: 3045 | 3 对题意的理解应该是在Te的时候并发执行CB1 .. CBe，然后串行执行后面的。
对于后面串的.Net里有Task.ContinueWith(Task Another)可以做到，一个个串起来好
了。
前面的并发需要做一个Sync Task.WaitAll()在后面串行执行之前。 |
x*****0
发帖数: 452 | 4 谢谢回复。请问可以这么说吗？
在Te时间之前，可以有很多线程同时执行register？
【在 l******s 的大作中提到】
: 对题意的理解应该是在Te的时候并发执行CB1 .. CBe，然后串行执行后面的。
: 对于后面串的.Net里有Task.ContinueWith(Task Another)可以做到，一个个串起来好
: 了。
: 前面的并发需要做一个Sync Task.WaitAll()在后面串行执行之前。
|
l******s
发帖数: 3045 | 5 可以有很多执行register，那个只要加个lock就可以解决。我觉得这道题的考核重点是
对于callback函数的赋值方式和执行方式：
在event之前，是维护一个IEnumerable，执行时用并行foreach(){task.Run}
在event之后，是用 += 的方式赋值，执行时是串行。
考虑到系统执行不可能只允许一次event情形，可能需要加一个flag来标志当前状态是
执行event前还是执行event后。当串行运行完之后可以恢复到event前的状态，继续添
加并行Task到IEnumerable。
【在 x*****0 的大作中提到】
: 谢谢回复。请问可以这么说吗？
: 在Te时间之前，可以有很多线程同时执行register？
|
l******s
发帖数: 3045 | 6 I'll try writing up it. Let me know.
//Maintain 2 Task Queue, to avoid long time occupying Task list variable
when a sync event trigger calling happens.
IEnumerable TRegister;
IEnumerable TExecute;
//define 2 lock object:
Object oRegister
Object oExecute
//define a flag (false is after event; true is before event)
flag_Event = true;
void AddTask(Task t)
{
lock(oRegister)
{
TRegister.Add(t);
}
}
void Trigger_Event()
{
lock(oExecute)
{
lock(oRegister)
{
foreach(var t in TRegister)
{
TExecute.Add(t);
}
TRegister.Clear();
}
if(flag_event)
foreach(var t in TExecute)
t.Run();
else
foreach(var t in TExecute)
await t.Run();
Task.WaitAll();
TExecute.Clear();
flag_Event = !flag_Event;
}
} |
x*****0
发帖数: 452 | 7 谢谢啊！
【在 l******s 的大作中提到】
: I'll try writing up it. Let me know.
: //Maintain 2 Task Queue, to avoid long time occupying Task list variable
: when a sync event trigger calling happens.
: IEnumerable TRegister;
: IEnumerable TExecute;
: //define 2 lock object:
: Object oRegister
: Object oExecute
: //define a flag (false is after event; true is before event)
: flag_Event = true;
|
