Planowanie Round Robin w java

Question

Próbuję zaimplementować algorytm szeregowania Round Robin. Ale kod, który do tej pory zrobiłem, bierze pod uwagę tylko czas wybuchu. Muszę również wziąć pod uwagę czas przybycia procesu. Mam tablicę time_chart, której używam do przechowywania numeru aktualnie wykonywanego procesu. Ale jeśli żaden proces nie jest aktualnie wykonywany (to znaczy, jeśli wybrany proces zakończył wykonywanie, a kolejny proces nie dotarł), wartość 0 należy wstawić do tablicy time_chart.

I przechowywano czasu rozerwania oraz czas przybycia w matrycy 2D jako:

//proc[][0] is the AT array 
//proc[][1] is the BT array 

i czasem kwantowej zmienną q. Poniżej znajduje się mój kod:

int time_chart[] = new int[total_time]; 
int sel_proc = 1; 
int current_q = 0; 

for (int k = 0; k < total_time; k++) { 

    //Assign selected process to current time in the Chart 
    time_chart[k] = sel_proc; 

    //Decrement Remaining Time of selected process by 1 since it has been assigned the CPU for 1 unit of time 
    proc[sel_proc - 1][1]--; 

    //Updating value of sel_proc for next iteration 
    current_q++; 

    if (current_q == q || proc[sel_proc - 1][1] == 0)//If Time slice has expired or the current process has completed execution 
    { 
     current_q = 0; 
     //This will select the next valid value for sel_proc 
     for (int j = 1; j <= n; j++) { 
      sel_proc++; 
      if (sel_proc == (n + 1)) { 
       sel_proc = 1; 
      } 
      if (proc[sel_proc - 1][1] != 0) { 
       break; 
      } 
     } 
    } 
} 

// print timeline for testing 
for (i = 0; i < total_time; i++) { 
System.out.println("Time " + i + ": " + time_chart[i]); 
} 

obecnie wybierze następny proces, mimo że jeszcze nie dotarł. Dlatego muszę sprawdzić, czy następny proces nadszedł, czy nie. Próbowałem użyć proc[sel_proc][0] <= k, aby to sprawdzić, ale nie działało. Rozumiem przez to, że nie otrzymałem żadnych wyników. Nie mogę wymyślić innego sposobu sprawdzenia, czy następny proces nadszedł, czy nie. Jak mogę to sprawdzić i umieścić wartość 0 w tablicy, jeśli następny proces nie dotarł?

Answer 1

Mimo że można tego dokonać przy użyciu tylko tablic, logika może być łatwiejsza, jeśli utworzysz strukturę klas do przechowywania informacji o procesie i użyjesz dwóch Queues. Pierwszy Queue jest listą procesów uporządkowanych według czasu przybycia, a drugi Queue procesów, które są obecnie wykonywane.

można modelować przetwarzać coś wzdłuż tych linii

private static class Process { 
    public final int id; 
    public final int burstTime; 
    public final int arrivalTime; 
    public int executionTime; 

    public Process(int id, int burstTime, int arrivalTime) { 
     super(); 
     this.id = id; 
     this.burstTime = burstTime; 
     this.arrivalTime = arrivalTime; 
    } 
} 

Następnie utworzyć połączenie Kolejka procesów nieplanowanych (lub co kiedykolwiek wydaje stosowne) i dodać do tej kolejki procesów zamówionej przez czas przybycia. Queue<Process> = new LinkedList<>()

Teraz podczas pętli za każdym razem po prostu sprawdź nagłówek kolejki i sprawdź, czy czas przyjazdu procesu jest równy lub większy od bieżącego czasu. Jeśli jest usuwany z kolejki i dodawany do nagłówka kolejki programu planującego. LinkedList<Process> = new LinkedList<>()

Zawsze usuwa się proces głowicy z kolejki programu planującego i aktualizuje czas wykonania procesu. Upewnij się, że nie przekroczysz czasu burst, tzn. Czas wykonania jest zawsze zwiększany przez kwantowe OR burstTime - executionTime, w zależności od tego, która jest mniejsza. Po aktualizacji, jeśli czas wykonania jest krótszy niż czas burstTime, dodaj proces z powrotem do kolejki programu planującego.

