Chinaunix

标题: 关于抢占的问题 [打印本页]

作者: tomkedy 时间: 2011-06-24 12:40
标题: 关于抢占的问题
本帖最后由 tomkedy 于 2011-06-24 12:41 编辑

具体如下：

假设时钟中断的间隔为 10ms ，进程A的运行时长为 15ms，且获得CPU并在 time 0 的时候开始运行。当时间到达 6ms 时，拥有更高优先级的进程B到达就绪态，这时：

==========================================================

------
方案1：
------
进程A马上停止运行并切换至进程B，具体为，假设上下文切换需 1ms ，则进程B会在第 7ms 的时候开始运行。

------
方案2：
------
进程B将只是放在就绪队列的列首，当下一次时钟中断到来时（如：10ms），则调度进程B运行。

==========================================================

按照某资料所说，方案1为“可抢占“的例子，方案2为“非可抢占“的例子。我就有些疑惑，在印象中，是否可抢占跟时钟中断是分不开的。如果没有时钟中断的存在，如何中断当前进程而切换到另一个进程呢？如果方案1 可行，那系统又是如何检测到进程B比进程A的优先级高呢（进程B就绪可是发生在进程A占用CPU期间的，假设之前进程B可能进行了DMA等I/O操作）？且系统又是如何中断进程A转而切换至进程B呢？

个人感觉方案2 才是“可抢占“的（实际）例子，不知各位的看法怎样？

作者: tomkedy 时间: 2011-06-24 12:42
回复 1# tomkedy

顶

作者: guocslock 时间: 2011-06-24 17:36
条件有问题吧，时钟中断的间隔是10ms，那么如果进程A在开始运行后的10ms时间内，CPU除了运行A进程之外在这段时间内什么都不会做，因为系统没有更小的时间粒度了。所以条件中的A进程开始执行后的6ms这个时间点，对这个系统来说是不存在的。

作者: guocslock 时间: 2011-06-24 17:40
当然如果在10ms之内有中断的话，那么抢占会发生在中断处理函数退出的时候。

作者: guocslock 时间: 2011-06-24 17:41
回复 4# guocslock
sorry，这个中断是指除了时钟中断之外的中断。

作者: tomkedy 时间: 2011-06-24 20:22
本帖最后由 tomkedy 于 2011-06-24 20:27 编辑

条件有问题吧，时钟中断的间隔是10ms，那么如果进程A在开始运行后的10ms时间内，CPU除了运行A进程之外在这段时间内什么都不会做，因为系统没有更小的时间粒度了。所以条件中的A进程开始执行后的6ms这个时间点，对这个系统来说是不存在的。
guocslock 发表于 2011-06-24 17:40

没记错的话，DMA除了开始连接之外，都不需要CPU的参与，因此进程B如果之前执行的是DMA操作的话，那它有可能在 time 6ms 的时候执行完DMA操作而就绪的........

作者: tempname2 时间: 2011-06-24 23:00
可抢占时OS可以强行切换进程；协作时，除非进程自愿放弃CPU，不然可以一直执行到底。可抢占时，进程切换契机一般是中断返回时，不一定非是时钟中断。至于具体细节，那就依赖于实现了。最简单的实现：所有中断返回时执行同一段代码，代码扫描所有存在的进程描述符，如果找到比当前进程优先级更高的进程，切换之。

作者: tomkedy 时间: 2011-06-29 21:52

可抢占时OS可以强行切换进程；协作时，除非进程自愿放弃CPU，不然可以一直执行到底。可抢占时，进程切换契机一般是中断返回时，不一定非是时钟中断。至于具体细节，那就依赖于实现了。最简单的实现：所有中断返回时执行同一段代码，代码扫描所有存在的进程描述符，如果找到比当前进程优先级更高的进程，切换之。
tempname2 发表于 2011-06-24 23:00

同意你的说法，但有些问题还是不太清晰，如下：

还是用之前的例子，如果按照你的实现方式（上文里提到的“最简单的实现：所有中断返回时执行同一段代码，代码扫描所有存在的进程描述符，如果找到比当前进程优先级更高的进程，切换之“），那到底是进程A中断返回还是进程B中断返回而导致进程切换呢？似乎都不太现实......

另，我查了一下ULK3，但里面也没有详细说明。

附：在ULK3的第七章里“进程的抢占“这一小节里（260页，中文版），原文为“......Linux的进程是抢占式的。如果进程进入TASK_RUNNING状态，内核检查它的动态优先级是否大于当前正在运行进程的优先级。如果是，current的执行中断，并调用调度程序选择另一个进程运行（通常是刚刚变为可运行的进程）。当然，进程在它的时间片到期时也可以被抢占........”。（ULK3里也没有说明内核是“如何检测“到进程的动态优先级比current的大（到底谁占CPU且在检查比较优先级？））.............

作者: 为什么删我贴 时间: 2011-06-30 11:39
提示: 作者被禁止或删除内容自动屏蔽

作者: int-main 时间: 2011-06-30 11:45

关键是如果cpu都不知道B就绪了，那这个“就绪”有什么意义。
换句话说就是什么是就绪，什么时候会就绪
为什么删我贴发表于 2011-06-30 11:39

说的有道理，但好像还有另外意思，能否说明白一下？

作者: 为什么删我贴 时间: 2011-06-30 12:06
提示: 作者被禁止或删除内容自动屏蔽

作者: jack4010 时间: 2011-06-30 13:27
进程A执行6ms后，如果产生中断，系统自动切换到中断模式（硬件跳转），执行中断向量表中指定的函数。这个切换，是用户模式到suv模式的切换，不属于进程调度的切换。
如果是可抢占的，在suv模式下会进行进程调度。如果是非抢占式的，中断处理后返回A继续执行。
抢占代表的是进程切换，模式切换不算在内。

产生中断的原因很多，不仅仅只有时钟。具体可以看linux内核代码

作者: tomkedy 时间: 2011-06-30 13:29
本帖最后由 tomkedy 于 2011-06-30 21:30 编辑

我能想到的一个进程从挂起（阻塞，睡眠等等）变成就绪可能有两种情况：1）A创建了B；2）B等待的资源被释放了。
第一种情况，内核肯定知道B被创建了而且优先级高于A。那么问题其实就不存在了。
第二种情况，由于这个时候cpu一直是被A占用，所以要么是A释放了资源了，要么是硬件释放了资源（中断）。这时问题就变为在释放资源的时候是否要进行一次调度，如果调度就是方案1，如果不调度就是方案2.所以问题也就不存在了
为什么删我贴发表于 2011-06-30 12:06

楼上，谢谢你的回复。我的看法如下：

对于你说的第一种情况，我觉得如果进程A在创建进程B的最后阶段不进行一次调度处理，则内核是不会知道进程B的优先级高于进程A从而实现方案1的（但个人认为创建进程一般是不需要再进行进程调度的）......

对于你的方案二，如果进程A占用的只是一个共享的变量，那释放它也要一次调度？

作者: yulihua49 时间: 2011-06-30 14:59

关键是如果cpu都不知道B就绪了，那这个“就绪”有什么意义。
换句话说就是什么是就绪，什么时候会就绪
为什么删我贴发表于 2011-06-30 11:39

当然是通过事件。时钟是事件，其他中断也是事件。

作者: tomkedy 时间: 2011-06-30 20:31

当然是通过事件。时钟是事件，其他中断也是事件。
yulihua49 发表于 2011-06-30 14:59

楼上，进程是由软件实现的，那是否每个进程就绪都要通过“软中断”通知CPU？

作者: tomkedy 时间: 2011-06-30 21:52
回复 13# tomkedy

........

作者: vupiggy 时间: 2011-07-01 06:56
楼主从睡眠、抢占、中断、用户态、内核态、操作系统设计和实现… 没一个概念是清晰的，一通胡来，难得有空给你补课

作者: ruslin 时间: 2011-07-01 09:25
在c++论坛终于找到了点自信。

我举个通俗的例子了：
进程A：正在执行一个系统调用，死循环，进程run状态并且占用cpu。
进程B：vi程序正在阻塞在read系统调用，进程睡眠状态。优先级高于A
你按一下键盘，产生一中断。通过内核input子系统会唤醒进程B（进程B进入run状态，但是未占用cpu），此时如果内核可抢占的，在中断返回时，内核会调度B进程占用cpu执行（进程A仍然在run状态，但是被放弃了cpu）。
内核抢占的本质就是：正在run状态占用着cpu的并且正在内核态执行的进程被动的放弃了cpu。

作者: vupiggy 时间: 2011-07-01 11:03

在c++论坛终于找到了点自信。
ruslin 发表于 2011-07-01 02:25

