Tidsplan (datalogi) - Schedule (computer science)

Inden for databaser og transaktionsbehandling (transaktionsstyring) er en tidsplan (eller historie ) for et system en abstrakt model til at beskrive udførelse af transaktioner, der kører i systemet. Ofte er det en liste over operationer (handlinger), der er ordnet efter tid, udført af et sæt transaktioner , der udføres sammen i systemet. Hvis ordren i tid mellem bestemte operationer ikke bestemmes af systemet, anvendes en delordre . Eksempler på sådanne operationer er anmodning om en læsning, læsning, skrivning, afbrydelse, begåelse, anmodning om en lås, låsning osv. Ikke alle transaktionstyper skal inkluderes i en tidsplan og typisk kun valgte operationstyper (f.eks. Dataadgangsoperationer ) er inkluderet, efter behov for at begrunde og beskrive visse fænomener. Tidsplaner og skemaegenskaber er grundlæggende begreber i databasens samtidighedskontrolteori .

Formel beskrivelse

Følgende er et eksempel på en tidsplan:

I dette eksempel repræsenterer den vandrette akse de forskellige transaktioner i tidsplanen D. Den lodrette akse repræsenterer tidsrækkefølge for operationer. Skema D består af tre transaktioner T1, T2, T3. Tidsplanen beskriver transaktionernes handlinger som vist i DBMS . Først læser og skriver T1 for at objekt X og derefter forpligter sig. Derefter læser og skriver T2 for at modsætte Y og forpligter sig, og endelig læser og skriver T3 for at modsætte Z og forpligter sig. Dette er et eksempel på en seriel tidsplan, dvs. sekventiel uden overlapning i tiden, fordi alle tre transaktioners handlinger er sekventielle, og transaktionerne ikke er sammenflettet i tiden.

At repræsentere tidsplan D ovenfor ved en tabel (snarere end en liste) er kun for nemheds skyld at identificere hver transaktions operationer i et blik. Denne betegnelse bruges i hele artiklen nedenfor. En mere almindelig måde i den tekniske litteratur til at repræsentere en sådan tidsplan er ved en liste:

D = R1 (X) W1 (X) Com1 R2 (Y) W2 (Y) Com2 R3 (Z) W3 (Z) Com3

Normalt er en operation med det formål at argumentere om samtidighedskontrol i databaser modelleret som atomisk , der forekommer på et tidspunkt uden varighed. Når dette ikke er tilfredsstillende, angives start- og sluttidspunkter og muligvis andre punktbegivenheder (sjældent). Virkelige udførte operationer har altid en vis varighed og specificerede respektive tidspunkter for forekomst af begivenheder inden i dem (f.eks. "Nøjagtige" tidspunkter for start og afslutning), men med hensyn til samtidighedskontrol begrundes normalt kun forrang i tiden for hele operationerne (uden at se på ganske komplekse detaljer om hver operation) betyder noget, dvs. hvilken operation der er før eller efter en anden operation. Desuden betyder forholdet mellem to specifikke operationer i mange tilfælde ikke noget og bør ikke specificeres, mens det specificeres for andre par operationer.

Generelt kan operationer af transaktioner i en tidsplan interleave (dvs. transaktioner kan udføres samtidigt), mens tidsordrer mellem operationer i hver transaktion forbliver uændrede som underforstået af transaktionens program. Da ikke altid tid ordrer mellem alle operationer af alle transaktioner stof og behov for at blive specificeret, en tidsplan er generelt en partiel orden mellem operationer i stedet for en samlet ordre (hvor ordre for hvert par bestemmes, som i en liste over operationer ). Også i det generelle tilfælde kan hver transaktion bestå af flere processer og i sig selv være korrekt repræsenteret af en delvis rækkefølge af operationer snarere end en samlet ordre. Generelt er en tidsplan således en delvis rækkefølge af operationer, der indeholder ( indlejring ) delordrer af alle dens transaktioner.

Tidsordre mellem to operationer kan repræsenteres af et ordnet par af disse operationer (fx eksistensen af ​​et par (OP1, OP2) betyder, at OP1 altid er før OP2), og en tidsplan er i almindelighed et sæt af sådanne bestilte par. Et sådant sæt, en tidsplan, er en delvis rækkefølge, der kan repræsenteres af en acyklisk rettet graf (eller rettet acyklisk graf , DAG) med operationer som noder og tidsrækkefølge som en rettet kant (ingen cyklusser er tilladt, da en cyklus betyder, at en første (enhver) operation på en cyklus kan være både før og efter (enhver) anden anden operation på cyklussen, hvilket modsiger vores opfattelse af tid ). I mange tilfælde bruges en grafisk gengivelse af en sådan graf til at demonstrere en tidsplan.

