Algorithme d'ordonancement

Soyez le premier à donner votre avis sur cette source.

Snippet vu 18 095 fois - Téléchargée 20 fois

Contenu du snippet

l'algorithme nous fait montrer une simulation de la mémoire virtuelle ;comment est l'ordonnancement des pages en mémoire selon les politiques fifo,lru et fifo seconde chance

Source / Exemple :


#include<stdio.h>
//*****************************************************
//structure de donnée sur l'etat de la memoire
#define NUMBER_FRAMES 10;
struct memorystatetype {
	char state; 	//libre 1 alloue 0
	int page; 	//numero de page logique si alloue

};
struct memorystatetype memorystate[10];
//*****************************************************
//structure de donnée sur la table de page
#define NUMBER_PAGES 20;
struct pagetabletype {
	int frame; 	//numero page physique
	char in;	//bit de validité 1:in 0:out
	char reference;	//bit de reference
	//int loadtime;
	long loadtime;	//temps de chargement
	//int lastreferencetime;
	long lastreferencetime;//temps derniers reference
	char dirty;	//bit de modification
	};

struct pagetabletype pagetable[20];
//*****************************************************
//STRUCTURES DE DONNÉES SUR LA CHAINE DE REFERENCE
#define max_references 30;
struct referencestringtype {
	int page;	//la page referencee
	char accessmode;   // lecture 0 ecriture 1
	};

struct referencestringtype referencestring[30];

 //*****************************************************
//initialisation
//initialiser la memoire
void initmem(int m)
{int i;
for(i=1;i<=m;i++)
{
	memorystate[i].page=-1;
	memorystate[i].state=0;
}
}
//*****************************************************
 //initialiser la table des pages TCP
void initTCP(int k)
{
int i;
for (i=1;i<=k;i++)
{
	pagetable[i].frame=-1;
	pagetable[i].in=0;
	pagetable[i].reference=0;
	pagetable[i].loadtime=0;
	pagetable[i].lastreferencetime=0;
	pagetable[i].dirty=0;
}
}

//*****************************************************
//procedure de l'affichage de l'etat de la memoire
void memorystatedraw(int test, int m, int ref)
{
	int i;
	//switch (test)
	{ 	if (test==-1) {	//printf("|        ");
				printf("%d",ref);
					  printf("                             ");
				printf("               référence incorrecte    \n");
				  }
		if (test==0)  {	//printf("Page référencée n° ");
				printf("        ");
				printf("%d", ref);

			  printf("                      ");
				for (i=1; i<=m; i++)
				{
					if (memorystate[i].page==-1)
						printf(" ");
					else
						printf("%d", memorystate[i].page);
					printf("     ");
				}
				printf("        succes             \n");
				 }
		if (test==1) {	//printf("Page référencée n° ");
					  printf("        ");
				printf("%d",ref);
						//printf("      Etat de la mémoire    | ");
			  printf("                    ");
						for (i=1; i<=m; i++)
						{
					if (memorystate[i].page==-1)
											printf(" ");
										else
						printf("%d", memorystate[i].page);
							printf("     ");
						}
					printf("     echec                   \n");
						}
	}
}

//*****************************************************
//intialisee la chaine de reference
void initrefstring(int n)
{int i;
//intialisee la chaine de reference
for (i=1;i<=n;i++)
{
	referencestring[i].page=-1;
}
}

 //*****************************************************
//fonction de choix de l'algoithme de remplacement
int choixalgo(int choix)
{
	printf("\n\n                                                        \n");
	printf("         Algorithmes  de  remplacement\n");
	printf("                                                          \n\n");
	printf("         Pour    F I F O                 Tapez   1\n");
	printf("         Pour    L R U                   Tapez   2\n");
	printf("         Pour    F I F O  2ieme chance    Tapez   3\n");
	printf("                                                  \n");
	printf("         Donner votre choix : ");
choix:	scanf("%d",&choix);
return (choix);
}

 //*****************************main*********************//