真不明白你这自信哪里找来的，连问题都没搞清楚是啥就 blabla， bso。

作者: ruslin 时间: 2011-07-01 16:29
回复 19# vupiggy

如果你是高手你肯定明白几句话就要讲清楚内核抢占给不太了解内核的人来说是非常困难的。
如果你自己也不是很清楚的话。。。

作者: jack4010 时间: 2011-07-02 01:14
回复 18# ruslin
进程基本的是三个状态，run,ready,wait。进入run状态表明占用CPU。可抢占的话A进入ready状态。
具体看内核代码吧，那个很直观

作者: vupiggy 时间: 2011-07-02 01:23

回复 vupiggy

如果你是高手你肯定明白几句话就要讲清楚内核抢占给不太了解内核的人来说是非常困难的 ...
ruslin 发表于 2011-07-01 09:29

哎呦，您知道内核态抢占耶，高手，高手，高高手。

但是... ... 您哪只眼看见他们上面讨论内核态抢占的问题了？您确定您明白楼主在问什么以及上面他们在讨论什么吗？您就继续感觉良好吧您。

作者: vupiggy 时间: 2011-07-02 01:24
顺便说一声，``为什么删我帖''童鞋的回答大抵正确，楼主理解不了就要自己看书啃源码去了，别人帮不了。

作者: ruslin 时间: 2011-07-02 16:18
本帖最后由 ruslin 于 2011-07-02 16:39 编辑

回复 21# jack4010

慎重回答，参考ulk3 第3章
linux进程不区分正在cpu上执行和准备执行状态。都是TASK_RUNNING
正是因为TASK_RUNNING得进程数大于cpu个数，才有抢占这回事

作者: tomkedy 时间: 2011-07-02 16:54

顺便说一声，``为什么删我帖''童鞋的回答大抵正确，楼主理解不了就要自己看书啃源码去了，别人帮不了。
vupiggy 发表于 2011-07-02 01:24

vupiggy，

谢谢你的回复，对于“为什么删我帖“的回答我已作了回复，详细在第13楼，vupiggy兄有空的话也可以点评下，但希望是平心静气的技术探讨，这样也可以使更多有兴趣的人参与到讨论中来..........

作者: vupiggy 时间: 2011-07-03 02:08

对于“为什么删我帖“的回答我已作了回复
tomkedy 发表于 2011-07-02 09:54

还真把那狗屁不通的回复当回事，好一个外恭内倨的小盆友。

知道为啥``为什么删我贴''不再回贴做解释吗？你连基本的概念都不清楚，怎么讨
论得下去？最致命的还不在于此，而在你对于他人的回复压根没有意愿去查证，去
深挖核实其合理性。相反地，你总是直觉地，非常主观地从脑袋里蹦出一些概念和
逻辑来反驳。自说自话非常惹人厌啊。

Read The Fxxking Code！而不是在脑袋里玩弄那些含混不清的概念，还觉得自
己理解得挺透彻。从那个自旋锁的帖子就可以看出来，你根本就不爱读代码理解代码，
叫别人怎么跟你讨论?

这样吧，解释一下为什么说你13楼的回复狗屁不通，省得小盆友不服气。

我觉得如果进程A在创建进程B的最后阶段不进行一次调度处理，则内核是不会知道
进程B的优先级高于进程A从而实现方案1的
tomkedy 发表于 2011-06-30 06:29

你觉得？你觉得进程 A 不通过内核怎么有能力自己创建进程 B？这是不是最基本
的常识？既然创建进程需要通过内核，如果新创建的进程优先级更高，内核怎么会
不知道？事实上，Linux 进程模型的实现是把子进程挂在父进程所在优先级的 run
queue 上，代码调用的层次大概是：do_fork() 先调用 copy_process() 复制一份
进程描述子为子，进行一系列初始化之后，最终会调到 wake_up_new_task()，这
个函数负责把子进程挂到适当的 run queue 上。

（但个人认为创建进程一般是不需要再进行进程调度的）......
tomkedy 发表于 2011-06-30 06:29

你认为？认为个屁。如果您肯屈尊区读一下 Linux 的代码就知道，如果不复制 VM，
内核让子进程先运行，为了避免可能不必要的 Copy On Write。看函数
wake_up_new_task()：

