최단 남은 시간 우선 : 자바 멀티 쓰레딩

Question

자바에서 CPU 스케줄링 알고리즘을 시뮬레이트하려고하는데, 멀티 쓰레딩을 사용하고 있습니다. FCFS (First Come First Serve)와 SJF (Shortest Job First)를 성공적으로 구현했습니다. 하지만 문제는 SJF의 선제 형식 인 SRTF (최단 남은 시간 우선)를 생각할 때입니다. CPU에 대한

• 스레드, 똑딱 유지하는 CLOCK 변수 (간단한 시계 증가) 모든 100ms 있습니다 나는 다음과 같은 모델을 사용하고 있습니다. 실행을 시작하기 전에 CPU가 사용 가능한지 확인하는 프로세스에 대해 boolean isAvailable; 플래그가 있습니다.
• 프로세스 목록에서 준비 대기열로 프로세스를 푸시하는 Long Term Scheduler (LTS) 용 스레드입니다.
• ReadyQueue에서 프로세스를 가져 와서 CPU에 할당하는 STS (Short Term Scheduler) 용 스레드입니다.
• 실행을 위해 STS에서 ReadyQueue에서 프로세스를 제거하면 프로세스가 CPU의 isAvailable 플래그를 확인합니다. true이라면, 플래그를 false로 설정하고 실행을 시작합니다 (단지 시뮬레이션 일 뿐이므로 (100 * burstTime) ms에 대해 잠자기 상태로 스레드를 만들고 있습니다). 그렇지 않으면 프로세스가 대기 중으로 계속 대기합니다 : while(CPU.isAvailable != true);.

나는 그들의 도착 및 버스트 시간과 함께 프로세스 목록을 가지고 있습니다. 비 선점 형 스케줄링 (FCFS 및 SJF)을 시뮬레이트 할 때까지는 괜찮습니다. 그러나 SRTF를 시도 할 때 현재 실행중인 프로세스 스레드를 선점하는 방법을 찾을 수 없습니다.

SRTF의 경우 ReadyQueue에서 다음 프로세스를 선택하는 방법을 알고 있습니다. 대기열에서 프로세스를 선택하면 플래그를 false으로 설정하려고 할 수 있습니다. 그렇다면 어떤 스레드가 원래 실행되고 있었는지 어떻게 알 수 있습니까? 그리고 동기화 b/w 스레드를 많이 사용하지 않기 때문에 CPU 스레드를 사용하는 여러 프로세스가 있습니다. 그것의 조금 엉망이 점점. 도와주세요. 감사! 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(); 
    } 
    } 
} 

코드 : LTS에 대한

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(); 
      } 
    } 
} 

코드 :

이

은 프로세스의 코드입니다

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; 
    } 
} 

Answer 1

문제 번호 1은 공유한다는 것입니다 상태가 스레드로부터 안전하지 않습니다. 부울과 같은 단순한 것조차도 스레드 (즉, "휘발성") 전반에 대한 가시성을 보장하기 위해 올바른 스레딩 프리미티브가 필요합니다.