1.html

网上一个牛人整理的关于linux内核编译

&nbsp;&nbsp;&nbsp; 下面讨论如果某个元素r[k]其键值r[k].key增大后，如何对堆进行调整。<br>
&nbsp;&nbsp;&nbsp; 假设在堆中，元素r[k]的键值r[k].key大于等于其双亲的键值r[INT((k-1）/2)].key，小于等于左右孩子的键值r[2* i+1].key和r[2*i+2].key，如果键值r[k].key增大，其键值仍然大于其双亲接点的键值，但可能由于大于其左右孩子的键值而破坏了构成堆的条件。通过在序列中把r[k]和左右孩子结点中键值较小的结点相互交换，在二叉树中把r[k]向下移动，即可把序列调整为一个堆。<p>
堆调整算法的时间复杂度<p>
&nbsp;&nbsp;&nbsp; 无论某个堆中元素的键值是增大还是减小，堆调整算法执行结点交换的次数都是很少的。假设在一个堆中存在n个元素，则堆二叉树的层数不超过1+Log 2n，当堆中某一元素的键值增大时，该元素在堆中向下移动；当堆中某一元素的键值减小时，该元素在堆中向上移动。由于堆二叉树的层数不超过1+Log2n，因此，执行堆调整算法时，结点交换的次数不超过Log2n，也就是说，堆调整算法的时间复杂度仅仅为O（Log2n）。显然，堆调整算法的时间复杂度很低，这也是我们选择堆数据结构来选择优先级最高线程的原因。<p>
向堆中加入一个元素，从堆中删除一个元素<p>
&nbsp;&nbsp;&nbsp; 向堆中加入一个元素时，把元素放在序列的最后，然后执行键值减小的上移调整；从堆中删除一个元素时，首先把被删除的元素和最后一个元素交换，把元素从序列的最后删除，再根据删除元素的键值和交换元素的键值大小执行上移或下移调整。如果删除元素的键值小于交换元素的键值，执行下移调整；如果删除元素的键值大于交换元素的键值，执行上移调整。<p>
<p>
<br>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I510" ID="I510"></A><center><b><font size=+2>就绪线程管理部件的数据结构及其实现</font></b></center><br>
空闲处理机栈、处理机状态数组<p>
&nbsp;&nbsp;&nbsp; 在系统中设置一空闲处理机栈，所有空闲的处理机记录在空闲处理机栈中，当某一处理机空闲时，把处理机号压入栈中，如果有线程需要运行，从栈中弹出一个处理机分配给线程使用。当就绪线程堆非空时，所有处理机都已分配给了线程，空闲处理机栈一定是空的。<br>
在系统中设置一处理机状态数组，每个处理机对应数组中的一个元素。在数组中记录着各个处理机需要切换的线程，在大多数情况下，当前运行的线程和需要切换的线程二者相同，表示不需要执行处理机切换，如果二者不同，需要申请处理机中断，请求处理机执行处理机切换，切换另一线程占用处理机。<br>
运行线程堆和就绪线程堆<br>
&nbsp;&nbsp;&nbsp; 在虚拟地址基于文件的操作系统中，设置了两个堆数据结构：运行线程堆和就绪线程堆。所有正在处理机上运行的线程记录在运行线程堆中；所有等待到处理机上去运行的线程记录在就绪线程堆中。运行线程堆中线程的个数最多不超过系统支持的处理机数。<br>
系统按照各个线程的优先数对两个堆实施管理。在就绪线程堆中，堆顶元素是优先数最小优先级最高的线程，如果需要选择一个就绪线程占用处理机，选择堆顶元素对应的线程；在运行线程堆中，堆顶元素是优先数最大优先级最低的线程，如果需要选择一个运行线程放弃处理机，也选择堆顶元素对应的线程。由于线程优先数越小，优先极越高，优先数越大，优先极越低，因此，运行线程堆是一个最大化堆。<br>
&nbsp;&nbsp;&nbsp; 由于系统选择优先级最高的线程占用处理机运行，一般情况下，就绪线程堆堆顶元素对应线程的优先数大于运行线程堆堆顶元素对应线程的优先数。如果由于某些原因线程的优先数发生了变化（例如，线程改变了优先数、处于运行线程堆中线程睡眠、线程终止退出等），就绪线程堆堆顶元素对应线程的优先数，可能小于运行线程堆堆顶元素对应线程的优先数，表示系统中某个处于就绪态线程的优先级高于另一个处于运行态线程的优先级，需要系统执行处理机切换，使运行线程堆堆顶元素对应线程放弃处理机，就绪线程堆堆顶元素对应线程占用处理机。<p>
向运行线程堆或就绪线程堆插入线程的算法<p>
&nbsp;&nbsp;&nbsp; 如果存在空闲处理机，从空闲处理机栈弹出一个处理机号分配给线程，把分配的处理机号记录在线程的控制块中，在处理机状态数组中记录该处理机需要切换的线程，直接把线程加入到运行线程堆中，并请求处理机执行处理机切换。<br>
如果不存在空闲处理机，比较需要插入的线程优先级和运行线程堆堆顶元素对应的线程的优先级，如果需要插入线程的优先级不高于运行线程堆堆顶元素对应线程的优先级，直接把新创建的线程加入到就绪线程堆中。<br>
&nbsp;&nbsp;&nbsp; 如果需要插入线程的优先级高于运行线程堆堆顶元素对应线程的优先级，把需要插入的线程和运行线程堆堆顶元素相互交换，对运行线程堆执行下移调整，把原运行线程堆堆顶元素对应的线程加入到就绪线程堆中；同时，在处理机状态数组中对应处理机元素中，把需要切换线程域设置为新插入线程的线程标识符，请求处理机执行处理机切换。<p>
从运行线程堆或就绪线程堆删除线程的算法<p>
&nbsp;&nbsp;&nbsp; 如果线程处于就绪线程堆中，直接从就绪线程堆中删除。<br>
&nbsp;&nbsp;&nbsp; 如果线程处于运行线程堆中，就绪线程堆非空，把删除的线程和就绪线程堆堆顶元素对应的线程执行交换，对运行线程堆执行下移调整，再从就绪线程堆中把线程删除；同时，在处理机状态数组对应处理机的元素中，把需要切换线程域设置为原就绪线程堆堆顶元素对应的线程，并请求处理机执行处理机切换。<br>
&nbsp;&nbsp;&nbsp; 如果线程处于运行线程堆中，就绪线程堆为空，直接从运行线程堆中删除；同时，在处理机状态数组对应处理机元素中，把需要切换线程域设置为空。把处理机号压入空闲处理机栈中，并请求处理机执行处理机切换，处理机切换为空闲状态。<p>
<p>
<br>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I511" ID="I511"></A><center><b><font size=+2>就绪线程管理部件提供的调用</font></b></center><br>
&nbsp;&nbsp;&nbsp; 管理运行线程堆和就绪线程堆的模块统称为就绪线程管理部件，就绪线程管理部件为上层共提供了四个调用：<p>
&nbsp;&nbsp;&nbsp; 向运行线程堆或就绪线程堆中插入线程：线程对信号量执行V操作时，可能需要唤醒线程，调用本功能向运行线程堆或就绪线程堆插入线程。<br>
&nbsp;&nbsp;&nbsp; 从运行线程堆或就绪线程堆删除线程：线程对信号量执行P操作时，可能需要使线程睡眠，调用本功能从运行线程堆或就绪线程堆删除线程。<br>
&nbsp;&nbsp;&nbsp; 线程优先数调整：改变线程优先数时调用本功能，首先从运行线程堆或就绪线程堆删除线程，修改线程优先数后再插入到运行线程堆或就绪线程堆中。<br>
&nbsp;&nbsp;&nbsp; 处理机切换响应：处理机管理部件仅仅选择哪些线程应该在处理机上运行，如果需要某个处理机执行处理机切换，通过中断网络向处理机申请中断，处理机响应中断，触发中断服务程序执行处理机切换的操作，并调用本功能通知处理机管理部件已完成处理机切换。<p>
<p>
<p>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I512" ID="I512"></A><center><b><font size=+2>信号量</font></b></center><br>
内核中信号量管理部件的实现<p>
&nbsp;&nbsp;&nbsp; 信号量（semaphore）是E. W. Dijkstra在1965年提出的一种用于实现进程之间同步和互斥的方法。一个信号量的值可以为0，表示没有积累下来的唤醒操作，也没有在信号量上睡眠的进程；或者为正值，表示有一个或多个被积累下来的唤醒操作；或者为负值，其绝对值为在信号量上睡眠的进程数。<br>
&nbsp;&nbsp;&nbsp; 信号量管理部件提供四个功能调用：<br>
&nbsp;&nbsp;&nbsp; &middot;申请一个信号量<br>
&nbsp;&nbsp;&nbsp; &middot;释放一个信号量<br>
&nbsp;&nbsp;&nbsp; &middot;对信号量执行P操作<br>
&nbsp;&nbsp;&nbsp; &middot;对信号量执行V操作<p>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I513" ID="I513"></A><center><b><font size=+2>信号量和P、V操作</font></b></center><br>
&nbsp;&nbsp;&nbsp; 对信号量存在两种操作：对信号量的P操作和对信号量的V操作。<br>
&nbsp;&nbsp;&nbsp; 对一信号量执行P操作时检查其值是否大于零。若是则将其值减1（用掉一个保存的唤醒信号）并继续执行；若值小于等于零则将其值减1后睡眠，此时P操作并未结束。检查数值、改变数值、以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作(atomic action)完成，即保证一旦一个信号量操作开始，则在操作完成或阻塞之前别的进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是非常重要的。<br>
&nbsp;&nbsp;&nbsp; V操作递增信号量的值。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的P操作，则由系统选择其中的一个并允许其完成它的P操作，于是，对一个有进程在其上睡眠的信号量执行一次V操作之后，该信号量的值加1，在其上睡眠的进程少了一个。递增信号量的值和唤醒一个进程同样也是不可分割的。不会有进程因执行V而睡眠。<p>
<p>
<br>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I514" ID="I514"></A><center><b><font size=+2>内核中的信号量</font></b></center><br>
&nbsp;&nbsp;&nbsp; 在LFYOS中，信号量是内核维护的一种资源，应用程序通过使用信号量实现线程之间的同步和互斥。<br>
&nbsp;&nbsp;&nbsp; 线程可以通过内核提供的调用申请和释放信号量资源。申请信号量时，用资源ID作调用的入口参数。如果两个或多个线程使用相同的资源ID申请信号量，信号量管理部件保证它们申请到相同的信号量，以实现线程之间正确的同步和互斥。使用完信号量后应释放信号量资源，以便其它进程使用。<br>
&nbsp;&nbsp;&nbsp; LFYOS中信号量P、V操作的语义也和Dijkstra提出的信号量的语义有所不同。<br>
&nbsp;&nbsp;&nbsp; 对于信号量V操作，线程可以指定递增信号量的值，不仅仅可以实现对信号量值的加一操作，而且可以增加任意一个整数；甚至可以指定唤醒所有睡眠在该信号量上的线程。信号量V操作的返回值为信号量的当前值，通过指定递增信号量的值为零，执行信号量V操作可以查询信号量的当前值。线程还可以对某个线程而不是对信号量执行V操作，由信号量管理部件对线程正在上面睡眠的信号量执行V操作把线程唤醒。<br>
&nbsp;&nbsp;&nbsp; 对于信号量P操作，如果信号量的当前值小于等于0时，线程可以选择是睡眠还是直接返回；如果执行P操作的线程睡眠，等到其它线程执行了V操作后，执行P操作的线程返回。P操作的返回值为一整数类型的变量，如果其它线程执行的V操作同时唤醒了多个线程，这些线程P操作的返回值从1开始递增排序，哪一个线程可以进入临界区由应用程序确定。在LFYOS中，不仅线程自己可以执行P操作，而且可以代替其它线程对某个信号量执行P操作，从而使其它线程睡眠；再通过对信号量执行V操作将其唤醒，因此，通过P、V操作可以实现对线程的调度和控制。<br>
&nbsp;&nbsp;&nbsp; LFYOS中信号量和Dijkstra提出的信号量的另一点不同是：释放信号量时，如果存在线程睡眠在信号量上，这些线程被全部唤醒；而Dijkstra提出的信号量没有释放操作。<br>
&nbsp;&nbsp;&nbsp; 如果执行对信号量的V操作时，指定唤醒所有睡眠在该信号量上的线程，P、V操作的语义类似于UNIX内核中的sleep（）和wakeup（）函数。<p>
<p>
<p>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I515" ID="I515"></A><center><b><font size=+2>信号量管理数据结构</font></b></center><br>
&nbsp;&nbsp;&nbsp; 信号量管理数据结构见后面的“数据结构”部分，在系统中设置一信号量控制块数组，每个信号量对应着数组中的一个元素。<br>
&nbsp;&nbsp;&nbsp; 信号量分成两类：空闲信号量和已经分配的信号量。所有空闲信号量链成一个单向链，用一个变量（空闲信号量链首）指向空闲信号量链，按先进后出的栈式管理方式实施对空闲信号量的管理。<br>
&nbsp;&nbsp;&nbsp; 线程由于对某个信号量执行了P操作而睡眠，睡眠在某个信号量上的所有线程都已经从就绪线程堆或运行线程堆中删除，并链成一个双向的环链，链首指针保存在信号量控制块数组中。执行V操作时把睡眠的线程从线程环链中删除，插入就绪线程堆或运行线程堆中。<p>
<p>
<p>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I516" ID="I516"></A><center><b><font size=+2>信号量管理的实现</font></b></center><br>
&nbsp;&nbsp;&nbsp; 信号量管理包括四个对信号量操作的实现：<br>
&nbsp;&nbsp;&nbsp; &middot;申请一个信号量<br>
&nbsp;&nbsp;&nbsp; &middot;释放一个信号量<br>
&nbsp;&nbsp;&nbsp; &middot;对信号量执行P操作<br>
&nbsp;&nbsp;&nbsp; &middot;对信号量执行V操作<br>
&nbsp;&nbsp;&nbsp; 执行对信号量的P操作和V 操作以前，首先检查信号量的状态，如果是一个没有分配的信号量，不能对其执行任何操作，信号量操作直接返回，否则根据不同的操作请求，进行相应的处理：<br>
&nbsp;&nbsp;&nbsp; 执行P操作时，对信号量的值执行减一操作，根据减一后信号量的值，分别处理：<br>
&nbsp;&nbsp;&nbsp; 如果大于等于0，P操作直接返回，返回值为1。<br>
&nbsp;&nbsp;&nbsp; 如果小于零，但是指定了P操作不睡眠，对信号量的值执行加一操作后P操作返回，返回值为0。<br>
&nbsp;&nbsp;&nbsp; 如果小于零，但是指定了P操作可以睡眠，把线程从运行线程堆或就绪线程堆删除，插入到信号量的睡眠线程环链中，使线程睡眠。当线程被其它线程执行的V操作唤醒时，这些被唤醒线程的P操作返回，被V操作唤醒的各个线程的返回值从2开始顺序递增。<br>
&nbsp;&nbsp;&nbsp; 执行对线程的V操作时，首先根据线程确定的信号量并设置递增信号量的值为1，然后设置一初始值为0的递增计数器，根据指定的递增信号量的值，循环重复执行以下操作：<br>
&nbsp;&nbsp;&nbsp; 对信号量的值和计数器的值执行加一操作。<br>
&nbsp;&nbsp;&nbsp; 如果在信号量的睡眠线程环链中存在睡眠的线程，唤醒环链上的第一个线程，把线程从信号量的睡眠线程环链中删除，插入到运行线程堆或就绪线程堆中，设置P操作的返回值为计数器的当前值；其它情况不执行线程唤醒操作。<br>
&nbsp;&nbsp;&nbsp; 执行申请信号量调用时，从空闲信号量栈中取出一个信号量，执行初始化操作后把信号量ID返回给应用程序。<br>
&nbsp;&nbsp;&nbsp; 执行释放信号量调用时，如果信号量上存在睡眠线程，执行V操作将其唤醒；然后把信号量插入空闲信号量栈中。<p>
<p>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I517" ID="I517"></A><center><b><font size=+2>线程迁移</font></b></center><br>
内核中线程迁移部件的实现<p>
&nbsp;&nbsp;&nbsp; 在LFYOS中，线程和进程的关系是一种临时性的关系，线程并非永久性地属于某一个进程，通过线程迁移调用一个线程可以从一个进程进入另一个进程，执行被调用进程相应的功能，在被调用进程中执行完毕后，通过线程返回调用线程退回到原进程中运行。通过线程迁移调用和线程返回调用，线程实现了在不同进程之间的迁移。<br>
&nbsp;&nbsp;&nbsp; 通过线程迁移调用，一个线程进入另一个进程时，在新进程中，只能从进程初始执行点开始执行。通过在进程初始执行点处放置一定的检查程序，可以防止恶意的线程对进程的破坏，保证线程调用的安全性。<br>
&nbsp;&nbsp;&nbsp; 同样，当一个线程从一个进程返回到原来的进程时，系统也要保证线程返回到正确的执行点，防止恶意的特洛伊木马造成的破坏，为此，在线程控制块中专门设置了线程返回控制块栈。当一个线程执行线程迁移调用，从一个进程进入另一个进程时，系统保存线程返回调用时应该恢复的返回地址、进程标识符等信息；当线程执行线程返回调用从一个进程返回到原来的进程时，根据以前保存的线程返回地址，恢复线程在原进程环境中的运行。通过保存线程返回地址，防止服务进程对调用进程恶意的破坏，保证线程返回的安全性。<p>
线程迁移部件提供的功能调用及实现<p>
&nbsp;&nbsp;&nbsp; 线程迁移部件提供了两个功能调用：线程迁移调用和线程返回调用。<br>
&nbsp;&nbsp;&nbsp; 线程迁移部件分下面三步执行线程迁移调用：<br>
&nbsp;&nbsp;&nbsp; &middot;判断目标进程是否是一个合法的进程，如果非法直接返回出错；否则继续向下执行。<br>
&nbsp;&nbsp;&nbsp; &middot;如果需要把当前应该保存的信息压入线程返回控制块栈中，执行压栈操作，如果压栈操作溢出，直接返回出错信息；如果不需要执行压栈操作或需要执行压栈操作且压栈操作没有溢出，继续向下执行。<br>
&nbsp;&nbsp;&nbsp; &middot;最后把线程的当前所属进程设置为目标进程，根据目标进