if (!(clone_flags & CLONE_VM)) {
/*
* The VM isn't cloned, so we're in a good position to
* do child-runs-first in anticipation of an exec. This
* usually avoids a lot of COW overhead.
*/
if (unlikely(!current->array))
__activate_task(p, rq);
else {
p->prio = current->prio;
p->normal_prio = current->normal_prio;
list_add_tail(&p->run_list, &current->run_list);
p->array = current->array;
p->array->nr_active++;
inc_nr_running(p, rq);
}
set_need_resched();
}

复制代码

看见那个 list_add_tail() 了吗，子进程被插到父进程前面去鸟。

稍微解释一下set_new_resched(); 进程进入内核(经由中断，系统调用)之后，执行完服
务例程，回到刚才被中断的运行点之前，都要检查一下进程的 TIF_NEED_RESCHED
标志，如果被置就要调用 schedule()，看 arch/x86_64/kernel/entry.S，作为系
统调用的例子，去除不重要的细节，在返回用户空间继续执行之前：

sysret_check:
GET_THREAD_INFO(%rcx)
cli
...
movl threadinfo_flags(%rcx),%edx
...
sysret_careful:
...
bt $TIF_NEED_RESCHED,%edx
call schedule
...

复制代码

有木有调度一次，有木有？骂你不冤吧？

对于你的方案二，如果进程A占用的只是一个共享的变量，那释放它也要一次调度？
tomkedy 发表于 2011-06-30 06:29

释放？你确信你了解``释放''的含义？你以为进程访问完资源以后悄无声息地离开
就叫做释放？如果这事儿真发生鸟，只能说明这部分负责共享资源的同步代码有大
虫子了。释放必然伴随一个唤醒过程，或唤醒一个指定(阻塞在该资源上的)进程，
或唤醒一整个 wait queue。阻塞的进程一般都是通过将进程状态指定为
TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE，然后调 schedule()，在这个函数
里进程被从 run queue 上拎走，如果没有其它代码显式地唤醒它重新把它挂入
run queue，这个进程就不可能再有任何机会运行了。

看 try_to_wake_up() 最后部分代码，这是一次抢占可能发生的场景：

out_running:
trace_sched_wakeup(p, success);
check_preempt_curr(rq, p, wake_flags);
...

复制代码

再看 check_preempt_curr() CFS的实现(sched_fair.c) 最后那一段：

preempt:
resched_task(curr);

复制代码

于是 run queue 的首(curr)进程，回到 entry.S 中的汇编代码部分就会发现
TIF_NEED_RESCHED 被设置于是调用 schedule，呼唤调度器，抢占发生。

要是你对``为什么删你贴''的回复真以为意，继而进入内核源码去求证，你还会有
那些古怪的疑问吗？你压根就不想去看代码，自以为概念清晰，自说自话。

要不是71有一天假，谁有时间搁这废话，你继续玩儿好，以后少陪鸟。

作者: vupiggy 时间: 2011-07-03 02:13
这样的问题都不应该发到这 C/C++ 版，隔壁内核源码版才是这贴应该的去处，而且那里的版主超 nice

作者: tomkedy 时间: 2011-07-03 20:37
本帖最后由 tomkedy 于 2011-07-03 20:44 编辑

vupiggy，

谢谢你的回复，我的看法如下：

你觉得？你觉得进程 A 不通过内核怎么有能力自己创建进程 B？这是不是最基本
的常识？既然创建进程需要通过内核，如果新创建的进程优先级更高，内核怎么会
不知道？事实上，Linux 进程模型的实现是把子进程挂在父进程所在优先级的 run
queue 上，代码调用的层次大概是：do_fork() 先调用 copy_process() 复制一份
进程描述子为子，进行一系列初始化之后，最终会调到 wake_up_new_task()，这
个函数负责把子进程挂到适当的 run queue 上。
vupiggy 发表于 2011-07-03 02:08

fork一个子进程的过程当然要内核参与，内核当然知道有关父进程和子进程的所有“信息”（当然包括A和B的优先级值）。但如果要选择一个进程来运行，则（一般来说）内核会对所有的就绪进程的优先级进程比较，选择优先级最高的先运行，而这项遍历-比较-选择（简写）的过程是由调度函数实现的。因此，我说“我觉得如果进程A在创建进程B的最后阶段不进行一次调度处理，则内核是不会知道进程B的优先级高于进程A从而实现方案1的”。

