GSoC2013 accept!

一大早收到两封来自google的邮件,终于不是thank you开头,读研这段日子收了好多公司的感谢信(微软、大摩、EMC、新思。。。集满七封是不是可以换一个offer?)google的这句Congratulations确实够振奋我心 🙂

Congratulations! Your proposal "[HURD] Improve the GDB Port for GNU Hurd" submitted to "GNU Project" has been accepted for Google Summer of Code 2013. Over the next few days, we will add you to the private Google Summer of Code Student Discussion List.
Now that you've been accepted, please take the opportunity to speak with your mentors about plans for the Community Bonding Period: what documentation should you be reading, what version control system will you need to set up, etc., before start of coding begins on 17 June.
Welcome to Google Summer of Code 2013! We look forward to having you with us.
With best regards,
The Google Summer of Code Program Administration Team
少年继续努力!为开源世界贡献一份力!

[逻辑题]放下那个坏球!

题目很简单,一共有12个小球,其中有一个的质量和其他不一样,问,如何用一架天平只称3次就找到那个坏球?

分析:12个球,3次,直觉就是4个球为一组,分3组。任意拿8个球出来称一次。有两种结果,平衡,不平衡。

情况一:天平平衡,说明选中的8个球都是好球,那么坏球一定在未选中的4个里。目标缩小到四个,接下来就好办了,从4个中任选两个,然后再拿两个好球出来称一次,若平衡,则坏球在未选中的两个中,不平衡则在选中的两个中;目标缩小到两个,取一个与好球称一次,结果立现,刚好称了三次。

情况二:天平不平衡,说明未选中的4个皆为好球,目标缩小为8,此种情况略复杂。对8个目标球进行编号1-8,并记天平左边盘子为A,右边盘子为B。则第一次称可以表示为A=(1,2,3,4),B=(5,6,7,8)。 假设A<B(因为不平衡,总有一边盘子重,用此记号方便描述,无他)。

第一个关键点来了我承认我是通过枚举的方式得到的),第二次称重方式为,A=(1,5,6),B=(2,7,0)。0表示好球,因为第一次称已经确定了4个好球。

此回合的结果有三。

A=B:说明坏球在3,4,8中。目标缩小到3个,但是现在只剩一次称的机会,需要确定三个球,貌似是不可能。但是,因为第一次称有额外的信息,即第一次称的结果A<B,说明要么是3,4球中有一个是轻的,要么是8号球重了。那么只需要把3,4球分别放在天平的两端,平衡则8好球是坏球,并且坏球是重的;不平衡则,轻的那端是坏球,并且坏球是轻的。

A<B:说明坏球在1,7中。目标缩小到2个,直接拿个好球来称一次就出结果。

A>B:说明坏球在2,5,6中。目标缩小到3个,类似上面的分析,额外信息是要么5,6中有一个是坏球,并且是重了;要么是2号球轻了。然后称一次5,6即可出结果。

这道题的关键之处在于,要充分利用前一次的信息来完成推理。

++++++++++++++++++++++++分割线++++++++++++++++++++++++++++++

到这里还没有结束,此题有个变种,13个球最少称几次能找到其中的坏球?

答案还是3!

思路如下:任选8个球称一次,若不平衡,目标缩小到8个,然后用上面的思路即可。

若平衡,则目标缩小为未选中的5个球。其实分析发现两次是可以确定5个球的,再次上编号,1,2,3,4,5。

然后 A=(1,2) B=(3,0),若平衡,说明4,5是坏球,目标为2,结果立现。

若不平衡,A<B,说明要么1,2有一个轻球,要么3是重球。称一次1,2即可。

若A>B,说明要么1,2有一个是重球,要么3是轻球,称一次1,2即可。

内核抢占和中断

以前一直不理解什么是内核抢占,现在好像懂了。

本文尝试解释什么是内核可抢占以及可抢占和可中断的区别。

首先被中断不是被抢占,中断和抢占是两个概念。抢占必须涉及进程上下文的切换,而中断是在中断上下文。

所谓可抢占抢的是进程上下文,人人都争取上台。可中断指的是是否可以中断当前CPU而进入我的中断处理函数。

如果内核是不可抢占的(比如说2.4的内核),一旦切进内核态,只要代码不是主动释放CPU它就可以一直占着CPU。例外,虽不可抢占,但若此时发生中断,代码还是要交出CPU,但是中断返回之后,代码又能霸占CPU了,此为可中断但不可抢占。

如果内核是可抢占的(比如2.6或之后的内核),上述情况就不会发生了。内核抢占发生在以下3种情况:

1. 从中断返回内核态时,若此时可抢占,则会强制调用schedule(),尝试抢占,被中断的内核代码不一定能继续霸着CPU。

2.内核变成可抢占状态,此时也会尝试抢占。

3.内核代码主动调用schedule()。

虽然2.6的内核提供内核抢占,但是也提供关闭的手段。是否可抢占是由preemt_count变量控制(per-cpu),有锁这个计数就+1,释放锁就-1.为0才是可抢占。每当释放锁的时候都会检查是否为0,为0则尝试抢占。

 

+++++++++++++++++++分割线++++++++++++++++++++++++++++++++

关于中断

中断分为上下两个部分。是为中断上半部(top half)、下半部(bottom half)。

上半部处理紧要事情。比如:通知硬件“我知道你请求中断了,继续干活去”,然后从设备缓冲区拷贝数据到内存。

下半部处理不那么要紧的任务。比如:网卡上来的数据推进协议栈,然后推给上层应用程序。

当前的内核有三种下半部的实现方式:softirq、tasklet、working queue。

         名称

上下文

特点

概述
Softirq

中断上下文

可中断不可睡眠 速度最快。同一个Softirq可能会同时运行在多个核上,必须非常小心的处理数据同步
Tasklet

中断上下文

可中断不可睡眠 基于Softirq实现,同一类的Tasklet不会被同时运行,编程代价小
Work queue

进程上下文

可中断可睡眠

基于内核线程实现

 

 

每天记一点,进步看的见。