Prozesse, Semaphoren

[jrockenf]

Hallo,

ich habe eine Aufgabe, bei der ich nicht weiter komme. Vielleicht kann mir jemand helfen.
Aufgabe 4:

In einem Geschäft wurde ein System zur Ermittlung der Besucher installiert. An beiden Eingängen ist ein Sensor angebracht, der die kommenden Besucher zählt. Die Ergebnisse werden von beiden Sensoren in regelmäßigen Abständen in einen gemeinsamen Puffer geschrieben. Der Puffer hat die Form einer FIFO Queue und kann 30 Elemente speichern. Eine Verarbeitungsstation holt in unregelmäßigen Abständen die Daten (elementweise) ab und verarbeitet diese. Es stehen die Operationen einfuegenDaten() zum Einfügen eines Elements in den Puffer und holeDaten(), die das erste Element des Puffers zurückliefert, zur Verfügung.
Der Puffer kann zu einem Zeitpunkt entweder von der Verarbeitungsstation gelesen oder von genau einem Sensor beschrieben werden.

a) Implementieren Sie mithilfe von Semaphoren die Funktionen lesen() und schreiben(int wert). Ein Sensor soll durch schreiben(int wert) Daten in den Puffer schreiben, und die Verarbeitungsstation soll mit lesen() diese abholen können.

b) Erläutern Sie kurz Ihre Lösung in Bezug auf die verwendeten Semaphoren und ihre Bedeutung.

c) Welche Probleme bezüglich der gesammelten Daten können durch ungünstiges Verhalten von den Sensoren und der Verarbeitungsstation entstehen? Wie könnte man diese Probleme lösen?

Ich soll die beiden Methoden lesen() und schreiben(int wert). Man könnte das ganze in c++ programmieren.

Wie sieht der Lösungsansatz für so eine Aufgabe aus. Kann mir jemand helfen?

Viele Grüße

Jan Rockenfeller

 

[Fujiyama]

Wie ist dein Lösungsansatz bzw woran hängt es momentan?

 

[KingLz]

Klar kann dir jemand helfen, aber Hausaufgaben lösen wird für dich aus Gründen keiner.

Wo hakt es denn? Am theoretischen Verständnis wie semaphore funktionieren oder an der Umsetzung? Wenn du konkret dein Verständnisproblem nennst kann man dir evtl auch helfen.

 

[jrockenf]

Erstmal brauche ich 2 Semaphoren.

Einen Semaphor, dass der Puffer voll ist und einen Semaphor, dass der Puffer leer ist.
Das sind in C++ zwei Varibalen denke ich.

sem empty; (bzw. int emty
sem full; (bzw. int full

Ich habe die beiden Operationen einfuegenDaten() und holeDaten() zur Verfügung.

Der eigentliche Puffer könnte ein Array sein:
int puffer[size];
size= 30;

void lesen() {
int i, tmp = 0;
while (tmp <= 30) {
sem_wait(&full);
tmp = holeDaten();
sem_post(&empty);
printf("%d\n", tmp);
}
}

So lange der Zähler kleiner oder gleich 30 ist, soll er Daten aus dem Puffer holen.

Die beiden Semaphoren sem_wait() und sem_post() sollen folgendes machen und sind zwei Funktionen.

Der Semaphore sem_wait() soll folgendes machen:

int sem_wait(sem_t *s) {
verringere den Wert der Semaphore s um 1
warte falls der Wert der Semaphore s negative ist
}

Der Semaphore sem_post() soll folgendes machen:

int sem_post(sem_t *s) {
erhöhe den Wert der Semaphore s um 1
falls ein oder mehr Threads warten, Thread holen
}

Die Funktion schreiben könnte man sol implementieren:

schreiben(int wert) {
int i;
for (i = 0; i < wert; i++) {
sem_wait(&empty);
schreiben(i);
sem_post(&full);
}
}

Schreibe Daten in den Puffer bis zum angegebenen Wert.

So ungefähr könnte die Lösung aussehen.

Das währe eine Lösungsansatz.

Viele Grüße Jan

 

[duAffentier]

Wieso fragst du denn die KI nicht? Oder evtl mit dem einzelnen Thema auseinandersetzen und dann auf die Lösung kommen.

a) Implementierung mit Semaphoren (kurz)​

Semaphoren:

Semaphore mutex(1);<br>Semaphore leer(30);<br>Semaphore voll(0);<br>
schreiben(int wert):

void schreiben(int wert)<br>{<br> leer.wait();<br> mutex.wait();<br><br> einfuegenDaten(wert);<br><br> mutex.signal();<br> voll.signal();<br>}<br>
lesen():

int lesen()<br>{<br> voll.wait();<br> mutex.wait();<br><br> int wert = holeDaten();<br><br> mutex.signal();<br> leer.signal();<br><br> return wert;<br>}<br>

---

b) Erläuterung (kurz)​

• mutex schützt den Puffer vor gleichzeitigem Zugriff
• leer verhindert Schreiben in einen vollen Puffer
• voll verhindert Lesen aus einem leeren Puffer

---

c) Probleme und Lösungen (kurz)​

• Pufferüberlauf → Sensoren blockieren (leer)
• Lesen leerer Daten → Verarbeitungsstation blockieren (voll)
• Veraltete Daten → Zeitstempel oder schnellere Verarbeitung

---

 

[honky-tonk]

