Questo è un frammentino del SO che scrissi a suo tempo...
E' la gestione della memoria... devo cercare da qualche parte il resto
e VENDERLO A ZIO BILL :rotolo) perchè cambi il "codebase" (!!!!) di Vista :sedia)
/****************************************************************************/
/* */
/* Module MEMORY */
/* External Declarations */
/* */
/****************************************************************************/
/* OSP constants */
#include <stdio>
#include <malloc>
#define MAX_PAGE 16 /* max size of page tables */
#define MAX_FRAME 32 /* size of the physical memory */
#define PAGE_DIM 512 /* size of a page in bytes */
#define COST_OF_PAGE_TRANSFER 6 /* cost of reading page from drum */
/* external enumeration constants */
typedef enum { false, true } BOOL; /* the boolean data type */
typedef enum { read, write } IO_ACTION; /* type of actions for I/O
requests */
typedef enum { load, store } REFER_ACTION; /* types of memory
reference */
typedef enum
{
running, ready, waiting, done
} STATUS; /* types of status */
typedef enum
{
iosvc, devint,
pagefault, startsvc,
termsvc, killsvc,
waitsvc, sigsvc, timeint
} INT_TYPE; /* types of interrupt */
/* external type definitions */
typedef struct page_entry_node PAGE_ENTRY;
typedef struct page_tbl_node PAGE_TBL;
typedef struct event_node EVENT;
typedef struct ofile_node OFILE;
typedef struct pcb_node PCB;
typedef struct iorb_node IORB;
typedef struct int_vector_node INT_VECTOR;
typedef struct frame_node FRAME;
/* external data structures */
extern struct frame_node
{
BOOL free; /* = true, if free */
PCB *pcb; /* process to which the frame currently belongs */
int page_id; /* vitrual page id - an index to the PCB's page tbl */
BOOL dirty; /* indicates if the frame has been modified */
int lock_count; /* number of locks set on page involved in an
active I/O */
int *hook; /* can hook up anything here */
};
extern struct page_entry_node
{
int frame_id; /* frame id holding this page */
BOOL valid; /* page in main memory : valid = true; not : false */
int *hook; /* can hook up anything here */
};
extern struct page_tbl_node
{
PCB *pcb; /* PCB of the process in question */
PAGE_ENTRY page_entry[MAX_PAGE];
int *hook; /* can hook up anything here */
};
extern struct pcb_node
{
int pcb_id; /* PCB id */
int size; /* process size in bytes; assigned by SIMCORE */
int creation_time; /* assigned by SIMCORE */
int last_dispatch; /* last time the process was dispatched */
int last_cpuburst; /* length of the previous cpu burst */
int accumulated_cpu; /* accumulated CPU time */
PAGE_TBL *page_tbl; /* page table associated with the PCB */
STATUS status; /* status of process */
EVENT *event; /* event upon which process may be suspended */
int priority; /* user-defined priority; used for scheduling */
PCB *next; /* next pcb in whatever queue */
PCB *prev; /* previous pcb in whatever queue */
int *hook; /* can hook up anything here */
};
extern struct iorb_node
{
int iorb_id; /* iorb id */
int dev_id; /* associated device; index into the device
table */
IO_ACTION action; /* read/write */
int block_id; /* block involved in the I/O */
int page_id; /* buffer page in the main memory */
PCB *pcb; /* PCB of the process that issued the request */
EVENT *event; /* event used to synchronize processes with I/O */
OFILE *file; /* associated entry in the open files table */
IORB *next; /* next iorb in the device queue */
IORB *prev; /* previous iorb in the device queue */
int *hook; /* can hook up anything here */
};
extern struct int_vector_node
{
INT_TYPE cause; /* cause of interrupt */
PCB *pcb; /* PCB to be started (if startsvc) or pcb that
caused page fault (if fagefault interrupt) */
int page_id; /* page causing pagefault */
int dev_id; /* device causing devint */
EVENT *event; /* event involved in waitsvc and sigsvc calls */
IORB *iorb; /* IORB involved in iosvc call */
};
/* extern variables */
extern INT_VECTOR Int_Vector; /* interrupt vector */
extern PAGE_TBL *PTBR; /* page table base register */
extern FRAME Frame_Tbl[MAX_FRAME]; /* frame table */
extern int Prepage_Degree; /* global degree of prepaging
(0-10) */
/* external routines */
extern siodrum(/* action, pcb, page_id, frame_id */);
/* IO_ACTION action;
PCB *pcb;
int page_id, frame_id; */
extern int get_clock();
extern gen_int_handler();
/* strutture dati interne al modulo */
typedef struct list_node NODE;
/* nodo della lista circolare */
struct list_node
{
int referenceBit;
PCB *pcb;
int pageIndex;
int frameIndex;
int time;
NODE *prev;
NODE *next;
};
/* variabili globali (vedere relazione) */
NODE *circularQueuePointer;
int lastDaemon;
int lastWorkingSet;
int framesFree;
/* variabili impostabili da file */
int TIME_DAEMON;
int TIME_WORKING_SET;
int DIM_WORKING_SET;
/* variabili usate dalla struttura
agganciata a pcb->hook */
int LEN_OFFSET;
int WORKING_OFFSET;
int LAST_OFFSET;
/* varabili usate dalla simulazione
dell'LRU (vedere relazione) */
int FIRST_CLOCK;
int WE_ARE_DOING_LRU;
/****************************************************************************/
/* */
/* Module MEMORY */
/* Internal Routines */
/* */
/****************************************************************************/
/* prototipi delle funzioni */
void memory_init(void);
void initWorkingSet(PCB *);
void resetWorkingSet(void);
void freeWorkingSet(PCB *);
int getNumberOfPagesInWS(PCB *);
int getPageIdFromWS(PCB *, int);
void insertPageInWS(PCB *, int);
void refer(int, REFER_ACTION);
int secondChanceAlgorithm(PCB *, int);
void insertPageInCircularQueue(int, int, PCB *);
void resetFrame(NODE *);
void daemon(void);
void newWorkingSet(void);
void get_page(PCB *, int);
void lock_page(IORB *);
void unlock_page(IORB *);
void removePageFromCircularQueue(int);
void deallocate(PCB *);
void loadPagesInWorkingSet(PCB *, int);
void prepage(PCB *);
int start_cost(PCB *);
void memory_init(void)
/*
Chiamata inizialmente da OSP
Inizializzazione delle variabili globali utilizzate, in particolare
della tabella dei frame (Frame_Tbl)
Vengono inoltre letti da file i valori per inizializzare TIME_DAEMON,
TIME_WORKING_SET, DIM_WORKING_SET e WE_ARE_DOING_LRU
Di conseguenza vengono inizilaizzate le variabili x_OFFSET da
utilizzare con la struttura agganciata a pcb->hook
*/
{
FILE *kludgeFile;
int i, j;
for (i=0; i<MAX_FRAME>hook che servir… per il working set
*/
{
pcb->hook = (int *)malloc(sizeof(int)*LAST_OFFSET);
if (!pcb->hook)
printf("GURU: malloc\n");
/* inizializzazione della lunghezza del working set a zero */
*(pcb->hook+LEN_OFFSET) = 0;
}
void resetWorkingSet(void)
/*
svuotamento del working set eseguito ponendo a zero l'elemento
individuato dalla variabile-costante LEN_OFFSET
*/
{
NODE *p = circularQueuePointer;
*(p->pcb->hook+LEN_OFFSET) = 0;
p = circularQueuePointer->next;
/* scorrimento completo della lista circolare */
while (p != circularQueuePointer)
{
*(p->pcb->hook+LEN_OFFSET) = 0;
p = p->next;
}
}
void freeWorkingSet(PCB *pcb)
/*
deallocazione della memoria occupata per la struttura
agganciata a pcb->hook
*/
{
if (pcb->hook)
{
free(pcb->hook);
pcb->hook = NULL;
}
}
int getNumberOfPagesInWS(PCB *pcb)
/*
ritorna il numero di pagine presenti nel working set
utilizzando il valore puntato dalla variabile-costante
LEN_OFFSET applicata alla struttura agganciata a pcb->hook
*/
{
return *(pcb->hook+LEN_OFFSET);
}
int getPageIdFromWS(PCB *pcb, int i)
/*
ritorna l'id della pagina i-esima presente nel working set
Viene utilizzata la variabile-costante WORKING_OFFSET
applicata alla struttura agganciata a pcb->hook
*/
{
return *(pcb->hook+WORKING_OFFSET+i);
}
void insertPageInWS(PCB *pcb, int pageIndex)
/*
inserisce l'id di una pagina nel working set individuato
dalla struttura agganciata a pcb->hook
Tale valore viene inserito davanti agli altri, i quali vengono
spostati di una posizione in avanti (con eventuale perdita
dell'ultimo)
*/
{
int j;
if (*(pcb->hook+LEN_OFFSET) > 0)
/*
se il working set non Š vuoto vengono spostati gli elementi
gi… presenti
*/
for (j=0; j <pcb>hook+LEN_OFFSET); j++)
*(pcb->hook+WORKING_OFFSET+j+1) = *(pcb->hook+WORKING_OFFSET+j);
if (*(pcb->hook+LEN_OFFSET) <DIM_WORKING_SET>hook+LEN_OFFSET))++;
/*
viene assegnato il valore da inserire alla prima posizione, individuata
dalla variabile-costante WORKING_OFFSET, sempre applicata a pcb->hook
*/
*(pcb->hook+WORKING_OFFSET) = pageIndex;
}
void refer(int logic_addr, REFER_ACTION action)
/*
Chiamata da OSP
Simula la conversione da indirizzo logico a indirizzo fisico
Individua la pagina del processo e quindi il frame di memoria, se
la pagina Š gi… stata caricata, altrimenti causa un pagefault
Setta il bit di riferimento a 1 e se si tratta di una scrittura
(action = store) setta il flag dirty a true
*/
{
int i, pageIndex, frameIndex;
PCB *pcb;
NODE *p;
/*
Salvo il processo in esecuzione (quindi quello che ha causato la refer
con un accesso in memoria). Infatti successivamente, in seguito a un
eventuale pagefault, un altro processo pu• entrare in esecuzione, ma
naturalmente occorrono i dati del processo precedente per completare
l'esecuzione della funzione, una volta caricata la pagina in memoria
*/
pcb = PTBR->pcb;
pageIndex = logic_addr / PAGE_DIM;
if (!pcb->hook)
/* se il processo Š nuovo allochiamo la struttura per il working set */
initWorkingSet(pcb);
if (!pcb->page_tbl->page_entry[pageIndex].valid)
/*
se la pagina non Š in memoria (flag valid = false) genero un interrupt
pagefault indicando sia la pagina mancante che il processo richiedente
*/
{
Int_Vector.cause = pagefault;
Int_Vector.page_id = pageIndex;
Int_Vector.pcb = pcb;
gen_int_handler();
}
if (!pcb->page_tbl->page_entry[pageIndex].valid)
printf("GURU: pagefault from refer");
/*
individuo il frame in cui Š collocata la pagina per accedere
alla struttura NODE per effettuare il settaggio del bit di
riferimento
*/
frameIndex = pcb->page_tbl->page_entry[pageIndex].frame_id;
p = circularQueuePointer;
while (p->frameIndex != frameIndex)
p = p->next;
p->referenceBit = 1;
/* aggiorno la variabile usata per indicare l'ultimo accesso effettuato */
p->time = get_clock()-FIRST_CLOCK;
if (action == store)
{
Frame_Tbl[frameIndex].dirty = true;
}
}
int secondChanceAlgorithm(PCB *pcb, int pageIndex)
/*
Chiamata da get_page in caso di mancanza di frames liberi
Si occupa di liberare un frame secondo l'algoritmo di seconda chance
Ritorna l'indice del frame liberato
*/
{
NODE *p;
NODE *page;
BOOL foundPage = false;
int lock;
int minimo;
NODE *pageToBeSentOff;
p = circularQueuePointer;
while (!foundPage)
/*
Scorrimento della lista circolare per trovare un frame con lock = 0
e la cui pagina allocata abbia bit di riferimento = 0
Nel frattempo un bit di riferimento = 1 viene posto a 0 e si procede
(viene data alla corrispondente pagina una seconda possibilt…)
*/
{
lock = Frame_Tbl[p->frameIndex].lock_count;
if ((p->referenceBit == 0) && (lock == 0))
foundPage = true;
else
{
if ((p->referenceBit == 1) && (lock == 0))
p->referenceBit = 0;
p = p->next;
/*
Il presente ciclo di scansione non termina se tutti i frame hanno
lock > 0 (ipotesi remota)
*/
}
}
/*
Terminato il ciclo p punta al nodo contenente il frame e la pagina
candidati al replacement
*/
circularQueuePointer = p;
minimo = p->time;
pageToBeSentOff = p;
printf("STAT 2nd %03d %03d %06d\n",p->pcb->pcb_id,p->pageIndex,p->time);
page = circularQueuePointer;
if ( (page->time <minimo>frameIndex].lock_count==0) )
{
minimo = page->time;
pageToBeSentOff = page;
}
page=page->next;
while (page!=circularQueuePointer)
{
if ((page->time <minimo>frameIndex].lock_count==0))
{
minimo = page->time;
pageToBeSentOff = page;
}
page=page->next;
}
printf("STAT LRU %03d %03d %06d\n",pageToBeSentOff->pcb->pcb_id,pageToBeSentOff->pageIndex,pageToBeSentOff->time);
if (WE_ARE_DOING_LRU)
p = pageToBeSentOff;
if (Frame_Tbl[p->frameIndex].dirty)
/*
Se il frame da sostituire Š stato soggetto a operazioni di scrittura
la pagina corrispondente viene scritta su disco
*/
siodrum(write, p->pcb, p->pageIndex, p->frameIndex);
/*
Il flag di valid della pagina sostituita viene posto a false
*/
p->pcb->page_tbl->page_entry[p->pageIndex].valid = false;
/*
Il nodo puntato da p viene modificato per contenere i nuovi valori
*/
p->referenceBit = 1;
p->pageIndex = pageIndex;
p->pcb = pcb;
p->time = 0;
return p->frameIndex;
}
void insertPageInCircularQueue(int frameIndex, int pageIndex, PCB *pcb)
/*
Chiamata da get_page
Inserisce i dati di una nuova pagina caricata in memoria nella
lista circolare: si tratta del frame_id, di page_id, del pcb
e del bit di riferimento
*/
{
NODE *p;
p = (NODE *)malloc(sizeof(NODE));
if (!circularQueuePointer)
/* se la lista Š vuota inserimento in testa ... */
{
circularQueuePointer = p;
p->next = circularQueuePointer;
p->prev = circularQueuePointer;
}
else
/* ... altrimenti inserimento in 'coda' */
{
p->prev = circularQueuePointer->prev;
p->next = circularQueuePointer;
circularQueuePointer->prev->next = p;
circularQueuePointer->prev = p;
}
p->pageIndex = pageIndex;
p->pcb = pcb;
p->frameIndex = frameIndex;
p->referenceBit = 1;
p->time = 0;
}
void resetFrame(NODE *p)
/*
Chiamata da daemon
Eliminazione del nodo puntato da p dalla lista circolare
Vengono anche aggiornate le strutture collegate
*/
{
PCB *pcb;
if (p->next == p)
/* se la lista ha un solo elemento ... */
circularQueuePointer = NULL;
else
/*
... altrimenti aggiornamento campi next e prev dei campi precedente e
successivo
*/
{
p->next->prev = p->prev;
p->prev->next = p->next;
}
pcb = p->pcb;
/*
aggiornamento del bit di validit… della pagina collegata al nodo
*/
pcb->page_tbl->page_entry[p->pageIndex].valid = false;
if (Frame_Tbl[p->frameIndex].dirty == true)
/*
Se il frame individuato da p Š stato coinvolto in operazioni di scrittura
la pagina corrispondente viene scritta su disco
*/
siodrum(write, p->pcb, p->pageIndex, p->frameIndex);
/* aggiornamento della tabella dei frames */
Frame_Tbl[p->frameIndex].free = true;
Frame_Tbl[p->frameIndex].pcb = NULL;
Frame_Tbl[p->frameIndex].page_id = -1;
Frame_Tbl[p->frameIndex].dirty = false;
free(p);
}
void daemon(void)
/*
Chiamata opzionalmente da get_page
Si occupa di rendere disponibili frames senza precludere
l'eventuale futuro accesso alle corrispondenti pagine allocate
fino a quando non vengono sostituite
*/
{
NODE *p;
NODE *pnext;
p = circularQueuePointer;
if (Frame_Tbl[p->frameIndex].lock_count == 0)
/*
Se il frame non Š locked esamino il bit di riferimento
Se questo Š nullo libero totalmente il frame, altrimenti
(bit di riferimento = 1) assegno il valore 0 a tale bit
In questo modo la pagina sar… candidata alla sostituzione
in una prossima chiamata a second chance, ma pu• ancora
essere utilizzata
*/
if (p->referenceBit == 0)
{
framesFree++;
circularQueuePointer = p->next;
resetFrame(p);
}
else
p->referenceBit = 0;
p = circularQueuePointer->next;
while (p != circularQueuePointer)
/* operazione precedente per il resto della lista circolare */
{
pnext = p->next;
if (Frame_Tbl[p->frameIndex].lock_count == 0)
if (p->referenceBit == 0)
{
framesFree++;
resetFrame(p);
}
else
p->referenceBit = 0;
p = pnext;
}
}
void newWorkingSet(void)
/*
Chiamata opzionalmente da get_page
Aggiorna la struttura del working set inserendo l'id delle
pagine che hanno bit di riferimento = 1 (e quindi che sono
state usate recentemente)
*/
{
NODE *p;
resetWorkingSet();
p = circularQueuePointer;
if (p->referenceBit == 1)
insertPageInWS(p->pcb, p->pageIndex);
p = circularQueuePointer->next;
while (p != circularQueuePointer)
{
if (p->referenceBit == 1)
insertPageInWS(p->pcb, p->pageIndex);
p = p->next;
}
}
void get_page(PCB *pcb, int page_id)
/*
Chiamata da OSP in seguito a un pagefault
Vengono indicati la pagina mancante (page_id) e il processo che
la richiede (pcb)
Oltre alle istruzioni per caricare la pagina in memoria, la funzione
si occupa anche di chiamare, sotto opportune condizioni, le funzioni
daemon e newWorkingSet
*/
{
int i;
BOOL foundFrame = false;
if ((get_clock() - lastDaemon) >= TIME_DAEMON)
{
/*
La funzione daemon viene chiamata se sono passati almeno TIME_DAEMON
clock dall'ultima volta e se i frames liberi sono inferiori al 10%
*/
if (framesFree < (MAX_FRAME*0.1))
daemon();
lastDaemon = get_clock();
}
for (i=0; (i<MAX_FRAME>= TIME_WORKING_SET)
{
newWorkingSet();
lastWorkingSet = get_clock();
}
}
void lock_page(IORB *iorb)
/*
Viene chiamata in seguito ad una operazione di I/O per bloccare
il frame coinvolto
La pagina coinvolta pu• non trovarsi in memoria; in tal caso
viene generato un pagefault
*/
{
int i, frameIndex, pageIndex;
PCB *pcb;
pcb = iorb->pcb;
pageIndex = iorb->page_id;
if (!pcb->hook)
/*
Come in refer, se il processo Š nuovo si approfitta per
inizializzare la struttura per il working set
*/
initWorkingSet(pcb);
if (!pcb->page_tbl->page_entry[pageIndex].valid)
/*
Se la pagina non Š in memoria si genera l'interrupt pagefault
*/
{
Int_Vector.cause = pagefault;
Int_Vector.page_id = pageIndex;
Int_Vector.pcb = pcb;
gen_int_handler();
}
frameIndex = pcb->page_tbl->page_entry[pageIndex].frame_id;
if (iorb->action == read)
Frame_Tbl[frameIndex].dirty = true;
/* viene incrementato lock_count (scopo principale della funzione) */
Frame_Tbl[frameIndex].lock_count++;
}
void unlock_page(IORB *iorb)
/*
Esegue l'operazione inversa di lock_page
Individuato il frame coinvolto, viene diminuito il valore
di lock_count nella tabella dei frames
*/
{
int frameIndex;
int pageIndex;
PCB *pcb;
pcb = iorb->pcb;
pageIndex = iorb->page_id;
frameIndex = pcb->page_tbl->page_entry[pageIndex].frame_id;
Frame_Tbl[frameIndex].lock_count--;
}
void removePageFromCircularQueue(int frameIndex)
/*
Chiamata da deallocate
Rimuove il nodo della lista circolare contenente il frame
individuato da frameIndex
*/
{
NODE *p;
if (circularQueuePointer == circularQueuePointer->next)
{
free(circularQueuePointer);
circularQueuePointer = NULL;
}
else
{
p = circularQueuePointer;
while (p->frameIndex != frameIndex)
p = p->next;
p->prev->next = p->next;
p->next->prev = p->prev;
if (p == circularQueuePointer)
circularQueuePointer = p->next;
free(p);
}
}
void deallocate(PCB *pcb)
/*
Chiamata da OSP per liberare lo spazio occupato da pcb
Rimuove i corrispondenti nodi della lista circolare,
il relativo working set e resetta i corrispondenti elementi
della tabella dei frames
*/
{
int i, frameIndex;
for (i=0; i<MAX_PAGE>page_tbl->page_entry
.valid)
{
frameIndex = pcb->page_tbl->page_entry.frame_id;
Frame_Tbl[frameIndex].free = true;
Frame_Tbl[frameIndex].pcb = NULL;
Frame_Tbl[frameIndex].page_id = -1;
Frame_Tbl[frameIndex].dirty = false;
framesFree++;
removePageFromCircularQueue(frameIndex);
}
freeWorkingSet(pcb);
}
void prepage(PCB *pcb)
/*
Chiamata da OSP
Vengono caricate le pagine individuate la working set
localizzato nella struttura agganciata a pcb->hook
*/
{
int i, id, numeroPagine;
/* verifica la presenza del working set */
if (pcb->hook)
{
/* numero di elementi presenti nel working set */
i = getNumberOfPagesInWS(pcb);
/* calcolo il numero di pagine in base al valore
di prepage degree */
numeroPagine = (Prepage_Degree * i) / 10;
for (i=0; i<numeroPagine; i++)
{
/* ottengo l'id della pagina i-esima dal working set */
id = getPageIdFromWS(pcb, i);
if (!pcb->page_tbl->page_entry[id].valid)
get_page(pcb, id);
}
}
}
int start_cost(PCB *pcb)
/*
Chiamata da OSP
Stima del costo della prepaginazione
*/
{
int i, j, id, numeroPagine, numeroSwap = 0;
if (pcb->hook)
{
i = getNumberOfPagesInWS(pcb);
/* calcolo in numero di pagine come in prepage */
numeroPagine = (Prepage_Degree * i) / 10;
for (i=0; i<numeroPagine>page_tbl->page_entry[id].valid)
/*
Se una pagina non Š in memoria provo a cercare un frame disponibile
Se lo trovo aumento di uno la variabile numeroSwap
altrimenti (replacement), prevedendo di fare anche uno swap out
aumento tale variabile di 2
*/
{
for (j=0; j<MAX_FRAME; j++)
if ((Frame_Tbl[j].free) && (Frame_Tbl[j].lock_count == 0))
{
numeroSwap++;
break;
}
if (j == MAX_FRAME)
numeroSwap += 2;
}
}
}
/* ritorno il numero di swap stimati per il costo di ogni swap */
return numeroSwap * COST_OF_PAGE_TRANSFER;
}
/* end of module */