Kommentar: Da en liste over operationer (og tabelnotationen, der bruges i denne artikel) altid repræsenterer en samlet rækkefølge mellem operationer, kan tidsplaner, der ikke er en samlet ordre, ikke repræsenteres af en liste (men altid kan repræsenteres af en DAG).

Typer af tidsplan

Seriel

Transaktionerne udføres ikke sammenflettet (se eksemplet ovenfor), dvs. en seriel tidsplan er en, hvor ingen transaktion starter, før en kørende transaktion er afsluttet.

Serialiserbar

En tidsplan, der svarer (i resultatet) til en serieplan, har egenskaben serializability .

I tidsplan E er rækkefølgen, hvor handlingerne i transaktionerne udføres, ikke den samme som i D, men i sidste ende giver E det samme resultat som D.

Modstridende handlinger

To handlinger siges at være i konflikt (modstridende par), hvis:

1. Handlingerne hører til forskellige transaktioner.
2. Mindst en af ​​handlingerne er en skriveoperation.
3. Handlingerne har adgang til det samme objekt (læs eller skriv).

Følgende sæt handlinger er modstridende:

• R1 (X), W2 (X), W3 (X) (3 modstridende par)

Mens følgende sæt handlinger ikke er:

• R1 (X), R2 (X), R3 (X)
• R1 (X), W2 (Y), R3 (X)

Konfliktækvivalens

Tidsplanerne S1 og S2 siges at være konfliktækvivalente, hvis følgende to betingelser er opfyldt:

1. Begge tidsplaner S1 og S2 involverer det samme sæt transaktioner (inklusive bestilling af handlinger inden for hver transaktion).
2. Begge tidsplaner har det samme sæt modstridende operationer.

Konflikt-serierbar

En tidsplan siges at være konfliktserialiserbar, når tidsplanen er konfliktækvivalent med en eller flere serielle tidsplaner.

En anden definition for konfliktserialiserbarhed er, at en tidsplan kan konfliktserialiseres, hvis og kun hvis dens forrangsgraf / serierbarhedsgraf, når kun forpligtede transaktioner overvejes, er acyklisk (hvis grafen er defineret til også at omfatte ikke-forpligtede transaktioner, så cyklusser, der involverer ikke-forpligtet transaktioner kan forekomme uden overtrædelse af konfliktserierbarhed).

Hvilket er konfliktækvivalent med den serielle tidsplan <T1, T2>, men ikke <T2, T1>.

Forpligtelsesbestemt

En tidsplan siges at være forpligtelsesordnet (forpligtelsesordret) eller forpligtelsesordre-serienummerbar, hvis den overholder forpligtelsesbestillingen (CO; også forpligtelsesbestilling eller forpligtelsesordre-seriabilitet) tidsplanegenskab. Dette betyder, at rækkefølgen i tid af transaktionernes forpligtelsesbegivenheder er kompatibel med forrangsrækkefølgen (delvis) for de respektive transaktioner, som induceret af deres tidsplans acykliske forrangsgraf (seriabilitetsgraf, konfliktgraf). Dette indebærer, at det også kan konfliktserieres. CO-ejendommen er især effektiv til at opnå global seriabilitet i distribuerede systemer.

Kommentar: Forpligtelsesbestilling , som blev opdaget i 1990, er naturligvis ikke nævnt i ( Bernstein et al. 1987 ). Dens korrekte definition vises i ( Weikum og Vossen 2001 ), men beskrivelsen deraf dens relaterede teknikker og teori er delvis, unøjagtig og vildledende. For en omfattende dækning af forpligtelsesbestilling og dens kilder se Forpligtelsesbestilling og Historien om forpligtelsesbestilling .

Se ækvivalens

To skemaer S1 og S2 siges at være visningsækvivalente, når følgende betingelser er opfyldt:

1. Hvis transaktionen i S1 læser en startværdi for objekt X, gør også transaktionen i S2.${\ displaystyle T_ {i}}$${\ displaystyle T_ {i}}$
2. Hvis transaktionen i S1 læser den værdi, der er skrevet af transaktionen i S1 for objekt X, gør også transaktionen i S2.${\ displaystyle T_ {i}}$${\ displaystyle T_ {j}}$${\ displaystyle T_ {i}}$
3. Hvis transaktionen i S1 er den sidste transaktion til at skrive værdien for et objekt X, er også transaktionen i S2.${\ displaystyle T_ {i}}$${\ displaystyle T_ {i}}$

