跳到主要內容

淺讀CuRT:task, context switch與scheduling

上一篇整理了CuRT從硬體上電後到跳入C function前所作的事情,本篇文章則會紀錄CuRT如何準備multitasking環境,以及CuRT於執行期的行為分析。

在app/shell/main.c中,我們可以看到main()的開頭為:

int main()
{
        SerialInit();
        init_interrupt_control();
        init_curt();
...

SerialInit()只是把UART port初始化,方便printf()可以正常運作。init_interrupt_control()則設定pxa255的interrupt controller可以接收外部的interrupt sources,稍後啟動的timer就會發出定期的interrupt驅動scheduling。init_curt()作的事情就比較多了點,讓我們進去瞧一瞧:

void init_curt()
{
        int i;
        for (i = 0; i < MAX_PRIO; i++) {
                prio_exist_flag[i] = false;
                init_list(&ready_list[i]);
        }
        init_list(&delayed_list);
        init_list(&blocked_list);
        init_list(&termination_wait_list);

        for (i = 0; i < MAX_THREAD; i++)
                thread_table[i] = NULL;

        is_start_os = false;
        interrupt_nesting = 0;
        os_time_tick = 0;
        current_top_prio = MAX_PRIO;
        total_csw_cnt = 0;
        total_thread_cnt = 0;
        current_thread = NULL;
        next_thread = NULL;

        /* create idle thread internally */
        thread_create(&idle_thread,
                        &idle_thread_stk[THREAD_STACK_SIZE-1],
                        idle_thread_func,
                        "idle-thread",
                        IDLE_THREAD_PRIO,
                        NULL);
}

CuRT在此處初始化task lists,不同task list代表task的狀態行為。ready_list[]表示共有MAX_PRIO個priority的ready list,每個priority會串接相同優先權的task,數字越小表示priority越高。delayed_list串接那些在等待timer喚起的task。bloacked_list則是串接等待其它resource(如:sem)釋放的那些task。接下來則是一些統計用的參數,以及幾個會影響CuRT運作的關鍵flags與物件,我們先記住它們的初始值即可,用到時再來看看行為會如何改變。接著,則是創建了一個最低優先權的task作為cpu idle時要運行的動作(等等我們就可看到,CuRT採取簡單的priority-based round robin排程策略,所以只要有更高優先權的task位於ready_list中,idle_thread就不會被執行到)。

OK,是時候觀察關鍵的thread_create()了:

/**
 * @brief Create thread
 *
 * @param thread - thread of the information contained threads structure
 * @param thread_stk - Created a pointer to the thread stack space
 * @param func - Generated a thread of the function
 * @param name - Thread name
 * @param prio - The priority of threads
 * @param pdata - Pass parameters to the function of a thread running
 * @retval RET_NO_ERR
 * @retval RET_ERR
 */
tid_t thread_create(thread_struct *thread,
                    stk_t *thread_stk,
                    THREAD_FUNC func,
                    char *name,
                    u8_t prio,
                    void *pdata)
{
        cpu_sr_t cpu_sr;
        stk_t *pstk;
        thread_struct *pthread;
        tid_t tid;

        if (thread == NULL || thread_stk == NULL || func == NULL ||
            name == NULL || (prio >= MAX_PRIO))
                return RET_ERR;

        pstk = thread_stk;
        pthread = thread;

        /* no failback */
        if ((tid = get_tid()) == RET_ERR) {
                return RET_ERR;
        }

        /* constrct thread_struct */
        pthread->tid = tid;
        pthread->stack_ptr = init_thread_stack(func, pdata, pstk);
        pthread->name = name;
        pthread->prio = prio;
        pthread->time_quantum = TIME_QUANTUM;
        pthread->delayed_time = 0;
        pthread->state = READY;

        /**
            since thread_create() might be called after OS running,
            some thread management datastructure sould be protected, here use irq & fiq disabled */
        cpu_sr = save_cpu_sr();
        thread_table[tid] = pthread;
        prio_exist_flag[prio] = true;
        total_thread_cnt++;
        insert_back_list(&ready_list[prio], &pthread->node);
        restore_cpu_sr(cpu_sr);

        /* if priority higher than existing thread, invoke the scheduler. */
        if (is_start_os == true && current_thread->prio > prio) {
                schedule(SCHED_THREAD_REQUEST);
        }
        return tid;
}

CuRT透過此function建構一個thread,使其擁有獨立的stack,在init_thread_stack()中,我們可以看到,CuRT將r0-12, r14, r15以及cpsr都給予了初始值,r13則存於thread_struct中的stack_ptr欄位。其中pc(r15)初始指向thread_func,所以一旦發生context switch時,就會跳入該function開始執行。剩下動作則是初始化基本欄位,並將task串入適當的ready_list中。最後,由於is_start_os目前設為false,所以暫且先不進行任何scheduling。

接著,我們回到main(),發現CuRT繼續串入更多task。串完後,接著就是啟動的時刻了:

void start_curt()
{
        cpu_sr_t cpu_sr;
        list_node_t *pnode;
        int top_prio;

        cpu_sr = save_cpu_sr();
        is_start_os = true;
        /* examine the highest priority thread executed */
        top_prio = get_top_prio();
        pnode = delete_front_list(&ready_list[top_prio]);
        if (is_empty_list(&ready_list[top_prio]))
                prio_exist_flag[top_prio] = false;
        current_thread = entry_list(pnode, thread_struct, node);
        current_thread->state = RUNNING;
        restore_cpu_sr(cpu_sr);
        restore_context();
}

save_cpu_sr()基本上就是讀出cpsr,同時關閉中斷,由於CuRT是由timer interrupt驅動scheduling,關閉中斷也就表示關閉CuRT主動執行context switch的動作。接下來則挑出目前ready_list[]中最高priority的ready_list中的第一個task,將其設定為current_thread,然後打開中斷(注意,此時timer interrupt仍未啟動),restore_context()負責將current_thread的context(存於current_thread的stack中)恢復:

/**
 * @brief Restore the context of the current thread.
 *
 * In multi-tasking environment, restore the context of the thread.
 * @param
 * @retval
 */
restore_context:
        ldr r4, =current_thread            // sp = current_thread->sp
        ldr r4, [r4]
        add r4, r4, #8
        ldr sp, [r4]

        ldr r4, [sp], #4
        msr SPSR_cxsf, r4
        ldmfd sp!, {r0-r12, lr, pc}^

還記得main()中開啟了哪幾個thread嗎?總共六個。包括一個idle thread與五個application threads。其中info_thread與stat_thread優先權最高(都是1),所以啟動後優先執行,而由於到此時timer interrupt都還沒啟動,所以我們可以看到info_thread與stat_thread在印出基本訊息後,都呼叫了thread_suspend()以讓出CPU,進行重新scheduling。

前兩個threads執行完後,接著優先權就輪到了shell_thread。shell_thread一開始呼叫的init_os_timer()才正式起動了preemptive scheduling的機制。從此,若有更高優先權的task被加入時,高優先權的task在被創建時(透過thread_create()),就會判斷一次是否要插入目前正在執行中的task:

tid_t thread_create(thread_struct *thread,
                    stk_t *thread_stk,
                    THREAD_FUNC func,
                    char *name,
                    u8_t prio,
                    void *pdata)
{
...
        /* if priority higher than existing thread, invoke the scheduler. */
        if (is_start_os == true && current_thread->prio > prio) {
                schedule(SCHED_THREAD_REQUEST);
        }
        return tid;
}

若沒有任何新增task,則最高優先權task則會無止盡地執行下去,直到將自己的狀態改為blocked或delayed。

timer interrupt每次起來時,ARM會自動跳轉到arch/arm/mach-pxa/start.S:

irq_handler:
        b irq_service_routine

irq_service_routine會負責將目前context存進current_thread的stack中,然後跳到interrupt_handler()中,觀察目前是否有任何delayed task是否已經可被喚起。如果可以被喚起,就會將其擺回對應priority的ready_list(此處似乎是CuRT的一個bug?因為若priority高於current_thread,應該將其替換才是。)

至此,CuRT的整體流程就差不多結束了。果然是很"輕"啊~但是能夠隨手寫出關鍵RTOS行為作為教育之用,令人獲益良多,Jserv的確是個中高手。下一步呢?試著解答師大資訊系王老師所提出的幾個問題應該是不錯的練習。:-)

