Køer

En kø kjennetegnes ved at elementet som ble lagt inn først - det som har ventet lengst - er det som behandles først. Nye elementer legges bakerst i køen. Skal vi ta ut et element, tar vi alltid det som ligger først. En kø håndteres etter "First in, first out"-prinsippet (FIFO). Eksempler på anvendelse er implementasjon av en printer-kø, og simuleringer som involverer ulike typer køer.

Grensesnitt for en Kø

public interface Queue<E>{
	public void enqueue(E element); // Legge nytt element bakerst i køen
	public E dequeue(); // Fjerne første element fra køen; 
	public E first(); // Se på første element i køen; 
	public boolean isEmpty(); // Avgjøre om køen er tom 
	public int size(); // Antall elementer i køen 
	public String toString();     
}
                

Implementasjon

• Lenket liste
• Tabell
• Sirkulær tabell
• ...

Kø-simulering

• En kø er velegnet til å simulere køer av forskjellig slag, for eksempel en kundekø i en bank eller telefonkøer hos et teleselskapene.
• Jo flere kasser som er åpne / kundebehandlere som er operative, jo kortere vil ventetiden for kundene bli.
• Hvor mange kasser må være åpne for at ingen kunder skal behøve å vente mer enn et bestemt antall minutter?
• Ønsker ikke å ha flere åpne kasser enn nødvendig.
• I tidsdrevet simulering, starter vi en simuleringsklokke ved tid 0. Ved hvert tidsintervall som simuleringen gjennomføres for, sjekker vi om bestemte hendelser har inntruffet (om det kommer en ny kunde, om en eller flere av kassene er ledige). Isåfall prosesseres hendelsen(e), og aktuelle beregninger utføres.

Algoritme for enkel, tidsdrevet simulering

Her beskrives kun hoved-trekkene i algoritmen. Aktuelle beregninger - for eksempel gjennomsnittlig ventetid for hver kunde - er ikke tatt med.

Antakelser

• Sannsynligheten for at det kommer en kunde innenfor et tidsintervall er gitt, kalles p_k.
• Gjennomsnittlig tid som brukes for å betjene en kunde er gitt.
• Har en klasse Kasse som representer en kasse. Et Kasse-objekt har en variabel tidFerdigKunde som inneholder tidspunktet for når kassa vil bli ledig igjen.

1. For hvert tidsskritt:
   1. Trekk et tilfeldig tall mellom 0 og 1, rand. Hvis rand< p_k , settes en ny kunde inn i kunde-køen.
   2. For hver kasse,
      1. Undersøk om kassa er ledig
      2. Hvis ledig, ta første kunde - hvis det finnes noen - ut av køen.
      3. Beregn tidspunkt for når kassa vil bli ledig igjen, og sett kassens tidFerdigKunde.

Køsimulering 1

• Modifisert versjon av programmet fra læreboka.
• En kø - antall kasser varierer fra 1 til 10.
• Kundene kommer ved faste tidsintervaller (hvert 15. tidssteg).
• Fast behandligstid: 120 tidssteg.

package koer;

public class Kunde {

    private int ankomst; // Tidspunkt n��r kunden stiller seg i k��en
    
    public Kunde(int ankomst) {
        this.ankomst = ankomst;
    }
   
    public int behandlingstid(int avgang ) {
        return avgang - ankomst;
    }        
}

package koer;

public class Kasse {
        
    private int tidFerdigKunde; 
    
    public Kasse( int tidFerdigKunde){        
        this.tidFerdigKunde = tidFerdigKunde; 
    }
    
    public boolean erLedig(int tid ) {
        return tid >= tidFerdigKunde; 
    }
    
    public void settTidFerdigKunde(int tid ){ 
        tidFerdigKunde = tid; 
    }    
}

package koer;

public class QSim {

    static final int PROSESSERINGSTID = 120;
    static final int MAX_ANTALL_KASSER = 10;
    static final int MAX_ANTALL_KUNDER = 100;

    public static void main(String[] args) {
        long totalTid, antallKunder;
        LinkedQueue<Kunde> kundeQ; 
       
        // Gjennomf��rer simuleringen for variabelt antall kasser, 1 k�� 
        for (int k = 1; k <= MAX_ANTALL_KASSER; k++) {
            totalTid = 0; antallKunder = 0; 
            kundeQ = new LinkedQueue<Kunde>();
                        
            System.out.println("\n------------------------"); 
            System.out.println("Antall kasser: " + k); 
            
            // Lager k kasser, i utgangspunktet er alle ledige. 
            Kasse[] kasser = new Kasse[k];            
            for (int i = 0; i < kasser.length; i++) {
                kasser[i] = new Kasse(0);
            }
            
            // Starter p�� tid t=0, fortsetter helt til vi har behandlet 
            // MAX_ANTALL_KUNDER
            int t; 
            for (t = 0; antallKunder < MAX_ANTALL_KUNDER; t++) {

                // Kommer ny kunde hvert 15. tidssteg: 
                if (t % 15 == 0) {
                    kundeQ.enqueue(new Kunde(t));
                }

                for (int i = 0; i < kasser.length; i++) {                    
                    if (kasser[i].erLedig(t)) {
                        if (!kundeQ.isEmpty()) {
                            Kunde kunde = kundeQ.dequeue();
                            kasser[i].settTidFerdigKunde(t + PROSESSERINGSTID);
                            totalTid += kunde.behandlingstid(t + PROSESSERINGSTID);
                            antallKunder++;
                        }
                    }
                }
            }            
            System.out.println("Antall kunder: " + antallKunder);
            System.out.println("Antall tidssteg: " + t);
            System.out.println("Gjennomsnittlig behandlingstid: " + 
                    totalTid / antallKunder);
        }
    }
}

