Zadatak

Ostvariti program koji simulira tijek rezervacije stolova u nekom restoranu. Program na početku treba stvoriti određeni broj dretvi koji se zadaje u naredbenom retku. Svaka dretva/proces nakon isteka jedne sekunde provjerava ima li slobodnih stolova te slučajno odabire jedan od njih. Nakon odabira dretva ulazi u kritični odsječak te ponovo provjerava je li odabrani stol slobodan. Ako jest, označava stol zauzetim i izlazi iz kritičnog odsječka. U oba slučaja, nakon obavljene operacije ispisuje trenutno stanje svih stolova te podatke o obavljenoj rezervaciji. Prilikom ispisa za svaki stol mora biti vidljivo je li slobodan ili broj dretve/procesa koja je taj stol rezervirala. Broj stolova se također zadaje u naredbenom retku. Svaka dretva ponavlja isti postupak sve dok više nema slobodnih stolova. Program završava kada sve dretve završe.

Primjer ispisa: (3 dretve, 5 stolova)

Dretva 1: odabirem stol 2    
Dretva 2: odabirem stol 2    
Dretva 3: odabirem stol 5    
Dretva 2: rezerviram stol 2, stanje:    
-2---    
Dretva 1: neuspjela rezervacija stola 2, stanje:    
-2---    
Dretva 3: rezerviram stol 5, stanje:    
-2--3    
itd.

Lamportov algoritam

uđi_u_kritični_odsječak(I)
    ULAZ[I] = 1
    BROJ[I] = max ( BROJ[0], ..., BROJ[BR_DRETVI-1] ) + 1
    ULAZ[I] = 0

    za J = 0 do BR_DRETVI-1 čini
        dok je ULAZ[J] <> 0 čini
            ništa
        dok je BROJ[J] <> 0 && (BROJ[J] < BROJ[I] || (BROJ[J] == BROJ[I] && J < I)) čini
            ništa

izađi_iz_kritičnog_odsječka(I)
    BROJ[I] = 0

Veći dio rješenja je ponuđen kroz datoteke: lab2.py i lamport.py (i jednu i drugu je potrebno nadopuniti!)

Datoteka: lab2.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import time, threading, signal, sys, random
from lamport import KO_init, Udji_u_KO, Izadji_iz_KO

kraj = False     # na signal ova se varijabla mijenja

# broj dretvi i stolova se zadaje preko komandne linije
BR_DRETVI = 7
BR_STOLOVA = 5

stol = []
slobodno = BR_STOLOVA # broj slobodnih stolova

def odaberi_slobodni_stol():
    '''
    Funkcija vraća indeks nasumično odabranog slobodnog stola
    ili -1 ako nema slobodnog stola.
    Ovo se može napraviti na razne načine. Jedan je opisan u nastavku.
    '''
    # dok je slobodno > 0 radi
    #   x = slučajan broj od 0 do slobodno-1
    #   y = 0
    #   za i = 0 do BR_STOLOVA-1 radi
    #       ako je stol[i] == 0 tada
    #           ako je x == y tada
    #               vrati i
    #           inače
    #               y = y + 1

    return -1 # nema slobodnih stolova

def ispisi_stanje ():
    stanje = "".join ( str(x) if x > 0 else "-" for x in stol )
    print ( "Stolovi: " + stanje )

def posao_dretve (id):
    ''' Početna funkcija za nove dretve '''
    global slobodno
    while not kraj: # dok signal za kraj nije došao
        i = odaberi_slobodni_stol ()
        if i == -1:
            break
        print ( "Dretva " + str(id) + ": odabirem stol " + str(i) )
        time.sleep(1.0)

        Udji_u_KO (id-1) # id ide od 1-N, a polja od 0 do N-1
        if stol[i] == 0:
            stol[i] = id
            slobodno = slobodno - 1
            print ( "Dretva " + str(id) + ": rezerviram stol " + str(i) )
        else:
            print ( "Dretva " + str(id) + ": neuspjela rezervacija stola " + str(i) )
        ispisi_stanje ()
        Izadji_iz_KO (id-1)

        time.sleep(1.0)

def signal_kraj ( sig_num, frame ):
    ''' Na signal SIGINT (Ctrl+C) program završava '''
    print ( "\nPrimljen signal za završetak ... ")
    global kraj
    kraj = True

def main():
    signal.signal ( signal.SIGINT, signal_kraj )

    global BR_DRETVI, BR_STOLOVA, slobodno
    if len(sys.argv) == 3:
        BR_DRETVI = int(sys.argv[1])
        BR_STOLOVA = int(sys.argv[2])
        slobodno = BR_STOLOVA

    KO_init (BR_DRETVI)
    stol.extend ( [0] * BR_STOLOVA ) # u početku su svi stolovi slobodni
    ispisi_stanje ()
    dretva = [None] * BR_DRETVI
    for i in range(BR_DRETVI):
        dretva[i] = threading.Thread ( target = posao_dretve, args = (i+1,) )
        dretva[i].start()

    for i in range(BR_DRETVI):
        while dretva[i].is_alive():
            dretva[i].join (timeout=1)

    if not kraj:
        print ( "Svi stolovi zauzeti" )

if __name__ == "__main__":
    main()

Datoteka: lamport.py

BR_DRETVI = 0
broj = []
ulaz = []

def KO_init (N):
    global BR_DRETVI
    BR_DRETVI = N
    broj.extend ( [0] * N )
    ulaz.extend ( [0] * N )

def Udji_u_KO (I):
    # ostvariti prema algoritmu
    # može se koristiti funkcija max: broj[I] = max(broj) + 1
    pass

def Izadji_iz_KO (I):
    broj[I] = 0 # prema algoritmu

Ako se pokreće iz nekog okruženja, npr. IDLE-a, onda je broj stolova i broj dretvi kodiran u kodu (tamo se može promijeniti).