int main()
{
int n,m,k,i,x,choix,e,p,frame,victime,pl;
char rep,rep2;
int test,j;
 //******************************************************
printf("\n  **********************************************************\n");
printf("  ******Simulation de la memoire virtuelle******************\n");
printf("  **********************************************************\n\n");
rep='p';
rep2='p';
e=0;
n=0;

printf("donnez le nombre de cadre de page : ");
scanf("%d",&m);
initmem(m);

printf("donnez le nombre de page logique : ");
scanf("%d",&k);
initTCP(k);

		printf("donnez le nombre de reference : ");
			scanf("%d",&n);

				printf("entrez votre chaine de reference \n");
			for (i=1; i<=n;i++)
			{
			printf("N° de page : ");
			scanf("%d",&referencestring[i].page);

	}
//*****************************************************
	choix=choixalgo(choix);

//*****************************************************
// affichage
	printf("\n\n\n\n                                                    \n");
	printf("  Page référencée n° : ");
	printf("     Etat de la mémoire:    ");
	printf("   resultat :              \n");
	printf("                                                            \n");

//*****************************************************
	//parcourir les m peremiere reference
	//on aura surement m echec au depart

	e=0;
	for (x=1; x<=m; x++)
	{	e=e+1;
	pl=referencestring[x].page;
	memorystate[x].page= pl;
	pagetable[pl].frame= x;
	pagetable[pl].in=1;
	pagetable[pl].loadtime=x;   //time();
	pagetable[pl].lastreferencetime=x;
	if (referencestring[x].accessmode==1)
	pagetable[pl].dirty=1; //bit de modification
	else
	pagetable[pl].dirty=0;
	memorystatedraw(1,m,referencestring[x].page);
	}
//*****************************************************
	//parcourir la chaine de reference apres les m 1ere references
	for (i=m+1; i<=n; i++)
	{	test=-1;
	for (x=1; x<=k; x++)
	{  if (x==referencestring[i].page)
		{
		if (pagetable[x].in==1) test=0;
			else  test=1;
			}
	}
	//switch (test)
	//{	// reference incorrecte
		if (test==-1)
//*******************************************************
		//reference incorrecte
			{
			memorystatedraw(-1,m,referencestring[i].page);
			}
 //*******************************************************
		// cas de succes
		if (test==0)
			{
			p = referencestring[i].page;
			pagetable[p].lastreferencetime=i;   //time();
			pagetable[p].reference=1;
			memorystatedraw(0,m,referencestring[i].page);
			}

	if (test==1)
//****************************************************
	{	// defaut de page
		//case 1:	{
			p = referencestring[i].page;
						pagetable[p].lastreferencetime=i; //time();
								pagetable[p].reference=1;
			e=e+1;
//*******************************************************
//choix du l'algorithme de remplacement
			//switch (choix)
			// algo fifo
			if (choix==1)
					{
					//victime=replaceFIFO(k,frame);
					//printf("%d",victime);
					victime=memorystate[1].page;
					frame=pagetable[victime].frame;
					//chercher celle qui a le temps de chargement + ancien
					for (j=1; j<=k; j++)
					{
					if(pagetable[j].in==1)
					if (pagetable[j].loadtime < pagetable[victime].loadtime)
						{
						victime=j;
						frame=pagetable[j].frame;
						}
					}
				}
//**************************************************************
				//case 2:{  //replaceLRU;
			if (choix==2)
					{
					victime=memorystate[1].page;
													 frame=pagetable[victime].frame;
					//chercher celle qui a le temps de reference le + ancien
					//ça veut dire la moins recement utilisée
					for (j=1; j<=k; j++)
					{
					if(pagetable[j].in==1)
					if (pagetable[j].lastreferencetime < pagetable[victime].lastreferencetime)
						{
						victime=j;
						frame=pagetable[j].frame;
									}
								}
					}// fin case 2
 //************************************************************
	//algo 2 ieme chance
						  //case 3:  victime=replaceclock(k,frame);
			if (choix==3)
			{
		//	memorystatedraw(0,m,referencestring[i].page);
				victime =-1;
				while (victime==-1)
				//chercher celle qui a le temps de chargement + ancien
					{
				for (j=1; j<=k; j++)
						{
					printf("\npage:");
					printf("%d",j);
					printf("\nframe:");
													printf("%d",pagetable[j].frame);
					printf("\nin:");
													 printf("%d",pagetable[j].in);
					printf("\ncharge:");
					printf("%d",pagetable[j].loadtime);
					printf("\nref :");
					printf("%d",pagetable[victime].reference);

					if(pagetable[j].in==1)
					if ((victime==-1) || (pagetable[i].loadtime < pagetable[victime].loadtime))
									{
							victime=j;
									frame=pagetable[j].frame;
							}

						//si cette page est référencée on lui donne une 2eme chance
					if (pagetable[victime].reference==1)
							{
						printf("victime");
						printf("\n%d",victime);
						pagetable[victime].loadtime=i-1;   //time();
						printf("\niiii ");
						printf("%d",i);
							pagetable[victime].reference=0;
								victime=-1;

						}
					}

			} }

	//********************************************************
	//mettre a jour le TCP
				frame = pagetable[victime].frame;
				pl=referencestring[i].page;
					memorystate[frame].page= pl;
					pagetable[pl].frame = frame;
					pagetable[pl].in=1;
					pagetable[pl].loadtime=i;
					if (referencestring[i].accessmode==1)
					pagetable[pl].dirty=1; //bit de modification
				else
					{	pagetable[pl].dirty=0;
							pagetable[victime].in=0;
				}
				printf("\n");
				memorystatedraw(1,m,referencestring[i].page);
				printf("\nvictime ");
			printf("%d",victime);
			printf("\nframe ");
			printf("%d",frame);

				}

	test=-1;
	printf("                                                                 \n");
   //*****************************************************
	printf("le nombre de defaut de page est : %d\n",e);

}}

A voir également

Ajouter un commentaire Commentaires
Messages postés
1
Date d'inscription
vendredi 25 février 2011
Statut
Membre
Dernière intervention
16 novembre 2011

Bon code
Messages postés
26
Date d'inscription
vendredi 8 avril 2005
Statut
Membre
Dernière intervention
31 janvier 2008

Source intéressante, mais est ce que tu as implémenté ces mêmes algorithmes de façon à avoir de meilleures performances ?

Et as-tu prévu d'implémenter d'autres algorithmes d'ordonnancement tels que le LFU, NRU, Clock, ARC, LIRS, CAR ?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.