王亞軍 中國人民武裝警察部隊(duì)學(xué)院

Linux內(nèi)核優(yōu)先級倒轉(zhuǎn)分析

王亞軍 中國人民武裝警察部隊(duì)學(xué)院

Linux對于訪問同一內(nèi)核臨界區(qū)的多個(gè)進(jìn)程進(jìn)行同步的有效手段是內(nèi)核信號量機(jī)制。解決Linux內(nèi)核信號量操作中存在的優(yōu)先級倒轉(zhuǎn)問題，是將Linux運(yùn)用于實(shí)時(shí)系統(tǒng)的重要手段。文中在分析Linux內(nèi)核信號量操作源代碼的基礎(chǔ)上，結(jié)合嵌入式應(yīng)用深入分析其中存在的優(yōu)先級倒轉(zhuǎn)問題。

信號量 優(yōu)先級倒轉(zhuǎn) 嵌入式系統(tǒng) 等待隊(duì)列 實(shí)時(shí)性

1 引言

Linux內(nèi)核允許多個(gè)進(jìn)程并發(fā)執(zhí)行，從而極大限度地利用了CPU資源。但是為了避免多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，Linux內(nèi)核采取了嚴(yán)格的同步機(jī)制，信號量就是其中之一。如果一個(gè)進(jìn)程試圖獲得一個(gè)已經(jīng)被占用的信號量，該進(jìn)程就會被推進(jìn)一個(gè)等待隊(duì)列進(jìn)入“睡眠”狀態(tài)，從而釋放處理器，使處理器可以執(zhí)行其它進(jìn)程的代碼。當(dāng)持有信號量的進(jìn)程釋放信號量以后，在等待隊(duì)列中睡眠的進(jìn)程將被喚醒，并再次試圖獲得該信號量以進(jìn)入臨界區(qū)。

2 Linux內(nèi)核優(yōu)先級倒轉(zhuǎn)分析

在Linux-2.6.10內(nèi)核中，當(dāng)有多個(gè)進(jìn)程等待進(jìn)入一個(gè)臨界區(qū)時(shí)，當(dāng)前進(jìn)程略有優(yōu)勢，然后就是“先來先進(jìn)”，即先鏈入等待隊(duì)列的進(jìn)程先進(jìn)入臨界區(qū)，而進(jìn)程的優(yōu)先級并沒有起作用。也就是說，在這個(gè)等待隊(duì)列中，如果優(yōu)先級較低的進(jìn)程排在前面，而優(yōu)先級較高的進(jìn)程排在后面，那么優(yōu)先級較高的進(jìn)程就只能等待。Linux內(nèi)核實(shí)現(xiàn)了POSIX.4關(guān)于“實(shí)時(shí)進(jìn)程”調(diào)度的要求，支持執(zhí)行SCHED_FIFO、SCHED_RR和SCHED_OTHER三種不同的調(diào)度政策。適用于前兩種政策的進(jìn)程稱為實(shí)時(shí)進(jìn)程，而適用于SCHED_OTHER的則為面向分時(shí)應(yīng)用的普通進(jìn)程。由于實(shí)時(shí)進(jìn)程有較高的實(shí)時(shí)性要求，所以要將Linux內(nèi)核用于實(shí)時(shí)要求較高的嵌入式應(yīng)用，就應(yīng)該對等待進(jìn)入臨界區(qū)的進(jìn)程鏈表進(jìn)行優(yōu)化，減少實(shí)時(shí)進(jìn)程的等待時(shí)間。

從Linux-2.6.10內(nèi)核代碼中還可以看出，如果一個(gè)優(yōu)先級很低的進(jìn)程A已經(jīng)進(jìn)入某個(gè)臨界區(qū)，那么當(dāng)另一個(gè)優(yōu)先級很高的進(jìn)程B也要進(jìn)入該臨界區(qū)時(shí)，由于互斥信號量機(jī)制的阻攔而只能睡眠等待。由于互斥信號量所保護(hù)的臨界區(qū)內(nèi)允許進(jìn)程調(diào)度，已經(jīng)進(jìn)入某個(gè)臨界區(qū)的那個(gè)優(yōu)先級很低的進(jìn)程A一旦受阻進(jìn)入睡眠，再被喚醒時(shí)就很難得到機(jī)會運(yùn)行，因?yàn)橄到y(tǒng)中所有優(yōu)先級比A高但比B低的進(jìn)程都有可能擠在A的前面得到運(yùn)行。而進(jìn)程B盡管優(yōu)先級很高，卻反而只能等待這些進(jìn)程都交出運(yùn)行權(quán)，然后才能讓正在占用臨界區(qū)的進(jìn)程A完成其操作而退出臨界區(qū)。為了將Linux內(nèi)核用于實(shí)時(shí)要求較高的嵌入式應(yīng)用，也需要通過修改進(jìn)程優(yōu)先級的方法來解決優(yōu)先級倒轉(zhuǎn)問題。

