[MOS] deadlock detection

MOS: Modern Operating Systems

deadlock detection with one resource of each type

如果每种资源都是独一份的,可以用上面这样的图来分析资源竞争情况。
图中方块代表资源,圆形代表进程;指向进程的箭头表示资源被该进程拥有,而从进程出发的箭头表示其需要的资源。
有向图中只要存在一个闭环,就存在一个死锁

找出闭环的方法有很多种,这里给出一个比较直观的方法:
0)首先把图中所有箭头记为unmarked,初始化一个空链表L,并选中一个节点(无论是进程还是资源,这里只考虑抽象出的有向图)为当前节点
1)判断该节有没有出现在L中,如果没有则加入L尾部进入下一步;如果有则说明存在一个闭环,即发现死锁
2)当前节点如果有向外的unmarked箭头就顺着它找到下一个节点,同时将该箭头标记为marked,跳到1);如果没有unmarked箭头进入下一步
3)没有unmarked的箭头表明已经进入死胡同,删掉当前节点,回溯到源节点,将其设置为当前节点,跳到2)

deadlock detection with multiple resources of each type

当一种资源有多个可用实体时,我们使用一种基于矩阵的算法
向量E表示m种资源目前被占用的情况,A表示m种资源剩余量
矩阵C表示n个进程目前分别占用各种资源的情况,每行代表一个进程,每列是一种资源对应的各个进程占用情况,m列求和就等于Em
矩阵R表示n个进程目前对各种资源的需求量,行列意义同上
定义向量X<=Y当且仅当X的每个分量都<=Y的对应分量
算法步骤:
0)所有进程标记为unmarked
1)找到一个unmarked进程i,其占用的资源Ri<=A,下一步;没有满足该条件的进程,跳到3)
2)A=A+Ci,进程i标记为marked,跳到1)
3)如果所有进程都是marked,表示都得到了执行,没有死锁;否则,剩余的所有unmarked进程构成了死锁

虚拟机对x2apic destination mode的选择

首先简单介绍下apic的destination mode:

physical mode下高32bit(destination field)是apic id
logical mode下高32bit是MDA,又分为flat和cluster两种:
flat就是一个bitmap
而cluster包含两个部分,高16bit为cluster ID,后16bit为bitmap;这里还分flat和hierarchy;这里就不深究了。

根据intel spec:Flat logicalmode is not supported in the x2APIC mode. Hence the Destination Format Register(DFR) is eliminated in x2APIC mode. 在x2apic已经没有FDR,所以在logical mode下不再支持flat mode了,只有cluster mode由于x2apic在原来apic的8bit apicid基础上扩展到32bit

所以通过ioapic发中断和发MSI(不是MSIX)中断的设备就有问题了;他们需要做IR,interrupt remapping(VT-d提供的一项能力,通过IOMMU来做)
但是,也有些例外,比如使用physical mode且cpu个数小于256时,8bit的apic id已经完全可以cover所有的cpu了,而且这8bit直接可以写入x2apic的32bit的destination field,所以这种情况下可以直接使用x2apic physical mode而无需IR能力

https://patchwork.kernel.org/patch/2826342/这个邮件内容告诉我们,使用x2apic而同时又没有IR能力的情况,只有虚拟化场景(bios不能enable VT-d这种情况好像要被禁止了,enable x2apic一定要开VT-d)

然而,虚拟化场景下为何一定要enable x2apic呢?
IBM给出了答案Red Hat Enterprise Linux 6 implements x2APIC emulation for KVM guests. Advanced programmable interrupt controllers (APICs) are used in symmetric multiprocessor (SMP) computer systems. x2APIC is a machine state register (MSR) interface to a local APIC with performance and scalability enhancements. IBM lab tests show that enabling the x2APIC support for Red Hat Enterprise Linux 6 guests can result in 2% to 5% throughput improvement for many I/O workloads. You can enable the x2APIC support by specifying the -cpu qemu64,+x2apic option on the qemu-kvm command for a KVM guest.

然而这解释当然是隔靴搔痒,真正的解释还是要show me the patch:

 

topcoder: Xscoregame

这一题用递归很简单,直接深度优先搜索所有排序,取最大值即可,但是完全没有DP的思想而且求解时间不可接受;但是如果要DP,如何减少状态数?要知道本题的输入数列排序是影响最终结果的。

下面的解法是DP的,这个DP的妙处在于仍然用输入数列A的子数列组合As作为状态,但是这个状态下面仍然分一些子状态,不过不是用这个子数组的所有排序作为子状态而是用一种hash的方式,即将该子数组的可能结果(子数组每一种排序按题目算法所求得的状态值R=x+x^As[i])对64(2的6次方)求余所得作为子状态的index。

为什么可以这么做?因为题目中数组A最大的数为50(6bit,可覆盖),所以在一个状态转移到下一状态时,即某个子数组新加入一个元素的时候,其实只需要考虑状态值R的低6位不同的情况即可,因为只有低6位有后效性,只有低6位相同的所有排序只需取最大状态值(这里不用求具体排序,主要求最大值),其他都不用考虑了,而不同的低6位值可能带来不同的有效子状态。说白了,就是当前低6位不一样的,现在不能判定以后谁优谁劣,而当前低6位相同的,已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支,于是求解效率就呈几何级数地提高了。

 

topcoder: YetAnotherORProblem2

这题显示只有18%的AC率,题目本身不难,估计都是败在执行时间上了;我的解法如下,典型的DP思维,子问题是:如果已知长度为n-1的情况下,和或操作相等的数列,求长度为n的情况;状态index为每个满足条件的数列的和Sn-1(因为和或相等,也是该数列的或),状态值为该index对应的数列有多少种。状态转移方程为:

if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]

 

topcoder: YetAnotherTwoTeamsProblem

这是一道标记为hard的题,确实比较hard

开始用了一个比较简单暴力的方法,其实也是DP思路,但是状态取的比较偷懒,直接用了所有的可能组合作为状态,虽然在求解过程中可以利用到已经搜索过的状态,但是整个搜索空间还是太大了,导致虽然结果正确,但是严重超时了:

又做了一次伸手党,看了解答后醒悟了,其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。 点我展开分析内容

topcoder: ZigZag

再来水一道简单题:题目地址

想法很自然,记录下当前的方向,一旦出现方向不一致的就把总数加一,同时方向改变,否则continue,然而其实已经包含了动态规划思想

上代码:

看了下别人提交的,思路一样,只不过有人上来先把整个序列的变化趋势算一遍,即遍历seq,然后算出seq[i]-seq[i-1]的值记录下来记为V[i],其实要的就是一个正负号,然后再次遍历还是记录当前的方向,乘以当前遍历到的那个趋势V[i],乘积发生变化时就在结果上加一并改变当前方向值。

topcoder practice: ZooExchangeProgram

为了兴趣,也为了保持coding的能力,重新开始写一些算法题;为了对算法了解的更透彻,也为了锻炼表达能力,干脆在博客里面对解题代码进行详解,代码是自己写的,但也不排除参考了别人的解法,消化吸收了就是自己的,不是吗?

题面:

太长了,就不贴了,链接在此

代码及详解:

Mac新手键盘映射探索

作为Linux老司机都是重度终端依赖症患者,unix终端对ctrl键的摧残各位老司机都懂的;换了Mac后发现键盘极其反人类,右边control没有,左边control那么小而且位置感人,ctrl+r这种分分钟用的着的快捷键在Mac上换了各种姿势都不爽,这是要把左手按残的节奏阿,左手可是很重要的,咳,我说的是敲代码。

谷歌了一把键盘映射,发现一个叫keyremap4macbook的应用,几个论坛里面都强烈推荐,现在的版本叫做karabiner;先安装了前者,居然还要我重启,为了左手的解放勉为其难的重启了下,结果还是徒劳,完全没有任何反应,估计是版本的问题。这种ugly的非App Store应用折腾了我半天还无效,干脆就放弃了。

接着再求助搜索引擎,找到了这个,虽然是短短一行,但是却提醒了我,看来还是需要再探索一下Mac系统自身设置。人肉探索了一段时间后,发现了一个可以利用的点,如图所示,虽然注释文字描述的比较抽象,但是下面的菜单列表对正常智商的人来说一目了然了,显然是个映射关系,那么我们将那个“大户”command键合control键对调一下是否合理呢,我目前看来是合理的,作为程序员最需要效率的就是在terminal中挥散汗水的时间,而其他的操作对快捷键要求不高,那么我们需要的正是让control键无处不在,触手可及!

PTRACE的权限检查,自由是有前提的~

系统调用PTRACE的一切开始于这里:
COMPAT_SYSCALL_DEFINE4(ptrace, compat_long_t, request, compat_long_t, pid,
               compat_long_t, addr, compat_long_t, data)

首先提供了attach的绿色通道:
if (request == PTRACE_ATTACH || request == PTRACE_SEIZE) {
        ret = ptrace_attach(child, request, addr, data);
attach做的事情就是把当前进程变成了被trace进程的父进程,同时把被trace进程加入到当前进程的ptraced链表中;
__ptrace_link(task, current);
list_add(&child->ptrace_entry, &new_parent->ptraced);
    child->parent = new_parent;
但是这样做是有前提的,具体请看后面的分析,这里先按下不表。

attach?wtf?为啥要在用之前attach,搞得这么神秘,难道直接用不可以吗?
不可以,因为你不能直接访问其他进程的地址空间,否则地址空间的隔离不就变成笑话了。
所以这个ptrace系统调用入口做了个很重要的check:
ret = ptrace_check_attach(child, request == PTRACE_KILL ||
                  request == PTRACE_INTERRUPT);
    if (!ret) { //只有返回为0,即判断条件成立,才继续执行对ptrace的request
        ret = compat_arch_ptrace(child, request, addr, data);
        if (ret || request != PTRACE_DETACH)
            ptrace_unfreeze_traced(child);
    }
child->ptrace && child->parent == current
只有过了这一关,才能进行后面的操作(除了kil和interrupt,他们自己的处理逻辑里面有此类的判断或者无需),那难道随便就可以attach,那我就麻烦一点先attach呗;显然不会这么傻,前面卖了个关子,这里来看看attach里面做的权限检查,必须是有权的人才能随便搞的,屁民是要守法的!!

权限管理的水比较深,博主还没吃透,所以这里先简单列一下我能看懂的部分:
etval = __ptrace_may_access(task, PTRACE_MODE_ATTACH);
这里有两个条件,1)我自己人改自己人ok(这里的suid euid等等的请看后面链接);2)我的上层命名空间ok(我理解是,比如像root用户这种大boss)
    tcred = __task_cred(task);
    if (uid_eq(cred->uid, tcred->euid) &&
        uid_eq(cred->uid, tcred->suid) &&
        uid_eq(cred->uid, tcred->uid)  &&
        gid_eq(cred->gid, tcred->egid) &&
        gid_eq(cred->gid, tcred->sgid) &&
        gid_eq(cred->gid, tcred->gid))
        goto ok;
    if (ptrace_has_cap(tcred->user_ns, mode))
        goto ok;
另外还要做命名空间能力的检测,看看目标进程的命名空间有没有被ptrace的能力:
ns_capable(__task_cred(task)->user_ns, CAP_SYS_PTRACE)

参考链接