I realtidssystem med trådar, resurslåsning och prioriterad schemaläggning står man inför problemet med Priority Inversion. Detta problem kan göra beteendet hos trådar oförutsägbart och de resulterande buggar kan vara svårt att hitta. Det prioriterade arvsprotokollet är en lösning som genomförs i många system för att lösa detta problem, men riktigheten i denna lösning har aldrig formellt bekräftats i ett teoremtest. Som redan påpekats i litteraturen utgör den ursprungliga informella undersökningen av Arvsrättsprotokollet ett korrekt "säkert" för en felaktig algoritm. I detta dokument löser vi problemet med detta bevis genom att göra alla begrepp exakta och genomföra en variant av en lösning som föreslagits tidigare. Vi generaliserar också schemaläggningsproblemet till praktiskt taget relevanta fall där kritiska sektioner kan överlappa varandra. Vår formalisering i Isabelle/HOL bygger på Paulsons induktiva inställning till protokollverifiering. Formaliseringen avslöjar inte bara fakta som förbises i litteraturen, utan bidrar också till ett effektivt genomförande av detta protokoll. Tidigare genomföranden kritiserades för ineffektiva. Vår implementering bygger på det lilla PINTOS-operativsystemet som används för undervisning.
I REF specificerar formellt kravet på korrekthet (ingen prioritetsinversion) i protokollet om prioriterade arv med hjälp av Isabelle/HOL, och bevisar att ett genomförande är korrekt, men tidsmässiga egenskaper är inte modellerade.
Priority Inheritance Protocol Proved Correct
{'venue': 'ITP', 'journal': None, 'mag_field_of_study': ['Computer Science']}