Køsimulering 2

Kundeankomst og betjenigstid trekkes tilfeldig.

package koer;

import java.util.Random;

public class QSim2 {

    static final int MAX_ANTALL_KASSER = 10;
    static final int MAX_ANTALL_KUNDER = 100;
    
    // Sannsynligheten for at det kommer en kunde innenfor et tidssteg:
    static final double P=0.5; 

    public static void main(String[] args) {
        Random generator = new Random(); 
        
        long totalTid, antallKunder;
        LinkedQueue<Kunde> kundeQ; 
       
        // Gjennomf��rer simuleringen for variabelt antall kasser, 1 k�� 
        for (int k = 1; k <= MAX_ANTALL_KASSER; k++) {
            totalTid = 0; antallKunder = 0; 
            kundeQ = new LinkedQueue<Kunde>();
                        
            System.out.println("\n------------------------"); 
            System.out.println("Antall kasser: " + k); 
            
            // Lager k kasser, i utgangspunktet er alle ledige. 
            Kasse[] kasser = new Kasse[k];            
            for (int i = 0; i < kasser.length; i++) {
                kasser[i] = new Kasse(0);
            }
            
            // Starter p�� tid t=0, fortsetter helt til vi har behandlet 
            // MAX_ANTALL_KUNDER
            int t; 
            for (t = 0; antallKunder < MAX_ANTALL_KUNDER; t++) {

                // Trekker nytt tilfeldig tall. Hvis tallet som trekkes er 
                // mindre enn P, settes ny kunde inn i k��en. 
                if ( generator.nextDouble() < P ) {
                    kundeQ.enqueue(new Kunde(t));
                }

                for (int i = 0; i < kasser.length; i++) {                    
                    if (kasser[i].erLedig(t)) {
                        if (!kundeQ.isEmpty()) {
                            int betjeningstid = generator.nextInt(9)+1; 
                            Kunde kunde = kundeQ.dequeue();
                            kasser[i].settTidFerdigKunde(t + betjeningstid);
                            totalTid += kunde.behandlingstid(t + betjeningstid);
                            antallKunder++;
                        }
                    }
                }
            }   
            
            System.out.println("Antall kunder: " + antallKunder);
            System.out.println("Antall tidssteg: " + t);
            System.out.println("Gjennomsnittlig behandlingstid: " + 
                    totalTid / antallKunder);
        }
    }
}

Radix-sort

• Grunntallssortering
• Implementeres gjerne ved bruk av køer, en kø per grunntall (radix), dvs. 10 køer hvis vi skal sortere tall i 10-talls-systemet.
• Se notat skrevet av Jan Høiberg .

Prioritetskøer

• I vanlige FIFO-køer, setter vi inn elementer i den ene enden av køen, og tar ut elementer fra den andre enden.
• Av og til ønsker vi å prioritere elementene som ligger i køen.
• Noen må behandles med en gang, mens andre kan vente litt.
• En sykehuskø der pasientene blir prioritert etter hvor syke de er, er et eksempel på en prioritetskø.

Eksempel: Jobbfordeler (scheduler) i et operativsystem

• En maskin har som oftest mange jobber som kjører samtidig.
• En tradisjonell CPU kan til enhver tid kun utføre en jobb.
• En løsning er å plassere alle jobbene i en kø. Når en jobb tas ut av køen får den kjøre en liten stund før den legges bakerst i køen igjen. Da ser det ut som om alle jobbene kjører samtidig, men korte jobber vil ta uforholdsmessig lang tid på grunn av all ventingen.
• En bedre løsning er å senke prioriteten til jobber som allerede har kjørt lenge, slik at nye, korte jobber utføres raskt.

Operasjoner på prioritetskø

Vi må (minst) kunne utføre følgende to operasjoner på prioritetskøen:

1. settInn(x, p)
   Setter inn nytt element x med prioritet p.
2. fjernMin()
   Fjerner elementet med høyest prioritet fra prioritetskøen.

Mulige implementasjoner av prioritetskø

1. Lenket liste

• Setter nye elementer inn først i den lenkede listen O(1)
• Må traversere hele listen for å finne det minste elementet, O(N)

2. Sortert lenket liste

• Nye elementer må settes inn på riktig plass i listen, O(N).
• Tar alltid ut første element i listen, O(1).

3. Binært søketre

4. Binær heap