Ablieferungstermin und erreichbare Punktzahl für diese Aufgabe, sowie Voraussetzungen für die Prüfungszulassung entnehmen Sie bitte http://sar.informatik.hu-berlin.de.

Lab 4 – Tax Collectors Dilemma

In dieser Aufgabe betrachten wir als Szenario eine Stadt bestehend aus einer festen Anzahl an Steuereintreibern (SE). Jeder besitzt ein Anfangskapital von 300 EUR und verfolgt die Aufgabe, von anderen Bürgern der Stadt die Steuerschuld einzutreiben. Allerdings ist auch in unserem Szenario Korruption ein Problem: Jeder Steuereintreiber steckt die eingestrichenen Zahlungen in die eigene Tasche, wodurch sich das Anfangskapital vermehren kann. Andererseits nutzt er auch dieses Kapital, um fällige Steuerforderungen zu begleichen. Für einen Bürger unserer Stadt ergibt sich dadurch der folgende Tagesablauf:

• Der Steuereintreiber A wählt zufällig einen anderen Bürger B aus, von dem er die Steuerschuld einfordert.
• Die Steuer wird vom Konto des Schuldners B abgezogen und auf dem Konto des Eintreibers A gutgeschrieben. Der Steuersatz beträgt 50% des aktuellen Guthabens, wobei auf volle 100 EUR aufgerundet wird, mindestens jedoch 100 EUR.
• Wenn nun B nicht ausreichend Geld besitzt, wartet der Eintreiber A bis B das nötige Geld durch eigene Aktionen eingenommen hat.
• Ein Steuereintreiber soll durch einen Thread realisiert werden. Nach einer vollzogenen Buchung zieht sich der Thread mittels yield() kurzzeitig zurück und wiederholt den skizzierten Ablauf.

Nach einer vorgegebenen Laufzeit werden alle SE-Threads terminiert und es werden Statistiken ausgegeben.

• Pro Steuereintreiber:
  • Anzahl Eingangsbuchungen
  • Anzahl Ausgangsbuchungen
  • Kontostand
• Systemweit
  • Summe Geld im System
  • Summe aller Eingangsbuchungen
  • Summe aller Ausgangsbuchungen

Weitere Anforderungen sind:

• Deadlock-Behandlung - Im System kann es zu Deadlock-Situationen kommen, beispielsweise wenn SE A und B beide kein Geld besitzen, aber sich gegenseitig Forderungen stellen und warten. Deadlocks sollen geeignet behandelt werden, so dass sie die Funktionsfähigkeit des Systems nicht beeinträchtigen. Die aufgezeigte Situation kann beispielsweise dadurch aufgelöst werden, indem einer der Beteiligten zuerst die Steuerschuld bei einem dritten, bisher unbeteiligten SE C einfordert, der die nötige Deckung aufweist.
• Korrektheit - Die Gesamtmenge des Geldes im System ist konstant. Es darf kein Geld verschwinden und kein Geld entstehen.
• Fairness - Alle SE sollen die gleiche Chance haben, Geld einzutreiben oder Steuern zu zahlen.

Bitte verwenden Sie C/C++ unter Linux und legen Sie der Lösung ein Makefile bei, das die Quellen automatisiert übersetzt. Neben den Standardbibliotheken soll nur eine Untermenge der Pthreads API für die Lösung verwendet werden:

• Thread-Funktionen (pthread_create, pthread_exit, pthread_join, pthread_detach, pthread_cancel, pthread_equal, pthread_self, pthread_setcancelstate, pthread_setcanceltype, pthread_testcancel, sched_yield)
• Mutex-Funktionen (pthread_mutex_*, pthread_mutexattr_*)

Die Folien zum Praktikum sind hier zu finden. Die Abgabe der Lösung erfolgt über GOYA. Für Besonderheiten, aufgetretene Probleme und anderweitige Anmerkungen benutzen sie bitte eine Datei index.html. Die Abgabe endet am 03.07.2006 um 12:00 Uhr. Beginnen Sie bitte rechtzeitig mit der Lösung der Aufgabe, da später eingehende Lösungen nicht berücksichtigt werden können.