POLITECHNIKA POZNAŃSKA Laboratorium z systemów operacyjnych |
|||
Implementacja semaforów całkowitoliczbowych. |
|||
Rok akad. 2007/2008 |
Marcin Nawrot 83738 |
Data: |
|
Wydział Elektryczny |
|
|
Oddanie sprawozdania |
Studia dzienne |
|
|
|
Informatyka |
|
|
|
GR I3-B |
|
Ocena: |
|
Implementacja semaforów całkowitoliczbowych.
Należy uwzględnić kolejki procesów czekających pod semaforami. Procesy reprezentowane są przez bloki kontrolne.
1. Struktura danych użytych w programie:
struct element
{
int x;
};
struct kolejka
{
struct element data;
struct kolejka *next;
};
składnik kolejki skład się z „użytecznych” danych przechowywanych w struct data oraz ze wskaźnika next zawierającego adres następnego elementu
Kolejka FIFO użyta do bloków czekających pod semaforem.
Jedno-wymiarowa tablica o maksymalnej wielkości 100
int tab[SIZE]={0}; //tablicz
int key,n=100,liczba,zakres; //zmienne pomocnicze
int z;
struct kolejka *head, *tail, *head_zdejmij,*tail_zdejmij, *pomocnicza; //head-poczatek kolejki czekajacej na wejscie tail- koniec kolejki czekajacej na wejscie head_zdejmij-poczatek kolejki czekajacej na wyjscie tail_zdejmij- koniec kolejki czekajacej na wyjscie
struct element data; //struct kolejki
head = tail = NULL; //zainicjowanie kolejek
head_zdejmij = tail_zdejmij= NULL;
Funkcja dodająca element do kolejki ma postać:
struct kolejka *Insert(struct kolejka *tail, struct element data)
{
struct kolejka *wsk;
wsk = (struct kolejka*) malloc(sizeof(struct kolejka));
wsk->data = data;
wsk->next = NULL;
if (tail != NULL) tail->next = wsk;
return wsk;
}
przykładowe wywołanie funkcji:
head=tail=Insert(tail,data); // pierwsze wywołanie
tail = Insert(tail, data); // kolejne wywołania
Funkcja usuwająca element z kolejki ma postać:
struct kolejka *Remove(struct kolejka *head, struct element *data)
{
struct kolejka *wsk;
if (head!=NULL)
{
wsk = head->next;
*data = head->data;
free(head);
return wsk;
}
else return NULL;
}
przykładowe wywołanie funkcji:
head=tail=Insert(tail,data);// pierwsze wywołanie
tail = Insert(tail, data);// kolejne wywołania
2. Instrukcja użytkownika
Menu:
1 = Stworz blok: // tworzy blok wejsciaow czekajacy pod semaforem
2 = Stworz losowe bloki: // tworzy kilka losowych bloków wejsciaow czekajacy pod semaforem
4 = Stworz jeden blok zdejmowania: //tworzy blok wyjsciowy czekajacy pod semaforem
5 = Stworz kilka losowych blokow zdejmowania: //tworzy kilka losowych blokow wyjsciowy czekajacy pod semaforem
7 = Wpisz do tablicy blok: //Otwiera semafor przepuszcza jeden blok oczekujacy na wejscie
8 = Wypisz z tablicy: // otwiera semafor na jeden blok wyjsciowy
9 = Pokarz tablice i bloki: // Pokazuje zawartosc tablicy i blokow kontrolnych
0 = Koniec: //kończy program
3. Kod programu
// Marcin_Nawrot.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
enum
{
SIZE = 100
};
struct element
{
int x;
};
struct kolejka
{
struct element data;
struct kolejka *next;
};
struct kolejka *Insert(struct kolejka *tail, struct element data)
{
struct kolejka *wsk;
wsk = (struct kolejka*) malloc(sizeof(struct kolejka));
wsk->data = data;
wsk->next = NULL;
if (tail != NULL) tail->next = wsk;
return wsk;
}
struct kolejka *Remove(struct kolejka *head, struct element *data)
{
struct kolejka *wsk;
if (head!=NULL)
{
wsk = head->next;
*data = head->data;
free(head);
return wsk;
}
else return NULL;
}
int _tmain(int argc, _TCHAR* argv[])
{
int tab[SIZE]={0};
int key,n=100,liczba,zakres;
int z;
struct kolejka *head, *tail, *head_zdejmij,*tail_zdejmij, *pomocnicza;
struct element data;
head = tail = NULL;
head_zdejmij = tail_zdejmij= NULL;
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
for(int i=0;i<n;i++)cout<<tab[i]<<" ";cout<<endl;
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
cout<<"Podaj wielkosc tablicy(max=100): "<<endl;
cin>>n;
cout<<"Indeksy tablicy to:\n";
for(int i=0;i<n;i++)cout<<i<<" ";
cout<<endl;
do
{
cout<<"Menu:"<<endl;
cout<<"1 = Stworz blok: "<<endl;
cout<<"2 = Stworz losowe bloki: "<<endl;
cout<<"4 = Stworz jeden blok zdejmowania: "<<endl;
cout<<"5 = Stworz kilka losowych blokow zdejmowania: "<<endl;
cout<<"7 = Wpisz do tablicy blok: "<<endl;
cout<<"8 = Wypisz z tablicy: "<<endl;
cout<<"9 = Pokarz tablice i bloki: "<<endl;
cout<<"0 = Koniec: "<<endl;
cin>>key;
switch(key)
{
case 1: {cout<<"==============================\n";
cout<<"Podaj liczbe: ";
cin>>data.x;
cout<<endl;
if(head==NULL)
{
head=tail=Insert(tail,data);
}
else tail = Insert(tail, data);
break;
};
case 2: {cout<<"==============================\n";
cout<<"Podaj ile liczb ma zostac wpisanych: ";
cin>>liczba;
cout<<endl<<"Podaj gorny zakres losowania: ";
cin>>zakres;
for(int i=0;i<=(liczba-1);i++)
{
data.x=(rand()%zakres + 1);
if(head==NULL)
{
head=tail=Insert(tail,data);
}
else tail = Insert(tail, data);
};
break;
};
case 4:{cout<<"==============================\n";
do{
cout<<"Podaj indeks liczby do bloku zdjecia: "<<endl;
cin>>liczba;
}while(liczba>=n);
data.x=liczba;
cout<<endl;
if(head_zdejmij==NULL) head_zdejmij=tail_zdejmij=Insert(tail_zdejmij,data);
else tail_zdejmij = Insert(tail_zdejmij, data);
break;
};
case 5: {cout<<"==============================\n";
cout<<"Podaj ile liczb ma zostac wpisanych do bloku zdejmowania: ";
cin>>liczba;
for(int i=0;i<=liczba;i++)
{
data.x=rand()%n;
if(head_zdejmij==NULL)
{
head_zdejmij=tail_zdejmij=Insert(tail_zdejmij,data);
}
else tail_zdejmij = Insert(tail_zdejmij, data);
};
break;
};
case 7:{cout<<"==============================\n";
if(head==NULL){cout<<"Niema blokow oczekujacych ";break;}
for(int i=0;i<n;i++)
{ if(n==0)cout<<"Tablicy niema";
if(i==n){cout<<"tablica pelna"
<<endl
<<"Tablica pelna zwolnij miejsce w tablicy"
<<endl;}
if(*(tab+i)!=0)continue;
if(*(tab+i)==0)
{
*(tab+i)=head->data.x;
cout<<"Elemet dodany do tablicy to: "
<<head->data.x
<<endl
<<"Indeks elementu to: "
<< i
<<endl;
head = Remove(head,&data);
break;
};
}
break;
};
case 8:
{ cout<<"==============================\n";
if(head_zdejmij==NULL)
{
cout<<"Blok zdejmowania jest pusty"<<endl;
}
else{
if(*(tab+head_zdejmij->data.x)==0)cout<<"Brak elementu pod tym indeksem\n";
else
{
if(*(tab+head_zdejmij->data.x)!=0)
{
cout<<"Element zdjety to: "
<<*(tab+head_zdejmij->data.x)
<<"\nIndeks elementu to: "
<<head_zdejmij->data.x
<<endl;
head_zdejmij = Remove(head_zdejmij,&data);
};
}
}
break;
};
case 9:
{
pomocnicza = head;
cout<<"==============================";
cout<<"\nTablica: \n";
for(int i=0;i<n;i++)cout<<tab[i]<<" ";cout<<endl;
cout<<"==============================";
cout<<"\nBloki wejscia:\n";
while(pomocnicza!=NULL)
{ if(pomocnicza->next==NULL){cout<<pomocnicza->data.x<<endl;break;}
cout<<pomocnicza->data.x<<" | ";
pomocnicza=pomocnicza->next;
};
cout<<"==============================";
pomocnicza=head_zdejmij;
cout<<"\nBloki wyjscia:\n";
while (pomocnicza!=NULL)
{ if(pomocnicza->next==NULL){cout<<pomocnicza->data.x<<endl;break;}
cout<<pomocnicza->data.x<<" | ";
pomocnicza=pomocnicza->next;
}
cout<<"==============================";
cout<<endl;
break;
};
};
}while(key!=0);
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
for(int i=0;i<n;i++)cout<<tab[i]<<" ";cout<<endl;
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
while (head!=NULL)
{
head = Remove(head,&data);
printf("Remove(wejscie) -->%4d\n",data.x);
}
cout<<endl<<endl;
while (head_zdejmij!=NULL)
{
head_zdejmij = Remove(head_zdejmij,&data);
printf("Remove(wyjscie) -->%4d\n",data.x);
}
system("PAUSE");
return 0;
}
2