Linux Stuff

很不错的文章：http://blog.csdn.net/drshenlei/archive/2009/06/12/4265101.aspx 英文的博客出处：http://duartes.org/gustavo/blog/ 讲述了CPU与操作系统共同构筑保护模式的原理。

把cache分成许多行（line）,每一行分为两部分，一部分是Data，保存缓存的数据，另一部分是Tag，保存这这些数据在内存中的地址信息。每行之间没有关系，这样每次cpu访问的时候，把地址给每一行的tag进行比较，如果有相同即为命中。这就是“全相联Cache ”。 这种方式的缺点是，每次内存访问都要跟每一行的tag进行比较，造成结构上的复杂。 假设cache大小为64KB，每一行的data是32B，那么就有2048 line, 一次内存访问要跟每一个line的tag进行比较，才能确定是否命中，显然太复杂了。 为了解决这个问题，就对其进行改进，改进的结果就是直接映像Cache。 这种方式把访问内存的地址分为3个部分。高位地址，低位地址，和行内部地址。比如，地址为32位，cache大小为64KB, 每行的data大小为32B。 那么地址位如下分配： 高位地址范围为：[31-16]， 低位地址范围为[15-5]， 行内部地址范围为[4-0] 比如：对于地址 0x12345678， 0x1234为高位地址， 0x567 >> 1 为低位地址， 0x18为行内地址 在访问该内存的时候，首先用低位地址作为行号来检索 0x567 >> 1 = 0x293 就是第659行cache，找到这行cache用0x1234与其tag内的地址比较，相等则命中。 下面是图： 很显然这种结构，非常简单，只需要跟一行进行比较就可以了。不过，它的缺点是每一行对应内存中很多不同的地址，而且这些地址只能缓存在这一行中。 比如，当上面那个地址缓存了之后，我们又要访问地址0x43215678, 这时候还是找到第659行cache，但是只能将0x12345678的数据作废，重新读入新地址的数据。如果，这种情况频繁发生，会大大降低系统效率。 为了解决这个问题就出现了改进的“组相联Cache“，组相联Cache 把cache分成几个独立的组。 组相联映象把主存和CACHE都分为大块(组)和小块(实际意义上的快)

         n个进程共享M个资源，每个进程一次只能申请/释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不会产生死锁。 答：设max （i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：       max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n))<m+n 如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，       alloc(1)+ ┅+alloc(n)=m 另一方面所有进程将陷入无限等待状态。可以推出       need(1)+ ┅+need(n)<n 上式表示死锁发生后，n个进程还需要的资源量之和小于n， 这意味着此刻至少存在一个进程i,need(i)=0 ,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。