Prüfungsteilnehmer Prüfungsüermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 2004 66113 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichenSchulen PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Rechnerarchitektur,Datenb.,Betriebssys. Anzahl der gestelltenThemen (Aufgaben): 2 Anzahl der Druckseitendieser Vorlage: 15 Bitte wenden! Herbst2004 Einzelprüfungsnummer : 66I 13 Seite:2 Thema Nr. I SämtlicheTeilaufgabensind zu bearbeiten! Aufgabe 1: Normalformen Gegebensei die folgenderelationaleDatenbankder Mietwagenfirma,,MobilRent", Station,,München-Mitte": Mobil- KdNr Name Wohnort Buchungs-Aktion FahrRent datum zeup r23 Chomsky Nümberg n.ar.04 0 Micra Tvp TarifTage gfaDDe I ? t23 Chomsky Ntirnberg 07.10.03 - 25% Sprinter Transp 5 I 220 Neumann München 02.04.04 0 7IA Turing Klein Rückgabe- Stationsstation Ieiter Nürnberg- Backus Süd Ntimberg- Hoare Nord Mtinchen 20.02.04 8 8 8 Neumann Passau Lupo Klein I 2 t0% Micra Klein I 2 Miuel- 3 klasse 5 07.10.03 - 2s% A3 MünchenMitte MtinchenMitte MtinchenMitte Zuse Zuse Zuse ,,KdNr" stehtfür die Kundennummerder Kunden.An bestimmtenTagengewährtdie Firma Rabatt.FolgendefunktionaleAbhängigkeiten seienvorgegeben: KdNr -+ Name,Wohnort -+ Fahrzeug, KdNr, Buchungsdatum Typ, Tarifgruppe,Tage,Rückgabestation, Stationsleiter -+ Buchr.rngsdatum Aktion Fahrzeug-+ Typ, Tarilgruppe Typ -+ Tarifgruppe -+ Stationsleiter Rückgabestation 1. ErklärenSiekurz denUnterschied zwischen,,Schlüsselkandidaf' und ,,superschlüsse1... 2. ErklärenSie,warumnur (KdNr, Buchungsdatum)als Schlüsselkandidat in Fragekommt. 3. BegründenSie,warumnur Relationenmit einemzusammengesetzten Schlüsselkandid atendie2. Normalformverletzenkönnen. 4. ErläutemSie,inwiefernobigesSchemadie zweitebzw.dritteNormalformverletzt.ZeigenSie anhandobigerRelation,,MobilRent"möglicheAnomalienau{ die bei fehlenderNormalisierung auftretenkönnen. 5. BegründenSie,dassobigesSchemain ersterNormalformist und überführenSieesin die zweite, abernichtin die dritteNormalform.ErläutemSiedie dazudurchzuführenden Schritteieweils krrz. ZergenSie,inwiefemdie entstandene Relationdie dritteNormalformverletzt. 6. ÜrberführenSiedasSchema,ebenfallsmit kurzerErläuterung,nun in die dritte Normalform. FortsetzunsnächsteSeite! Herbst2004 Einzelprüfungsnummer : 661L3 Seite:3 Aufgabe2: E-R-Modellierung Für ein Transportunternehmen soil eineDatenbankfür folgendesSzenarioentwickelt werden: Die FirmaverfügtübermehrereAbteilungen,die vonjeweils einemMitarbeitergeleitetwerden,und jederMitarbeiter,von demName,Wohnortund Gehaltsstufe abgespeichert werdensollen,ist einer dieserAbteilungeneindeutigzugeordnet. Der BetriebbesitztmehrereTransporter verschiedener Typen.Dieseunterscheiden sichdurchGröße,maximaleNutzlastundbenötigteFührerscheinklasse. Die einzelnenFahrzeuge werdenfortlaufendnummeriertundessoll dasBaujahrsowiederTermrnzur nächsten Inspektionabgespeichert werden.NebendenVerwaltungsangesteliten (für Buchhaltung, Personal, Kundenbetreuung etc.)unddenhauseigenen KFZ-Meistem(zur LKW-Wartung)beschäftigt dasLogistikunternehmen natürlichinsbesondere Fahrer.Buchtein KundeeineTour, sowerdenflir diesewenigstens ein Fahrerund ein Transporter eingesetzt. Von dergebuchten Tourmüssenfolgende Datenabrufbarsein:Buchungsdatum, Terminunddie AnzahlderbenötigtenLKWs. Von denKunden müssenName,Wohnortund die zugehörige Firmavorliegen. ErstellenSieein E-R-Diagramm. VerarbeitenSiedabeinur die unbedingtnotwendigen Informationen,gebenSieaberan,wie die nichtim E-R-Modellauftauchenden Informationen bestimmtwerden können.LegenSieauchdie Primärschlüssel festundbegründen SieIhre Entscheidung, falls SiezusätzlichekünstlicheSchlüsseleinfüeen.GebenSiedie Funktionalitäten an. Aufgabe3: Threads 1. Besitztjeder ThreadeineneigenenKellerspeicher?ErläuternSie Ihre Antwort. 2. Besitztjeder Threadeinen eigenenAdressraum?ErläuternSie Ihre Anfwort. 3. ErläuternSie die Realisierungvon Threadsim Benutzer-Adressraum. 4. ErläuternSie die Realisierunsvon Threadsim System-Adressraum. 5. Threadsin Java: Im Folgendensoll derBetriebeinesParkhauses teilweisesimuliertwerden.Ein ObjektderKlasse Parkhaus repräsentiert dasParkhaus. JedesFahrzeugwird alseigenerThreadsimuliert. FolgendeKlassenseiengegeben: public class public ParkhausTest { void main(String[] args) static Parkhaus P : new Parkhaus (50); /* Hier Objekts 100 Threads mit Hilfe p erzeugen und starten { der Klasse Fahrzeug (siehe Teil-aufgabe und des a) */ FortsetzungnächsteSeite! Herbst2004 public Einzelprüfungsnummer : 66LL3 class Parkhaus t --'r '--!' int kapazitaet; P r J _ v d L \ ^y r*r.v: .a..-u{€- , i n t a n z F a h r z e u g e ; public Seite:4 / / Kapazitaet des Parkhauses // Anzahl der parkenden Fahrzeuge Parkhaus (int kapazitaet) { = kapazitaet; this.kapazitaet anzFahrzeuge = 0; i (Methode noch zv ergaenzen, siehe Teilaufgabe / / Einfahrt public void einfahrr ( ) { anzFahrzeuge++,' b) ) (Methode noch zo ergaenzen, / / Ausfahrt public void ausfahrt ( ) i anzFahrzeuge--; siehe Teilaufgabe b) ) ) public class Fahrzeug implements Runnable { private Parkhaus p; public Fahrzeug(Parkhaus p) this.P : P; { ) public void run ( ) { / / fn Parkhaus einfahren p.einfahrt ( ) ; / / Aufenthalt try t T h r e a d . s l e e p ( ( i n t ) ( M a t h . r a n d o m O * 1 0 0 0 0 )) ; (TnterruptedException e) { } c a t c h ) / / Aus 'Parkhaus ausfahren p. ausfahrt O ; a) ErgänzenSiedie KlasseParkhausTest so,dassmit Hilfe der KlasseFahrzeucr und des Objekts p einhundertThreads erzeugtund gestartetwerden. b) ErgänzenSiedie Methodeneinf ahrt O und ausf ahrt O der KlasseParkhaus so, dassderZugnff auf anzFah rzeuge unterwechselseitigem Ausschlussgeschieht!Fernersoll folgendesSzenariosimuliert werden:Wenn die Kapazitat des Parkhauseserschöpftist, warten einfahrbereiteFahrzeugein einer Wartezone.Immer wenn ein Fahrzevgdas Parkhausverlassen hat, verlässtein beliebigeswartendesFahrzeugdie Wartezone. Fortsetzung nächsteSeite! Herbst2004 Einzelprüfungsnummer : 66L13 Seite:5 Aufgabe4: Semaphore Vor dem Ztgang zu den Flugsteigeneines Flugplatzesfindet in einerSicherheitszoneeine Sicherheitsüberprüfung der Passagiere statt.In der Sicherheitszone dürfensich immer nur maximal10 Passagiereaufhalten. Die Sicherheitszone enthält einenKontrollbereich mit einemGeptickkontrolleurwd einemPersojedes nenkontrolleur. Um Gepäckstück eindeutigeinemPassagier zuordnenzu können,ist im Kontrollbereichnur maximalein Passagier erlaubt. Der Gepäckkontrolleur darf erstdaanmit seinerKontrollebeginnen,wennein Passagier denKontrollbereichbetretenhat.ErstnachdemderGepäckkontrolleur demPassagier dasGepäckstück abgenommenhat,darfderPersonenkontrolleur mit derKontrollebeginnen.Der Gepäckkonholleur darf demPassagier dasGepäckstück erstdannwiederzurückgeben, wennderPersonenkontrolleur seine Kontrollebeendethat. Nur wenneinekompletteKontrolle(Personund Gepäck)durchgeführt wurde,darfderPassagier den Kontrollbereich verlassen. FolgendeProzesse seiendefiniert: Passagier{ ) -- Gepäckkontrolleur { Gepäckstück l Personenkontrolleur { l StellenSiemit Hilfe von Semaphoren denobenskizziertenAblauf sicher.GebenSiedazudie Semaphoremit einemkurzenaussagekräftigen Kommentaran.GebenSieauchzu jedemSemaphor die Art (booleschoderganzzahlig) Anfangsbelegung sowiedie an. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 66113 Seite:6 Aufgabe 5: MaschinennaheProgrammierung Gegebensei eine einfacheMaschinemit folgendenEigenschaften: o . ' o E,sstehen8 RegisterRo-R7 mit je a Byte Breite zur verfügung. Das einzige Datenformat ist eine 4Byte lange Ganzzahl. In einemProgrammwerden Speicheradressen nur per Marken angegeben.Als Marken jedoch keine Zahlen,verwendetwerden. könnenbeliebigeZeichenreihen, Befehlssatz: Befehl Wirkung MOVE R/rr.Rn Rn :: Rrn MOVE int.Rtr Rn:: int MOVE marke.Rn MOVE Rm, marke ADD opl, op2,Rn SUB opl, op2,Rn MULT op[, op2,Rn DIV opl. on2.Rn JMP marke [Rn:: fmarke] fmarkel:: R.rn Rz := apl + ep2 JEQ Rfti, Rfl. marlee JGT Rt ?, Rrl, marke JLT Rrn,Rn. marke Rn :: opl - op2 Rn :: opl * op2 Rn :: opl div op2 (Gamzahldivision) unbedingterBefehlssprungzu Adressemarke Egf{l5q1t4ttr g ztr marke, falls Rrn = Rz Befehlssprungzs marl(e,falls Rm > R , Befehlsspmngzg marke,falls Rm < Rr Dabei gelten folgendeVereinbarungen: . tn,ne {0,1,...,7} ' markeist eine Speicheradresse, derenInhalt mrt lmarkel angegeben wird. I int ist eine ganzeZahl. ' Für opl und op2 können folgendeOperandeneingesetztwerden: c ein beliebiges RegisterP..m, m e {0,1,...,7) o eine ganzeZahl int alsunmittelbarerOperand o JedeZeile einesProgrammsenthältgenaueinenBefehl und evtl. einenKommentar,derdurch zwei Schrägstriche (ll) gekennzeichnet wird. o JedeZetle kann am Anfang durch eine Marke gefolgt von einem Doppelpunkt gekennzeichnet werden,um als Sprungzielzu dienen. . Beispiel frir ein Programm: anfang: MOVE 10, RO MOVE RO, R1 suB Rl, 5, Rl JLT RO, R1, anfang // // // // RO .: 10 Rl RO Rl Befehlssprung zu anfang, fal1s ROt : m0 , n > 0 ) 2. SetzenSie folgendehochsprachliche Routinezur Berechnun g der gxuzahligenWurzelcinergarzen > Zahl a 1 in ein Programmder gegebenen Maschineum. Der Wert derVariablena stehtan der Markea zurVerfügung.Der WertderVariablenerg soll an derMarke e rg abgespeichert werden.VerwendenSie Registerzur UmsetzungderübrigenVariablen. -/ ug : 0; oq : ai (ug while m : ug + ( (og-ug) r r r m: m * m ; (mm -- a) | ug = mi og : m+1; (mm < a) e l s - if ) ug = m; i else { og : rni div if | 2); / / Interva]l initialisieren // / / Mitte des Intervalls bilden bilden Quadrat der Mitte a ob Quadrat gleich / / Prüfen, so setzen, dass Abbruch/ / Intervall ist / / bedingung erfülIt als a, // Wenn Quadrat kleiner unten anpassen / / dann fntervall // Wenn Quadrat größer als at oben anpassen / / dann Intervall ) I erg : ug; // Intervalluntersrenze ist Erqebni-s Aufgabe6: Rechnernetze 1. MAc-Teilschicht: Beschreiben SiedasCSMA/CD-Verfahren. 2. Transportschicht: NennenSieUnterschiede zwischenTCP und UDP. -8 Herbst2004 Einzelprüfungsnummer: 66It3 Seite:8 ThemaNr. 2 SämtlicheTeilaufgabensind zu bearbeiten! Aufgabe1: Routing Im Intemetwerdendie beidenInterior GatewayProtokolle(IGP) DistanceVector und Link State verwendet.In dieserAufgabe soilen Sie die unterschiedlichen Vorgehensweisen der beidenRoutingprotokolleanhandeinesBeispielsnachvollziehen und erkläiren. Gegebensei dasin Abbildung1 dargestellte IP CoreNetzwerk.Es bestehtaus einerReihevon Routem,die miteinanderverbunden jeweils die Kostender einzelnenVerbindungen sind.Die Verbindungskanten gebenals Parameter an. gelten Diese in beideRichtungen. 2 ""W."""-.'... G "./" .l'"'o' 3 Abbildung I : Beispielnetz t . ErstellenSie für das in Abbildung I dargestellteBeispielnetzdie Distanzvektor-Tabelle im Router C für die erstenAustauschphasen, bis sich die Distanzvektor-Tabelle desRoutersC nicht mehr ändert.ErläuternSie dabeiIhre Vorgehensweise und erklärenSie weshalbsich die Tabellennach einer bestimmten Anzahl von Informationabgleichennicht mehr ändern. 2. Nehmen Sie nun an, dassdie Verbindung zwischenden beidenRoutern C und E ausftillt.BerechnenSie die neue Distanzvektor-Tabellenach den nächstenAustauschschrittenin Router C. 3. VerwendenSienun denLink State(Dijkstra)Algorithmus,um die RoutingTabelledesRouters C aufzubauen. Dabeiist wie in Teilaufgabe I von einemNetzohneAusf?illeauszugehen. DokumentierenSiedabeijeweilsdie Ergebnisse nachjedemSchrittin derForm einerTabellederbestätigten,betrachtetenund verworfenenAbstäinde. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 66I 13 Seite:9 Aufgabe 2: Verständnisfragen In dieserAufgabewerdenVerständnisfragen zv unterschiedlichen Themengestellt.Bitte haltenSie Ihre Antwoften kurz. 1. ErläuternSie die UnterschiedezwischenSimplex-,Halbduplex-,und Vollduplex-Übertragung. BeurteilenSie die Verfahrennachihrem Durchsatzunterder Voraussetzung,dassalle Mechanismen die gleiche Zeichenratezur Leitungscodierungverwenden. WelcheVermittlungsverfahren kennenSie?ErläuternSie die Unterschiedezwischenden Verfahren. WelcheNetzstrukturenkennenSie?GebenSie die drei Basistopologienan und erläuternSie die [Jnterschiede zwischenden Strukturen. 2 . Was verstehtman unter den Begriffen "(Repeating)Hub", "Switch (-ing Hub)", "Switchrouter" und "Router"? ZetchnenSie dasISO/OSI Schichtenmodellund erklärenSie stichpunktartigdie Aufgabender einzelnenSchichten. Was verstehtman unter dem Begriff CIDR? Wozu wird es eingesetztund warum wurde es eingeführt? SktzzretenSie den Aufbau einesGSM Kanals und erläuternSie die dabei eingesetztenMultiplextechniken. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 66113 Seite:10 Aufgabe 3: Datenbankanfragein SQL Wir betrachtendie DatenbankUtItveRsITAr mit denfolgendenBeispieltabellen: Sruogt'qr Semester Hauptfach 147m0 Schmidt t lnformatik 148000 Maier 2 lnformatik Matnr Name VontEsut'lc Name r0640 Einfühnrngin die lnformatik 10650 Datenstrukfuren r0410 DiskreteMathematik Vnr sws r0780 Datenbanken Fach 4 4 Informatik 3 3 Mathematik Informatik Informatik VeRnNSTALTUNc Vnr Semester Dozent 10650 ws 0102 Tarjan 10650 ss 2002 Mehlhorn r0780 ws 0102 Ullman Vnr NoTnxvERTEILUNG Semester Matnr Note 10650 ss 2002 r47000 3 10650 ss 2002 148000 I 10780 ws 0102 148000 2 VoneussETZUNG hatVorausI istVoraus 10650 10410 10650 10640 10780 10650 ErstellenSiein SQLfolgendeAnfragen: (Vnr, Name),die derDozent,,Ullman"gehaltenhat. a) BestimmenSiealleVorlesungen (Matnr,Name),die in derVorlesung,10780'eineNoteerhalten b) BestimmenSiealle Studierenden haben. im Fach,Informatik'. c) BestimmenSiedie AnzahlderVoriesungen (Vnr,Name)derVorlesung,Datenstrukturen'. d) BestimmenSiealle Voraussetzungen über alle ihre e) BestimmenSie fi.ir alle Studierenden(Matnr, Name)die Durchschnittsnoten gehörtenVorlesungen. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 66113 Seite:11 Aufgabe 4: Datenmodellierung und Datenbankaulbau Wir betrachtendie Datenbank UNIVERS ITAT ausAufgabe 3 a) Definieren Sie die Relationenschemas von UNIVERSITAT eigneteSchlüsselund Fremdschlüsselan. in SQL, und gebenSie dabei geb) Fügen Sie in SQL in jede der Relationen . STI,'DENT, . \€RANSTAITI'NG UNd . NOTE}IVERTEILLTNG ausAufgabe 3 jeweils mindestensein weiteresgeeignetesTupel ein, so dassdie natürlichen Schlüssel-und Fremdschlüsselbedingungen ausTeil a) erfüllt sind. c) Geben Sie ein ER-Diagramm (mit Funktionalitätsbedingungen) für das Datenbankschemaaus Aufgabe 3 an, in dem möglichst viele Relationenals Relationshipsmodelliert sind. Aufgabe 5: Funktionale Abhängigkeiten Gegebensei folgendeMenge F von funktionalenAbhängigkeiten: F = {BC -+ A, AC -+ DE, A -+ D}. a) GebenSiezwei unterschiedliche Ableitungenfür die funktionaleAbhängigkeitBC -->D an. - b) BestimmenSiedie Attributhüllevon BC tnter F. c) BestimmenSieein minimalesSystemG für F. BestimmenSiemit demSynthese-Algorithmus aus G eine3NF-Zerlegung desRelationenschemas,R mit derAttributmenge u = ABCDE md der MengeF von funktionalenAbhängigkeiten. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer: 66113 Seite:12 Aufgabe 6 : Betriebsmittel-Zuteilung Zu einem Zeitpunkt t sei in einem Systemmit drei Prozessen[A, B, C] folgende BetriebsmittelZuteilunggegeben: A hält eine Instanzvon Ressource-TypRl und zwei lnstanzenvom Ressource-TypR2 B hält eine Instanzvom Ressource-TypR2 und eine Instanzvom Ressource-TypR3 C hält eine lnstanzvom Ressource-TypR2. Dabei existiereninsgesamtim System: Eine Instanzvom Ressource-TypRl Vier Instanzenvom Ressource-TypR2 Zwei lnstanzenvom Ressource-TypR3. FolgendeAnfordemngenbestehen: A benötigt eine Instanz von R2, um erfolgreichterminieren^) können B benötigt eine Instanz von R2, um erfolgreichterminierenzu können C benötigteine Instanzvon R3, um erfolgreichterminierenz.skönnen. a) VervollständigenSie den Betriebsmtttel-Zuteilungsgraphen in folgendem Schema: b) ffi r o i . ,i, ffi R1 R2 R3 Gibt es Prozesse,die blockiert (: verklemmt)sind?Wennja: welcheProzessesind diesund warum? c) Was ändertsich am obigen Systemzustand bzgl. desBlockierensvon Prozessen,wenn zusätzlich zu den bestehendenAnforderungengilt: C benötigteine Instanzvom Ressource-Typ Rl, um erfolgreichterminierenzu können? FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 661r 13 Seite:13 Aufgabe 7: SicheresTerminieren von Prozessen Zu einemZeitpunkt/ sei ln etnem Systemmit fünf Prozessen [A, B, C, D, E] folgende B etriebsmittel-Zutei lun egeben: s/w-Drucker Scanner o l --+ 1 i i I 0 o l -----o- II NachfolgendeTabellegibt an,wie vieleRessourcen die Prozesse nochbenötigen,run bis zur erfolgreichenlqqnidqlqe@qi!_e{Leu_Iö:Ufqq: Prozess I Farbdrucker i s/w-Drucker i n l " Scanner t r ' Von jedemRessourcentlpsind ins t vorhanden: Farbdrucker s/w-Druckeri CD-Brennerl Scanner a) Stellen Sie zunächstdie für die beteiligtenProzessebenötigtenM atrizenNeed (: momentaner Restbedarfl, Max (= N4o"r*albedarf bei Betreten des Systems)und Allocation (= momentane Belegung) und den Vektor,4 vailable (: momentane Verf)gbarkeit) aü. Prüfen Sie anschließend(2. B. mit dem Banker'sAlgorithmus), ob das Systemin einem sicheren Zustandist (d. h. es existiert eine Reihenfolge,in der alle Prozesseterminierenkönnen).Falls der Ztstand.sicher ist, reicht die Auflistung einer möglichen Terminierungsreihenfolgemit der jeweiligen Angabe des aus einer TerminierungresultierendenAvailable Yektors. Falls der Zßtand, nicht sicher ist, gebenSie einen Systemzustandan, in dem Prozessenicht mebr erlol sreich terminierenkönnen. b) Ausgehend von obigerSituationbenötigeProzessE statteinemnun zwei CD-Brenner. Karn dieseAnforderungerfüllt werden? c) ErläuternSie knapp,warum der Lösungsansatz aüsa) in real existierendenSystemenschwierig umzusetzen ist! FortsetzungnächsteSeite! Herbst2404 Einzelprüfungsnummer: 66113 Seite:14 Aufgabe8: Paging-Strategien Bei derVerwaltungvon virtuellemSpeicherwerdenSeitenverdrängungsalgorithmen benötigt,da der virtuelleAdressraum i. A. erheblichgrößerist alsderphysikalischtatsächlichvorhandene Speicher. Gegebenseinun einProzess,der auf die logischenSeitenI bis 4 in derfolgendenReihenfolge zugreift: l, 3,2, 4, 3, 3, 4, 3, I jeweils eine,zwei, drei odervier Kawerdenproduziert,wenndemProzess Wie viele Seitenfehler chelnzur Verfügungstehen?Beantworten SiedieseFragenfür die Seitenverdrängungsalgorithmen: a) OPT (Belady'soptimaleStrategie) b) FIFO(First-ln-First-Out) c) LRU(Least-Recently-Used) -Lllnwels: g"urhtttt Siedabei,dassdie Kachelinzu Beginnleerist/sind;d. h. derersteZugriff auf einelogische SeiteerzeugtaufjedenFall einenSeitenfehler. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 661, 13 Seite:15 Aufgabe 9: Prozesskoordination EinekleinePKW-Tarkstellebesitze4 Tankplätze(TP1,...,TP4),wobeiman anjederSäulealle gängigenTreibstoff-Sorten zapfenkann.Fernerexistiertein Waschplatzzur Autowäsche, in demzu eigenau gewaschen (Waschplatz ein PKW werdenkann nemZeitpunkt WP).Von der Straßeherkommendkönnenbis zu 5,PKWsin derZufahrtzur Tankstellehaltenundwarten(Halteplätze HPl, ..., will immer HP5).Ein Kunde entwedertankenoderwaschen niemalsbeides.WeitereWarteplätze aufdemTankstellen-Gelände sindnichtnutzbar.Realisieren Ablaufder Sienun denreibunsslosen (Counting mit Zähl-Semaphoren Tankstelle Semaphores). a) Definieren Sie in einer beliebigenobjektorientiertenSpracheoder in Pseudo-Codedie benötigten Schnittstellen(Konstruktorenund Methoden) und die intemen Datenfeldereiner Zähl-Semaphore Semaphore. Eine konkrete Implementierungder Konstruktoren-und Methodenrümpfeist nicht nötis. b) BenutzenSie lhre Zähl-Semaphore ausTeil a), um den untenstehendenProgrammcodezu vervollständigen.Es könnenin Ihrer Lösungeiner,keiner oder mehrereSemaphore-Aufiufeauf einer ... -Linie stehen. class Tankstelle { Semaphore Tankplatz Semaphore Waochplatz Semaphore HaltePlabz public void = nevr $emaphore(.. . . . . .) ; = new Semaphore (. . . . . . . ) ; a new Semaphore (. ., . . . . ) ; (auto benuEzeTankstelle f ahreWarEestreif en (einAuto) ; (einAuto.willTankenO if ) { beleserankpi;;; i;i;;;i ' ; ) elee { belegeWaschplat.z (einAuto) ; ) f ahreAusf ahrt (einAut,o) ; ) I t tl r 1 einAuEo) {