3 Linux內(nèi)核優(yōu)先級倒轉(zhuǎn)解決方法

Linux-2.6.10內(nèi)核調(diào)度進(jìn)程的主要依據(jù)是進(jìn)程的優(yōu)先級，但又不是單純地按優(yōu)先級調(diào)度。普通進(jìn)程擁有一個(gè)初始的優(yōu)先級，即靜態(tài)優(yōu)先級，它從一開始由用戶指定后，就不能改變。而調(diào)度程序要用到的動態(tài)優(yōu)先級是通過一個(gè)關(guān)于靜態(tài)優(yōu)先級和進(jìn)程交互性的函數(shù)關(guān)系計(jì)算而來的。而對于實(shí)時(shí)進(jìn)程，它們所采用的是實(shí)時(shí)優(yōu)先級，內(nèi)核不為它們計(jì)算動態(tài)優(yōu)先級，這能保證給定優(yōu)先級別的實(shí)時(shí)進(jìn)程總能搶占優(yōu)先級比它低的進(jìn)程。SCHED_FIFO實(shí)現(xiàn)了一種簡單的、先入先出的調(diào)度算法，它不使用時(shí)間片。SCHED_FIFO級的進(jìn)程會比任何SCHED_OTHER級的進(jìn)程都先得到調(diào)度。一旦一個(gè)SCHED_FIFO級的進(jìn)程處于可執(zhí)行狀態(tài)，就會一直運(yùn)行，直到它自己受阻或顯式釋放處理器為止。SCHED_RR則是帶有時(shí)間片SCHED_FIFO，當(dāng)SCHED_RR級的進(jìn)程耗盡事先分配給它的時(shí)間片以后就不能繼續(xù)運(yùn)行了，這是一種實(shí)時(shí)輪流調(diào)度算法。

為了對等待進(jìn)入臨界區(qū)的進(jìn)程鏈表進(jìn)行改進(jìn)，減少實(shí)時(shí)進(jìn)程的等待時(shí)間，需要修改內(nèi)核中與此相關(guān)的源代碼，在將需要等待進(jìn)入臨界區(qū)的進(jìn)程鏈入到相應(yīng)的等待鏈表時(shí)，按照進(jìn)程的優(yōu)先級將其插入到鏈表中的適當(dāng)位置。由于內(nèi)核中需要在臨界區(qū)內(nèi)進(jìn)行的操作一般都是很短促的，而普通進(jìn)程又沒有較高的實(shí)時(shí)要求，所以這種改進(jìn)只對實(shí)時(shí)進(jìn)程來進(jìn)行。當(dāng)一個(gè)普通進(jìn)程等待進(jìn)入臨界區(qū)時(shí)，只是按照內(nèi)核中原來的安排，將其簡單地鏈入等待隊(duì)列的尾部。而對于實(shí)時(shí)進(jìn)程，則與進(jìn)程調(diào)度的思想相一致，按照實(shí)時(shí)優(yōu)先級從高到低的順序，將其插入到等待進(jìn)入臨界區(qū)的進(jìn)程鏈表之中。對于優(yōu)先級相同的實(shí)時(shí)進(jìn)程，仍然按照內(nèi)核中原來的安排，即先鏈入等待隊(duì)列的實(shí)時(shí)進(jìn)程先進(jìn)入臨界區(qū)。為此，需要對內(nèi)核中的相關(guān)源代碼進(jìn)行修改，將等待隊(duì)列分成兩個(gè)小的等待隊(duì)列。

4 結(jié)語

綜上所述，在Linux內(nèi)核中，信號量及其操作是內(nèi)核對訪問共享資源的多個(gè)進(jìn)程進(jìn)行同步的關(guān)鍵，對系統(tǒng)的性能具有重要影響。當(dāng)把linux內(nèi)核應(yīng)用于嵌入式系統(tǒng)時(shí)，由于嵌入式系統(tǒng)通常具有實(shí)時(shí)性要求，應(yīng)該對信號量操作中存在的優(yōu)先級倒轉(zhuǎn)情況進(jìn)行改進(jìn)，以提高內(nèi)核的實(shí)時(shí)性，這對于將Linux內(nèi)核應(yīng)用于具有實(shí)時(shí)性要求的嵌入式系統(tǒng)時(shí)是有意義的。

[1]毛德操,胡希明.Linux內(nèi)核源代碼情景分析[M].杭州:浙江大學(xué)出版社，2002.

[2]毛德操,胡希明.嵌入式系統(tǒng)[M].杭州:浙江大學(xué)出版社，2003.[3]彭曉明、王強(qiáng)編著，《Lniux核心源代碼分析》,北京,人民郵電出版社，2002

河北省科研基金項(xiàng)目支持(HBSZKT-2014143)。

王亞軍，1978年生，男，漢族，籍貫：黑龍江綏化市，單位：中國人民武裝警察部隊(duì)學(xué)院，副教授，碩士，研究方向：Linux操作系統(tǒng)。