Pamiętaj, że aktualny czas nie zostanie zwiększony o kwant, jeśli pozostały czas procesu był mniejszy niż kwant.

Answer 2

Właściwie powinieneś sprawdzić, czy czas przybycia procesu jest mniejszy lub równy w następnym nadchodzącym czasie. Powinieneś więc sprawdzić proc[sel_proc][0] <= k + 1. W szczególności, jedyną zmianą, że należy zrobić jest twój, jeśli który zamiast

if (proc[sel_proc - 1][1] != 0) { 
    break; 
} 

powinny stać się: (jeżeli czas wybuch pozostały nie jest zerowa, a jego przyjazd przed lub równa następnym razem, czyli k + 1)

if (proc[sel_proc - 1][1] != 0 && proc[sel_proc][0] <= k + 1) { 
     break; 
} 

ważniejsze, upewnij się, że Twoja ostatnia ważna jednostka czasu jest TOTAL_TIME - 1 i nie TOTAL_TIME się.Ponadto, są twoje czasy przybycia 0 lub oparte na 1, są to przypadki narożne, które musisz zachować ostrożność.

Answer 3

Co planujesz zaplanować za pomocą swojego algorytmu. Nigdy nie słyszałem o kimkolwiek, kto kroi czas, chyba że przy wdrażaniu systemu operacyjnego.

Podział czasu działa na poziomie systemu operacyjnego, ponieważ system operacyjny może wybrać, które (z odpowiednich) procesów/wątków, które chce uruchomić na procesorze, oraz ponieważ system operacyjny może zasadniczo zatrzymać wątek przy dowolnej instrukcji i przepłukać rejestry procesora Pamięć podręczna. Ta zasada działa tylko w kodzie, jeśli każde zadanie można podzielić na bardzo małe jednostki pracy (instrukcje "CPU"). W ten sposób, jeśli masz 100 zadań składających się z 100 jednostek i 4 rdzeni procesorów, możesz zaimplementować własny algorytm podziału czasu (ale nie polecam go).

Tradycyjnie, jeśli masz wiele równoczesnych zadań, używałbyś wątku z liczbą wątków równą liczbie rdzeni procesora (lub więcej, gdy zadania mają IO), i po prostu ustawiałbyś kolejkę zadań po ich otrzymaniu, oraz niech OS będzie się martwił o podział czasu.

Answer 4

Ten problem jest znacznie prostszy, jeśli zamiast pojedynczego int śledzić bieżący proces, używa się listy wszystkich. Dobrym wyborem jest utrzymywanie uporządkowanej listy, na której działa uruchomiony proces, a pozostałe postępują w kolejności, w jakiej powinny działać w przyszłości. Następnie zawsze możesz uzyskać następny proces, obracając listę. Aktualizowanie listy dla każdego kwantu jest proste. Kolekcja Java, która ułatwia wszystkie te opcje, nazywa się Deque.

coś takiego:

Deque<Integer> running = new ArrayDeque<>(); 
for (int quantum = 0; quantum < totalDuration; ++quantum) { 
    // Add new arrivals to the list of running processes. 
    // Note that if the processes are pre-sorted by arrival time, 
    // this loop can be made more efficient. This assumes no sorting. 
    for (int process = 1; process <= processCount; ++process) { 
    if (arrivalTime[process] == quantum) 
     running.addLast(process); // Use addFirst if new procs should run immediately. 
    } 
    if (running.isEmpty()) 
    timeChart[quantum] = 0; // Nothing to run 
    else { 
    // Select the process now at the head. 
    int selectedProcess = running.getFirst(); 

    // Decrement the running process's burst time. If it's done, remove 
    // it from the running list. 
    if (--burstTime[selectedProcess] == 0) 
     running.removeFirst(); 

    // Record the run for this quantum.   
    timeChart[quantum] = selectedProcess; 

    // Rotate the previous head to the tail of the list for next quantum. 
    if (running.size() > 1) 
     running.addLast(running.removeFirst()); 
    } 
} 

Uwaga Użyłem bardziej racjonalnych nazwiska i konwencje Java. Wybór nazw i typów danych jest nieco odrażający. Jak powiedzieli inni, byłoby jeszcze lepiej pogrupować czasy przyjazdu i wybuchu dla procesu w class.