7

Java で CPU スケジューリング アルゴリズムをシミュレートしようとしており、マルチスレッドを使用しています。私は FCFS (先着順) と SJF (Shortest Job First) の実装に成功しました。しかし、問題は、SJF の先制的な形式である SRTF (Shortest Remaining Time First) について考え始めたときです。次のモデルを使用しています。

  • CLOCK刻々と刻み続ける (単純なクロックのインクリメント) 変数を持つ CPU のスレッド100ms。プロセスが実行を開始する前に CPU が使用可能かどうかをチェックするためのboolean isAvailable;フラグがあります。
  • プロセスをプロセス リストから Ready Queue にプッシュする Long Term Scheduler (LTS) のスレッド。
  • ReadyQueue からプロセスを取得して CPU に割り当てる Short Term Scheduler (STS) のスレッド。
  • プロセスが実行のために STS によって ReadyQueue から削除されると、プロセスはisAvailableCPU のフラグをチェックします。の場合、フラグを false に設定し、その実行を開始します (これは単なるシミュレーションであるtrueため、スレッドをスリープ状態にするだけです)。(100 * burstTime) msそれ以外の場合、プロセスはビジー状態で待機し続けます: while(CPU.isAvailable != true);.

プロセスのリストとその到着時間とバースト時間を事前に持っています。非プリエンプティブ スケジューリング (FCFS および SJF) をシミュレートするまでは問題ありません。しかし、SRTF を試してみると、現在実行中のプロセス スレッドをプリエンプトする方法が見つかりません。

SRTF については、ReadyQueue から次のプロセスを選択する方法を知っています。isAvailableキューからプロセスを選択したらフラグを設定しようとすることはできfalseますが、どのスレッドが最初に実行されていたかを知るにはどうすればよいですか? また、同期白黒スレッドをあまり使用していないため、CPUスレッドを使用する複数のプロセスがあります。少し混乱しています。助けてください。ありがとう！

これはプロセスのコードです:

enum State {ARRIVED, WAITING, READY, RUNNING, EXECUTED}
public class Process implements Runnable
{
    int pid;
    int arrTime;
int burstTime;
int priority;
long startTime;
long endTime;
State procState = null;

Process(int pid, int arrTime, int burstTime, int priority)
{
    this.pid = pid;
    this.arrTime = arrTime;
    this.burstTime = burstTime;
    this.priority = priority;
    this.procState = State.ARRIVED;
    this.startTime = 0;


    this.endTime = 0;    /* I also considered adding a timeElapsedUnderExecution
 attribute to the process. So I can check after every cycle if the CPU is still available
 and keep incrementing the time elapsed. Once the timeElapsed becomes same as burstTime, i
 stop the process. Or if after a cycle, the CPU is not available, i know from where to
 resume my Process. Is this the way to go ? */

    }

boolean isReady()
{
    if((this.arrTime <= CPU.CLOCK) && (this.procState == State.ARRIVED))
        return true;
    else return false;
}

@Override
public void run() {
    // TODO Auto-generated method stub
    if(this.procState == State.READY)
        this.procState = State.WAITING;

    while(!CPU.isAvailable());

    try 
    {
        this.procState = State.RUNNING;
        System.out.println("Process " + pid + " executing...");
        this.startTime = CPU.CLOCK;
        System.out.println("Process " + this.pid + ": Begins at " + this.startTime);
        Thread.sleep(this.burstTime * 100);
        this.endTime = CPU.CLOCK;
        System.out.println("Process " + this.pid + ": Ends at " + this.endTime);
        this.procState = State.EXECUTED;

    }
    catch (InterruptedException e) 
    {
        // TODO Auto-generated catch block
        System.out.println("Interrupted: " + pid);
        e.printStackTrace();
    }
    }
}

CPU のコード:

    import java.util.LinkedList;
    import java.util.Queue;

    public class CPU implements Runnable

{
    static Long CLOCK = new Long(0);
    static LinkedList<Process> ReadyQ = new LinkedList<Process>();
private static boolean isAvailable = true;
static boolean done = false;

public static boolean isAvailable() {
    return isAvailable;
}

public static void setAvailable(boolean isAvailable) {
    CPU.isAvailable = isAvailable;
}

static void incrementCLOCK()
{
    LTS.checkArrival();
    CPU.CLOCK++;
    try {
        Thread.sleep(100);
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    System.out.println("Clock Tick: " + CPU.CLOCK);
}

@Override
public void run() {
    // TODO Auto-generated method stub
    System.out.println("CPU starts.!!!");
    while(CPU.done != true)
        synchronized(CPU.CLOCK)
        {
            incrementCLOCK();
            }
    }
}

LTS のコード:

public class LTS implements Runnable 
{
    private static Process[] pList = null;
    private final int NUM;
    static Integer procStarted;
    static Integer procFinished;
    static boolean STSDone = false;


LTS(Process[] pList, int num)
{
    this.NUM = num;
    LTS.pList = pList;
}

static void checkArrival()
{
    if(pList == null) return;
    for(int i = 0; i < pList.length; i++)
        if(pList[i].isReady())
        {
            pList[i].procState = State.READY;
            System.out.println("Process " + pList[i].pid + " is now ready.");
            CPU.ReadyQ.add(pList[i]);
        }
}

@Override
public void run() {
    // TODO Auto-generated method stub
    System.out.println("Long Term Scheduler starts.!!!");
    while(LTS.STSDone != true)
    {
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
    System.out.println(LTS.STSDone);
    System.out.println("LTS ends.!!!");
        CPU.done = true;
    }
}
4

1 に答える 1

0

問題番号 1 は、共有状態がスレッドセーフではないことです。ブール値のような単純なものでも、スレッド間での可視性を確保するために正しいスレッド化プリミティブが必要です (別名「揮発性」)。

于 2012-10-01T20:31:42.653 に答える