不用鎖實(shí)現(xiàn)隊(duì)列讀寫(xiě)？

yuhang001

今日去面試，面試官說(shuō)不用鎖實(shí)現(xiàn)一個(gè)隊(duì)列，這個(gè)隊(duì)列只有一個(gè)進(jìn)程讀和一個(gè)進(jìn)程寫(xiě)，應(yīng)該怎樣實(shí)現(xiàn)呢？

zliming

CPU在操作同一個(gè)內(nèi)存地址時(shí)會(huì)鎖住總線，這時(shí)不會(huì)中斷，也就不會(huì)線程切換。

這樣實(shí)現(xiàn)的

flyingtime

用signal符合要求不：
1、進(jìn)程1寫(xiě)隊(duì)列，直到隊(duì)列滿開(kāi)始發(fā)送一個(gè)信號(hào)給進(jìn)程2，此時(shí)進(jìn)程1開(kāi)始等待隊(duì)列不為滿的信號(hào)；
2、進(jìn)程2開(kāi)始時(shí)等待一個(gè)讀的信號(hào)，當(dāng)進(jìn)程1發(fā)給它一個(gè)信號(hào)時(shí)它將讀取隊(duì)列并刪除已讀的節(jié)點(diǎn)，同時(shí)發(fā)送信號(hào)給進(jìn)程1；
3、返回第一步

dreamice

原帖由 yuhang001 于 2009-5-5 23:32 發(fā)表
今日去面試，面試官說(shuō)不用鎖實(shí)現(xiàn)一個(gè)隊(duì)列，這個(gè)隊(duì)列只有一個(gè)進(jìn)程讀和一個(gè)進(jìn)程寫(xiě)，應(yīng)該怎樣實(shí)現(xiàn)呢？

只有一個(gè)進(jìn)程讀，一個(gè)進(jìn)程寫(xiě)，那就意味著不會(huì)出現(xiàn)并發(fā)的讀，和并發(fā)的寫(xiě)。于是，寫(xiě)的往隊(duì)列尾部寫(xiě)，讀的從隊(duì)列頭部度；寫(xiě)的時(shí)候，先判斷隊(duì)列是否滿了，如果沒(méi)滿，則寫(xiě)，寫(xiě)完了增加隊(duì)列計(jì)數(shù)；讀的時(shí)候，判斷隊(duì)列是否非空，非空的話，則讀出來(lái)后，再減少隊(duì)列元素計(jì)數(shù)。

daybreakcx

如果兼顧并行和防止隊(duì)空的操作的話設(shè)置一個(gè)對(duì)首指針和一個(gè)隊(duì)尾指針，為了防止并行使得數(shù)據(jù)錯(cuò)亂，我想使用鏈表結(jié)構(gòu)
入隊(duì)的時(shí)候申請(qǐng)空間，然后寫(xiě)入數(shù)據(jù)，再把對(duì)尾指針延后
出隊(duì)的時(shí)候如果非空，先把隊(duì)尾指針后移，這樣操作類(lèi)似于出隊(duì)?wèi)?yīng)該不會(huì)出現(xiàn)并行問(wèn)題
同時(shí)對(duì)于同一個(gè)隊(duì)列空間是互斥操作，因?yàn)榭臻g都是鏈表獨(dú)立的，一旦出隊(duì)就訪問(wèn)不到了，而且入隊(duì)的時(shí)候先申請(qǐng)空間填好然后才入隊(duì)，也避免了兩個(gè)寫(xiě)進(jìn)程往隊(duì)列同一塊空間寫(xiě)，個(gè)人認(rèn)為應(yīng)該可以的
不對(duì)的請(qǐng)指正

[ 本帖最后由 daybreakcx 于 2009-5-6 10:15 編輯 ]

cookis

IPC 呀，用消息隊(duì)列不行嗎？

zliming

http://b.cnc.qzone.qq.com/cgi-bi ... imestamp=1241579164

我試寫(xiě)了一個(gè)，不知道會(huì)不會(huì)出錯(cuò)，10000的數(shù)字排的正確

daybreakcx

樓上效率不低啊，這么快就發(fā)日志了

虎皮尖椒

除非說(shuō)的是可以使用隱含的鎖或者自己實(shí)現(xiàn)鎖，不然樓上幾位的做法都不能解決并發(fā)沖突。

zliming

了解的比較模糊：
多CPU多核操作總線，在北橋芯片里面就已經(jīng)固化了一個(gè)鎖了。
對(duì)同一內(nèi)存地址操作(讀后寫(xiě))已經(jīng)是有l(wèi)ock free