1.html

介绍linux下文件和设备编程

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability capability;<br>
};<p>
struct memory_process{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_number,max_file_number,file_ring;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int max_block_number,trigger_block_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int block_number,read_block_number,write_block_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int block_ring,read_block_ring,write_block_ring;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability capability;<br>
};<p>
struct memory_hash{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int hash_ring;<br>
};<p>
struct memory_body_struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int *free_physical_block,*free_file;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int *block_number,*free_block_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int *file_number,*process_number,*hash_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct physical_block *physical_block;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct file_window *file_window;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct memory_process *memory_process;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct memory_hash *hash;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int (*hash_function)(int file,int logic_block);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int my_processor,my_memory_body;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct memory_sleep_semaphore *wait_block;<br>
};<br>
struct install_memory_body_parameter{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char *base;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int (*hash_function)(int file,int logic_block);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int my_processor,my_memory_body;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int block_number,file_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int process_number,hash_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int first_block;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability capability;<br>
};<p>
#endif<p>
2、文件memory/call_memory.h<p>
#ifndef OS_MEMORY_MEMORY_CALL<br>
#define OS_MEMORY_MEMORY_CALL<p>
union memory_call_parameter{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct install_memory_body_parameter<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; memory_body_parameter;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int set_stack_flag;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }setup;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct open_file_window{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_window_id;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct file_window file_window;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability process_capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }open_file_window;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct close_file_window{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_window_id;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability file_capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }close_file_window;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct file_attribute{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_window_id;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct file file;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }file_attribute;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct memory_map_deal{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_window_id;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int begin_logic_address,end_logic_address;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability file_capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }memory_map_deal;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct flush_process_memory{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int give_up_flag;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int process_number;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability process_capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }flush_process_memory;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct flush_file_window{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int give_up_flag;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_window_id;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability file_capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }flush_file_window;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct mark_modify{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int file_window_id;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int begin_logic_address,end_logic_address;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability file_capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }mark_modifed;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct memory_resource&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; memory_resource;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct control_file_system{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; union file_system_operation_parameter parameter;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct capability capability;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }control_file_system;<br>
};<p>
#endif<p>
<p>
<br>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I507" ID="I507"></A><center><b><font size=+2>内核实现</font></b></center><br>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I508" ID="I508"></A><center><b><font size=+2>就绪线程</font></b></center><br>
内核中就绪线程管理部件的实现<p>
&nbsp;&nbsp;&nbsp; 在虚拟地址空间基于文件操作系统中，采用按优先级调度方式，调度各个就绪线程占用处理机。执行线程调度时，总是选择优先数最小，也就是优先级最高的线程占用处理机。内核利用堆数据结构选择优先数最小的线程。下面首先介绍堆数据结构，然后讨论选择优先数最小线程的算法。<br>



<center><A HREF="#Content">[目录]</A></center>
<hr><br><A NAME="I509" ID="I509"></A><center><b><font size=+2>堆数据结构</font></b></center><br>
堆的概念<p>
&nbsp;&nbsp;&nbsp; 假设r[0]，r[1]，… r[n-1]是一序列元素，如果对于任意r[i]，同时满足条件r[i].key≤r[2* i+1].key，r[i].key≤r[2*i+2].key，则称该序列是一个堆，也称为最小化堆，如果把不等式中的小于号≤换成大于号≥，称为最大化堆。在下面的讨论中，所有的堆指的是最小化堆。<br>
可以把序列r[0]，r[1]，… r[n-1]看成是按数组方式存储的一棵满二叉树，元素r[0]为树根，其它元素为树中的中间结点或叶子结点。考虑到在一棵按数组方式存储的满二叉树中，元素r[2*i+1]和元素r[2*i+2]是元素r[i]的左孩子和右孩子，因此在一个堆中，对于任一元素r[i]，其键值r[i].key一定小于等于其左右两个孩子的键值r[2* i+1].key和r[2*i+2].key。<br>
&nbsp;&nbsp;&nbsp; 根据堆的定义，可以得出堆的一个重要性质：如果一个按数组存放的满二叉树是堆，那么堆顶元素一定是堆中所有元素中键值最小的元素。<br>
&nbsp;&nbsp;&nbsp; 该性质可以根据堆二叉树的层数利用数学归纳法证明：<br>
&nbsp;&nbsp;&nbsp; 当堆二叉树的层数为1时，堆二叉树中只有一个元素r[0]，因此堆顶元素是堆中所有元素中键值最小的元素。<br>
&nbsp;&nbsp;&nbsp; 假设对于所有的层数小于n的堆二叉树，堆顶元素的键值是堆中所有元素中键值最小的元素。当堆二叉树的层树为n时，堆顶元素r[0]的左右子树一定是层数小于n的堆二叉树，左子树的堆顶元素是r[1]，右子树的堆顶元素是r[2]。根据假设可知r[1]是左子树中键值最小的元素，r[2]是右子树中键值最小的元素；再根据堆的定义：对于任意元素r[i]满足r[i].key≤r[2* i+1].key，r[i].key≤r[2*i+2].key，可知r[0].key≤r[1].key，r[0].key≤r[2].key，因此，堆顶元素r[0]一定是堆中所有元素中键值最小的元素。<br>
&nbsp;&nbsp;&nbsp; 堆的性质使得堆很适合从一组元素中选择最值元素（最大值或最小值）的场合，只要把所有可供选择的元素组织成一个堆，堆顶元素即为需要选择的最值元素。这也是我们采用堆数据结构选择优先数最小线程的原因。在LFYOS中，把所有处于就绪状态的线程根据线程的优先数组织成一个堆，堆顶元素即为优先级最高的线程，执行线程切换时，内核总是选择处于堆顶的线程占用处理机。<br>
&nbsp;&nbsp;&nbsp; 元素的健值发生变化时对堆的调整<br>
&nbsp;&nbsp;&nbsp; 假设在堆中存在n个元素r[0]，r[1]，… r[n-1]，这些元素之间全部满足条件r[i].key≤r[2* i+1].key和r[i].key≤r[2*i+2].key，由于某种原因，其中某个元素r[k]的键值r[k].key改变，破坏了构成堆的条件，需要对元素序列进行相应的调整，把元素序列恢复为一个堆。<br>
&nbsp;&nbsp;&nbsp; 元素r[k]的键值r[k].key改变有两种可能：键值r[k].key减小或键值r[k].key增大。在堆中，元素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]向上移动，即可把序列调整为一个堆。<br>
&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>