Puffer hat die Form einer FIFO Queue

der puffer muss mit der semaphore vor gleichzeitiger Bearbeitung geschützt werden. wenn er gerade bearbeitet wird darf kein anderer was am puffer machen.

lesen() und schreiben(int wert)

die beiden machst du da das die einzigen methoden sind die direkt den puffer verändern. nichts mit voll und leer semaphore. am besten recherchierst du mal was eine semaphore ist, dann wird es auch klar was zu tun ist.

 

[KingLz]

Als Tipp zum Verständnis:

Die Sensoren arbeiten beide gleichzeitig und unabhängig.

Was würde denn als Beispiel an einer Verkaufstheke passieren wenn alle Kunden gleichzeitig kaufen es aber nur einen Verkäufer gibt? (Es könnten hypothetisch alle auf einmal bedient werden, der Verkäufer kommt aber evtl. durcheinander im Ablauf)
Genau dieses Problem gilt es zu lösen.

Ein System bei dem man eine Marke zieht wäre nach meinem Verständis auch eine Art Semaphore als Beispiel.

 

[jrockenf]

Producer–Consumer-Fall
mit beschränktem Puffer (FIFO, Größe 30)
Zwei Sensoren = Producer, eine Verarbeitungsstation = Consumer.

Zugriffsregel: entweder genau ein Schreiber oder ein Leser gleichzeitig → Mutual Exclusion nötig.

Benötigte Semaphoren

Wir verwenden drei Semaphoren:
mutex = 1 // schützt den kritischen Bereich (Pufferzugriff)
leer = 30 // Anzahl freier Plätze im Puffer
voll = 0 // Anzahl belegter Plätze im Puffer

Schreiben durch einen Sensor
Funktion: schreiben(int wert)

schreiben(int wert):
P(leer) // warten, bis ein freier Platz im Puffer ist
P(mutex) // exklusiven Zugriff auf den Puffer anfordern
einfuegenDaten(wert)
V(mutex) // kritischen Bereich verlassen
V(voll) // ein neues Element ist im Puffer

Erklärung:
leer verhindert Überfüllen des Puffers
mutex stellt sicher, dass nur ein Sensor oder der Leser gleichzeitig zugreift

Lesen durch die Verarbeitungsstation
Funktion: lesen()

lesen():
P(voll) // warten, bis mindestens ein Element vorhanden ist
P(mutex) // exklusiven Zugriff auf den Puffer anfordern
daten = holeDaten()
V(mutex) // kritischen Bereich verlassen
V(leer) // ein Platz im Puffer ist wieder frei
return daten

Erklärung:
voll verhindert Lesen aus leerem Puffer
mutex verhindert gleichzeitiges Schreiben oder Lesen

Vg Jan

 

[KingLz]

Zugriffsregel: entweder genau ein Schreiber oder ein Leser gleichzeitig → Mutual Exclusion nötig.

Würde ich auch so sehen, aber warum ist die Schlussfolgerung dann:

Wir verwenden drei Semaphoren

Erklär mir mal warum du 3 Semaphore brauchst.
Ein Semaphor regelt den Zugriff auf eine geteilte Resource, damit nicht mehrere gleichzeitig etwas verändern können. Wie viele Resourcen gibt es zu verteilen? Und sind diese Resourcen unabhängig voneinander? (Wie viele Resourcen gibt es also wirklich)

Ich will hiermit nicht sagen, dass ich die Lösung kenne, sondern eine Diskussion anregen. Vielleicht sehe ich es auch falsch.

 

[jrockenf]

Hallo,

In der Aufgabe steht drin,
Der Puffer kann zu einem Zeitpunkt entweder von der Verarbeitungsstation gelesen oder von genau einem Sensor beschrieben werden.

Ich benötige also einen Semaphor, der diesen kritischen Zustand, das gleichzeitig geschrieben und gelesen wird verhindert.

Das ist der Semaphor mutex

Zusätzlich kann ich aber auch nicht Daten aus einem leeren Puffer lesen oder in einen vollen Puffer schreiben. Ich benötige also noch 2 Semaphoren die diese 2 kritischen Zustände verhindern.

So habe ich das verstanden.

Wie siehst du das?

Vg Jan

 

[KingLz]

Ich sehe das so:

Zugriff wird per Semaphore verwaltet.
Wer Zugriff hat darf machen was er will, weil wer anders darf nicht ran. (betrifft alle Variablen für die Warteschlange)

In deinem Code brauchst du die extra Semaphore nur weil du erst schaust ob Schreiben/Lesen möglich ist und dann die Resource beanspruchst.

Ich würde einfach die Resource beanspruchen und nachdem ich Zugriff habe schauen ob ich weiter arbeiten kann.
Falls leer/voll würde ich returnen und wieder Zugriff auf die Resource anfordern, wo in der Zwischenzeit ein anderer Teilnehmer den Status (voll/leer) verändert haben kann.

Ich kann dir aber nicht sagen was richtig ist, in der Aufgabenstellung ist von mehreren Semaphoren die Rede.

Würde man gleichzeitig Lesen und Schreiben können, also 2 Resourcen zu vergeben sein, wäre die Situation anders.

Wenn jede Variable der Warteschlange als "Resource" gesehen wird brauchst du natürlich mehrere Semaphore.
Kommt natürlich jetzt darauf an wie es der Aufgabensteller sieht.