NL9001262A

NL9001262A - Werkwijze voor het in een logisch georganiseerd systeem, van door digrafen te representeren groepen van met elkaar in relatie staande entiteiten, distribueren van status-informatie betreffende een digraaf en een inrichting voor het toepassen van een dergelijke werkwijze.

Info

Publication number: NL9001262A
Application number: NL9001262A
Authority: NL
Original assignee: Oce Nederland Bv
Priority date: 1990-06-05
Filing date: 1990-06-05
Publication date: 1992-01-02
Also published as: US5241673A

Description

Werkwijze voor het in een logisch georganiseerd systeem, van door digrafen te representeren groepen van met elkaar in relatie staande entiteiten, distribueren van status-informatie betreffende een digraaf en een inrichting voor het toepassen van een dergelijke werkwijze

De uitvinding heeft betrekking op een werkwijze voor het in een logisch georganiseerd systeem, omvattende een samenstel van door digrafen zonder subcykels te representeren groepen van via gerichte ribben met elkaar in relatie staande, door knooppunten te representeren entiteiten, distribueren van status-informatie betreffende de digraaf over de knooppunten van de digraaf, waarbij per digraaf aan elk knooppunt een unieke identifier is toegevoegd en waarbij met elk knooppunt dat niet een bijzondere status heeft, een verzameling geassocieerd is, waarvan ieder element een variabele representeert die separaat gekoppeld is met een onmiddellijke voorganger van het knooppunt, alsmede op een inrichting voor het toepassen van een dergelijke werkwijze. Een dergelijke werkwijze is bekend uit het artikel: M.Schelvis and E.Bledoeg: "The implementation of a Distributed Smal!talk", ECOOP188 proceedings, Lecture Notes in Computer Science 322, Springer-Verlag, pp. 212-232 (1988). Dit artikel beschrijft zo een werkwijze ten behoeve van het uitwisselen van pakketgebonden informatie zoals dat wordt toegepast in een gedistribueerd object-georiënteerd systeem, ten behoeve van het gedistribueerd reclameren van geheugenruimte, hierna aan te duiden met "Distributed Garbage Collection".

Garbage collection wordt veelal toegepast in systemen, waarin het geheugen georganiseerd is als een "heap", zoals in Smal1 talk of Lisp systemen. In Smalltalk systemen wordt bij de creatie van een object hieraan dynamisch geheugenruimte toegewezen van de heap. Objecten zijn door middel van referenties met elkaar verbonden. Een groep van naar elkaar refererende objecten vormt een gerichte graaf met de objecten als knooppunten en de referenties of pointers als ribben. Sommige objecten zijn van buiten de graaf toegankelijk en worden root-objecten genoemd. Objecten "leven" als ze een root hebben, dat wil zeggen als ze toegankelijk zijn via een vanuit een root-object vertrekkend pad door de graaf. Garbage collection heeft als doel geheugenruimte die wordt ingenomen door "dode" objecten, dat zijn objecten die niet meer toegankelijk en dus nutteloos zijn, weer vrij te geven.

Het genoemde artikel beschrijft een aantal volgens deze werkwijze werkende systemen welke zijn ingericht voor distributed garbage collection en vermeldt daarbij hun specifieke nadelen: - System Wide Mark and Sweep: dit systeem werkt niet als op een zeker moment niet alle aangesloten computer-eenheden tegelijk mee kunnen werken; - Reference counting and weighted reference counting: dit systeem kan geen cyclische structuren aan; en - Generation Scavenging: in dit systeem kunnen cyclische structuren niet worden gedetecteerd.

In genoemd artikel wordt voorts de wens geuit om te komen tot een verbeterde wijze van uitvoering van distributed garbage collection, waarbij genoemde nadelen niet aanwezig zijn. Het artikel onthoudt zich evenwel over de te nemen maatregelen, welke betrekking hebben op het samensten en van de uit te wisselen pakketten.

De uitvinding beoogt een werkwijze van de in de aanhef omschreven soort te verschaffen, waarbij de aan genoemde systemen verbonden nadelen, zijn vermeden. De uitvinding berust primair op het inzicht het proces om cykels te detecteren - door telkens de grootste, bij dat knooppunt op dat moment bekende, identifier van een knooppunt door te sturen - te onderbreken zolang er nog een van buitenaf komend pad naar de cykel is.

Overeenkomstig de uitvinding omvat de werkwijze als.in de aanhef is omschreven volgens een eerste methode de navolgende stappen: - het toekennen van de waarde van de identifier van een knooppunt met een bijzondere status aan elke variabele welke met dit knooppunt is gekoppeld; - het verwijderen van elke variabele welke gekoppeld is met een knooppunt, als in de daarmee geassocieerde verzameling elke variabele gelijk is aan de identifier van dat knooppunt of als de verzameling leeg is; - het toekennen van de waarde van de identifier van een knooppunt aan elke variabele welke gekoppeld is met dit knooppunt, -als deze iden-tifier aan een bepaald vergelijkingscriterium voldoet met betrekking tot de variabelen van de verzameling geassocieerd met het knooppunt en mits dit knooppunt niet een knooppunt met een bijzondere status is; en - het toekennen van de waarde van een variabele van de verzameling geassocieerd met een knooppunt aan elke variabele welke met dit knooppunt gekoppeld is, als alle variabelen van de verzameling geassocieerd met dit knooppunt identiek zijn en de identifier van dit knooppunt niet voldoet aan het vergelijkingscriterium met betrekking tot laatstgenoemde variabelen.

Bijzondere omstandigheden doen zich voor air de variabele zodanig gedefinieerd is dat deze een rij omvat, waarin geen, één of meer iden-tifiers van knooppunten voorkomen. In dergelijke omstandigheden wordt overeenkomstig de uitvinding de werkwijze van de in de aanhef omschreven soort volgens een tweede methode gekenmerkt door: A. het per knooppunt met bijzondere status toekennen van de identifier van het knooppunt aan elke variabele welke met dit knooppunt is gekoppeld; B. het per knooppunt dat niet een bijzondere status heeft, op basis van de variabelen uit de met het knooppunt geassocieerde verzameling, uitvoeren van de navolgende stappen: - het verwijderen van elke variabele met een rij, waarin als bestanddeel met een gedefinieerde ligging een rij van een andere variabele voorkomt, mits laatstgenoemde rij voorzien is van een merkteken; - het bepalen van een referentiewaarde door eerst aan de hand van een eerste vergelijkingscriterium een variabele te selecteren en vervolgens uit de door deze variabele omvatte rij, die iden-tifiers, inclusief merkteken indien aanwezig, te verwijderen welke voldoen aan een tweede, op de identifier van onderhavig knooppunt gebaseerd vergelijkingscriterium; en - het uit de resterende variabelen en de verkregen referentiewaarde afleiden van een waarde en deze als resultaatwaarde toe kennen aan elke variabele welke gekoppeld is met het onderhavig knooppunt waarbij, in het geval dat deze waarde voorzien is van een merkteken en de rij slechts een identifier bevat, het onderhavig knooppunt zekerheid heeft verkregen over de status van de digraaf.

De hier geschetste werkwijze is bij uitstek geschikt voor toepassing in een systeem, waarin dl grafen met subcykels voorkomen.

Een voorkeursuitvoeringsvorm van de werkwijze is gekenmerkt doordat de variabelen naar een replicaverzameling worden gekopieerd, waarna genoemde stappen, uit te voeren per knooppunt dat niet een bijzondere status heeft, worden uitgevoerd op de replicaverzameling.

Hierdoor is het mogelijk dat ook tijdens het uitvoeren van de werkwijze op een knooppunt, nieuwe waarden toegekend worden aan de variabelen door de knooppunten die met deze variabelen gekoppeld zijn, omdat de stappen uitgevoerd worden op de kopieer, van de variabelen in de repli caverzameli ng.

De werkwijze is ook toepasbaar in gevallen waar knooppunten met bijzondere status dynamisch worden toegevoegd aan of worden verwijderd van de digraaf doordat de werkwijze tevens de volgende stappen omvat: - het zetten van het tijdstempel behorend bij een knooppunt op het moment dat een koppeling wordt gecreëerd naar dit knooppunt toe, en - het zoveel wijzigen van het tijdstempel van een knooppunt dat een resultaatwaarde wordt verkregen die groter is dan een eerder verkregen resultaatwaarde in het geval een lege resultaatwaarde is ontvangen van een onmiddellijke voorganger.

De uitvinding zal nu nader worden toegelicht aan de hand van de bijgaande figuren, waarin:

Fig. 1 een logisch georganiseerd systeem toont, waarin een tweetal groepen van logische componenten voorkomen, waarbij elke groep wordt weergegeven door een digraaf;

Fig.2 een flow-diagram van dat deel van een eerste methode van de overeenkomstig de uitvinding uit te voeren werkwijze weergeeft, dat van toepassing is op knooppunten die geen bijzondere status hebben; Fig.3 een flow-diagram toont van dat deel van een tweede methode van de overeenkomstig de uitvinding uit te voeren werkwijze, dat van toepassing is op knooppunten die geen bijzondere status hebben;

Fig.4 een gedistribueerd object-georiënteerd systeem weergeeft, bestaande uit vier groepen, waarbij elke groep wordt weergegeven door een digraaf, verspreid over vier computer-eenheden;

Fig.5 Toegangsgrafen toont, welke zijn afgeleid uit het gedistribueerd object-georiënteerd systeem van Fig.4;

Fig.6 een flow-diagram van dat deel van de werkwijze weergeeft dat betrekking heeft op de ontvangst van een resultaatwaarde; en Fig.7 een flow-diagram toont van dat deel van de werkwijze dat van toepassing is bij het creëren van een referentie.

In deze figuren verwijzen gelijke cijfers naar overeenkomstige onderdelen.

Fig.l toont een logisch georganiseerd systeem 5. Allereerst zullen aan de hand van dit logisch georganiseerde systeem zowel de eerste als de tweede methode van de werkwijze overeenkomstig de uitvinding verduidelijkt worden. Later zullen beide methoden toegepast worden op een object-georiënteerd systeem. In het logisch georganiseerde systeem 5 uit Fig.l komen een tweetal groepen A en B van logische componenten voor, waarbij elke groep wordt weergegeven door een digraaf. Een digraaf bevat een aantal knooppunten (6a, 6b, ...) verbonden door gerichte ribben 7. Digraaf A wordt bovendien gekenmerkt door het knooppunt 6a met bijzondere status. Elk knooppunt bezit een identifier 8, welke in de knooppuntrepresentatie (cirkel, driehoek) is aangegeven. Met de knooppunten (6b, 6c, 6d), welke geen bijzondere status hebben, is een verzameling Pn met verwijzingscijfer 9b, respectievelijk 9c en 9d geassocieerd, waarbij n refereert naar de identifier van het betreffende knooppunt. Ieder knooppunt kan op elk willekeurig tijdstip een resultaatwaarde zenden naar een opvolgend knooppunt in de digraaf, waarbij deze waarde wordt toegekend aan die variabele, die separaat gekoppeld is met het zendende knooppunt en die element is van de verzameling geassocieerd met het ontvangende knooppunt. Deze resultaatwaarde wordt bepaald door een werkwijze, welke aan de hand van dit systeem zal worden beschreven, en volgens welke het mogelijk is uit de daarbij bepaalde resultaatwaarde op te maken of'in een digraaf een knooppunt met een bijzondere status niet aanwezig is. Het uitgangspunt bij deze werkwijze is gebaseerd op de systeemfunc-tionaliteit dat het knooppunt met bijzondere status (6a) zijn identifier met waarde 1 zal toekennen aan de met dit knooppunt gekoppelde variabele van de met verwijzingscijfer 9b aangeduide verzameling P2, geassocieerd met knooppunt 6b.

Dit veronderstelt voorts dat de met verwijzingscijfer 9c aangeduide verzameling P3, welke geassocieerd is met knooppunt 6c, een variabele bevat met waarde 2, welke van de identifier van de onmiddellijke voorganger 6b is afgeleid. Dit verder aan te duiden met P3^2}

De wijze waarop knooppunt 6c een resultaatwaarde zal doorzenden overeenkomstig de eerste methode naar een als opvolger aan te duiden knooppunt zal nu aan de hand van het door middel van het flow-diagram uit Fig.2 weergegeven programma worden uiteengezet. De start-situatie is aangegeven met 10. In stap 11 wordt getest of voldaan wordt aan de conditie dat alle variabelen uit Pn gelijk zijn aan n, of dat Pn een lege verzameling is. Wordt aan een van deze condities voldaan dan krijgt in stap 12 de berekende waarde de waarde "nil" en deze wordt toegekend aan met dit knooppunt gekoppelde variabelen. Hebben alle variabelen van een verzameling de waarde nil, dan is deze verzameling per definitie een lege verzameling. In het onderhavige voorbeeld met groep A is niet aan een van deze twee condities voldaan en wordt in een volgende stap 13 de conditie getest of alle variabelen uit P3 kleiner zijn dan de identifier van het knooppunt, i.e. 3. Aangezien geldt P3=P3[2]is hieraan voldaan. Als gevolg hiervan krijgt in stap 14 de resul taatwaarde de waarde van de identifier van het onderhavig knooppunt en wordt deze waarde toegekend aan de met het onderhavig knooppunt gekoppelde variabelen. Dit impliceert dat in P4 de waarde 3 toegekend wordt aan de met knooppunt 3 gekoppelde variabele. Hierna wordt dan de pseudo-eindtoestand 17 bereikt.'Het programma verkeert hierbij in een rustfase tot van buitenaf een signaal wordt gegeven om de beschreven stappen vanaf stap 10 weer uit te gaan voeren voor knooppunt 3.

Dezelfde werkwijze wordt nu toegepast om een waarde te bepalen voor het knooppunt met identifier 4. Er geldt: P4^3]. Toepassing van de beschreven werkwijze laat zien dat aan de conditie in stap 11 niet wordt voldaan, maar vervolgens wel aan de conditie in stap 13. In stap 14 zal dus de waarde 4 toegekend worden aan de met knooppunt 4 gekoppelde variabelen.

Voor P2 zal nu gelden P2^1 4j. Wordt de beschreven werkwijze toegepast op knooppunt 2, dan wordt aan geen der in de stappen 11 of 13 beschreven condities voldaan. Vervolgens wordt in stap 15 getest of alle elementen uit P2 identiek zijn en groter dan 2. Dit is niet het geval. Knooppunt 2 bereikt dan de pseudo-eindtoestand 17, zonder dat iets verzonden wordt naar een opvolger. Dit betekent in het onderhavige voorbeeld dat de situatie in A een stationnaire toestand heeft bereikt.

