8

このようなtxtファイルからモックプロセスを読み取る割り当てが与えられました。

ID: 35; Arrival_Time: 0; Total_Exec_Time: 4;
ID: 65; Arrival_Time: 2; Total_Exec_Time: 6;
ID: 10; Arrival_Time: 3; Total_Exec_Time: 3;
ID: 124; Arrival_Time: 5; Total_Exec_Time: 5;
ID: 182; Arrival_Time: 6; Total_Exec_Time: 2;

(先着順、最短プロセス次、最短残り時間、ラウンド ロビン q=2) の選択肢から 2 つのアルゴリズムを完了する必要があります。選択した 2 つのアルゴリズムに基づいて、現在の時刻とその時点で実行されているプロセスを出力する必要があります。私は FCFS を無事に完了しました。私の次のアプローチは SRT です。ただし、アルゴリズムの背後にあるロジックに深刻な問題が発生しています。

私は現在、ある程度（現在の時間9まで）機能する反復アプローチ（以下に投稿）を試みていますが、それは幸運な偶然かもしれないと感じています.

このアルゴリズム、または他の2つのうちの1つについて、誰か提案がありますか。私はこの仕事に数日間取り組んできましたが、プライドを捨ててスタックに投稿することにしました。

注: シェル スクリプトを使用するのはこれが初めてなので、私のコードは少し面倒かもしれません。私はまだ KornShell (ksh) を理解しようとしています。

file="/path/to/file.txt"
  IFS=': \;'
  i=0
  while read -r f1 f2 f3 f4 f5 f6  
    do 
      integer id[i]="$f2" #id array
      integer at[i]="$f4" #arrival time array
      integer et[i]="$f6" #exec time array
      integer rt[i]=0 #run time so far
      integer current[i]=i

      ((i++))
    done <"$file"

  integer curr_index=0
  integer currTime=0
  let totalProcesses=${#at[@]}
  let totalProcesses=totalProcesses-1
  let totalRunTime=0
  for x in ${et[@]}; do
    let totalRunTime+=$x
  done 

  scheduleTask () { 
    currTime=$1
    for y in ${current[@]}; do
      if (( rt[$y] < et[$y] )); then
        #if the program is not finished, keep going
        if (( at[$y] < $currTime )); then
          #if the program is in que, keep going
          let diff=et[$y]-rt[$y]#not currently using
          let currDiff=et[$curr_index]-rt[$curr_index] #not currently using         
          if (( et[$y] <= et[$curr_index] )); then #is this broken?
            curr_index=$y
          fi
        fi
      else
        echo "${id[$y]} RAN ${rt[$y]} out of ${et[$y]} seconds"

        unset current[$y]
      fi
    done
  }

  for (( i = 0; i < $totalRunTime; i++ )); do
    echo "================================="
    scheduleTask $i 
    ((rt[$curr_index]++))
    print "\t\tcurrent time: $i"
    print "\t\t\tcurrent process: ${id[$curr_index]}"
    echo "================================="
  done

SRT の適切な出力は次のようになります。

=================================
        current time: 0
            current process: 35
=================================
=================================
        current time: 1
            current process: 35
=================================
=================================
        current time: 2
            current process: 35
=================================
=================================
        current time: 3
            current process: 35
=================================
=================================
        current time: 4
            current process: 10
=================================
=================================
        current time: 5
            current process: 10
=================================
=================================
        current time: 6
            current process: 10
=================================
=================================
        current time: 7
            current process: 182
=================================
=================================
        current time: 8
            current process: 182
=================================
=================================
        current time: 9
            current process: 124
=================================
=================================
        current time: 10
            current process: 124
=================================
=================================
        current time: 11
            current process: 124
=================================
=================================
        current time: 12
            current process: 124
=================================
=================================
        current time: 13
            current process: 124
=================================
=================================
        current time: 14
            current process: 65
=================================
=================================
        current time: 15
            current process: 65
=================================
=================================
        current time: 16
            current process: 65
=================================
=================================
        current time: 17
            current process: 65
=================================
=================================
        current time: 18
            current process: 65
=================================
=================================
        current time: 19
            current process: 65
=================================
4

1 に答える 1

3

私はまだスタックオーバーフローに比較的慣れておらず、宿題についての考えや意見に無頓着でした。質問を削除することについて議論していましたが、この投稿 ( https://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions )を読んだ後、質問がガイドラインに適合していると判断しました。したがって、維持する価値があります。

最短残り時間アルゴリズムを見つけました。誰もこの質問に答えてくれなかったことに感謝しています。アルゴリズムを自分で (私の TA の助けを借りて) 考え出すことは価値がありました。したがって、提供された回答には基本的な疑似ロジックがあり、実際のコードはありません。

shortest = the first process read from the input(assuming it has already arrived)
while there are still processes to be run
     process = next process (out of processes that have not completed yet)
     if (process arrival time <= currentTime) #process arrived 
           if (process execution time < shortest execution time)
                 shortest = process

注: これは、TA (課題を書いた人) から受けた支援とほぼ同じです。そのため、この回答を投稿しても問題ないと思います。

于 2012-12-06T22:40:36.460 に答える