Python實現(xiàn)調(diào)度算法代碼詳解
調(diào)度算法
操作系統(tǒng)管理了系統(tǒng)的有限資源,當(dāng)有多個進程(或多個進程發(fā)出的請求)要使用這些資源時,因為資源的有限性,必須按照一定的原則選擇進程(請求)來占用資源。這就是調(diào)度。目的是控制資源使用者的數(shù)量,選取資源使用者許可占用資源或占用資源。
在操作系統(tǒng)中調(diào)度是指一種資源分配,因而調(diào)度算法是指:根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的的系統(tǒng)和系統(tǒng)目標(biāo),通常采用不同的調(diào)度算法,例如,在批處理系統(tǒng)中,為了照顧為數(shù)眾多的段作業(yè),應(yīng)采用短作業(yè)優(yōu)先的調(diào)度算法;又如在分時系統(tǒng)中,為了保證系統(tǒng)具有合理的響應(yīng)時間,應(yīng)當(dāng)采用輪轉(zhuǎn)法進行調(diào)度。目前存在的多種調(diào)度算法中,有的算法適用于作業(yè)調(diào)度,有的算法適用于進程調(diào)度;但也有些調(diào)度算法既可以用于作業(yè)調(diào)度,也可以用于進程調(diào)度。
目標(biāo)闡述:
將中綴表達式轉(zhuǎn)換為后綴表達式(Reverse Polish Notation:RPN 逆波蘭式)
參與運算的數(shù)據(jù)的正則表示為:[0-9]{1,}形式的十進制數(shù)
運算符優(yōu)先級:(從高到低)———————————————————————— ( ) 括號 / * % 除乘余 + - 加減————————————————————————
解:
第一步:使用正則詞法分析器flex生成一個詞法分析器,以處理輸入的中綴表達式。
從stdin接收輸入,檢測非法字符,并將處理后的中綴表達式輸出到stdout。
%option noyywrap %{ #include<stdio.h> #include<stdlib.h>%} %% [0-9]+ { printf("%s ",yytext); } [()*/%+-] { printf("%s ",yytext); } [[:space:]] {} . { printf("\nError\n");exit(1); } %% int main() { yylex(); printf("\n"); return 0; }
第二步:使用Python進行轉(zhuǎn)換。
從stdin接收一定格式的中綴表達式字符流,檢測是否在詞法分析器處理過程中出錯,然后使用調(diào)度場算法處理數(shù)據(jù),得到rpn列表。
import sys line=sys.stdin.readline() line2=sys.stdin.readline() if len(line2)>0: sys.stderr.write("Syntax Error after : ") sys.stderr.write(line) sys.stderr.write("\n") exit(1) lis=line.split(' ') lis.pop() lis_old=lis[:] lis.reverse() oplis=[] rpnlis=[] str='' arith_op="+-*/%" # '(' ')' [0-9]+ prior={ '/':1,'*':1,'%':1, '+':2,'-':2 } while len(lis)>0: str=lis.pop() if str=='(': oplis.append('(') elif str.isdigit(): rpnlis.append(str) elif len(str)==1 and arith_op.find(str[0])!=-1: if len(oplis)==0 or oplis[len(oplis)-1]=='(': oplis.append(str) else: while len(oplis)>0 and oplis[len(oplis)-1]!='(' \ and prior[oplis[len(oplis)-1]]<=prior[str]: rpnlis.append(oplis.pop()) oplis.append(str) elif str==')': while len(oplis)>0 and oplis[len(oplis)-1]!='(': rpnlis.append(oplis.pop()) if len(oplis)>0: oplis.pop() else: sys.stderr.write("Syntax Error while translating : Expected '('") sys.stderr.write("\n") exit(2) else: sys.stderr.write("Syntax Error : unkown notation -->") sys.stderr.write(str) sys.stderr.write("\n") exit(3) while len(oplis)>0 : if oplis[len(oplis)-1]!='(': rpnlis.append(oplis.pop()) else: sys.stderr.write("Syntax Error while translating : Unexpected '('") sys.stderr.write("\n") exit(1) print lis_old for i in lis_old: sys.stdout.write(i) print '' print rpnlis for i in rpnlis: print i, print '' exit(0)
實驗結(jié)果:
目前程序的局限:
未進行語法檢測。
不支持函數(shù)、變量標(biāo)識。
附錄:
算法示意圖,使用了3個空間。輸入用符號代替,如果輸入是一個數(shù)字則直接進輸出隊列,即圖中 b),d),f),h)。如果輸入是運算符,則壓入操作符堆棧,即圖中 c),e),但是,如果輸入運算符的優(yōu)先級低于或等于運算符棧頂?shù)牟僮鞣麅?yōu)先級,則棧內(nèi)元素進入輸出隊列(循環(huán)判定),輸入操作符壓入運算符堆棧,即圖中 g)。 最后,運算符堆棧內(nèi)元素入輸出隊列,算法結(jié)束。
附錄中資料摘自維基百科•調(diào)度場算法詞條。
總結(jié)
以上就是本文關(guān)于Python實現(xiàn)調(diào)度算法代碼詳解的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題,如有不足之處,歡迎留言指出!
- Python利用multiprocessing實現(xiàn)最簡單的分布式作業(yè)調(diào)度系統(tǒng)實例
- 詳解python調(diào)度框架APScheduler使用
- Python使用Redis實現(xiàn)作業(yè)調(diào)度系統(tǒng)(超簡單)
- Python使用multiprocessing實現(xiàn)一個最簡單的分布式作業(yè)調(diào)度系統(tǒng)
- python編寫網(wǎng)頁爬蟲腳本并實現(xiàn)APScheduler調(diào)度
- Python中定時任務(wù)框架APScheduler的快速入門指南
- 簡單的Python調(diào)度器Schedule詳解
相關(guān)文章
python靜態(tài)web服務(wù)器實現(xiàn)方法及代碼詳解
在本篇內(nèi)容里小編給大家分享了一篇關(guān)于python靜態(tài)web服務(wù)器實現(xiàn)方法,有需要的朋友們可以參考下。2022-11-11Django的數(shù)據(jù)模型訪問多對多鍵值的方法
這篇文章主要介紹了Django的數(shù)據(jù)模型訪問多對多鍵值的方法,Django是Python豐富多彩的web框架中最具人氣的一個,需要的朋友可以參考下2015-07-07解決windows下Sublime Text 2 運行 PyQt 不顯示的方法分享
問題描述:PyQt 環(huán)境正常,可以使用 Windows 的 虛擬 DOS 正常運行,但在 Sublime Text 2 下使用 Ctrl + B 運行后,界面不顯示,但查看任務(wù)管理器,有 python.exe 進程。2014-06-06python+elasticsearch實現(xiàn)標(biāo)簽匹配計數(shù)操作
這篇文章主要介紹了python+elasticsearch實現(xiàn)標(biāo)簽匹配計數(shù)操作,本文通過實例代碼給大家介紹的非常詳細,需要的朋友可以參考下2024-04-04