Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / Java
Tip/Trick

Lottery algorithm in Java

Rate me:
Please Sign up or sign in to vote.
4.50/5 (3 votes)
17 Oct 2012CPOL 29.5K   4   2
implementing lottery algorithm in java

Introduction

Lottery Scheduling is a probabilistic scheduling algorithm for processes in an operating system. Processes are each assigned some number of lottery tickets, and the scheduler draws a random ticket to select the next process. The distribution of tickets need not be uniform; granting a process more tickets provides it a relative higher chance of selection. This technique can be used to approximate other scheduling algorithms, such as Shortest job next and Fair-share scheduling.

Here is the implmentation of the lottery algorithm in Java by OmiD_Haghighatgoo:

Java
package project1;

import java.util.Random;

public class Lottery {
    public static void main(String[] arg) {

        Random rand = new Random();
        char[] process = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
        int[] arrival = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        boolean insert = false;
        int p = 0;
        int q=0;
        int max_tick = 0;
        int ticket[][] = new int[10][10];
        char temp[] = new char[10];
        for (int z = 0; z < 10; z++) {
            int digit = (int)rand.nextInt(30);
            arrival[z] = digit;
        }


        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 9; j++) {
                if (arrival[j] >= arrival[j + 1]) {
                    int temp2 = arrival[j];
                    arrival[j] = arrival[j + 1];
                    arrival[j + 1] = temp2;

                    char temp1 = process[j];
                    process[j] = process[j + 1];
                    process[j + 1] = temp1;
                }
            }
        int time = arrival[0];

        int[] request = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] lottery = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        for (int z = 0; z < 10; z++) {
            int digit = (int)rand.nextInt(20);

            if (digit == 0) {
                digit = 5;
            }

            request[z] = digit;

        }
        for (int i = 0; i < 10; i++) {
            System.out.print("\t process : " + process[i]);
            System.out.print("\t arival : " + arrival[i]);
            System.out.println("\t request : " + request[i]);
            System.out.println("");
        }

        int quantom = rand.nextInt(8);
        if (quantom == 0)
            quantom = 5;
        System.out.println("quantom : " + quantom);
        System.out.print("\t" + "time");
        System.out.print("\t" + "request");
        System.out.print("\t" + "process");
        System.out.print("\t" + "Lottery");
        System.out.println("\t" + "ticket");

        System.out.println("---------------------------------------------------------");
        while ((request[0] + request[1] + request[2] + request[3] + 
                request[4] + request[5] + request[6] + request[7] + 
                request[8] + request[9]) > 0) {
            System.out.println("---------------------------------------------------------");
            p = 0;
            for (int i = 0; i < 10; i++) {
                if ((request[i] > 0)) /*&& (time > arrival[i])*/ {
                    lottery[i] = request[i] / 2;
                    if ((lottery[i] == 0) && (request[i] > 0))
                        lottery[i] = 1;
                    for (int z = 0; z < lottery[i]; z++) {
                        ticket[i][z] = p++;
                        max_tick = p;
                    }
                    temp[i] = process[i];                


                    System.out.print("\t" );
                    System.out.print("\t" + request[i]);
                    System.out.print("\t" + temp[i]);
                    System.out.print("\t" + lottery[i]);
                    for (int z = 0; z < lottery[i]; z++)
                        System.out.print("\t" + "::" + ticket[i][z] + "::");
                    System.out.println();
                } else if ((request[i] > 0) && (time < arrival[i])) {
                    temp[i] = process[p];
                    lottery[i] = request[i] / 2;
                    if ((lottery[i] == 0) && (request[i] > 0))
                        lottery[i] = 1;
                    for (int z = 0; z < lottery[i]; z++){
                        ticket[i][z] = p++;
                        max_tick=p;
                    }

                    if (request[i] > 0) {
                        time += quantom;
                    } else {
                        time += (request[i] + quantom);
                    }

                    System.out.print("\t" + time);
                    System.out.print("\t" + request[p]);
                    System.out.print("\t" + temp[i]);
                    System.out.print("\t" + lottery[i]);
                    for (int z = 0; z < lottery[i]; z++)
                        System.out.print("\t" + "::" + ticket[i][z] + "::");
                    System.out.println();

                }
            }

            int winner = rand.nextInt(max_tick);
            for(int i =0;i<10;i++)
                for(int z=0;z<lottery[i];z++)
                    if(ticket[i][z]==winner)
                         q=i;
            System.out.println("---------------------------------------------------------");
            System.out.println("winner :" +"<<" +winner+">>" );
        
            if ((request[q] > 0))  {
            temp[q] = process[q];
            request[q] -= quantom;


            if (request[q] > 0) {
                time += quantom;
            } else {
                time += (request[q] + quantom);
            }

            if (request[q] < 0) {
                request[q] = 0;
            }
            
            System.out.print("\t" + time);
            System.out.print("\t" + request[q]);
            System.out.print("\t" + temp[q]);
                System.out.println();
            }else if ((request[q] > 0) && (time < arrival[q])) {
                                temp[q] = process[p];
            if (request[q] > 0) {
                time += quantom;
            } else {
                time += (request[q] + quantom);
            }

            System.out.print("\t" + time);
            System.out.print("\t" + request[q]);
            System.out.print("\t" + temp[q]);
            System.out.println();
            
        }
    }
}
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Iran (Islamic Republic of) Iran (Islamic Republic of)
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
Questioninshallah the write up is nice Pin
Member 1369555025-Feb-18 2:58
Member 1369555025-Feb-18 2:58 
SuggestionConditions Pin
Member 1122782512-Nov-14 3:08
Member 1122782512-Nov-14 3:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.