&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>