Hierna wordt het geval beschouwd dat het knooppunt met identifier 1 verwijderd wordt. P2 wordt dan P2^4^. Op het moment dat de werkwijze uitgevoerd wordt op de verzameling P2 wordt de stationnaire situatie doorbroken. P2^4^ voldoet aan de conditie gesteld in stap 15: dit houdt in dat alle variabelen uit P2 identiek zijn en de identifier van het knooppunt 2 kleiner is dan de waarde van de variabelen uit P2, i.e. 4. De waarde 4 zal dus toegekend worden aan de met knooppunt 2 gekoppelde variabele van P3. P3 wordt hierdoor D3{4[. Wordt in deze situatie de werkwijze uitgevoerd op de verzameling van het knooppunt met identifier 3, dan heeft dit tot gevolg dat ook hier de waarde 4 toegekend wordt aan de met knooppunt 3 gekoppelde variabele uit P4. P4 wordt hierdoor P4{4Wordt in deze situatie de werkwijze uitgevoerd op het knooppunt met identifier 4 dan is voldaan aan de conditie gesteld in stap 11. In stap 12 wordt dan de met knooppunt 4 gekoppelde variabele verwijderd uit P2. Bij het toepassen van de werkwijze op knooppunt 2 wordt ook voldaan aan de conditie van stap 11 en zal de met knooppunt 2 gekoppelde variabele uit P3 verwijderd worden. Voor knooppunt 3 geldt nu ook de conditie gesteld in stap 11. Hiermee is het doel van de werkwijze bereikt: inhoudende het distribueren van globale status-informatie van de digraaf - te weten de informatie over het ontbreken van het knooppunt met bijzondere status - over de knooppunten van de digraaf. Na stap 12 wordt dan eindtoestand 18 bereikt.

Van deze informatie kan gebruik worden gemaakt, bijvoorbeeld ten behoeve van garbage collection, door in stap 12 het knooppunt waarop de werkwijze werd toegepast te verwijderen. Passen we de werkwijze toe op digraaf B, dan is in te zien dat in knooppunt 3 propagatie langs de graaf stokt ondanks het ontbreken van een root, omdat de twee bij knooppunt 3 binnenkomende resultaatwaarden verschillend zullen zijn. In zijn algemeenheid geldt dat de eerste methode niet geschikt is als er subcykels zijn, omdat op een knooppunt met meerdere inkomende ribben de propagatie van pakketten gestopt wordt en derhalve via dit pad geen bijdrage meer wordt geleverd aan de werkwijze.

Vervolgens zal, nog steeds aan de hand van het logisch georganiseerd systeem uit Fig.l, de tweede methode uiteengezet worden welke methode bovenomschreven nadeel niet bezit en derhalve wel werkzaam is in het geval van subcykels. Dit gebeurt aan de hand van het flow-diagram in Fig.3. Bij deze methode omvat een variabele een rij van nul of meer identifiers van knooppunten. Als uitgangspunt nemen we de situatie, waarin de variabelen van de met de knooppunten geassocieerde verzamelingen P, als waarde de identifier van de met de variabele gekoppelde voorganger bezitten. Er is geen root aanwezig.

Veronderstel dat ten aanzien van knooppunt 3 van groep B de werkwijze toegepast wordt. Vertrekkende vanaf de uitgangssituatie in stap 30 worden in stap 31 de variabelen uit P3 gekopieerd naar de replicaver-zameling P'3. P'3 heeft dan als elementen 1 en 4, dit verder aan te duiden met P'3jl 4j. P13 is de replicaverzameling waarop de volgende stappen van de werkwijze worden toegepast. De onmiddellijke voorgangers van knooppunt 3 kunnen dan, terwijl de werkwijze wordt uitgevoerd, toch nog resultaatwaarden naar knooppunt 3 zenden en daarmee P3 wijzigen.

In stap 32 wordt onderzocht of variabelen in de replicaverzameling aanwezig zijn, die als prefix een andere variabele omvatten welke voorzien is van een merkteken. Is zulks het geval dan worden de met een dergelijke prefix voorkomende variabelen verwijderd. Dit is hier niet het geval, zodat P'3 ongewijzigd blijft.

Vervolgens wordt in stap 33 de referentiewaarde van het onderhavig knooppunt 3 bepaald. Allereerst wordt hiertoe het lexicografisch maximum van P‘3 bepaald hetgeen resulteert in de waarde pmax=4.

Vervolgens worden hiervan alle identifiers die kleiner zijn dan de identifier van het onderhavig knooppunt verwijderd. Dit levert een referentiewaarde met grootte 4 op, verder aangeduid als Ref=4. In stap 34 worden alle variabelen welke voorzien zijn van een merkteken verwijderd. Deze zijn niet aanwezig in P'3 zodat P'3 ongewijzigd blijft. In stap 35 wordt nagegaan of iedere variabele een prefix is van de referentiewaarde. Dit is niet het geval zodat het programma verder gaat met stap 37.

In stap 37 wordt, indien de referentiewaarde een merkteken bevat, dit merkteken verwijderd en tevens wordt de laatste identifier vervangen door de identifier van het onderhavig knooppunt, hetgeen de resultaat-waarde oplevert. Indien de referentiewaarde geen merkteken bevat wordt de identifier van het onderhavig knooppunt aan de referen- tiewaarde toegevoegd, zo deze aldaar nog niet aanwezig was, om de resultaatwaarde te bepalen. Dit levert als resultaatwaarde 4-3 op.

Het koppelteken in de notatie 4-3 scheidt de identifiers in de rij. Deze waarde wordt in stap 38 toegekend aan de met knooppunt 3 gekoppelde variabele in P2.

Vervolgens wordt in stap 39 nagegaan of de resultaatwaarde de vorm heeft van precies één identifier voorzien van merkteken. Daar dit niet het geval is zal het programma de pseudo-eindtoestand 41 bereiken. Vanuit deze eindtoestand moet de werkwijze nog Qen zodanig aantal keren uitgevoerd worden tot de definitieve eindtoestand 40 wordt bereikt. Heeft een bepaald knooppunt de definitieve eindtoestand eenmaal bereikt, dan wordt de werkwijze niet langer ten aanzien van dit knooppunt uitgevoerd.

Vervolgens veronderstellen we dat voor knooppunt 2 de werkwijze uitgevoerd gaat worden. Ten aanzien van dat knooppunt geldt: P2{4-3|.

In stap 31 wordt de replicaverzameling gemaakt: P'2^4-3 Vervolgens worden in stap 32 die variabelen verwijderd, welke als prefix een andere variabele met merkteken bezitten. Daar deze niet aanwezig zijn blijft P'2 ongewijzigd.

In de volgende stap 33 wordt de referentiewaarde bepaald. Hiertoe wordt eerst het lexicografisch maximum van P'2 bepaald. Hetgeen oplevert: pmax=4-3. Vervolgens wordt hieruit de referentiewaarde afgeleid door alle identifiers die kleiner zijn dan de identifier van het onderhavig knooppunt te verwijderen. Hierdoor verkrijgt de referentiewaarde de waarde 4-3.

Vervolgens worden in stap 34 van alle variabelen met merkteken de laatste identifier en tevens het merkteken verwijderd. Daar deze niet in P'2 aanwezig zijn, blijft deze verzameling ongewijzigd.

Daarna wordt in stap 35 nagegaan of elke variabele een prefix is van de referentiewaarde. Daar dit het geval is, wordt overgegaan naar stap 36.

In stap 36 wordt de resultaatwaarde bepaald door in het geval dat de referentiewaarde een merkteken bevat deze als resultaatwaarde te nemen. Bevat de referentiewaarde geen merkteken, dan wordt de resultaatwaarde bepaald door achteraan de eigen identifier voor zover niet aanwezig toe te voegen en tevens een merkteken toe te kennen. Dit levert voor de resultaatwaarde de waarde 4-3-2* op, aangeduid als

Res=4-3-2*.

Vervolgens bereikt het programma stap 38 waarbij de verkregen resultaatwaarde wordt verzonden naar de knooppunten 3 en 4.

In stap 39 wordt nagegaan of de resultaatwaarde bestaat uit precies één identifier met merkteken. Dit is niet het geval zodat de pseudo-eindtoestand 41 wordt bereikt. Het programma verkeert hier ten aanzien van het betreffende knooppunt in de rustfase tot van buitenaf weer een signaal wordt gegeven om de beschreven werkwijze vanaf stap 31 uit te voeren. In tabel 1 zijn de tussenresultaten voov’ de verschillende knooppunten vermeld bij een repeterende uitvoering van de beschreven werkwijze, totdat alle knooppunten de definitieve eindtoestand 40 hebben bereikt. Hiermee is het doel van de werkwijze bereikt: inhoudende het distribueren van globale status-informatie van de digraaf - te weten de informatie over het ontbreken van het knooppunt met bijzondere status - over de knooppunten van de digraaf, welke digraaf in dit voorbeeld een subcykel bevatte.

Verondersteld is dat in dit voorbeeld de volgorde waarin de knooppunten de werkwijze uitvoeren is: 3, 2, 1, 4, 3, 2, 4, 1, 3, 2 en 1. Per knooppunt zijn kolomsgewijs de tussenresultaten van de werkwijze weergegeven. De stapnummers komen overeen met de nummers uit het flow-diagram van Fig.3.

De volgorde waarin de knooppunten de werkwijze uitvoeren mag willekeurig zijn. Uit bovenstaande volgt dat de uitvoering van de werkwijze alleen aanleiding kan geven tot een nieuwe resul taatwaarde, en dus tot de voortplanting van een verandering naar de volgende knooppunten als de ingangswaarden veranderd zijn.

TABEL 1 stap knooppunt 3 knooppunt 2 knooppunt 1 knooppunt 4 31 P3' {l 4¾ P2' {4-3 ^ PI1 {4-3-2*J· P4' <4-3-2*} 32 P3' {l 4} P2' {4-3} PI' {4-3-2*} P4' {4-3-2*} 33 Ref =4 Ref = 4-3 Ref = 4-3-2* Ref = 4 34 P3' {l 4$ P2‘ *{4-3} PI1 { 4-3 } P4‘ {4-3} 35 no yes yes no 36 - Res=4-3-2* Res=4-3-2* 37 Res=4-3 - - Res=4 39 no no no no 40 - stap knooppunt 3 knooppunt 2 knooppunt 4 knooppunt 1 31 P3' {4-3-2* 4{ P2' {4-3*} P4'{4-3*{ PI1 { 4-3*} 32 P3' {4-3-2* 4} P2‘ {4-3*} P4' {4-3*} P1‘ {4-3*} 33 Ref=4-3 Ref=4-3* Ref=4* Ref=4-3* 34 P3' {4-3 4} P2‘ {4 } P4' { 4} PI' {4} 35 yes yes yes yes 36 Res=4-3* Res=4-3* Res=4* Res=4-3* 37 - 39 no no yes no 40 - - terminated stap knooppunt 3 knooppunt 2 knooppunt 1 31 P3‘ {4-3* 4*} P2' {4*} PI'{4*} 32 P31 {4* ] P2' { 4*} Pl'{4*} 33 Ref=4* Ref=4* Ref=4*

34 P3'{ } P2' { } PI' { J

35 yes yes yes 36 Res=4* Res=4* Res=4* 37 - 39 yes yes yes 40 termfnated ternrinated terminated

In het volgende geval wordt aangetoond dat bij het wel aanwezig zijn van een root de knooppunten niet de definitieve eindtoestand 40 bereiken.Stel dat in Fig.l in digraaf B knooppunt 4 verbonden is met een niet in de figuur weergegeven knooppunt van bijzondere status met een zekere identifier, stel 5. Herhaald toepassen van de aangegeven werkwijze op de knooppunten van de digraaf leidt er dan toe dat de resultaatwaarde 5-4 rond gaat in de digraaf, al dan niet voorzien van merkteken. Op grond van stap 33 zal de lengte van deze resultaatwaarde niet verkort worden, zodat voor de resultaatwaarde nooit een door een merkteken (*) gekarakteriseerde notatie, bevattende slechts één identifier (X*), kan ontstaan, hetgeen wel nodig is om een knooppunt in de terminale fase te brengen.

Zoals eerder vermeld zullen nu beide methoden toegepast worden op een object-georiënteerd systeem, zoals dat bijvoorbeeld is weergegeven in Fig.4.

Allereerst wordt het object-georiënteerd systeem nader toegelicht. In Fig. 4 is het systeem samengesteld uit vier via communicatiekanalen met elkaar gekoppelde computer-eenheden (CE1, CE2, CE3 en CE4). Objecten zijn weergegeven door knooppunten. Referenties tussen objecten worden gerepresenteerd door pijlen tussen de desbetreffende knooppunten. Root-objecten zijn weergegeven in de vorm van-een driehoekje. Groepen van objecten, die door middel van referenties met elkaar samenhangen, vormen een groep. Alleen root-objecten kunnen van buiten de groep worden aangeroepen. De andere objecten kunnen alleen binnen de groep worden aangeroepen en wel door die objecten, waardoor ze worden gerefereerd. Objecten worden als "levend" beschouwd als ze een root hebben, dat wil zeggen als ze uitgaande van een root-object bereikbaar zijn via een pad van naar elkaar refererende objecten.

Een aldus omschreven logisch georganiseerd systeem, dat werkzaam is als hiervoor uiteengezet, kan met voordeel worden voorzien van garbage collection functionaliteit welke als doel heeft geheugenruimte ingenomen door niet als "levend" te beschouwen objecten en derhalve als "dode" te betitelen objecten weer vrij te maken, daar "dode" objecten van buitenaf niet meer aan te roepen zijn en dus geen functie meer in het systeem vervullen.

In de in Fig.4 weergegeven uitvoeringsvorm van een logisch georgani- seerd systeem wordt per computer-eenheid in het desbetreffende geheugendeel een lijstvormige verzameling bijgehouden van objecten waarnaar door buiten die computer-eenheid gelegen objecten wordt gerefereerd. Een dergelijke lijst, welke verder wordt aangeduid met "toegangstabel", is schematisch in de figuur aan de onderzijde van de desbetreffende computer-eenheid onder aanduiding van verwijzingscijfer 50 weergegeven. Elk object waarnaar op afstand gerefereerd wordt, met andere woorden een object waarnaar gerefereerd wordt door een object gelegen op een andere computer, heeft een entry in de toegangstabel van de bijbehorende computer-eenheid. Deze entry omvat de pointer naar het object (i.c. de lokale identifier van het object) waarnaar gerefereerd wordt en tevens de identifiers van de computer-eenheden, waarin objecten voorkomen, die refereren naar het onderhavige object. Indien van toepassing kan in de entry tevens een tijdstempel dat aan het betreffende object is toegekend worden opgenomen. Zo geeft de eerste entry van de bij computer-eenheid CE4 behorende toegangstabel 50 (in casu: "2 | CE2, CE3 J 2.4" ) aan, dat van buitenaf gerefereerd wordt naar het object met lokale identifier 2 en wel door objecten die zich bevinden op CE2 en CE3 en dat aan dit object het tijdstempel 2.4 is toegekend.

Het is mogelijk de werkwijze volgens de uitvinding toe te passen op alle naar elkaar refererende objecten binnen eenzelfde groep. Echter voor het lokaal binnen een computer-eenheid gelegen gedeelte van een groep van objecten zijn efficiëntere werkwijzen ten behoeve van gar-bage collection te vinden, daar de in dergelijke situaties toe te passen werkwijzen niet gedistribueerd en incrementeel behoeven te werken. Daarom is bij een gedistribueerd object-georiënteerd systeem een werkwijze bestaande uit een combinatie van een werkwijze met een lokale geheugen reclamatie en de werkwijze volgens de uitvinding te prefereren. Daarbij moet als bekend worden verondersteld om binnen het proces van een gedistribueerde garbage collection door iedere computer-eenheid op gezette tijden een lokale garbage collection te laten uitvoeren, hetgeen op meerdere manieren te realiseren is.

In een bekende uitvoeringsvorm vindt lokale garbage collection plaats door het markeren van alle levende objecten, welke gevonden zijn bij het systematisch aflopen van referenties van alle objecten uitgaande van een root-object, en het vervolgens verwijderen van de niet gemarkeerde objecten. Op deze manier worden lokale objecten, die geen root hebben, verwijderd. Daarbij blijven objecten, die in de toegangstabel voorkomen en op grond hiervan per definitie een root hebben, gehandhaafd. Gedurende het doorlopen van de graaf wordt tevens bijgehouden welke objecten refereren naar een object op een andere computer-eenheid. Deze referenties welke tupels.worden genoemd, bestaan uit de host-identifier en de index in de toegangstabel van het object waarnaar wordt gerefereerd en worden doorgegeven aan de computer-eenheden, waarop deze externe objecten zich bevinden.

Een computer-eenheid zal deze referenties ontvangen en ze gebruiken om zijn toegangstabel aan te passen. Entries, waarvan de lijst met refererende computer-eenheden leeg is, worden verwijderd. Deze objecten hebben immers geen root meer en zullen dan ook bij een volgende lokale garbage collection actie worden verwijderd De hierboven geschetste procedure werkt goed voor acyclische groepen. De procedure werkt niet goed als cykels in de groep voorkomen. Is dit het geval dan wordt een der methoden van de werkwijze volgens de uitvinding op een aangepaste wijze uitgevoerd, en wel als volgt:

Gedurende het aflopen van de objecten welke naar elkaar referen, uitgaande van een lokale root, wordt ten behoeve van een lokale garbage collection eveneens bijgehouden welke objecten refereren naar een ander extern object. Voor deze externe objecten wordt op basis van de lokale root in de betekenis van resultaatwaarde-bepalend knooppunt een resultaatwaarde bepaald volgens een der methoden van de werkwijze overeenkomstig de uitvinding.

Daarnaast wordt gedurende het aflopen van de objecten welke naar elkaar refereren, uitgaande van telkens een entry uit de toegangstabel eveneens bijgehouden welke objecten naar een ander extern object referen. Voor deze externe objecten wordt een resultaatwaarde bepaald op basis van de gegevens (binnengekomen resultaatwaarden, identifier) behorende bij het knooppunt van de entry. Het bepalen van de resultaatwaarde geschiedt volgens een der methoden van de werkwijze overeenkomstig de uitvinding.

De knooppunten welke op de bovenbeschreven manier betrokken zijn bij het uitwisselen van resul taatwaarden vormen een gerichte graaf, waarbij een ribbe in beginsel het pad of de weg aangeeft, waarlangs overdracht van een resultaatwaarde plaats vindt. Een op deze manier gedefinieerde graaf zal verder aangeduid worden met "toegangsgraaf". Per gedistribueerd systeem kunnen verscheidene toegangsgrafen voorkomen. In Fig.5 zijn de toegangsgrafen weergegeven die uit het gedistribueerde object-georiënteerde systeem van Fig.4 geconstrueerd kunnen worden.

Bij het uitvoeren van een werkwijze overeenkomstig de uitvinding kan om na te gaan welke resultaatwaarden berekend moeten worden met voordeel gebruik worden gemaakt van de volgende stelregel: "Mocht voor hetzelfde extern object zowel een resultaatwaarde van een root als een of meer resultaatwaarden van andere objecten bepaald zijn, dan is alleen de resultaatwaarde van de root relevant".

Dit impliceert dat mocht een extern gerefereerd object op een pad liggen uitgaande van een root, dan hoeft de graaf uitgaande van het extern gerefereerde object niet meer afgelopen te worden. Tevens is het niet nodig dat er tussen knooppunten van een toegangsgraaf gelegen binnen dezelfde computer-eenheid resultaatwaarden worden uitgewisseld. De resul taatwaarden welke gedurende een op een computer-eenheid uitgevoerde garbage collection actie bepaald zijn worden verzameld en pakketsgewijs aan de relevante computer-eenheden toegezonden. Een ontvangende computer-eenheid zorgt ervoor dat de toegezonden resultaatwaarden in de desbetreffende verzamelingen van de extern gerefereerde knooppunten worden opgenomen, hetgeen geschiedt volgens de regels zoals hiervoor vermeld bij het uitvoeren van de werkwijze volgens de uitvinding.

De resultaatwaarde geeft uitsluitsel of zekere objecten, waarnaar van buitenaf gerefereerd wordt, nog op enigerlei wijze gerefereerd worden door een root-object in een andere computer-eenheid.

Zijn de resultaatwaarden samengesteld volgens de regels behorende bij de eerste methode van de werkwijze overeenkomstig de uitvinding dan is dit uitsluitsel ook gegeven als cykels voorkomen in de keten van referenties. Zijn de resultaatwaarden samengesteld volgens de regels behorende bij de tweede methode van de werkwijze overeenkomstig de uitvinding dan is dit uitsluitsel ook gegeven als subcykels voorkomen in de keten van referenties.

Nu zal gedetailleerd een wijze van gedistribueerde garbage collec-tion worden beschreven toegepast op de toegangsgraaf C van Fig.5, welke gebaseerd !s op de tweede methode van de werkwijze en waarbij gebruik wordt gemaakt van tijdstempels. Onder een tijdstempel wordt een stapsgewijs te verhogen of te verlagen getal verstaan (bijvoorbeeld de tijdswaarde op het moment van afdrukken), eventueel gevolgd door de identifier van de computer-eenheid.

Telkenmale wanneer een referentie wordt gecreëerd wordt een tijdstempel aangemaakt en ten behoeve van de werkwijze als identifier toegekend aan het te refereren knooppunt. Hierbij worden de stappen weergegeven in het flow-diagram van Fig.6 gevolgd. De startsituatie is aangegeven met verwijzingscijfer 60. In stap 61 wordt nagegaan of het te refereren object al een entry in de toegangstabel bezit. Is dit niet het geval dan wordt in stap 62 een entry gecreëerd. In stap 63 wordt het tijdstempel gezet en als identifier toegekend aan het te refereren knooppunt. Deze stap wordt ook uitgevoerd als de entry al bestaat. In stap 64 wordt tenslotte de resultaatwaarde van het refererende knooppunt toegevoegd aan de verzameling geassocieerd met het te refereren knooppunt.

In tabel 2 zijn voor een aantal computer-eenheden in het systeem van Fig.4 enige daarin voorkomende objecten met bijbehorende tijdstempels weergegeven. Door het tijdstempel te voorzien van een identifier van de betreffende computer-eenheid worden deze tijdstempels globaal uniek.

t i | TABEL 2 |

I I

j lokale identifier computer-eenheid waarop tijdstempel I

| van het object het object zich bevindt van het object]

I I

| 1 (root) 1 1.1 j j 3 1 2.i j | 2 2 L2 | j 8 2 2.2 | j 1 (root) 4 1.4 j j 2 4 2.4 j j 4 4 3.4 j

I I

In een eenvoudige vorm bestaat het tijdstempel uit een serienummer gevolgd door de identifier van de computer-eenheid. Het serienummer wordt centraal op een computer-eenheid uitgereikt en telkenmale stapsgewijs verhoogd bij het zetten van een tijdstempel.

De lokale identifier van ieder object, welke ook is weergegeven in Tabel 2, wordt gebruikt als index in de bij die computer-eenheid behorende toegangstabel en voorts wordt het aangegeven tijdstempel aan de entry in die toegangstabel toegevoegd.

In tabel 3 is een mogelijk verloop van een gedistribueerde garbage collection actie overeenkomstig de werkwijze toegepast op toegangsgraaf C van Fig.5 weergegeven. Elk knooppunt of object is in tabel 3 aangeduid met zijn tijdstempel en computer-eenheid.

i i | TABEL 3 |

I I

| stap CE1 1.1 CE2 1.2 CE4 2.4 CE1 1.1 |

I I

I root root I

| 31 | P‘ {l.lj P' {1.2} | j j 32 j P‘{ l.l] P' {1.2} j j j 33 j Ref = 0 Ref = 0 j j

j 34 | P' {l.l} P' {1.2J | I

J 35 j no no j j | 36 j Res= 1.2 Res=2.4 j j j 37 Res=l.l - - Res=l.l j | 39 no no j j 40 - - - j I_l

Per knooppunt of object, welke in de tabel van links naar rechts zijn getoond, wat de volgorde aangeeft waarin de objecten betrokken zijn bij een garbage collection actie, zijn de tussenresultaten vermeld bij het bepalen van de door te geven resultaatwaarden. Daar elke computer-eenheid vrij is om op een willekeurig moment een garbage collection te starten, zou een andere sequentie genomen kunnen zijn en zouden dan andere waarden voor de uit te wissselen resultaatwaarden gevonden worden. Hierdoor wordt echter de werkzaamheid van de procedure met betrekking tot garbage collection niet aangetast. Verondersteld is, overeenkomstig tabel 3, dat computer-eenheid 1 een garbage collection uit gaat voeren. Dit betekent dat alle objecten die geen verbinding met een root hebben worden verwijderd. Refererend naar Fig.4 betekent dit dat vanaf de lokale root 1 en, zoals blijkt uit de toegangstabel, vanaf het extern gerefereerde object 3, grafen doorlopen zullen worden.

De graaf doorlopend vanaf root 1 markeert de objecten 2, 3 en 4 en signaleert een externe referentie naar CE2. Bij het doorlopen van de graaf vanaf object 3 wordt al direct duidelijk dat vanaf object 3 de rest van de graaf al onderzocht is bij het doorlopen van de graaf vanuit root 1 en dit dus verder niet meer behoeft te gebeuren. Er wordt nu een resultaatwaarde bepaald, welke tezamen met een referentie volgens de werkwijze op basis van root 1 naar CE2 wordt verstuurd. De root stuurt per definitie het eigen tijdstempel door.

Verondersteld is dat na computer-eenheid 1 vervolgens computer-eenheid 2 een garbage collectie uit gaat voeren. Dit houdt in dat alle objecten die dood zijn verwijderd worden. Refererend naar Fig.4 betekent dit dat knooppunten 5, 6 en 7 verwijderd worden. Tevens worden ribben en knooppunten van de toegangsgrafen verzameld. Voor computer-eenheid 2 zijn dat de knooppunten 2 en 8. Daar deze knooppunten extern gerefereerd worden zoals blijkt uit de toegangstabel vormen zij tevens de objecten van waaruit referenties verder doorlopen zullen worden om de levende objecten te markeren. Bij het doorlopen van de graaf vanaf object 8 wordt 9 gemarkeerd, zodat dit object blijft bestaan. Het doorlopen van de graaf vanaf knooppunt 2 leidt via knooppunt 1 naar een externe referentie op CE1 en via zowel knooppunten 3 als 4 naar een externe referentie op CE4. Vervolgens wordt er een resultaatwaarde bepaald op basis van object 2 welke tezamen met een referentie en overeenkomstig de werkwijze verstuurd wordt naar CE1 en CE2. De respectievelijke computer-eenheden dragen er daarbij zorg voor dat deze resultaatwaarden, volgens de regels van de werkwijze, worden opgenomen in de verzamelingen geassocieerd met de betrokken knooppunten. De stappen die doorlopen moeten worden bij ontvangst van een resultaatwaarde door een object of knooppunt, zijn weergegeven in het flow-diagram uit Fig.7.

De beginsituatie voor zo'n object of knooppunt is aangegeven met 70.

In stap 71 wordt nagegaan of door het betreffende object of knooppunt een "lege" resultaatwaarde is ontvangen. Dit is het geval als een resultaatwaarde afkomstig van een zendend knooppunt voor het desbetreffende knooppunt voor een eerste maal ontbreekt, nadat voorafgaand wel een resultaatwaarde van dit zendend knooppunt is ontvangen. Is van dit zendend knooppunt geen lege resultaatwaarde ontvangen, dan wordt in stap 72 de eerder ontvangen resultaatwaarde van dit knooppunt vervangen door de zojuist ontvangen resultaatwaarde.

Is daarentegen wel een lege resul taatwaarde ontvangen dan wordt in stap 73 de op een eerder tijdstip ontvangen resultaatwaarde van het refererend knooppunt verwijderd nadat een resultaatwaarde door het ontvangende knooppunt is berekend gebaseerd op de oude situatie. Vervolgens wordt in stap 74 een nieuwe resultaatwaarde berekend. Deze resultaatwaarde wordt in stap 75 vergeleken met de resultaatwaarde gebaseerd op de oude situatie. Is de nieuw berekende resultaatwaarde kleiner dan de resultaatwaarde gebaseerd op de oude situatie dan wordt in stap 76 het tijdstempel van het onderhavig knooppunt verhoogd totdat de nieuw berekende waarde groter is. Zodra dit het geval is, hetgeen dan in stap 75 wordt vastgesteld, wordt eindtoestand 77 bereikt. Het nut van deze stappen zal in een later voorbeeld worden toegeiicht.

Verondersteld is vervolgens dat na de garbage collection actie van computer-eenheid 2, ook computer-eenheid 4 een dergelijke actie gaat uitvoeren. Levende objecten worden dan gemarkeerd door beginnend vanaf root 1 en vanaf de entries uit de toegangstabel i.e. knooppunten 2 en 4 de daarvan vertrekkende grafen te doorlopen.

De graaf uitgaande van de lokale root 1 bezit een externe referentie. Hiervoor wordt een resultaatwaarde bepaald op basis van deze lokale root.

De graaf uitgaande van knooppunt 2 levert een externe referentie op voor CE1. De graaf uitgaande van knooppunt 4 levert echter geen externe referentie op.

Vervolgens worden de daarbij verkregen resultaatwaarden en referenties samengesteld en pakketsgewijs verzonden naar de desbetreffende computer-eenheden. De op basis van knooppunten 2 en 1 verzonden resultaatwaarden worden, overeenkomstig de werkwijze, na ontvangst geplaatst in de met respectievelijk knooppunt 3 en 8 geassocieerde verzamelingen.

Het resultaat van de aangegeven procedure met betrekking tot gedistribueerde garbage collection is, dat er nu een stabiele situatie is ontstaan: Ten gevolge van het telkens aanwezig zijn van de resultaat-waarde van root 1 van CE1 wordt een mogelijke circulatie van een lexicografisch maximale resultaatwaarde geblokkeerd Opgemerkt zij dat in het onderhavige voorbeeld geen resultaatwaarde wordt verzonden die samengesteld is op basis van knooppunt 3 van CE1 met tijdstempel 2.1, daar al een root-resultaatwaarde naar knooppunt 2 van CE2 wordt verzonden.

Aangetoond zal nu worden dat, als de referentie vanuit het root-object verwijderd wordt, de dode objecten eveneens worden verwijderd. Hierbij wordt uitgegaan van de situatie welke verkregen is in het vorige voorbeeld. In tabel 4 is het verloop van de gedistribueerde garbage collection actie weergegeven. Elk object is weer aangeduid met zijn tijdstempel en computer-eenheid. Verondersteld is, overeenkomstig tabel 4, dat computer-eenheid CE1 als eerste een garbage collection uitvoert, na het verwijderen van de referentie -vanuit de root naar het object met lokale identifier 2 van CE1. Bij het markeren van levende objecten vanuit object 1.1 wordt geen externe referentie meer gevonden. Dus op basis van object 1.1 zal nu geen resultaatwaarde worden bepaald. Bij het markeren van levende objecten vanuit objecten die in de toegangstabel voorkomen, wordt nu nog steeds een remote referentie gevonden, waarvoor echter nu geen root-resul taatwaarde klaar staat. Nu is de resul taatwaarde van object 3 van CE1 in de tabel aangegeven met zijn tijdstempel 2.1 noodzakelijk. Na een aantal stappen bereiken de betreffende knooppunten vervolgens de definitieve eindtoestand 40. Als gevolg hiervan worden ze verwijderd uit de toegangstabel en bij een lokale garbage collection zullen ze dan definitief opgeruimd worden. Hiermee is aangetoond dat de tweede methode van de werkwijze overeenkomstig de uitvinding werkzaam is op cyclische structuren, waarin subcykels voorkomen.

! I

I TABEL 4 I

I I

I CE1 2.1 CE2 1.2 CE4 2.4 CE1 2.1 | | 31 P'^2.4 1.2} P'{2.4-2.l} P'{2.4-2.1-1.2*} P'-{2-4-2.1-1.2* 2.4}| | 32 P'{2.4 1.2} P'J2.4-2.1} P'{2.4-2.1-1.2*} P*/2.4-2.1-1.2* 2.4jj | 33 Ref=2.4 Ref=2.4-2.1 Ref=2.4 Ref=2.4-2.1 j | 34 P'{2.4 1.2} P'}2.4-2.1} P‘-(2.4-2.1} P'{2.4-2.1 2.4] | | 35 no yes no yes | | 36 - Res=2.4-2.1-1.2* - Res=2.4-2.1* j | 37 Res=2.4-2.1 - Res=2.4 - j j 39 no no no no | I 40 - - - |

I I

| CE2 1.2 CE4 2.4 CE1 2.1 CE2 1.2 j | 31 P'{2.4-2.1*] P'{2.4-2.1*} P'{2.4-2.1* 2.4*jp'{2.4*j | j 32 P'}2.4-2.1*} P'}2.4-2.1*} Ρ']2.4*} P'{2.4*} j j 33 Ref=2.4-2.1* Ref=2.4 Ref=2.4* Ref=2.4* j I 34 P'{2.4} P'«(2.4} P' { j p| j j | 35 yes yes yes yes | | 36 Res=2.4-2.1* Res=2.4* Res=2.4* Res=2.4* j I 37 - - - | | 39 no yes yes yes |

I I

| 40 - terminated terminated terminated | L_!

In het nu volgende deel zal aangetoond worden dat de werkwijze correct blijft werken in situaties, waarin referenties op afstand tussen objecten wegvallen door oorzaken, gelegen buiten garbage collec-tion acties. Als een referentie wegvalt betekent dit voor de desbetreffende graaf dat een ribbe wegvalt. Bij het pakketsgewijs doorgeven van resultaatwaarden ten behoeve van gedistribueerde garbage collec-tion zullen aan de ontvangstzijde de resultaatwaarden normaliter worden toegekend aan de betreffende variabelen, waarbij dan telkens de oude waarde vervangen wordt door de nieuwe waarde. Verdwijnt een ribbe, dan zal bij het pakketsgewijs verzenden van de referenties gedurende de volgende keer, de referentie behorende bij de verdwenen ribbe voor de eerste maal ontbreken. De ontvangende computer-eenheid verwijdert dan de identifier van de refererende computer-eenheid uit de entry van de toegangstabel en in het geval dat dit de enige refererende computer-eenheid is voor deze entry, wordt de entry verwijderd uit de toegangstabel. Mochten er verder geen lokale referenties zijn naar dit object dan zal het object bij een lokale garbage collection worden verwijderd. Maar wanneer er nog andere remote referenties voor deze entry zijn, dan zal het voor de eerste maal ontbreken van een resultaatwaarde voor dit knooppunt ten aanzien van de werkwijze inhouden, dat een "lege" resultaatwaarde wordt ontvangen.

In het volgende voorbeeld zullen de stappen van Fig.7, die betrekking hebben op de ontvangst van een lege resultaatwaarde, worden toege-1 icht.

Veronderstel dat de referentie vanuit 2.4 naar 2.1 verdwijnt. Dit kan (buiten eventuele garbage collection acties) alleen gebeuren als de root nog aanwezig is. Veronderstel dat CE4 hierna een lokale garbage collection uitvoert. Deze stuurt nu een lege resultaatwaarde naar CE1. Bij "ontvangst" van deze lege resultaatwaarde worden de stappen van het flow-diagram van Fig.7 doorlopen. Tussenresultaten hiervan zijn in tabel 5 weergegeven. Daarbij wordt zijn tijdstempel verhoogd.

i i | TABEL 5 |

I I

| CEl 2.1 CE1 2.1 CE 3.1 <- hernieuwd | j 31 P'{2.4 1.2 J P'{l.2} P’{l.2j tijdstempel j I 32 Ρ'<2.4 1.2} P‘{1.2} P’-jl.2} j j 33 Ref=2.4 Ref=0 Ref=0 j | 34 P'{2.4 1.2} P'jl.2} P'}l.2j | | 35 no no no | j 36 - - - j j 37 Res=2.4-2.1 Res=2.1 Res=3.1 j j 39 no no no | j 40 - - - j

I I

I t

Vertrekkend vanuit beginsituatie 70 wordt, bij ontvangst van de pakketsgewijze verzonden resultaatwaarden, voor een zeker knooppunt in stap 71 getest of de ontvangen resultaatwaarde leeg is, met andere woorden of in het pakket van resul taatwaarden een resultaatwaarde voor de eerste maal ontbreekt. Dit is hier het geval. In stap 73 wordt dan de op een eerder tijdstip ontvangen resul taatwaarde van het refererend knooppunt verwijderd, nadat op grond hiervan een resultaatwaarde is berekend. Deze berekening is met vermelding van de tussenresultaten voor de onderhavige situatie weergegeven in de linkerkolom van Fig.5 en levert als resultaatwaarde: 2.4-2.1. Vervolgens wordt in stap 74 dezelfde berekening uitgevoerd, echter nu op basis van de bin-nengekomen lege resultaatwaarde, waardoor geldt: Ρ'=Ρ'|ΐ.2^. Dit levert als resultaatwaarde: 2.1. Deze berekening is weergegeven in de tweede kolom van tabel 5. De laatst verkregen resul taatwaarde wordt in stap 75 vergeleken met de in stap 73 berekende resultaatwaarde. Is de nieuw berekende resultaatwaarde kleiner dan wordt in stap 76 het tijdstempel van het onderhavig knooppunt verhoogd totdat de nieuw berekende waarde groter is. In het onderhavige voorbeeld is de nieuw berekende resultaatwaarde inderdaad kleiner, zodat, het tijdstempel verhoogd wordt tot 3.1. Hernieuwde berekening van de resultaatwaarde op basis van dit tijdstempel is weergegeven in de derde kolom van tabel 5. Deze resultaatwaarde is nu groter dan de resultaatwaarde berekend in stap 73 , hetgeen in stap 75 wordt vastgesteld, waarna eindtoestand 77 bereikt wordt.

3.1 is de resultaatwaarde die bij een volgende lokale garbage collec-tion op CE 1 verzonden wordt naar CE 2. Als nu verdere garbage collec-tion acties worden uitgevoerd, wordt de graaf afgebroken.

Door het verhogen van dit tijdstempel is nu voorkomen dat, in het geval dat de referentie vanuit de root 1 van CE1 naar knooppunt 3 van CE 1 zou verdwijnen, een resultaatwaarde van de vorm 2.4-2.1 gaat circuleren in de cykel gevormd door de knooppunten 3 op CE 1 en 2 op CE 2, respectievelijk met tijdstempels 2.1 en 1.2. Deze cykel kan dan niet gedetecteerd worden omdat detectie geïnitieerd wordt door het knooppunt dat onder andere zijn eigen tijdstempel in stap 33 weer terugkrijgt als referentiewaarde. Door deze maatregelen is de werkwijze ook geschikt om gebruikt te worden als referenties worden verwijderd.

Ook zijn situaties denkbaar waarbij nieuwe referenties gecreëerd worden. Door het toepassen van tijdstempels is, ook in deze dynamische situaties, de werkwijze nog steeds toepasbaar. Wordt een nieuwe referentie gecreëerd naar een reeds bestaand object dan wordt het tijdstempel van dit object hernieuwd, zoals blijkt uit het flow-diagram van Fig.6. Dit speelt onder andere een rol als root-objecten zich verplaatsen, hetgeen toegelicht zal worden aan de hand van de als stationnair te beschouwen situatie welke via de etappen weergegeven in tabel 3 bereikt is.

Veronderstel dat de root zich verplaatst door eerst een referentie op afstand, bijvoorbeeld naar object 2 van CE2, te creëren en vervolgens de lokale referentie te verbreken. Hierna migreert de root naar CE2. Dit levert een stationnaire situatie op, waarbij het maximum van de cykel nu geblokkeerd wordt bij knooppunt 1.2 van CE 2. Verplaatst de root zich echter verder, dan wordt het maximum geblokkeerd voor knooppunt 1.4 van CE 4. Verplaatst de root zich daarna nogmaals dan komt het maximum weer terug bij het knooppunt waar het gevormd was, hetgeen tot gevolg heeft dat de graaf vanaf hier afgebroken gaat worden. Dit nu is voorkomen, door de maatregelen getoond in het flow-diagram van Fig.6, waarbij er voor gezorgd wordt dat als een nieuwe referentie wordt toegevoegd, het tijdstempel van het knooppunt waarnaar de referentie verwijst, hernieuwd wordt. De gedistribueerde garbage collection actie zal dan telkenmale herstart worden.

Het mag duidelijk zijn dat de geschetste methode, waarbij asynchroon en incrementeel een knooppunt kan bepalen of de digraaf, waarvan het knooppunt onderdeel is, nog een bepaalde status heeft, welke status bepaald wordt door een knooppunt dat de rol van "root" op zich neemt, ook op andere gebieden waar structuren in de vorm van een digraaf voorkomen, toepassing kan vinden. Hierbij kan gedacht worden aan documenten die links bevatten naar andere documenten, of gedistribueerde hypertext media.

Claims

1. Werkwijze voor het in een logisch georganiseerd systeem, omvattende een samenstel van door digrafen zonder subcykels te representeren groepen van via gerichte ribben met elkaar in relatie staande, door knooppunten te representeren entiteiten, distribueren van status-informatie betreffende de digraaf over de knooppunten van de digraaf, waarbij per digraaf aan elk knooppunt een unieke identifier is toegevoegd en waarbij met elk knooppunt dat niet eer. bijzondere status heeft, een verzameling geassocieerd is, waarvan ieder element een variabele representeert die separaat gekoppeld is met een onmid-dellijke voorganger van het knooppunt, met het kenmerk, dat de werkwijze de navolgende stappen omvat: - het toekennen van de waarde van de identifier van een knooppunt met een bijzondere status aan elke variabele welke met dit knooppunt is gekoppeld; - het verwijderen van elke variabele welke gekoppeld is met een knooppunt als in de daarmee geassocieerde verzameling elke variabele gelijk is aan de identifier van dat knooppunt of als de verzameling leeg is; - het toekennen van de waarde van de identifier van een knooppunt aan elke variabele welke gekoppeld is met dit knooppunt, als deze identifier aan een bepaald vergelijkingscriterium voldoet met betrekking tot de variabelen van de verzameling geassocieerd met het knooppunt en mits dit knooppunt niet een knooppunt met een bijzondere status is; en - het toekennen van de waarde van een variabele van de verzameling geassocieerd met een knooppunt aan elke variabele welke met dit knooppunt gekoppeld is, als alle variabelen van de verzameling geassocieerd met dit knooppunt identiek zijn en de identifier van dit knooppunt niet voldoet aan het vergelijkingscriterium met betrekking tot laatstgenoemde variabelen.

2. Werwijze volgens conclusie 1, met het kenmerk, dat het bepaalde vergelijkingscriterium behelst, dat de identifier van het knooppunt groter is dan elke variabele van de verzameling.

3. Werkwijze volgens een der conclusies 1 of 2, met het kenmerk, dat als in de met het knooppunt geassocieerde verzameling, elke variabele gelijk is aan de identifier van dat knooppunt of als de verzameling leeg is eveneens het knooppunt wordt verwijderd.

4. Werkwijze voor het in een logisch georganiseerd systeem, omvattende een samenstel van door digrafen te representeren groepen van via gerichte ribben met elkaar in relatie staande, door knooppunten te representeren entiteiten, distribueren van status-informatie betreffende de digraaf over de knooppunten van de digraaf, waarbij per digraaf aan elk knooppunt een unieke identifier is toegevoegd en waarbij met elk knooppunt dat niet een bijzondere status heeft, een verzameling geassocieerd is, waarvan ieder element een variabele representeert die separaat gekoppeld is met een onmiddellijke voorganger van het knooppunt, welke variabele een rij omvat van nul of meer identifiers van knooppunten, welke werkwijze wordt gekenmerkt door: A. het per knooppunt met bijzondere status toekennen van de identifier van het knooppunt aan elke variabele welke met dit knooppunt is gekoppeld; B. het per knooppunt dat niet een bijzondere status heeft, op basis van de variabelen uit de met het knooppunt geassocieerde verzameling, uitvoeren van de navolgende stappen: - het verwijderen van elke variabele met een rij, waarin als bestanddeel met een gedefinieerde ligging een rij van een -andere variabele voorkomt, mits laatstgenoemde rij voorzien is van een merkteken; - het bepalen van een referentiewaarde door eerst aan de hand van een eerste vergelijkingscriterium een variabele te selecteren en vervolgens uit de door deze variabele omvatte rij, die identi fiers, inclusief merkteken indien aanwezig, te verwijderen welke voldoen aan een tweede, op de identifier van onderhavig knooppunt gebaseerd vergelijkingscriterium; en - het uit de resterende variabelen en de verkregen referentiewaarde afleiden van een waarde en deze als resultaatwaarde toe kennen aan elke variabele welke gekoppeld is met het onderhavig knooppunt waarbij, in het geval dat deze waarde voorzien is van een merkteken en de rij slechts een identifier bevat, het onderhavig knooppunt zekerheid heeft verkregen over de status van de digraaf.

5. Werkwijze volgens conclusie 4, met het kenmerk, dat de variabelen naar een replicaverzamel ing worden gekopieerd, waarna genoemde stappen uit te voeren per knooppunt dat niet een bijzondere status heeft worden uitgevoerd op de replicaverzameling.

6. Werkwijze volgens een der conclusies 4 of 5, waarbij de per digraaf aan elk knooppunt toegevoegde unieke identifier een tijdstem-pel omvat, met het kenmerk, dat de werkwijze tevens de volgende stappen omvat: - het zetten van het tijdstempel behorend bij een knooppunt op het moment dat een koppeling wordt gecreëerd naar dit knooppunt toe; en - het zoveel wijzigen van het tijdstempel van een knooppunt dat een resultaatwaarde wordt verkregen die groter is dan een eerder verkregen resultaatwaarde in het geval een lege resul taatwaarde is ontvangen van een onmiddellijke voorganger.

7. Werkwijze volgens een der conclusies 4 of 5, met het kenmerk, dat het bestanddeel met gedefinieerde ligging een begindeel van een rij is.

8. Werkwijze volgens een der conclusies 4 of 5, met het kenmerk, dat aan de hand van het eerste vergelijkingscriterium een variabele wordt geselecteerd met een rij welke lexicografisch maximaal is, waarbij geldt dat een rij voorzien van een merkteken lexicografisch groter is dan een aan deze rij gelijke rij zonder merkteken en dat aan· de hand van het tweede vergelijkingscriterium de identifier, inclusief merkteken indien aanwezig, uit de rij wordt verwijderd als de identifier kleiner is dan de identifier van het onderhavig knooppunt.

9. Werkwijze volgens een der conclusies 4 of 5, met het kenmerk, dat het afleiden van de resultaatwaarde uit de resterende variabelen en de verkregen referentiewaarde de navolgende stappen omvat: - het uit elke van een merkteken voorziene rij verwijderen van zowel de laatste identifier als dit merkteken; - het vervolgens vergelijken van alle variabelen met de referentiewaarde, waarbij a. in het geval dat de rij van elke variabele gelijk is aan een begindeel van de rij van de referentiewaarde en de referentiewaarde is voorzien van een merkteken de resultaatwaarde de referentiewaarde representeert; b. in het geval dat de rij van elke variabele gelijk is aan een begindeel van de rij van de referentiewaarde en de referentiewaarde niet is voorzien van een merkteken de referentiewaarde wordt voorzien van het merkteken en achteraan de eigen identifier wordt toegevoegd, indien deze aldaar nog niet aanwezig was ter verkrijging van de genoemde resultaatwaarde; c. in het geval dat er ten minste een variabele is waarvan de rij niet gelijk is aan een begindeel van de rij van de referentiewaarde en tevens de referentiewaarde geen merkteken bevat de eigen identifier achteraan wordt toegevoegd, indien deze aldaar nog niet aanwezig was, ter verkrijging van genoemde resul taatwaarde; en d. in het geval dat er ten minste een variabele is waarvan de rij niet gelijk is aan een begindeel van de rij van de referentiewaarde en tevens de referentiewaarde voorzien is van een merkteken het merkteken wordt verwijderd en de laatste identifier wordt vervangen door de identifier van het onderhavig knooppunt ter verkrijging van genoemde resul taatwaarde.

10. Werkwijze volgens conclusie 9 waarbij het logisch georganiseerd systeem uitgevoerd is als een object-georiënteerd systeem waarin de objecten de entiteiten representeren en waarin root-objecten entiteiten met bijzondere status representeren en waarbij de per digraaf aan elk knooppunt toegevoegde unieke identifier een tijdstempel omvat, met het kenmerk, dat het bestanddeel met gedefinieerde ligging een begindeel van een rij is, dat aan de hand van het eerste vergelij-kingscriterium een variabele wordt geselecteerd met een rij welke lexicografisch maximaal is, waarbij geldt dat een rij voorzien van een merkteken lexicografisch groter is dan een aan deze rij gelijke rij zonder merkteken, dat aan de hand van het tweede vergelij-kingscriterium de identifier, inclusief merkteken indien aanwezig, uit de rij wordt verwijderd als de identifier kleiner is dan de identifier van het onderhavig knooppunt en dat de werkwijze tevens de volgende stappen omvat: - het zetten van het tijdstempel behorend bij een knooppunt op het moment dat een koppeling wordt gecreëerd naar dit knooppunt, - het zodanig wijzigen van het tijdstempel van een knooppunt als nodig is om een resultaatwaarde te krijgen die groter is dan een eerder verkregen resultaatwaarde in het geval een lege resultaatwaarde is ontvangen van een onmiddellijke voorganger en - het verwijderen van het onderhavig knooppunt ingeval de bij het knooppunt behorende resultaatwaarde een uit slechts een identifier bestaande rij voorzien van merkteken omvat, nadat deze resultaatwaarde is toegekend aan de met het knooppunt gekoppelde variabelen.

11. Werkwijze volgend conclusie 10 waarbij het object-georiënteerd systeem uitgevoerd is als een gedistribueerd object-georiënteerd systeem, waarin objecten behorende tot een toegangs-graaf groepsgewijs geordend zijn en waarbij het gedistribueerd object-georiënteerd systeem tevens omvat een of meer door communicatie-kanalen verbonden computer-eenheden, met het kenmerk, dat de per computer-eenheid verkregen resultaatwaarden bestemd voor objecten aanwezig op eenzelfde volgende computer, pakketsgewijs worden verzonden, waarbij het in het pakket wegvallen van een variabele, het toekennen van een lege resultaatwaarde aan de variabele tot gevolg heeft.

12. Inrichting omvattend een logisch georganiseerd systeem, dat omvat een samenstel van door digrafen zonder subcykels te representeren groepen van via gerichte ribben met elkaar in relatie staande, door knooppunten te representeren entiteiten, waarbij per digraaf aan elk knooppunt een unieke identifier is toegevoegd en waarbij met elk knooppunt dat niet een bijzondere status heeft, een verzameling geassocieerd is, waarvan ieder element een variabele representeert die separaat gekoppeld is met een onmiddellijke voorganger van het knooppunt, met het kenmerk, dat de inrichting is voorzien van: - middelen voor het toekennen van de waarde van de identifier van een knooppunt met een bijzondere status aan elke variabele welke met dit knooppunt is gekoppeld; - middelen voor het verwijderen van elke variabele welke gekoppeld is met een knooppunt als in de daarmee geassocieerde verzameling elke variabele gelijk is aan de identifier van dat knooppunt of als de verzameling leeg is; - middelen voor het toekennen van de waarde van de identifier van een knooppunt aan elke variabele welke gekoppeld is met dit knooppunt, als deze identifier aan een bepaald vergelijkingscriterium voldoet met betrekking tot de variabelen van de verzameling geassocieerd met het knooppunt en mits dit knooppunt niet een knooppunt met een bijzondere status is; en - middelen voor het toekennen van de waarde van een variabele van de verzameling geassocieerd met een knooppunt aan elke variabele welke met dit knooppunt gekoppeld is, als alle variabelen van de verzameling geassocieerd met dit knooppunt identiek zijn en de iden-tifier van dit knooppunt niet voldoet aan het vergelijkingscriterium met betrekking tot laatstgenoemde variabelen.

13. Inrichting omvattende een logisch georganiseerd systeem, dat omvat een samenstel van door digrafen te representeren groepen van via gerichte ribben met elkaar in relatie staande, door knooppunten te representeren entiteiten, waarbij per digraaf aan elk knooppunt een unieke identifier is toegevoegd en waarbij met elk knooppunt dat niet een bijzondere status heeft, een verzameling geassocieerd is, waarvan ieder element een variabele representeert die separaat gekoppeld is met een onmiddellijke voorganger van het knooppunt, welke variabele een rij omvat van nul of meer identifiers van knooppunten, met het kenmerk, dat de inrichting is voorzien van: A. middelen voor het per knooppunt met bijzondere status toekennen van de identifier van het knooppunt aan elke variabele welke met dit knooppunt is gekoppeld; en B. middelen voor het per knooppunt dat niet een bijzondere status heeft, op basis van de variabelen uit de met het knooppunt geassocieerde verzameling uitvoeren van de navolgende stappen: - het verwijderen van elke variabele met een rij, waarin als bestanddeel met een gedefinieerde ligging een rij van een andere variabele voorkomt, mits laatstgenoemde rij voorzien is van een merkteken; - het bepalen van een referentiewaarde door eerst aan de hand van een eerste vergelijkingscriterium een variabele te selecteren en vervolgens uit de door deze variabele omvatte rij, die iden-tifiers, inclusief merkteken indien aanwezig, te verwijderen welke voldoen aan een tweede, op de identifier van onderhavig knooppunt gebaseerde vergelijkingscriterium; en - het uit de resterende variabelen en de verkregen referentiewaarde afleiden van een waarde en deze als resultaatwaarde toe kennen aan elke variabele welke gekoppeld is met het onderhavig knooppunt waarbij, in het geval dat deze waarde voorzien is van een merkteken en de rij slechts een identifier bevat, het onderhavig knooppunt zekerheid heeft verkregen over de status van de digraaf.