Serier, der kan ses

En tidsplan siges at kunne ses-serieres, hvis den svarer til en seriel tidsplan. Bemærk, at pr. Definition er alle tidsplaner, der kan konfliktserialiseres, serbare.

Bemærk, at ovenstående eksempel (som er det samme som eksemplet i diskussionen om konfliktserialiserbar) både kan serieserialiseres og konfliktserialiseres samtidigt. Der er dog tidsplaner, der kan ses-serier, der ikke er konflikt-serierbare: disse tidsplaner med en transaktion, der udfører en blind skrivning :

Ovenstående eksempel kan ikke konfliktserialiseres, men det kan serieserieres, da det har en seriekvivalent seriel tidsplan <T1, | T2, | T3>.

Da det bestemmes, om en tidsplan kan ses-serierbar, er NP-komplet , har visningsserialiserbarhed kun lidt praktisk interesse.

Gendannes

Transaktioner begås først efter alle transaktioner, hvis ændringer de læser, begår.

Disse tidsplaner kan inddrives. F kan genvindes, fordi T1 forpligter sig før T2, hvilket gør den værdi, der læses af T2, korrekt. Så kan T2 forpligte sig. I F2, hvis T1 blev afbrudt, skal T2 afbrydes, fordi værdien af ​​A, den læste, er forkert. I begge tilfælde efterlades databasen i en konsistent tilstand.

Uoprettelig

Hvis en transaktion T1 afbrydes, og en transaktion T2 begår, men T2 er afhængig af T1, har vi en uoprettelig tidsplan.

I dette eksempel er G uoprettelig, fordi T2 læser værdien af ​​A skrevet af T1 og begået. T1 afbrød senere, derfor er den af ​​T2 læste værdi forkert, men da T2 er begået, er denne tidsplan uoprettelig.

Cascadeless

Også "Undgå kaskadeafbrydelser (ACA)". Undgår, at en enkelt transaktion afbrydes, fører til en række tilbagekøb af transaktioner. En strategi for at forhindre kaskadeafbrydelser er at tillade, at en transaktion ikke læser uforpligtede ændringer fra en anden transaktion i samme tidsplan.

Følgende eksempler er de samme som dem i diskussionen om inddrivelse:

I dette eksempel, selvom F2 kan genvindes, undgår det ikke kaskadeafbrydelser. Det kan ses, at hvis T1 afbrydes, skal T2 også afbrydes for at opretholde korrektheden af ​​tidsplanen, da T2 allerede har læst den ikke-forpligtede værdi skrevet af T1.

Følgende er en gendannelsesplan, der undgår kaskadeafbrydelse. Bemærk dog, at opdateringen af ​​A af T1 altid går tabt (da T1 afbrydes).

Bemærk, at denne tidsplan ikke kan seriebestemmes, hvis T1 bliver forpligtet. Kaskadeafbrydelse er tilstrækkelig, men ikke nødvendig for, at en tidsplan kan inddrives.

Streng

En tidsplan er streng - har egenskaben strenghed - hvis der for to transaktioner T1, T2, hvis en skriveoperation af T1 går forud for en modstridende operation af T2 (enten læse eller skrive), så begår eller afbryder begivenheden for T1 også forud for den modstridende drift af T2.

Enhver streng tidsplan er kaskadeløs, men ikke det omvendte. Strenghed tillader effektiv gendannelse af databaser fra fejl.

Hierarkisk forhold mellem klasser for seriabilitet

Følgende udtryk illustrerer de hierarkiske (indeslutnings) forhold mellem serielizabilitet og gendannelsesklasser :

• Seriel ⊂ forpligtelsesbestilt ⊂ konfliktserialiserbar ⊂ visningsserialiserbar ⊂ alle tidsplaner
• Seriel ⊂ streng ⊂ kaskadeløs (ACA) ⊂ genoprettelig ⊂ alle tidsplaner

Den Venn-diagram (nedenfor) illustrerer ovennævnte bestemmelser grafisk.

Venn-diagram for klasser for serie- og inddrivelighed

Praktiske implementeringer

I praksis anvender databaser på de fleste generelle formål konfliktserialiserbare og genoprettelige (primært strenge) tidsplaner.

Se også

• tidsplan (projektledelse)

Referencer

• Philip A. Bernstein , Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems , Addison Wesley Publishing Company, 1987, ISBN  0-201-10715-5
• Gerhard Weikum , Gottfried Vossen: Transaktionelle informationssystemer , Elsevier, 2001, ISBN  1-55860-508-8