Problema 1   Sia GestoreProcessi un tipo astratto specificato come segue:

TipoAstratto GestoreProcessi

Commento

gestisce in una coda di priorità n processi numerati da 0 ad n-1

Sorte

GP (sorta per il dominio di interesse),

Funzioni

  

Crea : (Intero) ==> GP
precondizioni e postcondizioni per Crea(n) = g
pre: n>0
post: g è il gestore di processi per n processi, con coda di priorità vuota

InCoda : (GP,Intero,Intero) ==> GP
precondizioni e postcondizioni per InCoda(g,p,k) = g'
pre: p in { 0..n-1 } e p non è già in coda
post: g' è ottenuto da g inserendo il processo p in coda con priorità k

OutCoda : (GP,Intero) ==> GP
precondizioni e postcondizioni per OutCoda(g,p) = g'
pre: p è in coda
post: g' è ottenuto da g eliminando il processo p dalla coda di priorità

Massimo : (GP) ==> Intero
precondizioni e postcondizioni per Massimo(g)=p
pre: g non è vuota
post: p è il processo con massima priorità (uno qualsiasi dei processi di massima priorità se più di uno)

AggiornaPriorita : (GP,Intero,Intero) ==> GP
precondizioni e postcondizioni per AggiornaPriorita(g,p,k) = g'
pre: p è in coda
post: g' è ottenuto da g ponendo la priorità del processo p a k

CodaVuota : (GP) ==> Boolean
precondizioni e postcondizioni per CodaVuota(g)=b
pre: nessuna
post: b=true se la coda di g è vuota, b=false altrimenti

  

FineTipoAstratto

Domanda 1   Scrivere una classe C++ GestoreProcessi (file .h e file .cpp) che realizzi il tipo astratto GestoreProcessi, in modo da rendere tutte le operazioni del tipo astratto il più efficienti possibili. Qualora si faccia uso di strutture dati note (quali Heap, AlberiRicerca, TavoleHash) si riporti solo la definizione della classe (file .h) e il codice delle funzioni che sono state sostanzialmente modificate per adattare la struttura al caso sotto esame. Per le altre funzioni riportare solo una breve descrizione delle modifiche apportate.

Domanda 2   Calcolare per ogni funzione della classe GestoreProcessi il costo computazionale.