尝试讲清楚编辑距离求解

这篇文章是尝试给像作者一样的算法爱好者(业余的委婉说法)解释一下编辑距离求解方法的思考过程,其实也是为了强迫自己真正的吃透编辑距离求解的方法论,以期能达到举一反三的效果。根据以上受众定位,我首先还是引入一段对编辑距离的解释,然后再从递归到递推(动态规划)讲讲对这个问题求解本身的正向思考过程,而不是拿到一个解法来说明它的正确性。

编辑距离的定义是用增删改三种操作将一个字符串演变为一个目标字符串所需的操作次数。比如将horse转化为ros,可以是如下步骤:
1)删除h变成orse; 2)删除o变成rse; 3)增加o变成rose; 4)删除e变成ros
也可以是如下步骤:
1)改h为r变成rorse; 2)删r变成rose; 3)删e变成ros
显然第二种策略要优于第一种,但是这种演变策略的排列组合随着源串a和目的串b的长度增长会几何级数的增长。我们需要用程序来求解。

这是一个典型的考动态规划的编程题,很多文章都会给出一个递推公式,但是这个递推公式为何正确,得到这个公式的思考过程是啥,为什么这么思考?回答了这几个问题才算理解了编辑距离的精髓,而且才能有举一反三的可能性。看了很多解释的文章,感觉都是从结果来理解和解释递推过程反证过程的有效性,隔靴搔痒,没有讲到这个公式是怎么得来的,怎么一下子就能得出这么精妙的计算方法,感觉就像现在解释机器学习模型的原理那样,训练出来一个有效的神经网络结构,然后再试图解释每一层是在干嘛,然而并不是一开始设计的时候就知道会是这样。但编辑距离这个算法是完全由人想出来的,必然是有设计者的心路历程可循。下面讲下我对这个问题的理解思路。

最容易想到的方法是递归,递归函数以目标字符串和源字符串为输入参数,代码如下:

Continue reading “尝试讲清楚编辑距离求解”

vfio 直通设备的 memory region 初始化

vfio特别用一个数据结构来管理设备的memory region
注意到它还有个域是VFIOMmap结构的指针:
感觉是不是有冗余,那么外层结构里面的mem是不是指向内层中的mem呢?
上面的mem还有个奇怪的注释:slow,难道还有一种快一点的MR?那是不是指这里是IO的MR,另外还有个RAM的mr?

Continue reading “vfio 直通设备的 memory region 初始化”

AI来了。云计算凉了?

笔者身处云计算行业,如今的IT界言必称AI给我带来了巨大的精神压力,无时不在思考AI和云计算的关系,云计算在AI大潮下是不是已经明日黄花了,是不是要转行做AI?所谓人类一思考上帝就发笑,我觉得上帝没这么肤浅,毕竟咱也是上帝的AI产品不是~,有空还是要自我迭代一下,继续自觉优化下肉神经网络参数的

Continue reading “AI来了。云计算凉了?”

IOMMU group and ACS cap

VFIO做VM的设备直通过程中,需要把直通设备所在iommu group里面所有的设备都unbind掉,这是为啥呢,iommu group又是啥,木有遇到该问题的小伙伴你们肯定年轻而富有:)你们的设备都是有ACS的呢,这又是啥,咱先来看看官方文档吧:

Continue reading “IOMMU group and ACS cap”

libvirt 向qemu传文件描述符

libvirt创建的qemu进程里面有一些fd的参数,这些文件是libvirt帮qemu打开的一些设备文件句柄等,比如:
qemu … -netdev tap,fd=24,id=hostnet1,vhost=on,vhostfd=25
因为需要libvirt帮忙先配置好后端以及处于安全考虑;但是qemu起来就是另外一个进程,给个fd号就能直接用了吗,显然不是,下面从代码角度分析下

Continue reading “libvirt 向qemu传文件描述符”

sriov vf get iommu group kernel code trace

VF device driver call:
pci_enable_sriov -> sriov_enable -> pci_iov_add_virtfn -> pci_device_add -> device_add ->
pci bus register a iommu notifier will be called when device_add start to notify:

intel_iommu_init -> iommu_bus_init -> “nb->notifier_call = iommu_bus_notifier;”

ops->add_device:

intel_iommu_add_device:

iommu_group_get_for_dev:
this will find or create an iommu group for the VF device

Linux 内核 schedule时的preemption notify机制

内核进行进程切换时,先调用了__schedule,在关抢占后调用context_switch:
prepare_task_switch里面调用fire_sched_out_preempt_notifiers,进而调用prev进程注册的sched_out操作,
这里是分支:如果是新创建的进程被调度了,要调用schedule_tail:
回到主题:finish_task_switch这里会调用fire_sched_in_preempt_notifiers:
preempt_notifiers在哪里注册的呢,对kvm来说是这里:

kvm模块加载的时候vmx_init->kvm_init里面初始化了kvm_preempt_ops

所以kvm_sched_in和kvm_sched_out被调用时的上下文是关抢占的

[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: