g******d
发帖数: 1774 | 1 面试题是这样的，c++
有很多同时进行的 request 或者action, 都会call同一个function,
需要你在这个function中控制同时执行的request/action的数目。
这个数目可变，
譬如， 刚开始， 允许的数目是 1， 也就是每次只有一个可以执行，相当于mutex. 假
如有500 个request, 那就是一个完了在下一个
过一段时间， 用户把允许的数目改为500， 也就是同时可以500个一起（当然也是
protected), 相当于semaphore, 假如有500个，可以不等待一起执行， 假如是1000个
，第一批500个同时进行，后面的就得等 someone to sem_post.
一开始思路就是这样，讨论了一会。 但问题是， 这个数目可以动态变化， 怎么实现。
这样的话， mutex 和 semaphore 都不能选了，semaphore不能改值， 想到可以可以
用 conditional_variable, 把“到了500个”作为一个event, 很快时间到了，也没能
给出答案。后来想想， 好像是可以的。
哪位大牛看看怎么实现比较好？ |
f*******t
发帖数: 7549 | 2 其实就是要实现一个能动态改大小的thread pool |
p***o
发帖数: 1252 | 3 这种问题在mutex/semaphore/conditional variable这一层解决不知道多少坑，
要用高一层的语义:
1 先实现一个multiple producer multiple consumer的queue。
2 实现一个scheduler线程管理允许数目和worker数目。worker数目不够就开新的，
worker数目多了的话往queue里插退出指令。
3 实现worker，从queue里取任务，如果是退出指令就退出。
搞定了再讨论讨论work stealing这类优化。
现。
【在 g******d 的大作中提到】
: 面试题是这样的，c++
: 有很多同时进行的 request 或者action, 都会call同一个function,
: 需要你在这个function中控制同时执行的request/action的数目。
: 这个数目可变，
: 譬如， 刚开始， 允许的数目是 1， 也就是每次只有一个可以执行，相当于mutex. 假
: 如有500 个request, 那就是一个完了在下一个
: 过一段时间， 用户把允许的数目改为500， 也就是同时可以500个一起（当然也是
: protected), 相当于semaphore, 假如有500个，可以不等待一起执行， 假如是1000个
: ，第一批500个同时进行，后面的就得等 someone to sem_post.
: 一开始思路就是这样，讨论了一会。 但问题是， 这个数目可以动态变化， 怎么实现。
|
g******d
发帖数: 1774 | 4
【在 p***o 的大作中提到】
: 这种问题在mutex/semaphore/conditional variable这一层解决不知道多少坑，
: 要用高一层的语义:
: 1 先实现一个multiple producer multiple consumer的queue。
: 2 实现一个scheduler线程管理允许数目和worker数目。worker数目不够就开新的，
: worker数目多了的话往queue里插退出指令。
: 3 实现worker，从queue里取任务，如果是退出指令就退出。
: 搞定了再讨论讨论work stealing这类优化。
:
: 现。
|
g******d
发帖数: 1774 | 5 很有见地。 当时觉得是个很常见的pattern，讨论时发现在这一层还不好办。
面试官提了一种情况，所有request 是从一个queue 出来， 然后系统会为每个request
call HandleRequest
e.g.
HandleRequest (Request request)
{
}
其中有好几个stage, 只有在用其中一个function 的stage 才需要 concurrency
control，才想着看在内部怎么搞
【在 p***o 的大作中提到】
: 这种问题在mutex/semaphore/conditional variable这一层解决不知道多少坑，
: 要用高一层的语义:
: 1 先实现一个multiple producer multiple consumer的queue。
: 2 实现一个scheduler线程管理允许数目和worker数目。worker数目不够就开新的，
: worker数目多了的话往queue里插退出指令。
: 3 实现worker，从queue里取任务，如果是退出指令就退出。
: 搞定了再讨论讨论work stealing这类优化。
:
: 现。
|
g****t
发帖数: 31659 | 6 Assuming you can use Redis, would it be a straightforward project ?
I did not familiar with cpp. python and redis queue often worked
well.
: 很有见地。 当时觉得是个很常见的pattern，讨论时发现在这一层还不好
办。
: 面试官提了一种情况，所有request 是从一个queue 出来， 然后系统会
为每个
request
: call HandleRequest
: e.g.
: HandleRequest (Request request)
: {
:
: }
: 其中有好几个stage, 只有在用其中一个function 的stage 才需要
concurrency
: control，才想着看在内部怎么搞
【在 g******d 的大作中提到】
: 很有见地。 当时觉得是个很常见的pattern，讨论时发现在这一层还不好办。
: 面试官提了一种情况，所有request 是从一个queue 出来， 然后系统会为每个request
: call HandleRequest
: e.g.
: HandleRequest (Request request)
: {
:
: }
: 其中有好几个stage, 只有在用其中一个function 的stage 才需要 concurrency
: control，才想着看在内部怎么搞
|
g******d
发帖数: 1774 | 7 可以具体阐述一下？ 这个redis queue 怎么用可以实现？ 是指在共用的这个function
里用个redis？还是在外面 把现有的queue换成redis queue， 然后queue 可以动态设
多少可以同时process？ 这样的话 很多不需要同步protection也要protected 的啦？
【在 g****t 的大作中提到】
: Assuming you can use Redis, would it be a straightforward project ?
: I did not familiar with cpp. python and redis queue often worked
: well.
:
:
: 很有见地。 当时觉得是个很常见的pattern，讨论时发现在这一层还不好
: 办。
:
: 面试官提了一种情况，所有request 是从一个queue 出来， 然后系统会
: 为每个
: request
:
: call HandleRequest
|
g****t
发帖数: 31659 | 8 https://python-rq.org/
It looked to me it would be quite easy to implement pptwo’s step one
by
using above software.
Redis handled the concurrency of read/write key/value very well. U can use
it as a global concurrency control server .
: 可以具体阐述一下？ 这个redis queue 怎么用可以实现？ 是指在共用的
这个
function
: 里用个redis？还是在外面 把现有的queue换成redis queue， 然后queue
可以
动态设
: 多少可以同时process？ 这样的话 很多不需要同步protection也要
protected
的啦？
【在 g******d 的大作中提到】
: 可以具体阐述一下？ 这个redis queue 怎么用可以实现？ 是指在共用的这个function
: 里用个redis？还是在外面 把现有的queue换成redis queue， 然后queue 可以动态设
: 多少可以同时process？ 这样的话 很多不需要同步protection也要protected 的啦？
|
n******t
发帖数: 4406 | 9 暈，清清楚楚一道題，就變成了一堆東西瞎堆。。。
不過也好，大家都有活幹，不過我認爲還是會幹的人幹，別人給錢不上班最好 。
function
【在 g******d 的大作中提到】
: 可以具体阐述一下？ 这个redis queue 怎么用可以实现？ 是指在共用的这个function
: 里用个redis？还是在外面 把现有的queue换成redis queue， 然后queue 可以动态设
: 多少可以同时process？ 这样的话 很多不需要同步protection也要protected 的啦？
|
g****t
发帖数: 31659 | 10 What is your solution ?
In real life, I did not suggest doing such type of thing by yourself. Why
not try to find a library first.
: 暈，清清楚楚一道題，就變成了一堆東西瞎堆。。。
: 不過也好，大家都有活幹，不過我認爲還是會幹的人幹，別人給錢不上班
最好 。
: function
【在 n******t 的大作中提到】
: 暈，清清楚楚一道題，就變成了一堆東西瞎堆。。。
: 不過也好，大家都有活幹，不過我認爲還是會幹的人幹，別人給錢不上班最好 。
:
: function
|
|
|
g******d
发帖数: 1774 | 11 能否共享一下你的solution？这个题本身是很明确的，题意就是在那个特地的function
里做concurrency control， 其他同学的建议在外层也是个思路。
【在 n******t 的大作中提到】
: 暈，清清楚楚一道題，就變成了一堆東西瞎堆。。。
: 不過也好，大家都有活幹，不過我認爲還是會幹的人幹，別人給錢不上班最好 。
:
: function
|
n******t
发帖数: 4406 | 12 直接做就好，這些function都share一個變量，用鎖保護，函數開始先加鎖檢查這個變
量是不是500，不是的話，加1放鎖，否則調pthread_cond_wait.
函數結束的時候，加鎖，-1，調 pthread_cond_signal,然後放鎖。
問題是，爲啥並行度檢測要放到某個函數裏面去，一般來說應該統一調配，除非有特殊
的理由。
function
【在 g******d 的大作中提到】
: 能否共享一下你的solution？这个题本身是很明确的，题意就是在那个特地的function
: 里做concurrency control， 其他同学的建议在外层也是个思路。
|
c*******v
发帖数: 2599 | 13 It looked to me that the requests are not as simple as you thought.
He was asked to control the threads of request/action with some complicate
control logic.Thus,the control logic need to be saved in a separate module (
a function).
Since the control logic is quite complicate, in real life project, I would
suggest using Redis lock/queue/etc.
=============================The control logic:=====
譬如， 刚开始， 允许的数目是 1， 也就是每次只有一个可以执行，相当于mutex. 假
如有500 个request, 那就是一个完了在下一个
过一段时间， 用户把允许的数目改为500， 也就是同时可以500个一起（当然也是
protected), 相当于semaphore, 假如有500个，可以不等待一起执行， 假如是1000个
，第一批500个同时进行，后面的就得等 someone to sem_post.
【在 n******t 的大作中提到】
: 直接做就好，這些function都share一個變量，用鎖保護，函數開始先加鎖檢查這個變
: 量是不是500，不是的話，加1放鎖，否則調pthread_cond_wait.
: 函數結束的時候，加鎖，-1，調 pthread_cond_signal,然後放鎖。
: 問題是，爲啥並行度檢測要放到某個函數裏面去，一般來說應該統一調配，除非有特殊
: 的理由。
:
: function
|
n******t
发帖数: 4406 | 14 The idea is the same if you want the maximum cucurrency to be tunable, and
can just left as an excercise if you understand how original code works.
The key observation is that threads have to wait on conditions to be
satisfied, whether it is one condition or two conditions, is not essential.
(
個變
特殊
【在 c*******v 的大作中提到】
: It looked to me that the requests are not as simple as you thought.
: He was asked to control the threads of request/action with some complicate
: control logic.Thus,the control logic need to be saved in a separate module (
: a function).
: Since the control logic is quite complicate, in real life project, I would
: suggest using Redis lock/queue/etc.
: =============================The control logic:=====
: 譬如， 刚开始， 允许的数目是 1， 也就是每次只有一个可以执行，相当于mutex. 假
: 如有500 个request, 那就是一个完了在下一个
: 过一段时间， 用户把允许的数目改为500， 也就是同时可以500个一起（当然也是
|
g****t
发帖数: 31659 | 15 There could be some corner cases because the interviewee
did not tell people how the MaxConcurrency is changed.
But I agreed that the most fundamental case will be a thread pool that the
size could be changed based on some conditions.
However, sometimes it was not easy to let “這些function都share一個變量
”.
If performance did matter, I would set a key in Redis instead of using a
shared variable. Also, Redis can be used in multi-platforms and can be
accessed by other languages.
To me, by using Redis as a global resource, we may have cleaner and more
robust solution (though slower).
: The idea is the same if you want the maximum cucurrency to be
tunable,
and
: can just left as an excercise if you understand how original
code
works.
: The key observation is that threads have to wait on conditions
to be
: satisfied, whether it is one condition or two conditions, is not
essential.
: (
: 個變
: 特殊
【在 n******t 的大作中提到】
: The idea is the same if you want the maximum cucurrency to be tunable, and
: can just left as an excercise if you understand how original code works.
: The key observation is that threads have to wait on conditions to be
: satisfied, whether it is one condition or two conditions, is not essential.
:
: (
: 個變
: 特殊
|
w*******d
发帖数: 59 | 16 这和read write lock的设计有什么区别？multiple read不就允许动态控制多少个
thread可以读？
现。
【在 g******d 的大作中提到】
: 面试题是这样的，c++
: 有很多同时进行的 request 或者action, 都会call同一个function,
: 需要你在这个function中控制同时执行的request/action的数目。
: 这个数目可变，
: 譬如， 刚开始， 允许的数目是 1， 也就是每次只有一个可以执行，相当于mutex. 假
: 如有500 个request, 那就是一个完了在下一个
: 过一段时间， 用户把允许的数目改为500， 也就是同时可以500个一起（当然也是
: protected), 相当于semaphore, 假如有500个，可以不等待一起执行， 假如是1000个
: ，第一批500个同时进行，后面的就得等 someone to sem_post.
: 一开始思路就是这样，讨论了一会。 但问题是， 这个数目可以动态变化， 怎么实现。
|
w********m
发帖数: 1137 | 17 就是设计一个semaphore
talk is cheap，show the code
白板上写点代码就完了 |
d********b
发帖数: 1 | 18 这个应该用event loop吧， 就两个process，第一个接受request, 让后把它放进queue
里， 第二个读queue，可以一次读一个，或者500个，取决你的参数，然后执行
callback function
唯一的lock是在queue上，用mutex即可。但更好的是用lock free |
n******t
发帖数: 4406 | 19 If you want to make this one a typical scenario in big companies, it is your
choice. But all i know this is a very straightforward application of thread
programming, but you want to use the heaviest IPC (socket) and plus some
middleware to accomplish it.
BTW, how do you know redis does not have "corner cases", you read all its
source code?
【在 g****t 的大作中提到】
: There could be some corner cases because the interviewee
: did not tell people how the MaxConcurrency is changed.
: But I agreed that the most fundamental case will be a thread pool that the
: size could be changed based on some conditions.
: However, sometimes it was not easy to let “這些function都share一個變量
: ”.
: If performance did matter, I would set a key in Redis instead of using a
: shared variable. Also, Redis can be used in multi-platforms and can be
: accessed by other languages.
: To me, by using Redis as a global resource, we may have cleaner and more
|
g****t
发帖数: 31659 | 20 I read part of the Redis source code. However, that was not the
reason that I would like to consider to use well maintained library in this
use case. I preferred to use existing library because I thought the use
case
was NOT straightforward and the development risk could be very high.
(I did not consider the maintain cost yet). For example, those requests
could
come from different processes in different machines.
With that said, i was totally OK with that you believed that the task was
just a straightforward application of pthread,signal, etc.
Quite often, many different engineering paths/styles could all lead good
solutions.
: If you want to make this one a typical scenario in big companies, it
is your
: choice. But all i know this is a very straightforward application of
thread
: programming, but you want to use the heaviest IPC (socket) and plus
some
: middleware to accomplish it.
: BTW, how do you know redis does not have "corner cases", you read all
its
: source code?
【在 n******t 的大作中提到】
: If you want to make this one a typical scenario in big companies, it is your
: choice. But all i know this is a very straightforward application of thread
: programming, but you want to use the heaviest IPC (socket) and plus some
: middleware to accomplish it.
: BTW, how do you know redis does not have "corner cases", you read all its
: source code?
|
|
|
b***i
发帖数: 3043 | 21 增加后，很容易理解。原来阻塞的可以继续。减少呢？不能立刻少吧？得等原来的一些
结束了，才能保持新的限制。
但是感觉和原来的semaphore没有大的区别啊？
public:
Semaphore(unsigned long init) :count_(init) {}
void notify() {
std::lock_guard lock(mutex_);
++count_;
condition_.notify_one();
}
void wait() {
std::unique_lock lock(mutex_);
while (!count_) // Handle spurious wake-ups.
condition_.wait(lock);
--count_;
}
每个线程要wait, work, notify
增加300，就直接多notify300次
减少200，就在每个线程那个结束的时候判断是否还需要继续减少，如果减少就不
notify，直到需要减少的达到需要
这样不行吗？
现。
【在 g******d 的大作中提到】
: 面试题是这样的，c++
: 有很多同时进行的 request 或者action, 都会call同一个function,
: 需要你在这个function中控制同时执行的request/action的数目。
: 这个数目可变，
: 譬如， 刚开始， 允许的数目是 1， 也就是每次只有一个可以执行，相当于mutex. 假
: 如有500 个request, 那就是一个完了在下一个
: 过一段时间， 用户把允许的数目改为500， 也就是同时可以500个一起（当然也是
: protected), 相当于semaphore, 假如有500个，可以不等待一起执行， 假如是1000个
: ，第一批500个同时进行，后面的就得等 someone to sem_post.
: 一开始思路就是这样，讨论了一会。 但问题是， 这个数目可以动态变化， 怎么实现。
|
g****t
发帖数: 31659 | 22 Btw, I appreciated your comments and opinions.
: I read part of the Redis source code. However, that was not the
: reason that I would like to consider to use well maintained
library in
this
: use case. I preferred to use existing library because I thought
the
use
: case
: was NOT straightforward and the development risk could be very
high.
: (I did not consider the maintain cost yet). For example, those
requests
: could
: come from different processes in different machines.
: With that said, i was totally OK with that you believed that the
task
was
: just a straightforward application of pthread,signal, etc.
【在 g****t 的大作中提到】
: I read part of the Redis source code. However, that was not the
: reason that I would like to consider to use well maintained library in this
: use case. I preferred to use existing library because I thought the use
: case
: was NOT straightforward and the development risk could be very high.
: (I did not consider the maintain cost yet). For example, those requests
: could
: come from different processes in different machines.
: With that said, i was totally OK with that you believed that the task was
: just a straightforward application of pthread,signal, etc.
|
g******d
发帖数: 1774 | 23 不一样啊，read-write lock control many read threads, but doesn't control how
many of reader threads can be there. let alone dynamically change the
number
【在 w*******d 的大作中提到】
: 这和read write lock的设计有什么区别？multiple read不就允许动态控制多少个
: thread可以读？
:
: 现。
|
l***p
发帖数: 358 | 24 const int capacity = 500;
int queueLen = 0;
Lock lock;
ConditionVariable cv(lock);
void execute(Task & task)
{
{
Mutex mutex(lock);
++queueLen;
while (queueLen >= capacity) {
cv.wait();
}
}
task.run();
{
Mutex mutex(lock);
--queueLen;
cv.signal();
}
}
Did I miss anything? |
n******t
发帖数: 4406 | 25 The problem here is, as long as you and I are not taking responsibility of
how this should be done, talking about risk is just something in the air and
can not be serious. Also remember that big components for a small feature
almost always involves larger risk in practice.
Better stick to the technical issues.
this
【在 g****t 的大作中提到】
: I read part of the Redis source code. However, that was not the
: reason that I would like to consider to use well maintained library in this
: use case. I preferred to use existing library because I thought the use
: case
: was NOT straightforward and the development risk could be very high.
: (I did not consider the maintain cost yet). For example, those requests
: could
: come from different processes in different machines.
: With that said, i was totally OK with that you believed that the task was
: just a straightforward application of pthread,signal, etc.
|
c*******v
发帖数: 2599 | 26 Agreed.
I was in charge of overseeing products for a while and sometimes could not
switch back to pure technique perspective.
and
【在 n******t 的大作中提到】
: The problem here is, as long as you and I are not taking responsibility of
: how this should be done, talking about risk is just something in the air and
: can not be serious. Also remember that big components for a small feature
: almost always involves larger risk in practice.
: Better stick to the technical issues.
:
: this
|
g******d
发帖数: 1774 | 27 ok, suppose you have initially 1000 actions, which calls this execute
function, with 500 as initial capacity,
all goes well,
and at some point, the capacity is reduced to 1, what to accomplish that?
【在 l***p 的大作中提到】
: const int capacity = 500;
: int queueLen = 0;
: Lock lock;
: ConditionVariable cv(lock);
: void execute(Task & task)
: {
: {
: Mutex mutex(lock);
: ++queueLen;
: while (queueLen >= capacity) {
|
l***p
发帖数: 358 | 28 change the capacity to 1
【在 g******d 的大作中提到】
: ok, suppose you have initially 1000 actions, which calls this execute
: function, with 500 as initial capacity,
: all goes well,
: and at some point, the capacity is reduced to 1, what to accomplish that?
|
n******t
发帖数: 4406 | 29 He wants the concurent execution to be capped, not the waiting executions to
be capped. In your case, every thread wanting to run this function will
increment towards the cap.
【在 l***p 的大作中提到】
: const int capacity = 500;
: int queueLen = 0;
: Lock lock;
: ConditionVariable cv(lock);
: void execute(Task & task)
: {
: {
: Mutex mutex(lock);
: ++queueLen;
: while (queueLen >= capacity) {
|
l***p
发帖数: 358 | 30 The capacity exactly defines the number of maximum cocurrent excuetions,
which could be dynamically set, etiher 5 or 500.
On the other hand, the pipeline might grow over the capacity, but the
current executions will never exceed that capacity.
But there is a race condition. For example, 500 excuetions in progress, you
now set it to 1, you can't take the 499 out until they are done on their
owns. Should we do it? It depends. |
