Python實(shí)現(xiàn)調(diào)度算法代碼詳解

2020-01-04 16:12:45

字體：大中小

供稿：網(wǎng)友

調(diào)度算法

操作系統(tǒng)管理了系統(tǒng)的有限資源，當(dāng)有多個(gè)進(jìn)程（或多個(gè)進(jìn)程發(fā)出的請求）要使用這些資源時(shí)，因?yàn)橘Y源的有限性，必須按照一定的原則選擇進(jìn)程（請求）來占用資源。這就是調(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)度算法；又如在分時(shí)系統(tǒng)中，為了保證系統(tǒng)具有合理的響應(yīng)時(shí)間，應(yīng)當(dāng)采用輪轉(zhuǎn)法進(jìn)行調(diào)度。目前存在的多種調(diào)度算法中，有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度；但也有些調(diào)度算法既可以用于作業(yè)調(diào)度，也可以用于進(jìn)程調(diào)度。

目標(biāo)闡述：

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式（Reverse Polish Notation：RPN 逆波蘭式）
參與運(yùn)算的數(shù)據(jù)的正則表示為：[0-9]{1,}形式的十進(jìn)制數(shù)

運(yùn)算符優(yōu)先級：（從高到低）————————————————————————( )   括號/ * %  除乘余+ -   加減————————————————————————

解：

第一步：使用正則詞法分析器flex生成一個(gè)詞法分析器，以處理輸入的中綴表達(dá)式。
從stdin接收輸入，檢測非法字符，并將處理后的中綴表達(dá)式輸出到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進(jìn)行轉(zhuǎn)換。

從stdin接收一定格式的中綴表達(dá)式字符流，檢測是否在詞法分析器處理過程中出錯(cuò)，然后使用調(diào)度場算法處理數(shù)據(jù)，得到rpn列表。

import sysline=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_oldfor i in lis_old:  sys.stdout.write(i)print ''print rpnlisfor i in rpnlis:  print i,print ''exit(0)

實(shí)驗(yàn)結(jié)果：

python,調(diào)度算法,python調(diào)度算法代碼

目前程序的局限：
未進(jìn)行語法檢測。
不支持函數(shù)、變量標(biāo)識。

附錄：

python,調(diào)度算法,python調(diào)度算法代碼

算法示意圖，使用了3個(gè)空間。輸入用符號代替，如果輸入是一個(gè)數(shù)字則直接進(jìn)輸出隊(duì)列，即圖中 b),d),f),h)。如果輸入是運(yùn)算符，則壓入操作符堆棧，即圖中 c),e)，但是，如果輸入運(yùn)算符的優(yōu)先級低于或等于運(yùn)算符棧頂?shù)牟僮鞣麅?yōu)先級，則棧內(nèi)元素進(jìn)入輸出隊(duì)列（循環(huán)判定），輸入操作符壓入運(yùn)算符堆棧，即圖中 g)。最后，運(yùn)算符堆棧內(nèi)元素入輸出隊(duì)列，算法結(jié)束。

python,調(diào)度算法,python調(diào)度算法代碼