留言

這個網誌中的熱門文章

誰在呼叫我?不同的backtrace實作說明好文章

今天下班前一個同事問到:如何在Linux kernel的function中主動印出backtrace以方便除錯? 寫過kernel module的人都知道,基本上就是用dump_stack()之類的function就可以作到了。但是dump_stack()的功能是如何作到的呢?概念上其實並不難,慣用手法就是先觀察stack在function call時的變化(一般OS或計組教科書都有很好的說明,如果不想翻書,可以參考 這篇 ),然後將對應的return address一層一層找出來後,再將對應的function名稱印出即可(透過執行檔中的section去讀取函式名稱即可,所以要將KALLSYM選項打開)。在userspace的實作可參考Jserv介紹過的 whocallme 或對岸好手實作過的 backtrace() ,都是針對x86架構的很好說明文章。 不過從前面兩篇文章可以知道,只要知道編譯器的calling convention,就可以實作出backtrace,所以是否GCC有提供現成的機制呢?Yes, that is what __builtin_return_address() for!! 可以參考這篇 文章 。該篇文章還提到了其他可以拿來實作功能更齊全的backtrace的 程式庫 ,在了解了運作原理後,用那些東西還蠻方便的。 OK,那Linux kernel是怎麼做的呢?就是用頭兩篇文章的方式啦~ 每個不同的CPU架構各自手工實作一份dump_stack()。 為啥不用GCC的機制?畢竟...嗯,我猜想,除了backtrace以外,開發者還會想看其他register的值,還有一些有的沒的,所以光是GCC提供的介面是很難印出全部所要的資訊,與其用半套GCC的機制,不如全都自己來~ arm的實作 大致上長這樣,可以看到基本上就只是透過迭代fp, lr, pc來完成: 352 void unwind_backtrace (struct pt_regs * regs , struct task_struct *tsk) 353 { 354 struct stackframe frame ; 355 register unsigned long current_sp asm ( "

淺讀Linux root file system初始化流程

在Unix的世界中,file system佔據一個極重要的抽象化地位。其中,/ 所代表的rootfs更是所有後續新增file system所必須依賴前提條件。以Linux為例,黑客 Jserv 就曾經詳細說明過 initramfs的背後設計考量 。本篇文章不再重複背景知識,主要將追蹤rootfs初始化的流程作點整理,免得自己日後忘記。 :-) file system與特定CPU架構無關,所以我觀察的起點從init/main.c的start_kernel()開始,這是Linux作完基本CPU初始化後首先跳進的C function(我閱讀的版本為 3.12 )。跟root file system有關的流程羅列如下: start_kernel()         -> vfs_caches_init_early()         -> vfs_caches_init()                 -> mnt_init()                         -> init_rootfs()                         -> init_mount_tree()         -> rest_init()                 -> kernel_thread(kernel_init,...) 其中比較重要的是mnt_int()中的init_rootfs()與init_mout_tree()。init_rootfs()實作如下: int __init init_rootfs(void) {         int err = register_filesystem(&rootfs_fs_type);         if (err)                 return err;         if (IS_ENABLED(CONFIG_TMPFS) && !saved_root_name[0] &&                 (!root_fs_names || strstr(root_fs_names, "tmpfs"))) {          

kernel panic之後怎麼辦?

今天同事在處理一個陌生的模組時遇到kernel panic,Linux印出了backtrace,同事大致上可以知道是在哪個function中,但該function的長度頗長,短時間無法定位在哪個位置,在這種情況下,要如何收斂除錯範圍呢?更糟的是,由於加入printk會改變模組行為,所以printk基本上無法拿來檢查參數的值是否正常。 一般這樣的問題會backtrace的資訊來著手。從這個資訊我們可以知道在function中的多少offset發生錯誤,以x86為例(從 LDD3 借來的例子): Unable to handle kernel NULL pointer dereference at virtual address 00000000 printing eip: d083a064 Oops: 0002 [#1] SMP CPU:    0 EIP:    0060:[<d083a064>]    Not tainted EFLAGS: 00010246   (2.6.6) EIP is at faulty_write+0x4/0x10 [faulty] eax: 00000000   ebx: 00000000   ecx: 00000000   edx: 00000000 esi: cf8b2460   edi: cf8b2480   ebp: 00000005   esp: c31c5f74 ds: 007b   es: 007b   ss: 0068 Process bash (pid: 2086, threadinfo=c31c4000 task=cfa0a6c0) Stack: c0150558 cf8b2460 080e9408 00000005 cf8b2480 00000000 cf8b2460 cf8b2460        fffffff7 080e9408 c31c4000 c0150682 cf8b2460 080e9408 00000005 cf8b2480        00000000 00000001 00000005 c0103f8f 00000001 080e9408 00000005 00000005 Call Trace:  [<c0150558>] vfs