快捷導(dǎo)航

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

更新時(shí)間：2017年12月01日 11:50:09 作者：燕云

這篇文章主要介紹了Python實(shí)現(xiàn)調(diào)度場(chǎng)算法代碼詳解，具有一定參考價(jià)值，需要的朋友可以了解下。

調(diào)度算法

操作系統(tǒng)管理了系統(tǒng)的有限資源，當(dāng)有多個(gè)進(jìn)程（或多個(gè)進(jìn)程發(fā)出的請(qǐng)求）要使用這些資源時(shí)，因?yàn)橘Y源的有限性，必須按照一定的原則選擇進(jìn)程（請(qǐng)求）來占用資源。這就是調(diào)度。目的是控制資源使用者的數(shù)量,選取資源使用者許可占用資源或占用資源。

在操作系統(tǒng)中調(diào)度是指一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對(duì)于不同的的系統(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)先級(jí)：（從高到低）————————————————————————
( )   括號(hào)
/ * %  除乘余
+ -   加減————————————————————————

解：

第一步：使用正則詞法分析器flex生成一個(gè)詞法分析器，以處理輸入的中綴表達(dá)式。
從stdin接收輸入，檢測(cè)非法字符，并將處理后的中綴表達(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á)式字符流，檢測(cè)是否在詞法分析器處理過程中出錯(cuò)，然后使用調(diào)度場(chǎng)算法處理數(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)

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

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

附錄：

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