你认为？认为个屁。如果您肯屈尊区读一下 Linux 的代码就知道，如果不复制 VM，
内核让子进程先运行，为了避免可能不必要的 Copy On Write。看函数
wake_up_new_task()：
vupiggy 发表于 2011-07-03 02:08

这是linux的做法，不代表所有操作系统都会让子进程先运行，因此不见得所有操作系统都要在fork的末尾都要进程调度......

释放？你确信你了解``释放''的含义？你以为进程访问完资源以后悄无声息地离开
就叫做释放？如果这事儿真发生鸟，只能说明这部分负责共享资源的同步代码有大
虫子了。释放必然伴随一个唤醒过程，或唤醒一个指定(阻塞在该资源上的)进程，
或唤醒一整个 wait queue。阻塞的进程一般都是通过将进程状态指定为
TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE，然后调 schedule()，在这个函数
里进程被从 run queue 上拎走，如果没有其它代码显式地唤醒它重新把它挂入
run queue，这个进程就不可能再有任何机会运行了。
vupiggy 发表于 2011-07-03 02:08

对于某些共享资源的管理，如：管程，是需要像你所说的在“释放”之后，需要“唤醒“潜在等待的进程；而对于其他的一些同步管理的方法，如“自旋锁“，就不需要“唤醒”操作。如果进程在临界区里需要执行较长时间，则采用前一种方法较合适，让等待的进程都先阻塞，以节省CPU周期；但如果进程只需要在临界区里执行很短时间（如我的例子，只有一个共享变量），则采用忙等待的方式较合算（相对于各个等待进程的切换开销）。

Read The Fxxking Code！而不是在脑袋里玩弄那些含混不清的概念，还觉得自
己理解得挺透彻。从那个自旋锁的帖子就可以看出来，你根本就不爱读代码理解代码，
叫别人怎么跟你讨论?
vupiggy 发表于 2011-07-03 02:08

我不是不愿意看代码，但操作系统并不只有linux，看问题不应只局限在linux上，虽然linux也是个相当出色的操作系统（个人看法）......

作者: vupiggy 时间: 2011-07-04 02:23
你确信你还清楚你在讨论什么？B如果在等待自旋锁就已经是运行态了，谈何在哪个时间点进入就绪态？

有点哭笑不得，这小伙子前两天连几行自旋锁实现的代码都看不明白，怎么就信心爆棚一本正经地教育起别人自旋锁来了。哎，这业界夸夸其谈，眼高手低，纸上谈兵的可是真不少。假期结束，恕我失陪，happy hacking, oh no, happy talking!

作者: tomkedy 时间: 2011-07-04 06:40

你确信你还清楚你在讨论什么？B如果在等待自旋锁就已经是运行态了，谈何在哪个时间点进入就绪态？

有点哭 ...
vupiggy 发表于 2011-07-04 02:23

vupiggy，

谢谢你的回复。请再重看11楼，13楼，28楼的回复...........

作者: 为什么删我贴 时间: 2011-07-04 12:25
提示: 作者被禁止或删除内容自动屏蔽

作者: tomkedy 时间: 2011-07-05 11:25
本帖最后由 tomkedy 于 2011-07-05 11:32 编辑

你确信你还清楚你在讨论什么？B如果在等待自旋锁就已经是运行态了，谈何在哪个时间点进入就绪态？

有点哭 ...
vupiggy 发表于 2011-07-04 02:23

vupiggy，

其实如果你重看11楼，13楼、28的话，你会发现对于“为什么删我贴”所提的方案2，我是持保留态度的。原因是如果进程只需要在临界区里执行很短时间（如我的例子，只有一个共享变量），则一般采用忙等待的方式较合算（相对于各个等待进程的切换开销）。而如果套到我的例子里，那就是进程B一直都是忙等待，即进程B处于运行态；但我例子里的假设条件是进程B处于就绪态，那显然是不符合题目要求的（我所需要的例子是可以证明题目里方案1或方案2正确的例子）。因此，在13楼里，我说到“对于你的方案二，如果进程A占用的只是一个共享的变量，那释放它也要一次调度？”.......

对于题目中的方案1，如果如资料所说的，则应该是一般情况下就会出现的，也就是一般化的例子都应该可以证明，但我却想不出（因此要发帖请教各位）。另，个人是比较赞同18的例子，这个例子在日常里经常能碰到，但不知为何你会持反对意见.....

作者: kallytin 时间: 2011-07-06 12:19
回复 32# tomkedy

关注

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)