rt-threadスレッドスケジューラ現在の最高優先度スレッドアルゴリズムを取得するプロセス分析

9044 ワード

前章では、rt-threadオペレーティングシステムのスレッドスケジューラのソースコードを概説しました.ここでは、rt-threadがデバッグ時に、現在の最高優先度スレッドを取得するアルゴリズムプロセスをどのように取得するかについて説明します.
前に述べたように、rt-threadはビットマップを用いてこのプロセスを実現し、このプロセスを具体的に分析する前に、まずこのビットマップの構造と関連するいくつかのパラメータ変数を見てみましょう.
1ビットマップ構造及び関連パラメータ
1.1ビットマップ構造
rt-threadのソースファイルscheduler.cにおけるビットマップマッピングテーブルは、以下のように定義される.
const rt_uint8_t rt_lowest_bitmap[] =
{
    /* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

ここからしばらくは名堂が見えないので、しばらくスキップして、このビットマップに関するパラメータを見てみましょう.
1.2ビットマップに関するパラメータ
まだschedulerですcソースファイルには、次のように定義されたグローバル変数があります.
rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX];//     ,         
struct rt_thread *rt_current_thread;//         

rt_uint8_t rt_current_priority;//               

#if RT_THREAD_PRIORITY_MAX > 32//       32 
/* Maximum priority level, 256 */
rt_uint32_t rt_thread_ready_priority_group;//          
rt_uint8_t rt_thread_ready_table[32];//       ,         
#else
/* Maximum priority level, 32 */
rt_uint32_t rt_thread_ready_priority_group;//      ,         
#endif

上位ソースコードから分かるように、最大優先度がどの程度定義されているかにかかわらず、グローバル変数準備優先度グループが存在するが、最大優先度が32優先度より大きい場合にのみ、別のグローバル変数準備テーブルが存在する.これは配列であり、意味はともかく、後述する内容を参照する.
1.3スレッド制御ブロックにおけるビットマップに関するパラメータ
スレッド制御ブロックに含まれるメンバー変数については、以前に説明したが、ビットマップ操作に関するパラメータの一部については、以下のように詳細に説明していない.
//...    
/* priority */
    rt_uint8_t  current_priority;                       /**< current priority */
    rt_uint8_t  init_priority;                          /**< initialized priority */
#if RT_THREAD_PRIORITY_MAX > 32
    rt_uint8_t  number;
    rt_uint8_t  high_mask;
#endif
    rt_uint32_t number_mask;
//...

上記のソースコードから分かるように、スレッド制御ブロックには、ユーザ定義の最大優先度が32個より大きい場合にのみnumberおよびhigh_が存在するmask 2つのメンバー変数、この2つのメンバー変数、および別のメンバー変数number_maskはビットマップ演算用ですが、後ろのメンバー変数number_maskは、ユーザ定義の優先度の個数が32より大きいか32より大きいかにかかわらず存在する.それらの意味は一応後述の内容の解説を見る.
2パラメータの初期化時の変化
ここにいるcソースファイルの_rt_thread_Init関数:
//...
thread->init_priority    = priority;
thread->current_priority = priority;
//...
は、スレッドの初期化時に、スレッドの現在の優先度が初期優先度とすることを知る.
スレッド関数rt_を起動するthread_startupには次のコードがあります.
//...
    /* calculate priority attribute */
#if RT_THREAD_PRIORITY_MAX > 32
    thread->number      = thread->current_priority >> 3;            /* 5bit */
    thread->number_mask = 1L << thread->number;
    thread->high_mask   = 1L << (thread->current_priority & 0x07);  /* 3bit */
#else
    thread->number_mask = 1L << thread->current_priority;
#endif
//...

上記コードから分かるように、初回起動後のスレッドのメンバnumberは、現在の優先度を3桁右にシフトした値、すなわち5桁高い値をとる.
1左シフトnumberで得られた値をnumber_とするmaskの値、high_maskの値は1を左に移動thread->current_priority&0 x 07以降の値、すなわち、現在優先度が低い3桁の値を左記する.
このように、ユーザ定義の優先度レベルが32以上である場合、優先度の高い5ビットと低い3ビットは異なる意味を示すものであり、優先度はビットマップマスクに関するものにすぎない.
3スレッドスケジューリング中のパラメータの変化
スレッドrt_thread_startup後、rt_が呼び出されます.thread_resume関数は、rt_でスレッドをすぐに実行します.thread_resume関数ではrt_が呼び出されますschedule_insert_thread関数はスレッドをスケジューラに追加し、rt_schedule_insert_thread関数では、スレッド準備テーブルrt_が操作されます.thread_ready_tableとスレッド準備優先度グループrt_thread_ready_priority_groupは、次のコードで示されています.
//...
#if RT_THREAD_PRIORITY_MAX > 32
    rt_thread_ready_table[thread->number] |= thread->high_mask;
#endif
    rt_thread_ready_priority_group |= thread->number_mask;
//...
は上から見られ、システムはthread->number値を下とし、スレッド準備テーブルrt_thread_ready_tableの対応する値または上thread->high_mask,スレッド準備優先度グループth_thread_ready_priority_groupの値またはthread->number_mask.
4スケジューリングで現在の最優先スレッドを取得するプロセス
次にもちろん最も重要なのは、本明細書の核心内容である.これまで多くの内容は、関連パラメータがどのように変化するかを説明してきたが、これらのパラメータは最高優先度を取得する過程で使用されるため、その変化過程について説明する必要がある.
スレッドスケジューリング関数rt_schedule、システムは以下のコードを使用して現在の最高優先度スレッドを取得し、コードは以下の通りです.
//...
        register rt_ubase_t highest_ready_priority;

#if RT_THREAD_PRIORITY_MAX == 8
        highest_ready_priority = rt_lowest_bitmap[rt_thread_ready_priority_group];//            8     
#else
        register rt_ubase_t number;//number      
        /* find out the highest priority task */
        if (rt_thread_ready_priority_group & 0xff)// rt_thread_ready_priority_group      ,        number        
        {
            number = rt_lowest_bitmap[rt_thread_ready_priority_group & 0xff];
        }
        else if (rt_thread_ready_priority_group & 0xff00)
        {
            number = rt_lowest_bitmap[(rt_thread_ready_priority_group >> 8) & 0xff] + 8;
        }
        else if (rt_thread_ready_priority_group & 0xff0000)
        {
            number = rt_lowest_bitmap[(rt_thread_ready_priority_group >> 16) & 0xff] + 16;
        }
        else
        {
            number = rt_lowest_bitmap[(rt_thread_ready_priority_group >> 24) & 0xff] + 24;
        }
//    number   ,                        ,       ,            
//           ,                 
#if RT_THREAD_PRIORITY_MAX > 32 
highest_ready_priority = (number << 3) + rt_lowest_bitmap[rt_thread_ready_table[number]];
#else 
highest_ready_priority = number;
#endif
#endif 
/* get switch to thread */ 
to_thread = rt_list_entry(rt_thread_priority_table[highest_ready_priority].next,//                           
struct rt_thread, tlist);
//...

5スレッドがCPU占有時のパラメータ変化を失う
スレッドがCPUを失うには、次の方法があります.
自発的にCPUを失う:
1:ソースコードでsleepを呼び出し、delay関数はスレッドを使用してCPUを放棄する.
2:ソースコードでsuspendを呼び出すスレッドを保留する.
受動的にCPUを失う:
1:スレッドのタイムスライスが切れ、CPUを放棄する.
2:システムに割り込みが発生する、スレッドはCPUを一時的に失い、割り込みルーチンの実行が完了すると、ハードウェアによって自動的に完了する.
スレッドがCPUをアクティブに失うと、プログラムは最終的にrt_を実行します.schedule_remove_thread関数は、現在のスレッドをスケジューラから除去する.一方、受動的にCPUを失う場合(ここでは第1のものを指し、第2のものは完全にハードウェアによって完成し、ソフトウェアの介入を必要としない)、プログラムはrt_を実行する.list_remove(&(thread->tlist));現在のスレッドもスケジューラから削除し、rt_を実行します.list_insert_before(&(rt_thread_priority_table[thread->current_priority]),&(thread->tlist));現在のスレッドをスケジューラの対応するキューの最後に追加し、rt_を実行します.schedule();スレッドを再スケジュールします.
このことから,受動的にCPUを失う過程で,プログラムはスレッドの最高優先度を取得するアルゴリズムに関連するいくつかのパラメータを操作せず,rt_schedule_remove_thread関数:
/*
 * This function will remove a thread from system ready queue.
 *
 * @param thread the thread to be removed
 *
 * @note Please do not invoke this function in user application.
 */
void rt_schedule_remove_thread(struct rt_thread *thread)
{
    register rt_base_t temp;

    RT_ASSERT(thread != RT_NULL);

    /* disable interrupt */
    temp = rt_hw_interrupt_disable();

#if RT_THREAD_PRIORITY_MAX <= 32
    RT_DEBUG_LOG(RT_DEBUG_SCHEDULER, ("remove thread[%s], the priority: %d
", thread->name, thread->current_priority)); #else RT_DEBUG_LOG(RT_DEBUG_SCHEDULER, ("remove thread[%s], the priority: %d 0x%x %d
", thread->name, thread->number, thread->number_mask, thread->high_mask)); #endif /* remove thread from ready list */ rt_list_remove(&(thread->tlist));// if (rt_list_isempty(&(rt_thread_priority_table[thread->current_priority]))) { #if RT_THREAD_PRIORITY_MAX > 32// rt_thread_ready_table[thread->number] &= ~thread->high_mask; if (rt_thread_ready_table[thread->number] == 0) { rt_thread_ready_priority_group &= ~thread->number_mask; } #else rt_thread_ready_priority_group &= ~thread->number_mask; #endif } /* enable interrupt */ rt_hw_interrupt_enable(temp); }

上記のソースコードで表示され、rt_schedule_remove_thread関数では、スレッドスケジューラの最高優先度取得に関するいくつかのパラメータを逆操作する.
6後記
全体のアルゴリズムの過程の分析が終わって、実は今まで、ここではこのビットマップの原理に対して解釈していないで、個人は、これはあまり関係がないと思って、私達はただ知っているだけで、このような操作の流れで、このビットマップを結びつけて、やっと1つの時間と関係のないアルゴリズムを得ることができます.これがrt-threadオペレーティングシステムのスレッドスケジューリングの核心である.
最高優先度アルゴリズムの原理については、次のように参照してください.http://blog.csdn.net/prife/article/details/7077120