亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        進(jìn)程同步通信經(jīng)典問(wèn)題—讀者寫者問(wèn)題的算法分析與設(shè)計(jì)

        2021-07-22 07:07:54曾思源徐艷
        電子測(cè)試 2021年12期
        關(guān)鍵詞:信號(hào)量進(jìn)程優(yōu)先

        曾思源,徐艷

        (四川大學(xué)錦城學(xué)院計(jì)算機(jī)與軟件學(xué)院,四川成都,611731)

        關(guān)鍵字:讀者和寫者;同步通信;PV操作算法

        0 引言

        一個(gè)共享的數(shù)據(jù)集合,會(huì)面臨同時(shí)被多個(gè)進(jìn)程訪問(wèn)的情況。一個(gè)存儲(chǔ)器,一個(gè)數(shù)據(jù)庫(kù),亦或是內(nèi)存中的一個(gè)寄存器,都可以成為這個(gè)數(shù)據(jù)集合。其中一類進(jìn)程只有讀取數(shù)據(jù)的需求,且不會(huì)對(duì)數(shù)據(jù)進(jìn)行修改,我們稱此類進(jìn)程為讀進(jìn)程。而另外一類進(jìn)程會(huì)對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行修改,我們稱之為寫進(jìn)程。

        無(wú)論是多少個(gè)讀進(jìn)程存在,都不會(huì)對(duì)數(shù)據(jù)進(jìn)行修改,因此讀進(jìn)程是被允許同時(shí)訪問(wèn)的。但是寫進(jìn)程是不會(huì)被允許與其他讀/寫進(jìn)程同時(shí)訪問(wèn)數(shù)據(jù)集,因?yàn)檫@將違反Bernstein條件,破壞數(shù)據(jù)的完整性、正確性。

        1 讀者寫者問(wèn)題的算法分析

        1.1 信號(hào)量控制

        要實(shí)現(xiàn)讀寫進(jìn)程之間的互斥,我們首先想到的就是添加信號(hào)量。

        在操作系統(tǒng)中,信號(hào)量在解決多種多樣的進(jìn)程同步問(wèn)題起到了至關(guān)重要的作用,比如,信號(hào)量能夠保證兩個(gè)或者多個(gè)臨界區(qū)不被并發(fā)調(diào)用。同時(shí),信號(hào)量本質(zhì)上代表的,是某種資源的可利用數(shù)量。

        信號(hào)量只能通過(guò)初始化和兩個(gè)標(biāo)準(zhǔn)的原語(yǔ)來(lái)訪問(wèn)--作為OS核心代碼執(zhí)行,不受進(jìn)程調(diào)度的打斷[1]。P操作減少一個(gè)信號(hào)量的值,如果它的值大于零,進(jìn)程繼續(xù)執(zhí)行,否則就睡眠,等待喚醒;而V操作增加它的值,若有進(jìn)程在此信號(hào)量上睡眠,則喚醒之[2]。

        在該問(wèn)題當(dāng)中,我們首先嘗試使用信號(hào)量rw來(lái)達(dá)到我們的需求。因?yàn)樽x寫算法相同,所以以寫算法為例。信號(hào)量rw初始值賦為1。算法如下:

        寫進(jìn)程:

        1.2 存在的問(wèn)題

        假如此時(shí)有個(gè)讀進(jìn)程A進(jìn)入程序,首先會(huì)通過(guò)P(rw)拿走資源,然后進(jìn)入臨界區(qū)進(jìn)行讀文件操作。在此同時(shí),寫進(jìn)程B也試圖進(jìn)入程序,由于讀進(jìn)程A還沒(méi)有進(jìn)行V(rw),所以寫進(jìn)程B會(huì)被阻塞,只有當(dāng)讀進(jìn)程A通過(guò)V(rw)釋放掉資源,寫進(jìn)程B才能進(jìn)入臨界區(qū)。

        此算法的確解決了讀寫進(jìn)程之間的互斥問(wèn)題,但在此同時(shí),多個(gè)讀進(jìn)程之間也變成互斥訪問(wèn)了,并不滿足引言中所提出的需求,因此這種算法不能達(dá)到要求。

        1.3 改進(jìn)算法——讀者程序加入計(jì)數(shù)器實(shí)現(xiàn)讀者優(yōu)先

        我們通過(guò)1.1發(fā)現(xiàn),只加入一組信號(hào)量不能解決問(wèn)題。因此,在這里引入一個(gè)變量count,用來(lái)記錄當(dāng)前正在訪問(wèn)數(shù)據(jù)集的進(jìn)程的數(shù)量,進(jìn)而能更方便的解決后面的問(wèn)題。所有信號(hào)量初值均賦為1,count初值賦為0,寫進(jìn)程算法與1.1相同,因此不再贅述。實(shí)現(xiàn)如下:

        可以很明顯的看出,該算法與1.1最大的區(qū)別是在P(rw)和V(rw)操作的兩側(cè),加入了帶if檢測(cè)的count計(jì)數(shù)器。Count代表的是訪問(wèn)該進(jìn)程的讀進(jìn)程數(shù)量,進(jìn)入程序/退出程序時(shí)會(huì)進(jìn)行自動(dòng)的加減。If語(yǔ)句中的條件,目的是判斷當(dāng)前還有多少個(gè)讀進(jìn)程在訪問(wèn)臨界資源,如果是第一個(gè)進(jìn)程,便會(huì)通過(guò)P(rw)操作將寫進(jìn)程給阻塞掉。同時(shí),因?yàn)橛衖f的存在,不滿足條件的后來(lái)的讀進(jìn)程不會(huì)因?yàn)榍耙粋€(gè)讀進(jìn)程而阻塞在P(rw),從而實(shí)現(xiàn)了讀進(jìn)程之間的同步訪問(wèn)。

        需要特別注意的是,在控制count加減和加/解鎖操作的兩側(cè),都加入了新信號(hào)量mutex,保證count的增減和加/解鎖操作的連貫性。試想,假如沒(méi)有該信號(hào)量,此時(shí)進(jìn)來(lái)讀進(jìn)程A,剛進(jìn)行了P(rw)的操作,還沒(méi)來(lái)得及進(jìn)行count++的操作,又進(jìn)來(lái)另一個(gè)讀進(jìn)程B,此時(shí)的count還是為零,滿足if判斷的結(jié)果,試圖用P操作上鎖,但由于前一個(gè)進(jìn)程A沒(méi)有執(zhí)行V操作釋放信號(hào)量,所以進(jìn)程B就被阻塞了,這是不能被允許的。

        1.4 讀者優(yōu)先存在的問(wèn)題

        這種算法,基本實(shí)現(xiàn)了引言中的需求。但是弊端也很明顯,當(dāng)讀者進(jìn)程源源不斷的進(jìn)入,寫者進(jìn)程會(huì)一直處于等待資源的狀態(tài),也就是說(shuō),寫進(jìn)程會(huì)被“餓死”。因此這種算法不算是完美的,是一種優(yōu)先服務(wù)讀進(jìn)程的算法。

        1.5 進(jìn)一步改進(jìn)算法——寫者程序加入計(jì)數(shù)器實(shí)現(xiàn)寫者優(yōu)先

        在1.3中,單獨(dú)在讀進(jìn)程中加入帶檢測(cè)的count變量,雖然解決了一部分問(wèn)題,但也帶來(lái)了新的問(wèn)題。所以我們現(xiàn)在試著將count計(jì)數(shù)器變量加在寫者進(jìn)程。需要特別注意的是,要同時(shí)滿足引言中讀-讀同步訪問(wèn)的要求的話,我們就不能像在1.3中,將count單獨(dú)加入到寫進(jìn)程中。因此,我們要在1.3的基礎(chǔ)上,在寫進(jìn)程這邊添加帶if檢測(cè)的count變量。

        count在寫進(jìn)程中也是起到統(tǒng)計(jì)其進(jìn)程數(shù)量的作用,當(dāng)寫進(jìn)程的數(shù)量滿足條件的時(shí)候,我們能讓其主動(dòng)的做一定的操作,而不是被動(dòng)的將資源讓給一直涌入的讀進(jìn)程。以下變量初值與1.3相似,讀進(jìn)程算法與1.3相同,在此不再贅述。實(shí)現(xiàn)如下:

        在這里,讀寫進(jìn)程的count變量起到了類似的作用,下面以實(shí)例驗(yàn)證之。

        假如此時(shí)有三個(gè)程序:讀進(jìn)程A,寫進(jìn)程B,讀進(jìn)程C依次進(jìn)入隊(duì)列。我們假設(shè)讀進(jìn)程A此時(shí)已經(jīng)進(jìn)入臨界區(qū),正在讀取數(shù)據(jù),那該進(jìn)程一定經(jīng)過(guò)了P(mutex2),P(mutex1),P(mutex),P(rw),V(mutex),V(mutex1),V(mutex2) 這些操作。此時(shí)如果寫進(jìn)程B也想訪問(wèn)臨界區(qū)資源,由于此時(shí)寫進(jìn)程B是第一個(gè)到達(dá)的該類進(jìn)程,能通過(guò)if的檢測(cè),將會(huì)占用信號(hào)量mutex1。但是由于讀進(jìn)程還在臨界區(qū),并沒(méi)有釋放信號(hào)量rw,所以寫進(jìn)程會(huì)被阻塞。在此同時(shí),新加入的讀進(jìn)程C,一定會(huì)經(jīng)過(guò)P(mutex2),但是由于寫進(jìn)程沒(méi)有釋放mutex1,所以讀進(jìn)程C也會(huì)被阻塞。只有當(dāng)讀進(jìn)程A釋放掉信號(hào)量P(rw)的時(shí)候,才會(huì)將寫進(jìn)程B喚醒,進(jìn)行寫操作。寫進(jìn)程B完成操作后,會(huì)再次檢測(cè)后面是否還有寫進(jìn)程,如果沒(méi)有,才會(huì)釋放掉信號(hào)量mutex1。后面的讀進(jìn)程才有機(jī)會(huì)進(jìn)行臨界區(qū)。

        1.6 寫者優(yōu)先存在的問(wèn)題

        顯然,這種算法是一種寫者優(yōu)先的算法。只要存在寫進(jìn)程,就會(huì)阻塞后來(lái)的讀進(jìn)程。同時(shí)假如存在多個(gè)讀寫程序,系統(tǒng)也會(huì)優(yōu)先喚醒寫進(jìn)程。

        2 另一種公平的讀者寫者算法

        上面的所有算法,在實(shí)現(xiàn)需求的同時(shí),都有所偏袒,面對(duì)極端情況下會(huì)出現(xiàn)問(wèn)題。所以我們決定按照進(jìn)程到達(dá)的先后順序,進(jìn)行算法的實(shí)現(xiàn),以下算法變量初值與前篇類似。此算法部分內(nèi)容與1.3有重復(fù)之處,同時(shí)由于篇幅有限,因此在此簡(jiǎn)單描述增加的信號(hào)量:在1.3的寫進(jìn)程基礎(chǔ)上,首尾增加信號(hào)量w;在1.3讀進(jìn)程的第一個(gè)信號(hào)量mutex前后增加信號(hào)量w。

        下面是該算法的分析。

        在1.3中,我們發(fā)現(xiàn)只要有讀進(jìn)程存在,信號(hào)量rw的使用權(quán)就會(huì)一直在讀進(jìn)程手中,這種情況在加入信號(hào)量w后發(fā)生了改變:我們發(fā)現(xiàn),即使是后進(jìn)來(lái)的寫進(jìn)程,也能通過(guò)搶占信號(hào)量w來(lái)保證自己不被“餓死”,且進(jìn)程之間的執(zhí)行順序完全是按照搶占w的順序,即進(jìn)入隊(duì)列的先后順序。同時(shí)此算法也滿足引言中的其他需求,類似于是一種“先來(lái)先服務(wù)”的算法,不會(huì)造成讀/寫進(jìn)程的“饑餓”,也能提高系統(tǒng)的效率。

        3 讀者寫者問(wèn)題的實(shí)際應(yīng)用

        各類聯(lián)網(wǎng)售票系統(tǒng)會(huì)難以避免的遇到頻繁的數(shù)據(jù)查詢和更新請(qǐng)求。此時(shí)的查詢請(qǐng)求,比如多個(gè)消費(fèi)者試圖查看剩余售票情況是允許的。但系統(tǒng)允許一條更新請(qǐng)求執(zhí)行的過(guò)程中,此時(shí)則其他所有請(qǐng)求都不能被允許。否則就會(huì)出現(xiàn)一張票被賣出多次的情況。

        猜你喜歡
        信號(hào)量進(jìn)程優(yōu)先
        基于STM32的mbedOS信號(hào)量調(diào)度機(jī)制剖析
        債券市場(chǎng)對(duì)外開(kāi)放的進(jìn)程與展望
        40年,教育優(yōu)先
        商周刊(2018年25期)2019-01-08 03:31:08
        Nucleus PLUS操作系統(tǒng)信號(hào)量機(jī)制的研究與測(cè)試
        多端傳播,何者優(yōu)先?
        站在“健康優(yōu)先”的風(fēng)口上
        優(yōu)先待遇
        社會(huì)進(jìn)程中的新聞學(xué)探尋
        我國(guó)高等教育改革進(jìn)程與反思
        μC/OS- -III對(duì)信號(hào)量的改進(jìn)
        风韵人妻丰满熟妇老熟女视频| 国产在线丝袜精品一区免费| 18无码粉嫩小泬无套在线观看| 少妇被猛男粗大的猛进出| 热の国产AV| 亲少妇摸少妇和少妇啪啪| 嫩呦国产一区二区三区av| 免费人妻无码不卡中文字幕系| 国产人碰人摸人爱视频| 久久人妻av无码中文专区| 漂亮人妻出轨中文字幕| 一本丁香综合久久久久不卡网站| 久久99精品国产99久久6男男| 国产成人综合久久精品推荐免费| 免费人妻精品一区二区三区 | 精品国产青草久久久久福利| 久久久精品人妻一区亚美研究所 | 国产伦理自拍视频在线观看| 精品国产日韩一区2区3区| 欧美成人精品午夜免费影视| 久久久久久人妻精品一区百度网盘 | 国产精品乱码在线观看| 国产精品,在线点播影院| 日韩精品一区二区三区乱码| 亚洲国产精品久久人人爱 | 久久成人影院精品777| 亚洲伊人久久一次| 亚洲综合色视频在线免费观看 | 亚洲成av人影院| 无遮挡网站| 亚洲一区二区三区1区2区| 99久久无色码中文字幕人妻蜜柚| 日韩人妻无码一区二区三区久久99| 97超级碰碰碰久久久观看| 激情五月开心五月啪啪| 综合色区亚洲熟妇另类| 四虎精品成人免费观看| 亚洲av日韩av天堂久久不卡| 欧洲熟妇色xxxx欧美老妇性| 婷婷开心深爱五月天播播| 青青草国内视频在线观看|