5 įvadas

1 skyrius. Loginių išvadų ir žinių apdorojimo sistemų metodų ir mašinų analizė 14

1.1 Loginių išvadų metodai ir mašinos 14

1.1.1 Loginių išvadų tipų klasifikacija 14

1.1.2 Išvadų metodų klasifikavimas 16

1.1.3 19 punktų padalijimo būdas

1.1.4 Išvadų mašinos 23

1.2 Žinių apdorojimo sistemos (KPS) 25

1.2.1 Apibrėžtis ir struktūra 25

1.2.2 Klasifikacija 29

1.2.3 Darbo režimai 31

1.2.4 Veiklos vertinimas 33

1.3 Išvados dėl 1 skyriaus 35

2 skyrius. Modifikuotų išvadų loginės išvados metodo kūrimas 36

2.1 Formalios sistemos 36

2.2 Loginės išvados problemos teiginys 37

2.3 Išvados formulės išplėtimas

2.3.1 Pažodinių žodžių suvienodinimas 39

2.3.2 Sprendimų derinimas 40

2.3.3 Susitarimas dėl bendrųjų kintamųjų reikšmių disjunkcijų jungtyse 43

2.3.4 Dalinis 45 punktų padalijimas

2.3.5 Visiškas 47 punktų padalijimas

2.3.6 Išvesties procedūra 49

2.3.7 Pagrobimo paaiškinimų kūrimas

2.3.8 Lygiagrečios išvados metodas su išvados formulės išplėtimu

2.4 Išvados formulės sumažinimas 65

2.4.1 Išvadų sumažinimo procedūra 65

2.4.2 Išvadų mažinimo metodas

2.5 Modifikavimo parinkčių pasirinkimas 69

2.6 Išvados ypatumai teiginio skaičiavime 72

2.7 73 išvesties pavyzdys

2.8 Išvados dėl 2 skyriaus 77

3 skyrius. Modifikuotų išvadų loginių išvadų sistemos kūrimas 80

3.1 Išvadų sistemos struktūra 80

3.1.1 Apibendrinta sistemos struktūra 80

3.1.2 Išsami sistemos struktūra 82

3.2 Loginių išvadų sistemos veikimo režimai 85

3.2.1 Modifikuotų išvadų išvedimo būdas 86

3.2.2 Dedukcinės išvados režimas 88

3.2.3 Abduktyviosios išvados režimas 88

3.2.4 Nustatymo režimas 88

3.2.5 Tiesioginės prieigos prie žinių bazių būdas 89

3.2.6 Žinių bazės kūrimas

3.3 Loginių išvadų mašina modifikuotoms išvadoms 90

3.4 Deklaracinės logikos programavimo kalba

3.4.1 Loginės programos struktūra 96

3.4.2 Identifikatoriai ir konstantos 99

3.4.3 Komentarai 100

3.4.4 Pavyzdinė logikos programa 101

3.5 Išvadų sistemų efektyvumo įvertinimas 102

3.5.1 Veiklos vertinimo kriterijai 102

3.5.2 Atsiėmimo laiko apskaičiavimas 103

3.5.3 Išvados modifikavimo laipsnio apskaičiavimas 108

3.6 Išvados dėl 3 skyriaus 110

4 skyrius. Loginių išvadų sistemų taikymas modifikuotoms IZ išvadoms

4.1 Paraiškos 113

4.2 Pažangios mokymo sistemos 114

4.3 Ekspertų sistemos 119

4.4 Sumanus skaičiavimo procesų valdymas 121

4.5 Modifikuotų išvadų loginis išvesties modulis 1

4.5.1 Bendrosios kuriamos programinės įrangos charakteristikos 127

4.5.2 Išvesties modulio struktūra 128

4.5.3 Žinių bazės ir išvadų aprašymo kalba 129

4.5.4 Modulio 130 blokų įgyvendinimas

4.6 Loginių išvadų mokymo programa „Logika-V“ 134

4.6.1 Programos struktūra 134

4.6.2 Kalba, skirta apibūdinti šaltinio duomenis 135

4.6.3 Vartotojo sąsaja 136

4.6.4 Programos naudojimo pavyzdys 141

4.7 Išvados dėl 4 skyriaus 149

152 išvada

Santrumpų sąrašas 155

Bibliografija 156

Paraiškos 1

Įvadas į darbą

Ši disertacija skirta naujam modifikuojamų išvadų apie žinias, pateiktų teiginių skaičiavimo ir pirmos eilės predikatų skaičiavimo formulių pavidalu, loginės išvados metodui, taip pat modifikuojamų išvadų loginės išvados sistemai sukurti. Nagrinėjami žinių apdorojimo sistemų ir loginių išvadų mašinų konstravimo šiuo metodu klausimai, įskaitant jų programinės įrangos diegimo šiuolaikinėse lygiagrečiose skaičiavimo platformose ypatybes. Pateikiamos šio loginių išvadų metodo galimo taikymo sritys, nagrinėjamas modifikuotų išvadų loginės išvados panaudojimas intelektualiam skaičiavimo procesų valdymui, mokymo sistemose ir ekspertinėse sistemose.

Tyrimo temos aktualumas. Viena iš perspektyvių kompiuterinių sistemų sričių šiandien yra žinių apdorojimo sistemos (KPS). Jie jau plačiai paplitę (tai ypač pasakytina apie ekspertines sistemas (ES)), o ateityje jas bus galima naudoti beveik visur, padidinant beveik visų tipų skaičiavimo sistemų intelektinį lygį. Tačiau, nepaisant esamų sėkmių, šiuolaikiniai POP turi nemažai trūkumų. Visų pirma, jie negali išspręsti problemų, kurioms reikia patikimos išvados, kai yra nepatikima. Be to, šiuolaikiniai POP neveikia efektyviai lygiagrečiose platformose.

Skirtingai nuo duomenų, kurie yra bet kokių formalizuotų apdorojimo veiksmų operandai ir apdorojimo sistemos požiūriu neturi semantinio turinio, žinios atspindi tam tikrus realaus pasaulio aspektus ir iš pradžių turi semantinį turinį. Geriausia šiandien žinoma žinių apdorojimo sistema yra žmogaus smegenys. Tačiau jis taip pat turi tam tikrų trūkumų. Visų pirma, jis pasižymi mažu našumu sprendžiant daugelį problemų, smegenų veiklai įtakos turi daug veiksnių ir ji yra linkusi į klaidas. Be to, aplinkos sąlygos dažnai neleidžia naudoti žmogaus kaip žinių apdorojimo ir sprendimų priėmimo sistemos. Reikia modeliuoti žmogaus elgesį.

Yra du pagrindiniai natūralaus intelekto elgesio modeliavimo būdai. Pirmasis iš jų – modeliuoti atskirų smegenų struktūros elementų – neuronų ir jų jungčių darbą (neuroninio tinklo metodas). Būdingas jo trūkumas yra sunkumas (dažnai ir neįmanomas) sukurti semantinį samprotavimo eigos vaizdą. Antrasis metodas apima intelektualinių smegenų veikimo aspektų modeliavimą: sąvokų sistemą (semantinį tinklą), samprotavimą ir kt. Tuo pačiu šiuo metu dažniausiai naudojamas žmogaus samprotavimo modeliavimas, nes pagal tam tikras taisykles (pavyzdžiui, pagal logikos taisykles) imituojami aukšto lygio mąstymo procesai ir leidžia gana paprastai apibūdinti šaltinio duomenis bei interpretuoti. rezultatą, taip pat stebėti modeliavimo eigą.

Samprotavimo modeliavimas naudojant logiką yra viena iš prioritetinių mokslo sričių, tiriančių dirbtinio intelekto metodus ir priemones. Samprotavimas, parašytas pirmosios eilės predikatinės logikos arba teiginių logikos formulių forma, žmonėms atrodo gana natūralus. Formulės aiškinimas yra paprastas ir susideda iš pažodinių žodžių pakeitimo iš anksto apibrėžtomis išraiškomis, o jungiamuosius žodžius - žodžiais, atitinkančiais jų reikšmę.

Teiginių logika yra gana paprastas matematinis aparatas, kuris neturi labai didelių išraiškos galimybių. Tačiau dėl formulių apdorojimo paprastumo teiginių logika yra plačiai naudojama. Pirmosios eilės predikatų logika turi daug didesnes išraiškos galimybes. Tačiau formulių apdorojimas predikatiniuose skaičiavimuose yra daug sudėtingesnis, nes reikia atsižvelgti į predikatinių konstantų reikšmių priklausomybę nuo terminų rinkinių, derinti dalykinių kintamųjų reikšmes ir atsižvelgti į buvimo galimybę. funkcinių konstantų.

Pats samprotavimo modeliavimas atliekamas naudojant loginę išvadą (LI). Pradiniai loginių išvadų duomenys yra prielaidų ir išvados formulės. Patalpos yra faktų ir išvadų taisyklių rinkinys ir kartu sudaro žinių bazę. Išvada parašyta loginės formulės forma ir ateina (paprastai) iš išorės į loginių išvadų sistemą. Išvadų procedūros apdoroja išvadą ir pradines prielaidas, o darbo rezultatas gali būti pranešimas apie išvados teisingumą arba pradinių prielaidų modifikavimas.

Paprastai išskiriami šie pagrindiniai loginių išvadų tipai: dedukcinis, abdukcinis ir indukcinis. Dedukcinė išvada naudojama atsakyti į klausimą, ar pateikta išvada yra loginė pradinių premisų pasekmė. Abdukcinė išvada, jei išvada nėra išvedama iš pradinių premisų, leidžia papildyti pradinių premisų aibę faktais, kad išvada taptų išvedama. Indukcinė išvada, skirtingai nei abdukcinė išvada, leidžia papildyti pradinių premisų rinkinį bendromis taisyklėmis.

Šios išvadų rūšys žinomos ilgą laiką ir gali būti naudojamos sprendžiant daugybę problemų. Tačiau yra problemų, kurių neįmanoma arba sunku išspręsti naudojant tokio tipo išvadas, klasė. Ši problemų klasė daro prielaidą, kad yra teisinga ir išsami tam tikros dalykinės srities žinių bazė ir nepatikima išvada, kurią reikia pakeisti. Vadinasi, atsiranda iš esmės nauja loginės išvados problemos formuluotė: modifikuoti iš pradžių neišvestinę išvadą, kad ji taptų pradinių premisų pasekmė. Ši problema išspręsta naudojant naujo tipo LP – modifikuotų išvadų loginę išvadą. Galima pastebėti tokias šio tipo išėjimo taikymo sritis: - automatinės valdymo sistemos. Valdymo objekto būsena tokioje sistemoje apibūdinama loginės išvados formule, o leistinas būsenų diapazonas nurodomas pradinių patalpų formulių pavidalu. Jei objekto būsena yra už priimtinų ribų, išvada modifikuojama, kad objektas būtų grąžintas į priimtiną būseną;

Korekcinės mokymo sistemos. Pradinių prielaidų bazėje yra žinios iš tam tikros dalykinės srities. Mokinys įveda teiginį, kurio teisingumas (išvedimas iš pradinių premisų) patikrinamas, o jei jis neteisingas, taisomas;

Gramatinė sakinių analizė. Modifikuotų išvadų loginė išvada gali būti naudojama sakiniams atkurti ir naujiems sakiniams kurti;

Dinaminės architektūros skaičiavimo sistemos. Modifikuotų išvadų loginė išvada gali būti naudojama skaičiavimo procesams perduoti sistemose su dinamiškai kintančia sudėtimi ir skaičiavimo priemonių ryšiais;

Ekspertų sistemos. Jei vartotojo pirminė išvada yra neišsami arba neteisinga, logiška modifikuotų išvadų išvada leis paaiškinti (pataisyti) išvadą, o kai kuriais atvejais nurodyti būtinybę ištirti papildomas savybes.

Yra gana daug loginių išvadų metodų. Nemažos jų dalies pagrindinis trūkumas – nuoseklus žinių apdorojimo principas. Tai labai sumažina išvadų sistemų, naudojančių šiuos metodus, našumą. Šiuo atžvilgiu dėmesio verti lygiagrečių loginių išvadų metodai, pagrįsti sakinių padalijimo procedūra. Kiekvienas tokios išvesties veiksmas gali apimti nemažai operacijų, kurių daugumą galima atlikti lygiagrečiai. Tai ypač aktualu šiuo metu, nes dabar daugeliu atvejų kompiuterio našumas didinamas ne tik ir ne tiek tobulinant procesorių architektūrą ir mikroarchitektūrą, didinant laikrodžio dažnius, bet didinant procesoriaus elementų (procesorių ir branduolių) skaičių. .

Taigi neatidėliotinas uždavinys yra sukurti metodą ir sistemą, skirtą lygiagrečiam loginiam modifikuotų išvadų apie žinias išvadoms, pateiktoms teiginio skaičiavimo ir pirmosios eilės predikato skaičiavimo formulių pavidalu, kurie išplės SOZ sprendžiamų problemų klasę, paremtą loginių išvadų sistemos pagrindu ir padidinti jų darbo greitį.

Kuriant ir tyrinėjant metodus ir loginės išvados priemones, reikšmingai prisidėjo M. L. Cetlinas, M. M. Bongardas, Ya Z. Tsypkinas, D. A. Pospelovas, V. K. Finnas, G. S. Osipovas, V. N. Vaginas, T. A. Gavrilova, V. F. Khoroshevsky. P. Gaekas, T. Gavranekas, S. Osuga, U. Saeki, A. Samuelis, E. Huntas, J. Marinas, P. Stone'as, R. Michalskis, J. Carbonellas, T. Mitchellas, T. Mitchellas), D. Kvinlanas. Abdukcinis LE buvo tiriamas C. S. Pierce, V. K. Finn, V. N. Vagin, E. Yu Golovina, D. A. Strabykin, M. L. Dolzhenkova, D. D. Gabbay, P. Smets, C. Boutilier, P. Flach, A. Kakas darbuose. , K. Inoue ), C. Sakama, J. Josephson, S. Mcllraith, G. Paul ir kt.

Darbo tikslas – sukurti modifikuotų išvadų paralelinės loginės išvados metodą teiginių skaičiavimui ir pirmos eilės predikatų skaičiavimui ir jo pagrindu sukurti modifikuotų išvadų sistemą ir LP mašiną. Norint pasiekti tikslą, būtina išspręsti šias užduotis.

1. Sukurti modifikuotų išvadų paralelinio loginio išvedimo metodą teiginių skaičiavimui ir pirmos eilės predikatų skaičiavimui, leidžiantį modifikuoti neišvestinę išvadą ir padaryti ją pradinių premisų pasekmė.

2. Sukurti modifikuotų išvadų lygiagrečių loginių išvadų mašiną.

3. Sukurti lygiagrečią loginių išvadų sistemą, pagrįstą loginių išvadų mašina modifikuotoms išvadoms.

4. Sukurti sistemos ir mašinos efektyvumo vertinimo kriterijus, skirtus modifikuotų išvadų lygiagrečiai loginei išvadai.

Tyrimo metodai. Darbe iškeltam tyrimo tikslui pasiekti buvo naudojami algoritmų analizės, aibių teorijos, grafų teorijos, matematinės logikos, išvadų teorijos, loginio ir objektinio programavimo metodai.

Tyrimo mokslinė naujovė yra tokia.

1. Sukurtas teiginių logikos ir pirmos eilės predikatinės logikos modifikuotų išvadų lygiagrečių loginių išvadų metodas, kuris skiriasi nuo žinomų metodų tuo, kad papildomoms premisoms, gautoms abduktyviosios išvados rezultate, taikomos šios papildomos prielaidos: a. speciali transformavimo procedūra, leidžianti iš jų sudaryti išvados disjunktų papildymus, išvados sumažinimo metodą, taip pat paralelinį išvados modifikavimo variantų vertinimo algoritmą. Tai leidžia paversti neišvestinę išvadą, kad ji taptų pradinių prielaidų pasekmė.

2. Teiginių skaičiavimui ir pirmos eilės predikatiniam skaičiavimui sukurtas išvadų mažinimo metodas, kuris skiriasi nuo žinomų išvadų metodų tuo, kad sprendimams rasti naudoja lygiagrečią paiešką per sprendimų medį, nupjaunant dalį šakų. Tuo pačiu metu iš išvados sakinių pašalinami literalai, kurie nedalyvauja išvadų procese, taip padidinant modifikuotų išvadų loginių išvadų sistemos efektyvumą.

3. Sukurtas paralelinis išvados punktų modifikavimo variantų vertinimo ir parinkimo algoritmas, pasižymintis tuo, kad kiekvienam sakiniui priskiriama tam tikra skaitinė reikšmė, gauta sakiniui taikant specialią vertinimo funkciją. Tai leidžia pasirinkti geriausius iš viso pradinių disjunkcijų modifikavimo variantų rinkinio pagal pasirinktą disjunkto vertinimo funkciją.

4. Sukurti modifikuotų išvadų loginės išvados sistemos ir mašinos efektyvumo vertinimo kriterijai ir metodai, atsižvelgiant į loginės išvados dalybos sakiniais ypatumus, pasirinktą lygiagretumo laipsnį, kompiuterio architektūrą, išvadų tipus. išvados modifikavimas, leidžiantis įvertinti laiką, sugaištą loginei išvadai ir išvados modifikavimo laipsnį.

Praktinė tyrimo vertė yra tokia:

1. Sukurta lygiagrečių, loginių modifikuojamų išvadų išvedžiojimo sistema, kurios skiriamieji bruožai yra: lygiagrečių LP metodų ir mašinų naudojimas, dviejų lygių žinių bazės naudojimas, formulių interpretavimo bloko buvimas, kuri leidžia sukurti didelio našumo POP įvairiems tikslams remiantis sukurta loginių išvadų sistema. Išvados procesą galima lygiagretinti iki pažodinių suvienodinimo operacijų lygio, o tai padidina loginių išvadų greitį lygiagrečiose skaičiavimo platformose.

2. Sukurta deklaratyviosios logikos programavimo kalba, leidžianti apibūdinti žinias naudojant teiginio skaičiavimo ir pirmos eilės predikatinio skaičiavimo formules, naudoti funkcierius, daryti prielaidą, kad galima logines formules interpretuoti natūralia kalba.

3. Sukurta loginių išvadų mokymo programa, kurios skiriamieji bruožai yra šie: kelių tipų loginių išvadų įgyvendinimas dalijant sakinius teiginiams apskaičiuoti, įskaitant modifikuotų išvadų loginę išvadą, formulių konvertavimo mechanizmo buvimas. į daugybę sakinių, formulių aiškinimas natūralia kalba, išsami pažangos ataskaitos išvestis. Sistemos ypatybės leidžia ja naudotis tiriant loginių išvadų tipus ir metodus.

4. Sukurtos rekomendacijos modifikuotų išvadų lygiagrečios loginės išvados metodo ir sistemos panaudojimui sumaniam skaičiavimo procesų valdymui, intelektualiose mokymo sistemose ir ekspertinėse sistemose.

Apginti pateikiami šie dalykai:

1. Teiginių logikos ir pirmos eilės predikatinės logikos modifikuotų išvadų paralelinio loginio išvedimo metodas, leidžiantis transformuoti neišvestinę išvadą, kad ji būtų pradinių premisų pasekmė.

2. Teiginių skaičiavimo ir pirmos eilės predikatų skaičiavimo išvadų mažinimo metodas, leidžiantis pašalinti išvadų procese nedalyvaujančius literatus ir taip padidinti išvadų sistemos efektyvumą.

3. Lygiagretus išvados punktų modifikavimo variantų įvertinimo ir parinkimo algoritmas, leidžiantis iš visos pradinių sakinių modifikavimo variantų rinkinio atrinkti geriausius pagal pasirinktą optimalių sprendimų paieškos taisyklę.

4. Modifikuotų išvadų loginės išvados sistemos ir mašinos efektyvumo vertinimo kriterijai ir metodai, atsižvelgiant į loginės išvados dalybos sakiniais ypatumus, pasirinktą lygiagretumo laipsnį, kompiuterio architektūrą, išvados modifikavimo tipus.

5. Lygiagreti modifikuotų išvadų loginių išvadų sistema, pagrįsta lygiagrečia loginių išvadų mašina, galinti atlikti pagrindinius loginių išvadų tipus, taip pat modifikuotų išvadų loginę išvadą. Tyrimo rezultatų įgyvendinimas. Gauti teoriniai ir praktiniai rezultatai buvo panaudoti tiriamajame darbe „Loginių išvadų teorija ir taikymas modifikuojant išvadas“ (Rusijos Federacijos švietimo ministerijos dotacija E02-2.0-93), tiriamajame darbe „A. deklaratyviosios logikos programavimo aplinka klasterinei skaičiavimo sistemai“ (Vjatkos valstybinis universitetas, tiriamasis darbas Nr. 412) . Vjatkos valstybiniuose ir Vjatkos valstybiniuose humanitariniuose universitetuose į ugdymo procesą įtraukta loginės išvados mokymo programa.

Darbo aprobavimas. Pagrindinės tyrimo nuostatos ir rezultatai buvo pristatyti ir aptarti V tarptautinėje konferencijoje „Interaktyvios sistemos: žmogaus ir kompiuterio sąveikos problemos“, Uljanovskas, Uljanovsko valstybinis technikos universitetas, 2003 m. 9-oji „Nacionalinė dirbtinio intelekto konferencija KII-2004“, Tverė, 2004 m.; Visos Rusijos metinė Vjatkos valstybinio universiteto mokslinė ir techninė konferencija „Mokslas-gamyba-technologija-ekologija“, Kirovas (2004,2007,2008)

Išvadų ir sprendimų paieškos gamybos sistemose metodai.

Išvadų metodai, pagrįsti pirmyn ir atgal grandine.

Gamybos reprezentacijoje žinių sritis vaizduojama gamybos jei-tada taisyklių rinkiniu, o duomenys – faktų apie esamą situaciją rinkinys.

Išvadų variklis suderina kiekvieną KB saugomą taisyklę su DB esančiais faktais. Kai taisyklės dalis (sąlyga) atitinka faktą, suveikia taisyklė ir jos tada dalis (veiksmas) atlikta. Suaktyvinta taisyklė gali pakeisti daugelį faktų pridėdama naują faktą, kaip parodyta 6.1 pav. DB ir KB raidės naudojamos situacijoms ir sąvokoms pavaizduoti.

6.1 pav. Išvados mechanizmo ciklas degtukų ugnies procedūra

Dalių palyginimas, jei sukuriamos taisyklės su faktais išvesties grandinė. Išvadų grandinė parodo, kaip ES taiko taisykles išvadai gauti. Norėdami iliustruoti grandine pagrįstą išvadų metodą, apsvarstykite paprastą pavyzdį.

Tarkime, iš pradžių duomenų bazėje yra faktai A, B, C, D ir E, o žinių bazėje yra tik trys taisyklės:

1 taisyklė. Y&D → Z

2 taisyklė. X&B&E→Y

3 taisyklė. A→X

Išvesties grandinė pav. 6.2. parodo, kaip ES taiko taisykles faktui Z išvesti.

6.2 pav. Išvesties grandinės pavyzdys.

Pirma, 3 taisyklė vykdoma, kad iš paskelbto fakto A būtų išvestas naujas faktas X. Tada įvykdoma 2 taisyklė, siekiant išvesti faktą Y iš iš pradžių žinomų faktų B ir E, taip pat jau žinomo fakto X. Galiausiai taikoma 1 taisyklė. iš pradžių žinomas faktas D ir naujai gautas faktas Y atvykimui ir išvadai Z.

ES gali atspindėti savo išvadų grandinę, kad paaiškintų, kaip buvo priimtas konkretus sprendimas; tai yra didžioji jos aiškinamųjų galių dalis.

Išvadų variklis turi nuspręsti, kada taisyklės turėtų įsijungti. Yra du pagrindiniai būdai, kuriais taisyklės gali būti įgyvendinamos. Viena vadinama tiesiogine grandine (sąlygiškai daroma išvada), o kita – atvirkštine (tikslinė).

Šiame pavyzdyje naudojama tiesioginė išvesties grandinė.

Gamybos sistemos, kuriose pirmiausiai analizuojama antecedentinė dalis (sąlygos), turi vadinamąją sąlyginę inferencinę architektūrą. Tokios architektūros ekspertinės sistemos pavyzdys yra META-DENDRAL.

Alternatyvus architektūros tipas, gana dažnai naudojamas ekspertinėse sistemose, yra tikslo išvedimo (veiksmo išvedimo arba pasekmės – išvados) gamybos sistemos. Pavyzdžiui, tokia taisyklė kaip

galima interpretuoti kaip

„Loginė A, B ir C jungtis reiškia D“ arba

„Norint įrodyti D, būtina nustatyti A, B, C.

Pastaruoju atveju tikslas turi būti pasiektas dedukcine išvada. Tam išnagrinėjamos taisyklių pasekmės, siekiant rasti taisyklę, kuri leistų pasiekti tikslą. Radus tokią taisyklę, patikrinamos visos jos sąlygos. Jei sąlygos yra teisingos, išėjimas suaktyvinamas. Priešingu atveju tinkamų produktų paieška tęsiasi.

Pažvelkime į supaprastintą gamybos sistemos su nuoseklia išvadine architektūra pavyzdį. Raidės čia nurodo duomenų bazės elementus ir laikomos teisingomis, jei joje yra.

1 taisyklė: A&B&C→D

2 taisyklė: D&F→G

3 taisyklė: A&J→G

4 taisyklė: B→C

5 taisyklė: F→B

6 taisyklė: L→J

7 taisyklė: G→H

Tarkime, tikslas yra nustatyti H tiesą. Pirmas žingsnis yra patikrinti, ar H yra duomenų bazėje? Kadangi šiuo atveju taip nėra, sistema bando padaryti išvadą apie H tiesą naudodama taisykles, kurių H yra dešinėje. Tai yra 7 taisyklė. Dabar sistema bando daryti išvadą apie G tiesą, nes pastarojo tiesa reiškia H tiesą. Duomenų bazė patikrinama dar kartą: duomenų bazėje nėra G, todėl taisyklės polius, kuriame yra G dešinėje pusėje yra organizuotas. Yra keletas tokių taisyklių (dvi ar trys). Kaip „konfliktų sprendimo“ strategiją manysime, kad taisyklės yra išdėstytos pagal prioritetą, o taisyklė su mažiausiu skaičiumi atitinka aukščiausią prioritetą.

Šiuo atveju pasirenkama 2 taisyklė, todėl tikslas dabar tampa išvesti D ir F tiesą. Tam pakanka parodyti, kad A yra teisinga (kadangi ji yra duomenų bazėje), B yra teisinga (pagal į 5 taisyklę), C yra tiesa (pagal 4 taisyklę). Kadangi D ir F tiesa yra įrodyta, tai G tiesa išplaukia iš 2 taisyklės, o H – iš G tiesos (7 taisyklė). Taigi tikslas pasiektas. Elementai, kurie buvo įrodyta, kad yra teisingi, įtraukiami į duomenų bazę. Šiuo atveju tai yra elementai H, G, D, S.V. Tikslinės išvados architektūros pavyzdžiai yra MYCIN.

Išvados apie kadrus ir semantinius tinklus.

Išvestis ant rėmelių.

Rėmo duomenų struktūra.

Prieš aptardami išvestį kadrų sistemoje, atidžiau pažvelkime į rėmelio duomenų struktūrą.

Rėmelių sistema – tai hierarchinė struktūra, kurios mazgai yra kadrai su tam tikra duomenų struktūra.

1. Rėmo pavadinimas. Tai yra rėmeliui priskirtas identifikatorius. Rėmelio pavadinimas turi būti unikalus nurodytoje rėmelių sistemoje (unikalus pavadinimas). Kiekvienas kadras susideda iš savavališko skaičiaus laiko tarpsnių, kai kuriuos iš jų paprastai nustato pati sistema, kad atliktų konkrečias funkcijas, o likusius nustato vartotojas. Tai apima lizdą, rodantį kadrą – šio kadro pirminį elementą; antrinio rėmelio rodyklės lizdas, kuris yra antrinių rėmelių rodyklių sąrašas; anga, skirta įvesti vartotojo vardą, apibrėžimo datą, modifikavimo datą, komentarų dažnį ir kitus lizdus. Kiekvienas lizdas, savo ruožtu, taip pat yra vaizduojamas tam tikra duomenų struktūra.

2. Lizdų pavadinimas. Tai yra lizdui priskirtas identifikatorius; lizdas turi turėti unikalų pavadinimą rėmelyje, kuriam jis priklauso. Paprastai lizdo pavadinimas neturi reikšmės ir yra tik šio lizdo identifikatorius, tačiau kai kuriais atvejais jis gali turėti konkrečią reikšmę. Šie pavadinimai apima: požiūris; tiesioginis vaiko rėmelio rodyklė; rėmo apibrėžimo data; kadro modifikavimo data ir kt.

3. Paveldėjimo rodyklės.Šios nuorodos susijusios tik su hierarchinių tipų rėmų sistemomis, pagrįstomis hierarchiniais tipo ryšiais, pagrįstais abstrakčiais ir konkrečiais ryšiais. Jie parodo, kokią atributo informaciją apie lizdus aukščiausio lygio kadre paveldi tokie pat pavadinimai žemesnio lygio kadre.

4. Duomenų tipo indikatorius (slot atributai). Nurodo, kad lizdas turi skaitinę reikšmę, skaitinę reikšmę arba tarnauja kaip rodyklė į kitą kadrą (ty rodo kadro pavadinimą). Duomenų tipai apima rodyklę, sveikąjį skaičių, realųjį, loginį, pridedamą procedūrą, tekstą, sąrašą, lentelę, išraišką ir kt.

5. Lizdų vertė.Čia įvedama lizdo vertė. Lizdų reikšmė turi atitikti nurodytą to lizdo duomenų tipą, taip pat turi būti įvykdyta paveldėjimo sąlyga.

6. Procedūra – demonas. Yra tokie procedūrų tipai – demonai: jei reikia, jei pakeista, jei pridėta, jei pašalinta.

Demonas nurodo procedūrą, kuri automatiškai paleidžiama, kai įvykdoma tam tikra sąlyga. Tie. kai atributas sąlyginėje if sakinio dalyje apie demono būseną pakeičia savo reikšmę. Procedūros – demonai aktyvuojami kiekvieną kartą, kai bandoma pridėti arba pašalinti duomenis iš lizdo (numatytasis). Demonai paleidžiami, kai pasiekiamas atitinkamas lizdas. Pavyzdžiui, jei reikia, demonas paleidžiamas, jei jo reikšmė nebuvo nustatyta tuo metu, kai buvo pasiektas lizdas; if-added suveikia, kai į lizdą pakeičiama reikšmė; „if-remote“ paleidžiamas, kai ištrinama lizdo reikšmė. Be to, demonas yra pridedamos procedūros tipas.

7. Pridedama procedūra (procedūra – tarnautojas). Galite naudoti procedūrinio tipo programą, vadinamą lizdo verte kaip pareigūnas(LISP kalba) ir metodas(Smalltalk kalba). Tokiu atveju pridedama procedūra suaktyvinama pranešimu, perduotu iš kito kadro, arba kai tenkinamos sąlygos, kurias vartotojas nurodė kuriant kadrą.

Kai sakome, kad žinių vaizdavimo rėmais modeliai sujungia procedūrines ir deklaratyvias žinias, procedūrinėmis vertybėmis laikome ir pridedamas procedūras. Be to, žinių atvaizdavimo kalba su rėmeliais neturi specialaus išvesties valdymo mechanizmo, todėl vartotojas turi įgyvendinti šį mechanizmą naudodamas pridedamą procedūrą.

Išvestis rėmo sistemoje.

Taikant rėmo metodą, daroma prielaida, kad žinios sistemoje pateikiamos atskirų žinių klasterių arba postruktūrių pavidalu, kuriuose yra informacijos apie stereotipus (t. y. apie kai kurias bendrąsias tam tikros klasės objektų ar situacijų charakteristikas. prie šios prielaidos, suprasti situaciją sistemai reiškia ieškoti sukauptų struktūrų sąraše tokių, kurios geriausiai apibūdintų nagrinėjamą situaciją. Šiuo atveju tarpai užpildomi tam tikra informacija ir tikrinamas užpildytas kadras, ar tam tikra situacija yra tinkama Neatitikimo atveju ieškoma naujo kadro ir procesas tęsiamas.

Taigi galime išskirti tris pagrindinius procesus, vykstančius rėmo sistemose:

1. Sukurkite rėmelio egzempliorių. Norėdami sukurti kadro egzempliorių, turite rasti tinkamą rėmelį ir užpildyti jo vietas informacija, apibūdinančia nagrinėjamos situacijos specifiką. Norint užpildyti lizdus, ​​naudojama speciali informacija, kaip rasti galimus lizdų „užpildžius“. Ši informacija dažnai saugoma procedūrine forma.

2. Rėmelių aktyvinimas. Kai rėmelis laikomas tinkamu konkrečiai situacijai apibūdinti, jį suaktyvina visuotinis procesas. Jei aptinkama per daug skirtumų tarp kadrų turinio ir nagrinėjamos situacijos specifinių bruožų arba jie yra pakankamai rimto pobūdžio, organizuojama kito, tinkamesnio kadro paieška. Tokiu atveju „atmestame“ kadre gali būti nuorodų, kuriuos kadrus reikėtų tirti vietoj šio (pavyzdžiui, bendresnius ar, atvirkščiai, labiau specializuotus). Kai kurie duomenys, naudojami užpildyti „atmesto“ kadro vietas, gali būti naudojami svarstant naujus kandidatus.

3. Išvados organizavimas, susidedantis iš nuoseklios aktyvinimo paieškos rėmelių tinkle, kol randamas tinkamiausias ir jo pagrindu sukuriamas kadrų egzempliorius.

T. Winogradas pasiūlė derinti deklaratyvaus ir procedūrinio vaizdavimo rėmuose privalumus. Jo pasiūlymo esmė yra ta, kad žinios apie tiesioginio jų atvaizdavimo naudojant rėmelius funkcijas būtų saugomos deklaratyviąja forma, o žinios apie kadrų naudojimą – procedūrine forma.

Visų pirma procedūros gali saugoti žinias, kurios leidžia atsakyti į šiuos klausimus:

1. Kada aktyvuoti rėmelį? Kaip ir „demonai“, kadrai gali patys aktyvuotis, jei atpažįstama atitinkama situacija.

3. Kada reikia užpildyti vietas – skambučio metu ar vėliau, pagal poreikį?

Šių funkcijų įgyvendinimas gali būti priskirtas pridedamoms procedūroms. Procedūros taip pat gali įgyvendinti euristiką, skirtą rasti informaciją, reikalingą laiko tarpsniams užpildyti.

Nežinomybė.

Viena iš bendrų sprendimų priėmėjui prieinamos informacijos savybių yra jos netobulumas. Informacija gali būti neišsami, nenuosekli, neapibrėžta, nepatikima, neaiški, atsitiktinė arba įvairios šių aprašymų kombinacijos. Kitaip tariant, informacija dažnai nėra visiškai tinkama problemai išspręsti. Tačiau ekspertas įveikia šiuos trūkumus ir paprastai gali priimti gerus sprendimus ir priimti gerus sprendimus. Išmanusis DSS taip pat turi sugebėti susidoroti su netikrumu ir padaryti pagrįstas išvadas.

Iš esmės nustatomi keturi neaiškių intelektualiųjų DSS žinių šaltiniai: nežinomi duomenys, netiksli kalba, numanomas semantinis turinys ir sunkumai, susiję su skirtingų ekspertų požiūrių derinimu.

Nors netikrumas yra plačiai paplitęs realiame pasaulyje, jo valdymas praktinėse AI sistemose yra gana ribotas.

Neapibrėžtumas yra rimta problema. Bandymai vengti į tai atsižvelgti ir suvokti darbo su juo galimybes negali būti geriausia strategija kuriant išmaniąją DSS.

Todėl būtina tobulinti netikrumo sprendimo būdus.

Išmanieji DSS ir ES turi sugebėti valdyti neapibrėžtumą, nes Bet kurioje realaus pasaulio dalykinėje srityje yra netikslių žinių ir jums reikia susidoroti su neišsamiais, prieštaringais ar net trūkstamais duomenimis. Buvo sukurti įvairūs metodai, padedantys išspręsti intelektualiųjų ir ekspertinių sistemų neapibrėžtumą. Apsvarstysime žinomiausius neapibrėžtumo valdymo metodus: Bajeso tikimybinį samprotavimą ir jo plėtinius, tikrumo teoriją, neaiškią logiką.

Tikimybinė išvada.

Tikimybinis požiūris.

Atsitiktinis (arba tikimybinis) neapibrėžtumas gali būti siejamas su įvykių atsitiktinumu, pavyzdžiui, ekonominėmis situacijomis, objekto sąlygomis, atsitiktinumu įrangos gedimų pobūdžiu ir kitais veiksniais. Kuriant išmaniąją DSS ir organizuojant darbą su žinių bazėmis, daugelio žinių, faktų, įvykių ir duomenų patikimumo lygis skiriasi. Stochastinio neapibrėžtumo sąlygomis samprotavimui formalizuoti naudojama tikimybių teorija ir statiniai sprendimai. Diegiant samprotavimus, atsižvelgiant į neapibrėžtumą, apskaičiuoti tam tikros hipotezės tikimybę sprendimo variantui, galima naudoti Bajeso požiūris.

Panagrinėkime pagrindines Bajeso metodo ir Bayeso taisyklės nuostatas.

Leiskite A yra įvykis tikrovėje, ir IN– kitas įvykis. Tarkime, kad įvykiai A Ir IN nėra vienas kito nepaneigiantys, bet atsiranda sąlygiškai, kai pasireiškia kitas. Tikimybė, kad įvykis Aįvyks, jei įvyks IN, paskambino sąlyginė tikimybė.

Sąlyginė tikimybė matematiškai žymima kaip P(A|B), kurioje vertikali juosta reiškia „įvyko“, o visos tikimybės išraiška aiškinama kaip „sąlyginė tikimybė, kad įvykis įvyks A IN».

p(A|B) =(6.1)

Galimų sąnarių apraiškų skaičius A Ir IN, arba tikimybė, kad A Ir INįvyks kartu, vadinasi bendra tikimybė A Ir IN.

Matematiškai tai atrodo P(AÇB).

Galimų pasireiškimų skaičius IN yra tikimybė IN, P(B), ir tada

(6.2)

Taip pat sąlyginė tikimybė, kad įvyks įvykis IN su sąlyga, kad įvykis įvyko A pasiryžusi

(6.3)

p(BÇA) =p(B|A)´p(A)(6.4)

Taigi, jungties tikimybė yra komutacinė

p(AÇB)= p(BÇ A)

Vadinasi

p(AÇB) =p(B|A)´P(A)(6.5)

Pakeitus (6.5) į (6.2), gaunama tokia lygtis:

(6.6)

p(A|B) A su sąlyga, kad įvykis įvyko IN;

p(B|A)– sąlyginė tikimybė, kad įvyks įvykis IN su sąlyga, kad įvykis įvyko A;

p(A) A;

p(B)- tikimybė, kad įvyks įvykis IN.

Lygtis (6.6) žinoma kaip Bayeso taisyklė (arba formulė), kuri pavadinta Thomo Bayeso, XVIII amžiaus britų matematiko, pasiūliusio šią taisyklę, vardu.

Sąlyginės tikimybės sąvoka siūloma tada, kai manoma, kad įvykis A buvo priklausomas nuo įvykio IN. Šis principas gali būti taikomas tuo atveju, kai įvykis A priklauso nuo tam tikro skaičiaus nesuderinamų įvykių B 1, B 2, ..., B n.

Iš (6.2) galima išvesti šią lygčių rinkinį:

p(AÇB 1) =p(A|B 1)´p(B 1)

p(AÇB 2) =p(A|B 2)´p(B 2)

p(АÇВ n) =p(А|В n)´p(В n)

Arba po susijungimo.

(6.7)

Jei (6.7) sumuojamas per visą pilną įvykių sąrašą B i , gauname

(6.8)

Dėl to susidaro tokia sąlyginės tikimybės lygtis, t.y. P(A) išreikšta bendrosios tikimybės formule:

(6.9)

Jei įvykio apraiška A priklauso tik nuo dviejų vienas kitą paneigiančių įvykių, pavyzdžiui IN Ir NE Į, tada (6.9) atrodys taip:

p(A)=p(A|B)´p(B)+p(A\ØB)´p(ØB) (6.10)

Kur Ø logiška NE.

p(B)=p(B|A)´p(A)+p(B\ØA)´p(ØA) (6.11)

Dabar pakeiskime (6.11) į Bayes formulę (6.6), kuri veda į

(6.12) lygtis suteikia pagrindą naudoti tikimybių teoriją intelektualiųjų sistemų neapibrėžčiai valdyti.

Bajeso išvada.

Naudodami (6.12) lygtį, dabar galime nukreipti savo dėmesį nuo tikimybių teorijos prie intelektualių sistemų. Tarkime, kad visos žinių bazės taisyklės pateikiamos tokia forma:

Jeigu N tiesa

Tada SU tiesa (su tikimybe r}.

Ši taisyklė reiškia, kad jei įvykis Nįvyksta, tada tikimybė, kad įvykis SUįvyks r.

Kas atsitiks, jei įvykis SUįvyko, bet nežinome, ar įvykis įvyko N? Apsvarstykite galimybę apskaičiuoti tikimybę, kad įvykis N taip pat atsitiko.

(6.12) lygtis leidžia tai padaryti. Mes tiesiog naudojame N Ir SU vietoj A Ir IN. Intelektualiose sistemose N paprastai reiškia hipotezes ir SU– įrodymų, patvirtinančių šias hipotezes.

Taigi (6.12) lygtis, išreikšta hipotezėmis ir įrodymais, atrodo taip

p(H) – a priori (besąlyginė) tikimybė kad hipotezė N yra tiesa;

p(C|H)– tikimybė, kad hipotezė N ar tiesa, bus įrodymų rezultatas SU;

p(ØН)- a priori (besąlyginė) tikimybė, kad hipotezė N yra klaidinga;

p(С|ØН)– įrodymų radimo tikimybė SU net kai hipotezė N klaidinga.

(6.13) lygtis rodo, kad hipotezės tikimybė N, p(H) turi būti nustatyta prieš nagrinėjant bet kokius įrodymus.

Išmaniajame DSS, norint išspręsti ekspertų keliamas problemas, reikalingos tikimybės. Ekspertas nustato išankstines galimos hipotezės tikimybes p(H) Ir p(ØН), taip pat stebimų įrodymų sąlygines tikimybes SU, jei hipotezė N tiesa, p(C|H), o jei hipotezė N klaidinga p(С|ØН). Vartotojai pateikia informaciją apie pastebėtus įrodymus, o išmanioji sistema apskaičiuoja p(C|H) už hipotezę N atsižvelgiant į vartotojo pateiktus įrodymus SU. Tikimybė p(C|H) paskambino užpakalinė tikimybė hipotezes N su pastebimais įrodymais SU.

Panagrinėkime situacijas, kai ekspertas, remdamasis paprastais įrodymais SU, negali pasirinkti paprastos hipotezės, o pateikia kelias hipotezes N 1, N 2,…, N t. Arba kai yra daug įrodymų С 1, С 2, …, С n o ekspertas taip pat generuoja daug hipotezių.

(6.13) lygtį galime apibendrinti atsižvelgdami į daugybę hipotezių N 1, N 2, …, N t ir daugybė liudijimų С 1, С 2, …, С n. Tačiau hipotezės, kaip ir įrodymai, turi būti nesuderinami.

Paprastiems įrodymams C ir kelioms hipotezėms N 1, N 2, …, N t taip:

(6.14)

Dėl daugybės įrodymų С 1, С 2, …, С n ir daugybė hipotezių N 1, N 2, …, N t taip:

(6.15)

Taikant (6.15) lygtį reikia gauti visų galimų įrodymų derinių sąlygines tikimybes visoms hipotezėms. Šis reikalavimas užkrauna didžiulę naštą ekspertui ir daro jo užduotį beveik neįmanomą.

Todėl intelektualiosiose DSS ir ES neturėtų būti atsižvelgiama į kelių įrodymų bendros įtakos subtilybes, tačiau turėtų būti leidžiama sąlyginė įvairių įrodymų nepriklausomybė.

Vadinasi, vietoj neįgyvendinamos lygties (6.15) gauname

Norėdami paaiškinti, kaip intelektualioji sistema apskaičiuoja visas užpakalines tikimybes ir galiausiai nustato potencialiai teisingą hipotezę, apsvarstykite paprastą pavyzdį.

Tarkime, kad ekspertas, turintis tris sąlyginai nepriklausomus įrodymus C 1, C 2 Ir C 3, sukuria tris vienas kitą paneigiančias hipotezes N 1, N 2 Ir N 3 ir pateikia išankstines tikimybes šioms hipotezėms – p(H 1), p(H 2) Ir p(H 3) atitinkamai. Taip pat ekspertas nustato kiekvieno pažymėto įrodymo sąlygines tikimybes visoms galimoms hipotezėms.

6.1 lentelėje. parodomos eksperto pateiktos a priori ir sąlyginės tikimybės.

6.1 lentelė.

Priorinės ir sąlyginės tikimybės.

Tarkime, kad pirmiausia stebime įrodymus C 3 . Išmanioji sistema apskaičiuoja visų hipotezių posteriorines tikimybes naudodama (6.14) lygtį:

Taigi

Kaip matyti, ištyrus įrodymus C 3, pasitikėjimas hipoteze H 2 ir tampa lygus pasitikėjimui hipoteze H 1. Pasitikėjimas hipoteze H 3 taip pat didėja ir net apytiksliai pasiekia hipotezių pasitikėjimą H 1 Ir H 2.

Tarkime, dabar stebime įrodymus C 1. Užpakalinės tikimybės apskaičiuojamos naudojant (6.16) lygtį:

Taigi

Hipotezė H 2 dabar laikomas labiausiai tikėtinu, nes pasitikėjimas hipoteze smarkiai sumažėja.

Pamatęs įrodymus C 2„Smart DSS“ taip pat apskaičiuoja paskutines užpakalines tikimybes visoms hipotezėms:

Taigi

Nors pradinis eksperto pasiūlytas reitingas buvo H 1, H 2 ir H 3, tik hipotezės H 1 Ir N 3 liko svarstyti po visų įrodymų ( C 1, C 2 Ir C 3), kurie buvo pastebėti. Hipotezė H 2 dabar gali būti visiškai pašalintas.

Atkreipkite dėmesį, kad hipotezė N 3 dabar laikomas geresniu nei hipotezė H 1.

Naudojant Bajeso logika pagrįstus metodus, iškyla sunkumų gaunant didelį skaičių duomenų, reikalingų sąlyginėms tikimybėms nustatyti.

Praktikoje daroma prielaida apie stebėjimų nepriklausomumą, o tai, matyt, turi įtakos statinio modelio griežtumui. Panašios prielaidos pateikiamos metodu, pagrįstu Bajeso metodu, pasiūlytu.

Duda, Hartas ir Nielsonas pakeitė Bayes formules žinių inžinerijos išvadoms ir pasiūlė išvadų metodą, vadinamą dalyku Bayes.

Pagrindinius šio metodo tikslus jie sėkmingai įgyvendino PROSPECTOR ekspertų sistemoje.

Apytikslis samprotavimas.

Klasikinėje teiginių skaičiavimo teorijoje posakis „Jei A, Tada IN“, kur A Ir IN– teiginių kintamieji (propozicinis kintamasis yra kintamasis sakiniams, kurie nagrinėjami tik jų teisingumo ar klaidingumo požiūriu), parašyti kaip A®B, kur implikacija (®) laikoma jungiamuoju, kurio reikšmę lemia tiesos lentelė.

Taigi А®ВºØАВ (6.17)

Ta prasme, kad A®B(A reiškia B) ir ØАÚВ(ne A ar B) turi identiškas tiesos lenteles. Mūsų atveju svarbiau neaiškus pareiškimas"Jei A, Tada IN“, trumpai A®B, kuriame A(ankstesnis) ir IN(pasekmės) – neaiškios aibės, o ne teiginių kintamieji („proposition“ reiškia sakinį, posakį, teiginį).

Tipiški teiginių pavyzdžiai:

Jei „didelis“, tada „mažas“

Jei „slidus“, tada „pavojingas“;

Tai yra sakinių santrumpos:

Jei x yra „didelis“, tai y yra „mažas“;

Jei kelias yra „slidus“, tada vairavimas yra „pavojingas“.

Iš esmės šio tipo sakiniai apibūdina ryšį tarp dviejų neapibrėžtų kintamųjų. Tai reiškia, kad neapibrėžtas teiginys turėtų būti apibrėžtas kaip neryškus santykis (5.25), o ne kaip jungiamasis (6.17) prasme.

Čia pirmiausia patartina nustatyti Dekarto gaminys du neryškūs rinkiniai.

Leiskite A-neaiškus samprotavimo srities poaibis U ir tegul IN yra neryškus kitos samprotavimo srities poaibis V. Tada Dekarto sandauga A Ir IN, pažymėta А´В, apibrėžiamas taip

(6.18)

Kur U´V reiškia Dekarto aibių sandaugą U Ir V, t.y.

Atkreipkite dėmesį, kad kai A Ir IN– neaiškus, (6.18) paverčiamas įprastu Dekarto aibių sandaugos apibrėžimu.

Kitaip tariant, (6.18) reiškia, kad А´В neaiškus užsakytų porų rinkinys ( u, v), su narystės laipsniu (u, v)Į (A'B), pateikta pagal formulę. Šia prasme А´В yra neaiškus ryšys U Ir V.

6.1 pavyzdys. Leiskite

U=1+2(6.19)

V=1+2+3 (6.20)

A=1/1+0,8/2 (6.21)

B=0,6/1+0,9/2+1/3 (6.22)

A´B=0,6/(1,1)+0,9/(1,2)+1/(1,3)+0,6/(2,1)+0,8/(2,2)+0,8/(2,3) (6.23)

(6.17) apibrėžtą ryšį galima pavaizduoti ryšio matrica

Neaiškios formos teiginio reikšmė „Jei A, Tada IN“ paaiškėja, jei laikysime ypatingu sąlyginio teiginio „Jeigu A, Tada IN, Kitu atveju SU“, kur A, IN Ir SU– neryškūs poaibiai, galbūt skirtingų sričių U Ir V, atitinkamai.

Kalbant apie Dekarto sandaugą, paskutinis sakinys apibrėžiamas taip:

Jeigu A, Tada IN, Kitu atveju SU (6.25)

Kur + reiškia neaiškių aibių sąjungą А´В Ir (ØА´С).

Norėdami apibendrinti materialios implikacijos sąvoką neaiškioms aibėms, tarkime U Ir V– du galbūt skirtingi universalūs rinkiniai ir A, B Ir SU– neryškūs aibių poaibiai U, V Ir V atitinkamai.

Pirmiausia išsiaiškinkime teiginio prasmę

Jeigu A, Tada IN, Kitu atveju SU, tada apibrėžiame

Jeigu A, Tada IN kaip ypatingas teiginio If atvejis A, Tada IN, Kitu atveju SU.

Apibrėžimas. Pareiškimas Jei A, Tada IN, Kitu atveju SU yra dvejetainis neryškus ryšys U´V, apibrėžiamas taip:

Jei A, tada B, kitaip C=A´B+ØA´C (6.26)

Tai yra, jei A, B Ir SU– vienareikšmiai neryškūs santykiai U, V Ir V, tada Jei A, Tada IN, Kitu atveju SU– dvejetainis neryškus ryšys U´V, kuri yra Dekarto produkto sąjunga A Ir IN(žr. (5.23)) ir Dekarto neigimo sandaugą A Ir SU.

Kitas teiginys Jei A, Tada IN gali būti laikomas ypatingu teiginio Jei atveju A, Tada IN, Kitu atveju Su prielaida Ką SU– pilna komplektacija V.

Tai. Jeigu A, Tada IN Jeigu A, Tada IN, Kitu atveju V=А´В+ØА´V(6.27)

Iš esmės tai prilygsta teiginio If aiškinimui A, Tada IN pareiškimas Jei A, Tada IN, Kitu atveju abejingas.

6.2 pavyzdys. Iliustracijos (6.26) ir (6.27)

Tarkime, kad

A = mažas = 1/1+0,4/2

B=didelis=0,4/2+1/3

C=nedidelis=1/1+0,6/2

Tada Jei A, Tada IN, Kitu atveju С=(1/1+0.4/2)´(0.4/2+1/3)+(0.6/2+1/3)´ (1/1+0.6/2)= 0.4/(1.2)+1/ (1.3)+0.6/(2.1)+0.6/(2.2)+0.4/(2.3)+1/ (3.1)+0.6/(3.2)

Ką galima pavaizduoti kaip santykių matricą

Jeigu A, Tada IN, Kitu atveju C=

Taip pat

Jeigu A, Tada В=(1/1+0.4/2)´(0.4/2+1/3)+(0.6/2+1/3)´(1/1+1/2+1/3 ) =0.4/(1.2) )+1/(1.3)+0.6/(2.1)+0.6/(2.2)+0.6/(2.3)+ 1/(3,1)+1/(3,2)+1/(3,3)

Ar lygiavertis

Jeigu A, Tada B=

Išvados neuroniniuose tinkluose.

Hopfield tinklas.

Hopfieldas naudojo energijos funkciją kaip įrankį pasikartojantiems tinklams kurti ir jų dinamikai suprasti. Hopfieldo formalizavimas išaiškino informacijos saugojimo kaip dinamiškai stabilių pritraukėjų principą ir išpopuliarino pasikartojančių tinklų naudojimą asociatyvinei atminčiai ir kombinatorinio optimizavimo problemoms spręsti.

Dinaminis tinklo būsenų keitimas gali būti atliekamas bent dviem būdais: sinchroniniu ir asinchroniniu. Pirmuoju atveju visi elementai keičiami vienu metu kiekviename laiko žingsnyje, antruoju – kiekvienu laiko momentu pasirenkamas ir apdorojamas vienas elementas. Šis elementas gali būti pasirinktas atsitiktinai. Pagrindinė energetinės funkcijos savybė yra ta, kad tinklo būsenų evoliucijos metu pagal lygtį ji mažėja ir pasiekia lokalinį minimumą (traukiklį), kuriame palaiko pastovią energiją.

Asociatyvioji atmintis

Jei tinkle saugomi šablonai yra patrauklūs, jie gali būti naudojami kaip asociatyvioji atmintis. Bet koks pavyzdys, esantis saugomo mėginio traukos zonoje, gali būti naudojamas kaip rodyklė, norint jį atkurti.

Asociacinė atmintis paprastai veikia dviem režimais: saugojimo ir atkūrimo. Saugojimo režime nustatomi jungčių svoriai tinkle, kad pritraukėjai prisimintų rinkinį p n- matmenų pavyzdžiai ( x 1 , x 2 ,..., x p), kurį reikia išsaugoti. Antruoju režimu įvesties pavyzdys naudojamas kaip pradinė tinklo būsena, o tada tinklas vystosi pagal jo dinamiką. Išvesties modelis nustatomas, kai tinklas pasiekia pusiausvyrą.

Kiek pavyzdžių galima išsaugoti internete n dvejetainiai elementai? Kitaip tariant, kokia yra tinklo talpa? Jis yra baigtinis, nes tinklas su n dvejetainiai elementai turi maksimumą 2nįvairių būsenų, ir ne visos jos yra patrauklios. Be to, ne visi pritraukėjai gali saugoti naudingus modelius. Klaidingi pritraukėjai taip pat gali saugoti pavyzdžius, tačiau jie skiriasi nuo mokymo rinkinio pavyzdžių.

Energijos sumažinimas. Hopfield tinklas vystosi energijos mažinimo kryptimi. Tai leidžia išspręsti kombinatorinio optimizavimo problemas, jei jas galima suformuluoti kaip energijos mažinimo problemas. Ypač panašiai galima suformuluoti keliaujančio pardavėjo problemą.

Kai kurie kiti mokymo algoritmai iš 6.3 lentelės yra aprašyti šiuose darbuose: Adaline ir Madaline, tiesinė diskriminacinė analizė, Sammon projekcijos, pagrindinių komponentų analizė.

ANN kūrimo procesas.

Nors ANN procesas yra panašus į tradicinių kompiuterių IC struktūrinio projektavimo metodikas, kai kurie žingsniai yra unikalūs neuroninio tinklo programoms arba turi papildomų veiksnių. Toliau aprašytame procese darome prielaidą, kad preliminarūs sistemos kūrimo žingsniai, tokie kaip informacijos poreikių nustatymas ir galimybių studijos atlikimas, yra visiškai užbaigti. Tokie žingsniai būdingi bet kuriai informacinei sistemai.

Kaip parodyta pav. 6.8., ANN programos kūrimo procesą sudaro devyni etapai.

Įjungta 1 veiksmas Duomenys renkami, kad būtų naudojami mokyti ir išbandyti tinklą.

Svarbu atsižvelgti į tai, kad atliekama užduotis yra prieinama norint gauti ANN sprendimą ir kad yra tinkamų duomenų, kuriuos galima gauti šiam tikslui.

Įjungta 2 veiksmas Turi būti nustatyti mokymo duomenys ir sukurtas tinklo veikimo patikrinimo planas.

Įjungta 3-4 žingsniai Parenkama tinklo architektūra ir mokymo metodas. Specialių ANN kūrimo įrankių prieinamumas gali nustatyti neuroninio tinklo tipą, kurį reikia sukurti. Konkretus neuronų skaičius ir sluoksnių skaičius yra svarbūs aspektai.

Esami neuroninių tinklų modeliai turi parametrus, kurie suderina tinklą iki norimo vykdymo lygio. Dalis 5 veiksmo proceso yra tinklo svorių ir parametrų inicijavimas, kuris taip pat seka vykdymo atsaką. Dažnai pradinės vertės yra svarbios nustatant mokymo efektyvumą ir trukmę. Ši procedūra 6 veiksme konvertuoja naudojamus duomenis į neuroniniam tinklui reikalingą tipą ir formatą. Tai gali reikšti, kad reikia naudoti programas išankstinis gydymas duomenis. Duomenų saugojimas ir manipuliavimas turi būti organizuojamas, kad prireikus būtų patogu ir efektyviai perkvalifikuoti neuroninį tinklą. Be to, naudojamų duomenų pateikimo ir organizavimo būdas dažnai lemia ANN gautų rezultatų efektyvumą ir galbūt tikslumą.

Įjungta 7-8 žingsniai mokymas ir testavimas atliekami kaip intervalinis įvesties ir norimų išėjimų pateikimo į tinklą procesas.

Neuroninis tinklas apskaičiuoja faktinius išėjimus ir koreguoja svorius, kol faktiniai išėjimai atitinka norimą būseną. Norimi išėjimai ir jų ryšiai su įvestimis gaunami iš istorinių duomenų (1 veiksme surinktų duomenų dalis).

Įjungta 9 žingsnis procesą, gaunamas stabilus svorių rinkinys. Dabar tinklas gali atkurti norimus paskelbtų įvesties ir mokymo rinkinio rezultatus. Neuroninis tinklas yra paruoštas naudoti kaip nepriklausoma sistema arba kaip kitos programinės įrangos sistemos dalis.

6.8 pav. Dirbtinio neuroninio tinklo kūrimo ir konfigūravimo proceso seka.

„4 tema: 9 paskaita: Išvadų ir sprendimų paieškos gamybos sistemose metodai. Išvadų metodai, pagrįsti pirmyn ir atgal grandine. Gamybos metu...“

Sakhnyuk P.A.

4 tema:

9 paskaita: Išvadų ir sprendimų paieškos gamybos sistemose metodai.

Išvadų metodai, pagrįsti pirmyn ir atgal grandine.

Gamybos reprezentacijoje žinių sritis pavaizduota rinkiniu

gamybos taisykles ir duomenis reprezentuoja įvairūs faktai apie

JEI TADA,

esamą situaciją.

Išvadų mechanizmas lygina kiekvieną žinių bazėje saugomą taisyklę su faktais,

1 pav. Išvados mechanizmo ciklas degtukų ugnies procedūra

Jei taisyklių dalis suderinama su faktais, sukuriama išvadų grandinė. Išvadų grandinė parodo, kaip ES taiko taisykles išvadai gauti. Norėdami iliustruoti grandine pagrįstą išvadų metodą, apsvarstykite paprastą pavyzdį.

Tarkime, iš pradžių duomenų bazėje yra faktai A, B, C, D ir E, o žinių bazėje yra tik trys taisyklės:

1 taisyklė. Y&D Z 2 taisyklė.

X&B&EY 3 taisyklė. AX Išvesties grandinė pav. 2. parodo, kaip ES taiko taisykles faktui Z išvesti.

Sakhnyuk P.A.

2 pav. Išvesties grandinės pavyzdys.

Pirmiausia paleidžiama 3 taisyklė, kad būtų išvestas naujas paskelbto fakto A faktas X.

Tada įvykdoma 2 taisyklė, siekiant nustatyti faktą Y iš iš pradžių žinomų faktų B ir E, taip pat jau žinomo fakto X. Galiausiai 1 taisyklė taiko iš pradžių žinomą faktą D ir naujai gautą faktą Y, kad būtų padaryta išvada Z.

ES gali atspindėti savo išvadų grandinę, kad paaiškintų, kaip buvo priimtas konkretus sprendimas; tai yra didžioji jos aiškinamųjų galių dalis.

Išvadų variklis turi nuspręsti, kada taisyklės turėtų įsijungti. Yra du pagrindiniai būdai, kuriais taisyklės gali būti įgyvendinamos. Viena vadinama tiesiogine grandine (sąlygiškai daroma išvada), o kita – atvirkštine (tikslinė).

Šiame pavyzdyje naudojama tiesioginė išvesties grandinė.

Gamybos sistemos, kuriose pirmiausiai analizuojama antecedentinė dalis (sąlygos), turi vadinamąją sąlyginę inferencinę architektūrą. Tokios architektūros ekspertinės sistemos pavyzdys yra META-DENDRAL.

Alternatyvus architektūros tipas, gana dažnai naudojamas ekspertinėse sistemose, yra tikslo išvedimo (veiksmo išvedimo arba pasekmių) gamybos sistemos. Pavyzdžiui, A&B&CD formos taisyklė gali būti aiškinama kaip „Loginis A, B ir C junginys reiškia D“ arba „Norint įrodyti D, reikia nustatyti A, B, C“.

Pastaruoju atveju tikslas turi būti pasiektas dedukcine išvada. Tam išnagrinėjamos taisyklių pasekmės, siekiant rasti taisyklę, kuri leistų pasiekti tikslą. Radus tokią taisyklę, patikrinamos visos jos sąlygos.

Jei sąlygos yra teisingos, išėjimas suaktyvinamas. Priešingu atveju tinkamų produktų paieška tęsiasi.

Sakhnyuk P.A.

Pažvelkime į supaprastintą gamybos sistemos su nuoseklia išvadine architektūra pavyzdį. Raidės čia nurodo duomenų bazės elementus ir laikomos teisingomis, jei joje yra.

BD: AF taisyklė 1: A&B&CD 2 taisyklė: D&FG 3 taisyklė: A&JG 4 taisyklė: BC taisyklė 5: FB taisyklė 6: LJ taisyklė 7: GH Tarkime, kad tikslas yra padaryti išvadą apie H tiesą.

Visų pirma patikrinama, ar duomenų bazėje yra H? Kadangi šiuo atveju taip nėra, sistema bando padaryti išvadą apie H tiesą naudodama taisykles, kurių H yra dešinėje. Tai yra 7 taisyklė. Dabar sistema bando daryti išvadą apie G tiesą, nes pastarojo tiesa reiškia H tiesą. Duomenų bazė patikrinama dar kartą: duomenų bazėje nėra G, todėl taisyklės polius, kuriame yra G dešinėje pusėje yra organizuotas. Yra keletas tokių taisyklių (dvi ar trys). Kaip „konfliktų sprendimo“ strategiją manysime, kad taisyklės yra išdėstytos pagal prioritetą, o taisyklė su mažiausiu skaičiumi atitinka aukščiausią prioritetą.

Šiuo atveju pasirenkama 2 taisyklė, todėl tikslas dabar tampa išvesti D ir F tiesą. Tam pakanka parodyti, kad A yra teisinga (kadangi ji yra duomenų bazėje), B yra teisinga (pagal į 5 taisyklę), C yra tiesa (pagal 4 taisyklę). Kadangi D ir F tiesa įrodyta, tai iš 2 taisyklės seka G tiesa, o iš G tiesos seka H tiesa (7 taisyklė). Taigi tikslas pasiektas. Elementai, kurie buvo įrodyta, kad yra teisingi, įtraukiami į duomenų bazę. Šiuo atveju tai yra elementai H, G, D, S.V.

Tikslinės išvados architektūros pavyzdžiai yra MYCIN.

Bendrieji sprendinių paieškos būsenų erdvėje metodai.

Surašymo metodai. Daugelio intelektualiųjų sistemų problemų sprendimą galima apibrėžti kaip paieškos problemą, kai ieškomas sprendimas yra paieškos tikslas, o galimų kelių siekiant tikslo rinkinys reprezentuoja paieškos erdvę (arba būsenos erdvę). Sprendimų paieška erdvėje susideda iš operatorių sekos nustatymo, kurie paverčia pradinę būseną į tikslinę būseną.

Sakhnyuk P.A.

Paieškos būsenų erdvėje problemą bendra forma galima suformuluoti taip:

Tegu pradinė problema apibūdinama trigubu (S, F, T), kur S yra pradinių būsenų aibė; F – operatorių rinkinys, susiejantis vieną būseną su kita; T – tikslinių būsenų rinkinys. Problemos sprendimas yra surasti (fi F), kuri paverčia pradines operatorių f1,f2,…,fk būsenų sekas į galutines. Būsenos erdvės paieškos problema aprašoma naudojant grafų teorijos sąvokas. Nurodoma pradinė viršūnė (pradinė būsena) ir tikslinių viršūnių rinkinys T. Operatoriai, susiję su šiuo lygiu, naudojami nuosekliai nuo medžio šaknies viršūnių, kad būtų sukurtos tolesnių viršūnių. kitas lygis (viršūnės atidarymas). Lankai identifikuojami kaip transformacijos operatoriai.

Gautos sekančios viršūnės patikrinamos, ar jos yra tikslinės. Tada jie pereina į kitą lygį. Terminalo viršūnės yra tos, kuriose negalima taikyti jokių operatorių. Išplėtimas tęsiamas tol, kol pasiekiamas tikslas arba terminalo viršūnė. Būsenos grafo paieška yra grafiko G, kuriame yra tikslinė viršūnė, konstravimo procesas. Šis grafikas vadinamas paieškos grafiku. Skirtumas tarp kelių surašymo metodo įgyvendinimo variantų, kurie skiriasi nurodyta tvarka, kuria viršūnės bus surašytos.

Paieška pagal gylį. Ieškant gylyje, pirmiausia atskleidžiama didžiausio gylio viršūnė. Iš viršūnių, esančių tame pačiame gylyje, viršūnės pasirinkimas atidarymui nustatomas savavališkai. Siekiant apriboti galimybę sekti ne taku, įvedama gylio riba. Ribiniame gylyje esančios viršūnės neatidaromos.

Plotis pirmoji paieška. Viršūnės atsiskleidžia jų generavimo seka.

Paieška atliekama išilgai medžio pločio, nes viršūnės atidarymas vyksta viename lygyje.

Tikslinė viršūnė parenkama iškart po neršto. Pirmiausia ieškant plotyje, galima rasti trumpiausią kelią į tikslinę viršūnę, jei toks kelias yra. Fig. 3 paveiksle pavaizduoti paieškos grafikai, paieškų pagal gylį ir plotį konstrukcija.

Sakhnyuk P.A.

a) b) pav. 3. Paieškos grafikai, sudaryti naudojant paiešką pagal gylį (a) ir paiešką pagal plotį (b) Ieškokite pagal lankų kainą. Daugeliu atvejų lankams priskiriama tam tikra reikšmė, kad būtų galima įvertinti atitinkamos taisyklės naudojimą. Ieškant tikslinės viršūnės, stengiamasi rasti minimalių išlaidų kelią.

Viršūnės atskleidžiamos jų vertės didėjimo tvarka. Kiekvienai viršūnei reikia atsiminti minimalias kelio, nutiesto nuo pradinės viršūnės iki jos, kainą.

Ieškoti su grąžinimu (backtracking). Įgyvendinant tokią paiešką, renkantis taisyklę, nustatomas grįžimo taškas, t.y., jei tolimesnė paieška pasirinkta kryptimi sukelia sunkumų arba yra neperspektyvi, pereinama prie grįžimo taško, praeito ankstyvose paieškos stadijose. . Tada taikoma kita taisyklė ir paieškos procesas tęsiamas. Čia visos nesėkmingos iteracijos, atvedusios į aklavietę, pamirštamos vos pritaikius naują taisyklę, o paieška pereinama kita kryptimi. Šis grįžimo atgal metodas vadinamas chronologiniu atgaliniu keliu. Jis dažnai yra neveiksmingas, nes neprisimena nesėkmingų būsenų ir paieškos žingsnių, sutiktų tam tikru keliu. Daugelis jų vėliau teiks savo paslaugas Sakhnyuk P.A.

neigiamą poveikį įgyvendinant kitus kelius. Tai. daug naudingos informacijos atmetama ir nepanaudojama analizuojant tolimesnes paieškos kryptis.

Būtina išanalizuoti išvados veiksmus, kurie veda į aklavietes ir klaidas.

Norėdami tai padaryti, turite atsiminti pasitraukimo veiksmus. Be to, reikia grįžti ne į grįžimo tašką, esantį prieš duotąją būseną, o į būseną, sukėlusią nesėkmingą paiešką.

Būsenos erdvę vaizduojant grafiko pavidalu sprendimo paieškos metodams būdinga tai, kad jie daugiausia apima kelių taisyklių sekų taikymo rezultatų saugojimą. Dar viena ypatybė yra ta, kad jos veikia bandomuoju režimu, t.y., pasirenkant ir naudojant bet kuriai situacijai taikytiną taisyklę, galima grįžti prie šios situacijos ir taikyti kitą taisyklę. Brute-force metodų pranašumai yra gana paprastas jų įgyvendinimas ir galimybė iš esmės rasti sprendimą, jei toks yra. Tačiau praktikoje paieškos įgyvendinimo procese visada yra laiko ir atminties apribojimų. Didelėms erdvėms ir sudėtingoms problemų grupėms brutalios jėgos metodai yra nepriimtini – kombinatorinio sprogimo realybė. Norint susiaurinti paiešką, reikia informacijos, vadinamos euristika.

Euristinės paieškos metodai. Šiuos paieškos metodus galima naudoti, kai turite tam tikras nykščio taisykles, kurios leidžia sumažinti ieškomų sprendimų parinkčių skaičių. Euristinė informacija yra pagrįsta patirtimi, sveiku protu ir kūrėjo prielaidomis.

Taikant euristinės paieškos metodus, atviros viršūnės paprastai išdėstomos taip, kad paieškos procesas pasklistų perspektyviausiomis kryptimis. Norint nustatyti paieškos kryptį, naudojamas tam tikras matas, apibūdinantis viršūnės perspektyvas arba kelią, kuriame yra ši viršūnė. Šis matas vadinamas vertinimo funkcija f(n). Ši funkcija yra trumpiausio kelio nuo pradinės viršūnės iki tikslinės viršūnės kainos įvertinimas, jei jis eina per viršūnę n. Išplečiant viršūnę arba nustatant kelią, pasirenkama ta viršūnė, kuri turi mažiausią vertinimo funkcijos reikšmę. Vertinimo funkcija turi adekvačiai charakterizuoti paieškos erdvę, t.y. reikia pakankamai daug žinių apie probleminę sritį ir nuodugnią būsenos erdvės analizę. Praktikoje kiekybinių charakteristikų ir svorinių koeficientų naudojimas šioms žinioms atspindėti nėra pagrįstas, nes taikymas neleidžia efektyviai ieškoti sprendimų (gali prireikti didelių skaičiavimų).

Be to, euristinę paiešką naudojant vertinimo funkciją siūlo Sakhnyuk P.A.

patikimas valstybės erdvės išmanymas. Tačiau realioje praktikoje, priimdami sprendimus, jie susiduria su faktais ir žiniomis, kurios nėra pakankamai išsamios ir apibrėžtos.

Be to, paieškos procesą dažnai veikia laiko spaudimas. Tokiomis sąlygomis žmonės naudoja kitus metodus nei formalus matematinis samprotavimas.

Formalus matematinis samprotavimas yra monotoniškas, t.y. kiekviena išvada išplaukia iš ankstesnės. (Monotoniškumas yra kai kurių loginių ir matematinių operacijų (funkcijų) savybė, kuri, paprastai kalbant, susideda iš to, kad galimo operacijų rezultato pokyčio kryptis priklauso tik nuo to, kokios krypties keičiasi šios operacijos. .) Sprendimus priimantys asmenys naudoja nemonotoninius samprotavimus arba sveiko proto samprotavimus (pagrįstus bendromis elementariomis žiniomis).

Nors sveiko proto samprotavimai yra gana įprasti žmonėms, labai sunku pasiekti reikiamą tokių samprotavimų įgyvendinimo lygį dirbtiniu intelektu. (Tačiau kai kuriose klasikinėse ES, tokiose kaip MYCIN, PROSPECTOR, šis metodas gana sėkmingai įgyvendintas siekiant sumažinti paieškos erdvę.

Remiantis sveiku protu, paieškos procedūra grindžiama tam tikromis prielaidomis, nesant šioms prielaidoms prieštaraujančios informacijos.

Prielaidos gali keistis atsiradus papildomos patikslinančios informacijos, t.y. prielaidomis pagrįstose paieškos sistemose būtina peržiūrėti prielaidas apie situacijos pobūdį ir paieškos kryptį, gaunant naujus faktus ir žinias. Taip pat būtina peržiūrėti šių prielaidų pagrindu gautas išvadas. (Derinys su grąžinimo procedūromis) Sumažinimo metodas. Norint išspręsti problemą, reikia rasti reikalingų duomenų rinkinio, sprendžiant sudedamąsias užduotis. Užduotys aprašomos įvairiai: sąrašais, medžiais, masyvais. Apsvarstykime problemos aprašymo formą kaip paiešką būsenos erdvėje. Šiame vaizde antrinės užduotys laikomos ryšių tarp tam tikrų būsenų paieškos erdvėje paieškos problemos. Norint pavaizduoti pradinę problemą kaip papildomų užduočių rinkinį, naudojamas perėjimo prie naujo aprašymo operatorius. Šis operatorius pakeičia pradinę problemą taip, kad išsprendus visas paskesnes problemas, būtų pateiktas pradinės problemos sprendimas.

Kiekvienam pradinės problemos vaizdavimui gali būti tam tikras tokių operatorių rinkinys, kurių kiekvienas sukuria savo papildomų užduočių rinkinį. Kai kurios iš šių papildomų užduočių gali pasirodyti neišsprendžiamos. Kitoms dalinėms užduotims procesas kartojamas, t.y.

jos, savo ruožtu, taip pat redukuojamos į dalines užduotis. Tai tęsiasi tol, kol kiekviena subproblema turi akivaizdų sprendimą.

Sakhnyuk P.A.

Transformacijos procesas taip pat patogiai aprašomas naudojant grafų struktūras.

Pradinės problemos sprendimo su šiuo aprašymu paieškos procesas yra nukreiptas problemos mažinimo grafikas. Šis grafikas vadinamas IR/ARBA grafiku. Šio grafiko viršūnės yra užduočių ir papildomų užduočių aprašymai. IR/ARBA grafike yra dviejų tipų viršūnės. Tipas „I“ – atitinka problemą, kurią galima išspręsti su sąlyga, kad visos jos papildomos užduotys bus įgyvendintos atitinkamose viršūnėse. „ARBA“ tipas – atitinka uždavinį, kurio sprendimą galima gauti išsprendus vieną iš alternatyvių subproblemų atitinkamose sekančiose viršūnėse. Fig. 4. pateikiami IR/ARBA tipo grafikų fragmentai.

b) pav. 4. Pirminės problemos padalijimo į subužduotis vaizdavimas IR/ARBA grafiko pavidalu (a) ir IR/ARBA grafiko transformavimas (b).

Pradinė užduotis S0 suskirstyta į subužduočių grupes. Jį galima išspręsti sprendžiant subproblemas S1 ir S2; arba S3; S4 ir S5. Smailės N, S3, M, S5 yra „I“ tipo viršūnės. Brūkšninė linija rodo pradinės problemos sprendimo grafiko versiją. Daroma prielaida, kad žinomi smulkesnių užduočių S2, S7, S9, S10, S11 sprendimai. Kitų subproblemų sprendimai nežinomi. Papildomos viršūnės paprastai įvedamos į struktūrą taip, kad kiekviena papildomų užduočių rinkinys būtų suformuotas pagal savo pirminę viršūnę.

Sakhnyuk P.A.

IR/ARBA grafiko viršūnė gali būti IR arba ARBA tipo. Todėl pradinis grafikas transformuojamas ir įvedamos papildomos viršūnės N ir M, kurios tarnauja kaip atskiros pirminės viršūnės subproblemiems (S1, S2) ir (S4, S5. Taigi viršūnė S0 transformuojama į ARBA viršūnę).

Redukcijos grafiko įgyvendinimas panašus į sprendimų paieškos grafiko įgyvendinimą būsenų erdvėje. Ypatingu atveju, jei IR viršūnių nėra, gaunamas įprastas būsenos erdvės grafikas. Todėl redukcijos metodas tam tikru mastu yra būsenos erdvės požiūrio apibendrinimas.

IR/ARBA grafiko paieškos procesas susideda iš sprendimų grafiko (arba sprendimų medžio), kuris yra redukcijos grafiko pografas.

Metodai ieškant sprendimų didelėse būsenų erdvėse.

Yra įvairių būdų, kaip organizuoti sprendinių paiešką ir išvedimą didelėse būsenų erdvėse. Tam tikro metodo naudojimas siejamas su būsenos erdvės pobūdžiu, jos struktūrizuotumu, galimybe apibūdinti sprendimo sritį įvairiais abstrakcijos lygiais, gebėjimu įvertinti perspektyvius paieškos kelius ir kitus veiksnius.

Tikra probleminė sritis dažnai pasižymi tokia didele būsenų erdve, kad gali būti labai sunku praktiškai organizuoti paiešką naudojant brutalios jėgos metodus. Tačiau dažnai probleminėje srityje reikia rasti visus įmanomus sprendimus. Tokiais atvejais sprendimas yra naudoti generavimo ir tikrinimo metodą. Šis metodas gali būti naudojamas, jei erdvė yra faktorizuojama, t.y.

galima suskaidyti į gana nepriklausomas poerdes su būdingais nepilnais sprendimais. Būdingas neišsamus sprendimas leidžia spręsti apie visapusiškų sprendimų paieškos šioje poerdėje perspektyvas.

Metodo esmė yra ta, kad generatorius, suderintas su problemine sritis, generuoja daugybę būdingų nepilnų sprendimų, atitinkančių įvairių poerdvių aprašymus. Neužbaigti sprendimai tikrinami naudojant specialias vertinimo procedūras, o jei sprendimas yra nepriimtinas, visa jo sugeneruota tam tikros poerdvės užbaigtų sprendimų klasė yra pašalinama iš tolesnio svarstymo. Ankstyvoje paieškos stadijoje nupjovus tam tikras paieškos šakas negeneruojant ir netikrinus būsenos mazgų, ženkliai sumažėja analizuojamų būsenų skaičius. Jeigu nepilnas sprendimas pripažįstamas perspektyviu, tai jo pagrindu atitinkamoje poerdėje gilesniuose erdvės aprašymo hierarchijos lygiuose kuriami pilni sprendimai ir nustatoma, ar gauti sprendiniai yra tiksliniai.

Sakhnyuk P.A.

Hierarchinė generavimo ir tikrinimo metodo įgyvendinimo procedūra leidžia taikyti variantų atjungimo taisykles ankstyvosiose generavimo stadijose. Naudoti generavimo ir tikrinimo metodą faktorizuotoje erdvėje gali būti sudėtinga dėl to, kad dažnai nėra patikimų metodų būdingiems nepilniems sprendimams įvertinti, t. . Čia neįmanoma su dideliu pasitikėjimu nupjauti neperspektyvių šakų pradiniame paieškos etape. Visada yra rizika neįtraukti dalį būsenos erdvės, kuri atrodo neperspektyvi, bet pakankamai pajėgi pateikti sprendimą tolesniame apdorojime, kai atsiranda papildomos informacijos.

Tokios situacijos būdingos ilgalaikio planavimo ir projektavimo problemoms.

Be to, ne visada reikia ieškoti visų galimų sprendimų, o užtenka turėti kokį nors priimtiną.

Tokiais atvejais sprendimo erdvė yra abstrahuojama. Problemos sprendimas vykdomas skirtinguose abstrakcijos lygiuose, nuosekliai ją išaiškinant šiuose erdvės aprašymo lygiuose. Abstrakcija toliau atskleidžia svarbias problemai būdingas detales. Pagrindinė užduotis sumažinama iki fiksuoto antrinių užduočių aprašymų rinkinio. Paprastais atvejais abstrakčioje erdvėje pakanka vienos skaidinio, naudojamo skirtingoms konkrečios probleminės srities užduotims.

Jei probleminėje srityje yra daug problemų, tai neįmanoma išspręsti visų problemų naudojant tam tikrą paieškos erdvės mažinimo versiją. Pavyzdys yra problema, susijusi su roboto veiksmų planavimu judėti erdvėje ir manipuliuoti objektais. Tokiais atvejais abstrakcija turi atspindėti kintamą veiksmų plano struktūrą.

Galima naudoti nuoseklaus tobulinimo metodą iš viršaus. Šis metodas pasižymi tuo, kad sukuria kiekvienai užduočiai adekvačią abstrakciją. Be to, norėdami supaprastinti problemos sprendimo procesą, jie pirmiausia gauna apibendrintą erdvės aprašymą ir išsprendžia problemą šioje erdvėje, o tada pereina prie konkretesnio erdvės aprašymo. Taigi problemos sprendimas įgyvendinamas iš viršaus į apačią – nuo ​​sprendimo paieškos ir apibrėžimo abstrakčioje erdvėje iki šio sprendimo transformavimo ir jo konkretinimo žemesniuose (t. y. detalesniuose) aprašymo lygiuose.

Perėjimas į konkretesnį lygį atliekamas tik užbaigus sprendimą atitinkamame abstrakcijos lygyje.

Ieškant sprendimų didelėse būsenų erdvėse, taip pat naudojami euristiniai metodai ir procedūros. Dažnai sunku nustatyti grynai euristinį P.A.

procedūra, nes ji gali būti daugiau ar mažiau integruota į bet kurį iš nurodytų metodų. Pavyzdžiui, euristiniai vertinimai yra generavimo ir testavimo metoduose, kai generatorius sukuria hipotezes dėl būdingų neišsamių sprendimų, kurios vėliau tikrinamos. Taikant nuoseklaus tobulinimo iš viršaus metodą, daroma prielaida ir leidžiama, kad problemos sprendimas viršutiniuose abstrakcijos lygiuose leis nurodyti sprendimą detalesniuose problemos aprašymo lygiuose.

Būtinybę formuluoti hipotezes ieškant sprendimų gali lemti daug priežasčių: nesugebėjimas pasirinkti paieškos krypties tam tikrame sprendimo etape diegiant metodą, nepakankamų faktų ir žinių; laiko trūkumas išnagrinėti įvairius sprendimus;

riboti kiti ištekliai. Tokiais atvejais keliama pagrįsta hipotezė dėl tolimesnės kratos krypties, kuri galioja tol, kol, remiantis priimant sprendimą gauta nauja informacija, tampa akivaizdu priešingai. Praktikoje jie stengiasi įgyvendinti samprotavimus remdamiesi sveiko proto prielaida, ty nemonotonišką samprotavimą, o tai yra gana sunku praktinėse AI sistemose, kaip aptarta aukščiau.

Klasifikavimo klaida

Interneto ištekliai

Paskaitos metmenys

Programinės įrangos derinimas

Paskaita Nr.8.

Tambovas 2011 m

Kursas, grupės BIS-11, BIS-12

6 tema. Programinės įrangos derinimas

8 paskaita

Drausmės programavimo technologija

Kryptis 230400 „Informacinės sistemos ir technologijos“

Mokytojas: Mininas Jurijus Viktorovičius

Paskaitos tikslas

Paskaitos tikslas – suteikti supratimą apie programinės įrangos derinimo procesą ir būdus.

1. Klaidų klasifikavimas

2. Programinės įrangos derinimo būdai

3. Papildomos informacijos apie klaidą gavimo būdai ir priemonės

4. Programinės įrangos derinimo technika

Nuorodos

Pagrindinė literatūra

1. Ivanova G.S. Programavimo technologija M.: MSTU leidykla im. N.E. Bauman, 2002. - 320 p.

2. Zhogolevas E.A. Programavimo technologija M.: Mokslinis pasaulis, 2004. - 216 p.

3. Gagarina L.G., Kokoreva E.V., Visnadul B.D. Programinės įrangos kūrimo technologija. M.: Leidykla "FORUM" - INFRA-M, 2008. - 400 p.

Tolesnis skaitymas

1. Kaner S., Folk D., Nguyen E. Programinės įrangos testavimas. M.: DiaSoft, 2001. - 544 p.

2. Braude E. Programinės įrangos kūrimo technologija. Sankt Peterburgas: Petras, 2004. - 655 p.

3. Baranovas S.N., Domaratskis A.N., Lastočkinas N.K., Morozovas V.P. Programinės įrangos produkto kūrimo procesas. M.: FIZMATLIT, Nauka, 2000. - 176 p.

1. www.intuit.ru – Interneto informacinių technologijų universitetas.

2. http://citforum.ru/ - Informacinių technologijų centras.

3. http://www.tstu.ru/r.php?r=education – TSTU elektroninė biblioteka.

4. http://www.edu.ru/ - Federalinio portalo „Rusijos švietimas“ biblioteka

Programos derinimas yra vienas iš sunkiausių programinės įrangos kūrimo etapų, reikalaujantis išsamių žinių:

Naudojamų techninių priemonių valdymo specifika,

Operacinė sistema

Programavimo aplinka ir kalba,

Įgyvendinti procesai,

Įvairių klaidų pobūdis ir specifika,

Derinimo metodai ir susijusi programinė įranga.

Ši paskaita skirta aptarti du paskutinius klausimus.

Derinimas - yra programinės įrangos testavimo metu rastų klaidų lokalizavimo ir taisymo procesas. Lokalizacija yra programos sakinio nustatymo procesas, kurio vykdymas sukėlė įprasto skaičiavimo proceso sutrikimą. Norėdami ištaisyti klaidą, turite ją nustatyti priežastis, t.y. nustatyti teiginį ar fragmentą, kuriame yra klaida. Klaidų priežastys gali būti ir akivaizdžios, ir labai giliai paslėptos.

Apskritai derinimo sunkumus lemia šios priežastys:

Reikalauja, kad programuotojas gerai išmanytų naudojamos techninės įrangos valdymo specifiką, operacinę sistemą, aplinką ir programavimo kalbą, diegiamus procesus, įvairių klaidų pobūdį ir specifiką, derinimo būdus ir atitinkamą programinę įrangą;

Psichologiškai nepatogu, nes reikia ieškoti savo klaidų ir, kaip taisyklė, ribotą laiką;

Gali būti, kad klaidos skirtingose ​​programos dalyse gali sąveikauti, pavyzdžiui, dėl to, kad vieno modulio atminties sritis buvo ištrinta kito dėl adresų klaidų;

Nėra aiškiai apibrėžtų derinimo metodų.

Pagal apdorojimo etapą, kuriame atsiranda klaidų, jos išskiriamos (1 pav.):

- sintaksės klaidos - kompiliatoriaus (vertėjo, interpretatoriaus) užfiksuotos klaidos atliekant sintaksinę ir dalinai semantinę programos analizę;

- išdėstymo klaidos - linkerio (nuorodų rengyklės) aptiktos klaidos derinant programos modulius;

- vykdymo klaidos - klaidos, su kuriomis susiduria operacinė sistema, aparatinė įranga arba vartotojas vykdydamas programą.

1 pav. Klaidų klasifikavimas pagal programos apdorojimo etapus

Sintaksės klaidos. Sintaksės klaidos priskiriamos prie paprasčiausių, nes kalbos sintaksė, kaip taisyklė, yra griežtai formalizuota, o prie klaidų pridedamas išsamus komentaras, nurodantis jos vietą. Nustatyti tokių klaidų priežastis, kaip taisyklė, nėra sunku, o net ir neaiškiai žinant kalbos taisykles, per kelis paleidimus galima pašalinti visas tokio tipo klaidas.

Reikėtų nepamiršti, kad kuo geriau įformintos kalbos sintaksės taisyklės, tuo daugiau klaidų iš bendro skaičiaus kompiliatorius gali aptikti ir, atitinkamai, tuo mažiau klaidų bus aptikta tolesniuose etapuose. Šiuo atžvilgiu jie kalba apie programavimo kalbas su apsaugota sintaksė ir neapsaugota sintaksė. Pirmajam, žinoma, yra Pascal, kuris turi labai paprastą ir aiškiai apibrėžtą sintaksę, kuri puikiai patikrinama kompiliuojant programą, o antrajame – C/C++ su visomis jų modifikacijomis. Ko verta bent jau norint atlikti užduotį sąlyginiu operatoriumi C/C+, pavyzdžiui:

Šiuo atveju tikrinama ne c ir taip lygybė, o atliekama priskyrimas iš reikšmės n, po kurio operacijos rezultatas lyginamas su nuliu Jei programuotojas norėjo atlikti ne priskyrimą, o palyginimą. tada ši klaida bus aptikta tik vykdymo etape, kai bus gauti rezultatai, kurie skiriasi nuo laukiamų.

Išdėstymo klaidos. Išdėstymo klaidos, kaip rodo pavadinimas, yra susijusios su problemomis, aptiktomis sprendžiant išorines nuorodas. Pavyzdžiui, iškviečiamas kito modulio paprogramis, tačiau sujungiant modulius ši paprogramė nerandama arba nesujungiami parametrų sąrašai. Daugeliu atvejų tokio pobūdžio klaidas taip pat galima greitai lokalizuoti ir pašalinti.

Vykdymo laiko klaidos. Labiausiai nenuspėjama grupė apima vykdymo klaidas. Visų pirma, jie gali turėti skirtingą prigimtį ir atitinkamai pasireikšti skirtingai. Kai kurias klaidas aptinka ir dokumentuoja operacinė sistema. Yra keturi būdai, kuriais tokios klaidos gali pasireikšti:

Mašinos komandų vykdymo valdymo grandinių užfiksuoto klaidos pranešimo atsiradimas, pavyzdžiui, bitų tinklelio perpildymas, padalijimas iš nulio, pažeidimo pašalinimas ir pan.;

Pasirodo pranešimas apie operacinės sistemos aptiktą klaidą, pavyzdžiui, atminties apsaugos pažeidimą, bandymą rašyti į apsaugotus nuo rašymo įrenginius, failo nurodytu pavadinimu nebuvimą ir pan.;

- kompiuterio „užšalimas“, tiek paprastas, kai galima užbaigti programą neperkraunant operacinės sistemos, tiek „sunkus“, kai norint tęsti darbą reikia perkrauti;

Gautų ir laukiamų rezultatų neatitikimas.

Atkreipkite dėmesį, kad jei vartotojas aptinka klaidas vykdymo etape, tada pirmaisiais dviem atvejais, gavęs atitinkamą pranešimą, vartotojas, atsižvelgdamas į savo charakterį, poreikio laipsnį ir patirtį dirbant kompiuteriu, bandys suprasti, ką. atsitiko, ieškodamas jo kaltės arba kreipęsis pagalbos, arba bandys daugiau niekada nesusidurti su šiuo produktu. Kai kompiuteris užšąla, vartotojas gali net nesuprasti iš karto, kad kažkas ne taip, nors liūdna patirtis verčia sunerimti kiekvieną kartą, kai kompiuteris greitai nereaguoja į įvestą komandą, tai taip pat patartina nepamiršti. Pavojingos gali būti ir situacijos, kai vartotojas gauna neteisingus rezultatus ir naudoja juos savo darbe.

Vykdymo laiko klaidų priežastys yra labai įvairios, todėl lokalizavimas gali būti labai sudėtingas. Visas galimas klaidų priežastis galima suskirstyti į šias grupes:

Neteisingas šaltinio duomenų apibrėžimas,

Loginės klaidos

Klaidų kaupimasis skaičiavimo rezultatuose (2 pav.).

Klaidingas šaltinio duomenų identifikavimas įvyksta, kai I/O operacijų metu įvyksta kokių nors klaidų: perdavimo klaidos, konvertavimo klaidos, perrašymo klaidos ir duomenų klaidos. Be to, specialių techninių priemonių naudojimas ir klaidų apsaugantis programavimas leidžia aptikti ir užkirsti kelią tik kai kurioms iš šių klaidų.

Loginės klaidos yra skirtingo pobūdžio. Taigi jos gali atsirasti dėl klaidų, padarytų projektuojant, pavyzdžiui, renkantis metodus, kuriant algoritmus ar apibrėžiant klasių struktūrą, arba gali būti tiesiogiai įvedamos modulio kodavimo metu. Paskutinė grupė apima:

Neteisingo kintamųjų naudojimo klaidos, pavyzdžiui, nesėkmingas duomenų tipų pasirinkimas, kintamųjų naudojimas prieš juos inicijuojant, indeksų, kurie peržengia masyvų apibrėžimą, naudojimas, duomenų tipų atitikimo pažeidimai naudojant aiškų arba numanomą duomenų tipo apibrėžimą. atmintyje, kai naudojami netipiniai kintamieji, atvirieji masyvai , jungtys, dinaminė atmintis, adresų aritmetika ir kt.;

Skaičiavimo klaidos, pavyzdžiui, neteisingi nearitmetinių kintamųjų skaičiavimai, neteisingas sveikųjų skaičių aritmetikos naudojimas, neteisingas duomenų tipų konvertavimas atliekant skaičiavimus, klaidos, susijusios su aritmetinių ir loginių išraiškų operacijų prioritetų nežinojimu ir kt.;

Klaidos tarpmodulių sąsajoje, pavyzdžiui, sistemos konvencijų ignoravimas, tipų ir sekos pažeidimas perduodant parametrus, formalių ir faktinių parametrų matavimo vienetų nesilaikymas, vietinių ir globalių kintamųjų apimties pažeidimas;

Kitos kodavimo klaidos, pavyzdžiui, neteisingas programos logikos įgyvendinimas koduojant, ignoruojant konkrečios programavimo kalbos ypatybes ar apribojimus.

Skaitinių skaičiavimų rezultatuose kaupiasi klaidų, pvz., neteisingai atmetus trupmeninius skaičių skaitmenis, neteisingai panaudojus apytikslius skaičiavimo metodus, nepaisant skaitmenų tinklelio apribojimų realiems skaičiams atvaizduoti kompiuteryje ir pan.

Derinimo proceso metu reikia turėti omenyje visas pirmiau nurodytas klaidų priežastis. Be to, derinimo sudėtingumas taip pat padidėja dėl šių veiksnių įtakos:

Netiesioginis klaidų pasireiškimas;

Abipusės klaidų įtakos galimybė;

Galimybė gauti išoriškai identiškas skirtingų klaidų apraiškas;

Kai kurių klaidų apraiškų pakartojamumo trūkumas nuo paleidimo iki paleidimo (stochastinės klaidos);

Galimybė pašalinti išorines klaidų apraiškas tiriamoje situacijoje atliekant kai kuriuos programos pakeitimus, pavyzdžiui, kai į programą įtraukiami diagnostiniai fragmentai, išorinis klaidų pasireiškimas gali būti atšauktas arba pakeistas;

Atskirų programos dalių rašymas skirtingų programuotojų.

Programos derinimas bet kokiu atveju reikalauja mąstymo ir loginio visos turimos informacijos apie klaidą suvokimo. Daugumą klaidų galima aptikti remiantis netiesioginiais įrodymais, nuodugniai išanalizavus programos tekstus ir bandymų rezultatus, negaunant papildomos informacijos. Naudojami įvairūs metodai:

Rankinis testavimas;

Indukcija;

Išskaitymas;

Trackback.

Rankinis testavimo metodas. Tai paprasčiausias ir natūraliausias šios grupės metodas. Jei aptinkama klaida, turite paleisti bandomą programą rankiniu būdu, naudodami testų rinkinį, kurio metu klaida buvo aptikta.

Metodas yra labai efektyvus, tačiau netaikomas didelėms programoms, programoms su sudėtingais skaičiavimais ir tais atvejais, kai klaida atsiranda dėl neteisingo programuotojo supratimo, kaip atlikti tam tikras operacijas.

Šis metodas dažnai naudojamas kaip kitų derinimo metodų dalis.

Indukcinis metodas. Metodas pagrįstas kruopščia klaidų simptomų analize, kuri gali pasirodyti kaip neteisingi skaičiavimo rezultatai arba kaip klaidos pranešimas. Jei kompiuteris tiesiog užšąla, tada pagal paskutinius gautus rezultatus ir vartotojo veiksmus apskaičiuojamas klaidos pasireiškimo fragmentas. Tokiu būdu gauta informacija tvarkoma ir atidžiai išstudijuojama peržiūrint atitinkamą programos fragmentą. Dėl šių veiksmų iškeliamos hipotezės apie klaidas, kurių kiekviena yra patikrinama. Jei hipotezė teisinga, tada informacija apie klaidą yra detalizuojama, priešingu atveju iškeliama kita hipotezė. Derinimo seka naudojant indukcijos metodą parodyta fig. 3 algoritmo diagramos pavidalu.

3 pav. Indukcinio derinimo proceso schema

Svarbiausias etapas yra klaidos simptomų nustatymas. Tvarkant duomenis apie klaidą, patartina užsirašyti viską, kas žinoma apie jos apraiškas, ir fiksuoti tiek situacijas, kai fragmentas su klaida vykdomas įprastai, tiek situacijas, kuriose klaida pasireiškia. Jei ištyrus duomenis hipotezių nekyla, reikia papildomos informacijos apie klaidą. Papildomos informacijos galima gauti, pavyzdžiui, atliekant panašius testus.

Įrodinėjimo procese jie bando išsiaiškinti, ar visos klaidos apraiškos paaiškinamos pateikta hipoteze, jei ne visos, tai arba hipotezė neteisinga, arba yra keletas klaidų.

Išskaičiavimo metodas. Taikant dedukcijos metodą, pirmiausia susidaro įvairios priežastys, galinčios sukelti tokį klaidos pasireiškimą. Tada, išanalizavus priežastis, pašalinamos tos, kurios prieštarauja turimiems duomenims. Jei visos priežastys atmetamos, reikia atlikti papildomą tiriamo fragmento tyrimą. Priešingu atveju jie bando įrodyti labiausiai tikėtiną hipotezę. Jeigu hipotezė paaiškina gautus klaidos simptomus, tai klaida randama, kitu atveju tikrinama kita priežastis (4 pav.).

4 pav. Derinimo proceso schema naudojant dedukcijos metodą

Trackback metodas. Mažoms programoms atgalinis metodas yra veiksmingas. Jie pradeda nuo tos vietos, kur duoda neteisingą rezultatą. Šiuo klausimu sudaroma hipotezė apie pagrindinių kintamųjų vertes, kurios gali padėti gauti esamą rezultatą. Toliau, remiantis šia hipoteze, pateikiami pasiūlymai dėl kintamųjų verčių ankstesniame punkte. Procesas tęsiasi tol, kol bus nustatyta klaidos priežastis.

9 paskaita.Duomenų įvesties/išvesties valdymas

9.1 I/O techninės įrangos principai

Du žemesni I/O valdymo sistemos lygiai yra techninė įranga: patys įrenginiai, kurie tiesiogiai atlieka operacijas, ir jų valdikliai, padedantys organizuoti įrenginių ir likusios skaičiavimo sistemos bendradarbiavimą. Kitas lygis yra I/O įrenginių tvarkyklės , slepiantis nuo operacinės sistemos kūrėjų konkrečių įrenginių veikimo ypatybes ir suteikiantis aiškiai apibrėžtą sąsają tarp aparatinės įrangos ir viršutinio lygio – lygio , kuris savo ruožtu suteikia sąveikos tarp tvarkyklių ir visos skaičiavimo sistemos programinės dalies mechanizmą.

Ryžiai. 1. I/O sistemos struktūra

Kaip bet kurios OS dalis yra specialus posistemis, valdantis įvesties / išvesties įrangą. Pagrindinės užduotys, išspręstos naudojant šį posistemį, yra šios:

- posistemis turėtų suteikti vartotojams patogią ir suprantamą sąsają, leidžiančią pasiekti valdymo pultą tiek vieno vartotojo, tiek kelių vartotojų kompiuterio darbo režimais; kartu dažnai keliamas reikalavimas pasiekti vieningą sąsają prieigai prie skirtingų fizinių charakteristikų valdymo prietaisų, kuriems įgyvendinamas įrenginio nepriklausomumo principas;

- daugiaprogramiame laiko pasidalijimo sistemų veikimo režime posistemis turi užtikrinti tokį duomenų įvesties-išvesties proceso planavimą, kad būtų pasiektas maksimalus centrinio procesoriaus (CPU) ir įvesties-išvesties įrangos veikimo laiko persidengimas.

- Įvesties-išvesties įrenginių ir įvesties-išvesties įrangos OS posistemio sudėtis skirtingiems kompiuteriams labai skiriasi, tačiau galima išskirti vieną konceptualų principą, būdingą visiems posistemiams. Įvesties/išvesties įranga gali būti laikoma aparatūros procesorių, galinčių veikti lygiagrečiai vienas su kitu, taip pat su centriniu procesoriumi, rinkinys. Šie procesoriai vykdo vadinamuosius išorinius procesus. Pavyzdžiui, spausdinimo įrenginiui procesą gali sudaryti veiksmų rinkinys, užtikrinantis vežimo grįžimą, popieriaus judėjimą viena eilute ir bet kokio nurodyto simbolių skaičiaus spausdinimą eilutėje.

Išoriniai procesai sąveikauja su programinės įrangos procesais, kuriuos vykdo CPU ir laisvosios kreipties atmintis (RAM). Svarbu, kad programinės įrangos proceso vykdymo greitis gali būti keliomis eilėmis didesnis nei išorinio proceso greitis.

Įvesties/išvesties valdymo OS posistemis programinės įrangos procesų požiūriu yra sąsaja su valdymo skydeliu. Yra trijų tipų veiksmai su PU:

1. duomenų skaitymo-rašymo operacijos;

2. PU valdymo operacijos;

3. valdymo bloko būklės tikrinimo operacijos.

9.1.1 I/O įrenginiai

Įrenginiai skirstomi į dvi kategorijas (kai kurie jų nepatenka):

• blokuoti įrenginiai - informacija skaitoma ir rašoma blokais, blokai turi savo adresą (diskus)
• simbolių įrenginiai - informacija skaitoma ir įrašoma po simbolio (spausdintuvas, tinklo plokštės, pelės)

9.1.2 Įrenginių valdikliai

Įvesties / išvesties įrenginiai paprastai susideda iš dviejų dalių:

• mechaninis (nereikia suprasti pažodžiui) - diskas, spausdintuvas, monitorius
• elektroninis - valdiklis arba adapteris

Jei sąsaja tarp valdiklio ir įrenginio yra standartizuota (ANSI, IEEE arba ISO), nepriklausomi gamintojai gali gaminti suderinamus valdiklius ir įrenginius. Pavyzdžiui: IDE arba SCSI diskai.

Operacinė sistema dažniausiai susiduria ne su įrenginiu, o su valdikliu. Valdiklis, kaip taisyklė, atlieka paprastas funkcijas, pavyzdžiui, skaitydamas iš disko, bitų srautą paverčia blokais, susidedančiais iš baitų, stebi ir taiso klaidas, tikrinama bloko kontrolinė suma, jei ji atitinka nurodytą sektoriaus antraštėje, tada blokas skaitomas be klaidų, jei ne, skaitomas dar kartą.

9.1.3 Atminties adresų susietas įvestis/išvestis

Kiekvienas valdiklis turi keletą registrų, kurie naudojami palaikyti ryšį su centriniu procesoriumi. Naudodama šiuos registrus, OS valdo (skaito, rašo, įsijungia ir pan.) ir nustato įrenginio būseną (parengtį).

Daugelis įrenginių turi duomenų buferį (pavyzdžiui, vaizdo atmintį).

Prieigos prie valdymo registrų ir buferių įgyvendinimai:

• I/O prievado numeris - kiekvienam valdymo registrui priskiria 8 arba 16 bitų sveikąjį skaičių. RAM ir I/O įrenginių adresų erdvės šioje schemoje nesutampa.
  Trūkumai
  - skaitymui ir rašymui naudojamos specialios komandos, pavyzdžiui, IN ir OUT
  - reikalingas specialus proceso apsaugos mechanizmas
  - pirmiausia turite perskaityti įrenginio registrą į procesoriaus registrą

• atminties adreso erdvės įvestis/išvestis - registrai susieti su atminties adresų erdve.
  Trūkumai
  - kaupiant atmintį talpykloje, įrenginių registrai taip pat gali būti talpinami
  - Visi įrenginiai turi ištirti visas atminties prieigas, kad nustatytų, į kurias iš jų reaguoti. Viename bendrame autobuse tai gali būti lengvai įgyvendinama, tačiau keliuose kils problemų.

• mišrus įgyvendinimas - naudojamas x86 ir Pentium,
  prievadams skiriama nuo 0 iki 64K,
  nuo 640 iki 1M rezervuota duomenų buferiams.

Prieigos prie valdymo registrų ir buferių įgyvendinimo metodai

9.1.4 Tiesioginis prieiga Į atmintis (DMA – tiesioginė prieiga prie atminties)

Tiesioginė prieiga prie atminties įgyvendinama naudojant DMA valdiklis.

Valdiklyje yra keli registrai:

• atminties adresų registras
• baitų skaitiklis
• valdymo registruose gali būti:
  - I/O prievadas
  - skaityti arba rašyti
  - Nešioti vienetus (baitas po baito arba žodis po žodžio)

Be valdiklio nutinka taip:

1. Procesorius nurodo disko valdikliui nuskaityti duomenis į buferį,
2. Duomenys nuskaitomi į buferį, valdiklis patikrina nuskaitytų duomenų kontrolinę sumą (klaidų tikrinimas). Procesorius prieš pertraukimą persijungia į kitas užduotis.
3. Disko valdiklis inicijuoja pertraukimą
4. Operacinė sistema pradeda veikti ir gali nuskaityti duomenis iš buferio į atmintį

DMA valdiklio veikimas

Su valdikliu atsitinka taip:

1. Procesorius programuoja valdiklį (kokius duomenis ir kur reikia perkelti)
2. Procesorius nurodo disko valdikliui nuskaityti duomenis į buferį
3. Duomenys nuskaitomi į buferį, disko valdiklis patikrina nuskaitytų duomenų kontrolinę sumą (procesorius prieš pertraukimą persijungia į kitas užduotis).
4. DMA valdiklis siunčia skaitymo užklausą disko valdikliui
5. Disko valdiklis tiekia duomenis į magistralę, atminties adresas jau yra magistrale, duomenys įrašomi į atmintį
6. Kai įrašymas baigtas, disko valdiklis siunčia patvirtinimą DMA valdikliui
7. DMA valdiklis padidina naudojamą adresą ir sumažina baitų skaitiklio reikšmę
8. Viskas kartojama nuo 4 veiksmo, kol skaitiklio reikšmė tampa nuliu.
9. DMA valdiklis inicijuoja pertraukimą

Operacinei sistemai nereikia kopijuoti duomenų į atmintį, jie jau yra.

9.1.5 Pertraukimai

Įvesties/išvesties įrenginiui pradėjus veikti, procesorius pereina prie kitų užduočių.

Kad signalizuotų procesoriui, kad darbas baigtas, įrenginys inicijuoja pertraukimą, įvesdamas signalą į įrenginio specialiąją magistralės liniją (o ne į tam skirtą laidą).

Pertraukimo valdiklis - aptarnauja įeinančius pertraukimus iš įrenginių.

1. Jei laukiančių pertraukimų nėra, pertraukimas vykdomas nedelsiant.
2. Jei yra neapdorotų pertraukimų, valdiklis pertraukimą ignoruoja. Tačiau įrenginys ir toliau išlaiko pertraukimo signalą magistralėje, kol jis bus apdorotas.

Nutraukti operaciją

Darbo algoritmas:

• Įrenginys nustato pertraukimo signalą
• Pertraukimų valdiklis inicijuoja pertraukimą, nurodydamas įrenginio numerį
• Procesorius pradeda vykdyti pertraukimų apdorojimą, iškviesdamas procedūrą
• Ši procedūra patvirtina pertraukimo gavimą pertraukimo valdikliui.

9.2 Įvesties/išvesties programinės įrangos principai

9.2.1 Įvesties/išvesties programinės įrangos užduotys

Pagrindinės užduotys, kurias turėtų išspręsti įvesties / išvesties programinė įranga:

• Nepriklausomybė nuo įrenginių – pavyzdžiui, programa, nuskaitanti duomenis iš failo, neturi galvoti, iš ko skaito (CD, HDD ir pan.). Visas problemas turi išspręsti OS.
• Vienodas pavadinimų suteikimas – failo arba įrenginio pavadinimas neturi skirtis. (UNIX sistemose tai daroma pažodžiui).
• Klaidų valdymas – klaidas galima užfiksuoti valdiklio, tvarkyklės ir kt.
• Duomenų perdavimas - sinchroninis ir asinchroninis(pastaruoju atveju procesorius pradeda duomenų perdavimą ir pereina prie kitų užduočių, kol nutrūksta).
• Buferis
• Dedikuotų (spausdintuvų) ir nededikuotų (diskinių) įrenginių problema – spausdintuvas turi būti suteiktas tik vienam vartotojui, o diskas – daugeliui. OS turi išspręsti visas iškilusias problemas.

Trys pagrindiniai I/O operacijų atlikimo būdai:

• Programinės įrangos I/O
• Pertraukimu valdoma I/O
• I/O naudojant DMA

Pažvelkime į juos atidžiau.

9.2.2 Programinės įrangos įvestis/išvestis

Šiuo atveju visą darbą atlieka centrinis procesorius.

Pažvelkime į eilutės ABCDEFGH spausdinimo procesą naudojant šį metodą.

Eilutės ABCDEFGH spausdinimo veiksmai

Spausdinimo algoritmas:

1. Spausdinimo eilutė renkama vartotojo erdvėje.
2. Iškviečiant sistemos skambutį, procesas gauna spausdintuvą.
3. Skambinant sistemos iškvietimui, procesas reikalauja, kad eilutė būtų atspausdinta į spausdintuvą.
4. Operacinė sistema nukopijuoja eilutę į masyvą, esantį branduolio režimu.
5. OS nukopijuoja pirmąjį simbolį į spausdintuvo duomenų registrą, kuris yra susietas su atmintimi.
6. Simbolis atspausdintas ant popieriaus.
7. Žymeklis nustatomas į kitą simbolį.
8. Procesorius laukia, kol bus nustatytas spausdintuvo paruoštas bitas.
9. Viskas kartojasi.

Naudojant spausdintuvo buferį, pirmiausia visa eilutė nukopijuojama į buferį, o tada prasideda spausdinimas.

9.2.3 Pertraukimu valdoma įvestis/išvestis

Jei ankstesniame pavyzdyje buferis nenaudojamas, o spausdintuvas spausdina 100 simbolių per sekundę, tada kiekvienas simbolis užtruks 10 ms, per tą laiką procesorius bus neaktyvus ir laukia, kol spausdintuvas bus paruoštas.

Pažvelkime į tą patį pavyzdį, bet su šiek tiek patobulintu.

Spausdinimo algoritmas:

1. Tas pats pasakytina apie 8 punktą.
2. Procesorius nelaukia, kol spausdintuvas bus paruoštas, o iškviečia planuoklį ir persijungia į kitą užduotį. Spausdinimo procesas užblokuotas.
3. Kai spausdintuvas yra paruoštas, jis siunčia pertraukimą procesoriui.
4. Procesorius persijungia į spausdinimo procesą.

9.2.4 I/O naudojant DMA

Ankstesnio metodo trūkumas yra tas, kad pertraukimas įvyksta kiekvieną kartą, kai išspausdinamas simbolis.

Algoritmas nesiskiria, tačiau visą darbą atlieka DMA valdiklis.

9.3 Programinės įrangos lygiai ir I/O funkcijos

Keturi I/O lygiai:

I/O lygiai

9.3.1 Pertraukimų tvarkyklės

Pertraukimus reikėtų paslėpti kuo giliau operacinės sistemos gelmėse, kad su jais susidurtų kuo mažesnė OS dalis. Geriausia užblokuoti tvarkyklę, kuri paleido I/O.

Algoritmas:

1. Vairuotojas pradeda įvesties / išvesties operaciją.
2. Vairuotojas blokuoja save
   - vykdant žemyn procedūrą semafore
   - vykdant laukimo procedūrą būsenos kintamajame
   - vykdydami pranešimo gavimo procedūrą
3. Atsiranda pertraukimas
4. Pertraukimų tvarkytuvas pradeda veikti
5. Pertraukimų tvarkytojas gali atblokuoti tvarkyklę (pavyzdžiui, atlikdamas aukštyn procedūrą semafore)

9.3.2 Įrenginių tvarkyklės

Įrenginio tvarkyklė – reikalinga kiekvienam įrenginiui. Skirtingoms operacinėms sistemoms reikia skirtingų tvarkyklių.

Tvarkyklės turi būti branduolio dalis (monolitinėje sistemoje), kad galėtų pasiekti valdiklio registrus.

Tai viena iš pagrindinių operacinės sistemos strigimo priežasčių. Nes tvarkykles dažniausiai rašo įrenginių gamintojai ir įdeda į OS.

Loginė įrenginių tvarkyklių vieta. Tiesą sakant, duomenų mainai tarp valdiklių ir vairuotojų vyksta per magistralę.

Vairuotojai turi sąveikauti su OS per standartines sąsajas.

Standartinės sąsajos, kurias turi palaikyti tvarkyklės:

• Blokų įrenginiams
• Simbolių įrenginiams

Anksčiau, norėdami įdiegti branduolį, turėjote iš naujo kompiliuoti sistemos branduolius.

Šiais laikais OS dažniausiai įkelia tvarkykles. Kai kurios tvarkyklės gali būti įkeliamos karštai.

Funkcijos, kurias atlieka vairuotojai:

• apdoroti skaitymo ar rašymo užklausas
• įrenginio inicijavimas
• įrenginio energijos valdymas
• įrenginio (skenerio) pašildymas
• įjungiant įrenginį arba užvedant variklį

9.3.3 Nuo įrenginio nepriklausoma įvesties/išvesties programinė įranga

Nuo įrenginio nepriklausomos I/O programinės įrangos funkcijos:

• Vienoda įrenginių tvarkyklių sąsaja,
• Buferis
• Klaidų pranešimai
• Skirtų įrenginių paėmimas ir atleidimas (užrakinimas)
• Nuo įrenginio nepriklausomo bloko dydis

Nuosekli įrenginių tvarkyklių sąsaja

Be sąsajos, joje taip pat yra problemų

• įrenginio pavadinimo
• įrenginio apsauga

Buferis

Pažvelkime į kai kuriuos buferio pavyzdžius.

a) Nebuferinis įėjimas – po kiekvieno įvesto simbolio įvyksta pertraukimas

b) Buferis vartotojo erdvėje – reikiami atminties puslapiai turi būti įkelti į fizinę atmintį.

c) Buferis branduolyje su kopijavimu į vartotojo erdvę – puslapis įkeliamas tik pilnai branduolio buferiui, duomenys iš branduolio buferio į vartotojo buferį nukopijuojami per vieną operaciją. Problema gali kilti, kai branduolio buferis pilnas ir vartotojo buferio puslapis dar neįkeltas.

d) Dvigubas buferis branduolyje – jei vienas buferis yra pilnas ir kol jis yra puslapiuose, simboliai įrašomi į antrąjį buferį.

Klaidų pranešimai

Daugiausia klaidų kyla dėl I/O operacijų, todėl jas reikia nustatyti kuo anksčiau. Klaidos gali būti labai skirtingos, priklausomai nuo įrenginių.

Skirtų įrenginių fiksavimas ir atleidimas

Įrenginiams (spausdintuvui), su kuriais vienu metu turi veikti tik vienas procesas, būtina galimybė įsigyti ir išleisti įrenginius. Kai vienas procesas užima įrenginį, kiti atsiduria eilėje.

Nuo įrenginio nepriklausomo bloko dydis

Bloko dydis turi būti toks pat viršutiniuose lygiuose, o ne priklausyti nuo įrenginių (sektoriaus dydžių diske).

9.4. Vartotojo erdvės I/O programinė įranga

Šios programinės įrangos funkcijos:

• Prieiga prie I/O sistemos skambučių (per bibliotekos procedūras).
• Įvesties / išvesties formatavimas (pakeisti formatą, pavyzdžiui, į ASCII)
• Spooling (skirtiems įrenginiams) – sukuriamas procesas (pavyzdžiui, spausdinimo demonas) ir kaupimo katalogas.

I/O lygių ir funkcijų santrauka

Įvesties/išvesties sistemos lygiai ir pagrindinės funkcijos

Pagrindinė I/O posistemė tarnauja kaip tarpininkas tarp kompiuterinės sistemos procesų ir tvarkyklių rinkinio. Sistemos iškvietimai I/O operacijoms atlikti paverčiami iškvietimais į reikiamos įrenginio tvarkyklės funkcijas. Tačiau pareigos pagrindinė posistemė neapsiriboja vien bendrosios sistemos iškvietimo pavertimo iškvietimu į privataus vairuotojo funkciją veiksmais. Pagrindinė posistemė teikia kompiuterių sistemai tokias paslaugas kaip palaikymas blokavimas, neblokuojantis Ir asinchroninės sistemos skambučiai, buferizavimas Ir talpyklojeįvesties ir išvesties duomenys, spoolavimo ir išskirtinio išorinių įrenginių fiksavimo įgyvendinimas, klaidų apdorojimas ir pertraukia kylančių I/O operacijų metu, planuojant užklausų seką atlikti šias operacijas. Pažvelkime į šias paslaugas atidžiau.

Blokuojantys, neblokuojantys ir asinchroniniai sistemos skambučiai

Visus sistemos iškvietimus, susijusius su I/O operacijų įgyvendinimu, galima suskirstyti į tris grupes pagal proceso ir I/O įrenginio sąveikos įgyvendinimo būdus.

· Pirmoji grupė, labiausiai pažįstama daugumai programuotojų, apima blokuoti sistemos skambučius. Kaip rodo pats pavadinimas, naudojant tokį skambutį blokuojamas jį inicijavęs procesas, t. y. procesą operacinė sistema perkelia iš būsenos egzekucija valstybėje lūkesčius. Atlikus visas sistemos iškvietime nurodytas įvesties / išvesties operacijas, operacinė sistema perkelia procesą iš būsenos. lūkesčius valstybėje pasirengimas. Kai procesas bus pasirinktas dar kartą egzekucija, ten įvyks galutinis sistemos skambučio grąža. Tipiškas tokio sistemos iškvietimo naudojimo atvejis, kai procesui iš įrenginio reikia gauti griežtai apibrėžtą duomenų kiekį, be kurio jis negali atlikti tolesnio darbo.

· Antroji grupė apima neblokuojančių sistemos skambučių. Jų pavadinimas ne visai tiksliai atspindi reikalo esmę. Paprasčiausiu atveju taikytas procesas neblokuojantis skambutis, valstybei neperduodama lūkesčius išvis. Sistemos iškvietimas grįžta iš karto, visiškai, iš dalies arba visiškai įvykdęs jam priskirtas I/O operacijas, priklausomai nuo esamos situacijos (įrenginio būsenos, duomenų prieinamumo ir pan.). Sudėtingesnėse situacijose procesas gali būti blokuojamas, tačiau jo atblokavimo sąlyga yra visų būtinų operacijų atlikimas arba tam tikro laiko pabaiga. Tipiškas pritaikymas gali būti periodinis informacijos gavimo iš klaviatūros patikrinimas atliekant daug darbo reikalaujančius skaičiavimus.

· Trečioji grupė apima asinchroninės sistemos skambučiai. Naudojamas procesas asinchroninis sistemos skambutis, niekada jame nėra užblokuotas. Sistemos iškvietimas inicijuoja reikiamas įvesties/išvesties operacijas ir iškart grįžta, o po to procesas tęsia įprastą veiklą. Vėliau operacinė sistema informuoja procesą, kad įvesties/išvesties operacija buvo baigta, pakeisdama kai kurių kintamųjų reikšmes, išsiųsdama signalą, pranešimą ar kitu būdu. Būtina aiškiai suprasti skirtumą tarp neblokuojantis Ir asinchroniniai skambučiai. Neblokuojantis sistemos skambutis atlikti operaciją skaityti grįš iš karto, bet gali nuskaityti prašomą baitų skaičių, mažesnį skaičių arba iš viso nenuskaityti. Asinchroninis sistemos skambutis nes ši operacija taip pat grįš iš karto, tačiau reikiamas baitų skaičius anksčiau ar vėliau bus perskaitytas pilnai.

Buferis ir talpyklos kaupimas

Pagal buferis paprastai reiškia tam tikrą atminties sritį, skirtą informacijai saugoti, kai keičiamasi duomenimis tarp dviejų įrenginių, dviejų procesų arba proceso ir įrenginio. Keitimasis informacija tarp dviejų procesų priklauso proceso bendradarbiavimo sričiai, o jo organizavimą išsamiai išnagrinėjome atitinkamoje paskaitoje. Čia mus domina buferių naudojimas tuo atveju, kai vienas iš mainų dalyvių yra išorinis įrenginys. Yra trys priežastys, dėl kurių naudojami buferiai .

· Pirmoji priežastis buferizavimas– tai skirtingi mainų dalyvių informacijos priėmimo ir perdavimo greičiai. Apsvarstykite, pavyzdžiui, duomenų srauto perdavimo iš klaviatūros į modemą atvejį. Greitis, kuriuo klaviatūra pateikia informaciją, priklauso nuo žmogaus spausdinimo greičio ir paprastai yra žymiai mažesnis nei modemo duomenų perdavimo greitis. Kad modemas neužimtų viso spausdinimo laiko, nepasiekiamas kitiems procesams ir įrenginiams, patartina įvestą informaciją kaupti buferyje arba keliuose pakankamo dydžio buferiuose ir užpildyti buferius siųsti per modemą. .

· Antra priežastis buferizavimas– tai skirtingi duomenų kiekiai, kuriuos biržos dalyviai gali priimti arba gauti vienu metu. Paimkime kitą pavyzdį. Leiskite modemui pateikti informaciją ir įrašyti ją į standųjį diską. Be skirtingo operacijų greičio, modemas ir standusis diskas yra skirtingų tipų įrenginiai. Modemas yra simbolių įrenginys ir išveda duomenis baitas po baito, kol diskas yra blokuoti įrenginį ir norint atlikti jai rašymo operaciją, buferyje reikia sukaupti reikiamą duomenų bloką. Čia taip pat galima naudoti daugiau nei vieną buferį. Užpildęs pirmąjį buferį, modemas pradeda pildyti antrąjį, tuo pačiu metu įrašydamas pirmąjį į standųjį diską. Kadangi standžiojo disko greitis yra tūkstančius kartų didesnis nei modemo greitis, kai antrasis buferis bus pilnas, pirmojo įrašymo operacija bus baigta ir modemas vėl galės užpildyti pirmąjį buferį. tuo pačiu metu, kai įrašome antrąjį į diską.

· Trečia priežastis buferizavimas yra susijęs su poreikiu nukopijuoti informaciją iš programų, atliekančių I/O į operacinės sistemos branduolio buferį ir atgal. Tarkime, kad koks nors vartotojo procesas norėjo parodyti informaciją iš savo adresų erdvės į išorinį įrenginį. Norėdami tai padaryti, jis turi vykdyti sistemos iškvietimą bendriniu pavadinimu write, kaip parametrus perduodamas atminties srities, kurioje yra duomenys, adresą ir jo dydį. Jei išorinis įrenginys laikinai užimtas, gali būti, kad iki jo išleidimo reikiamos srities turinys bus sugadintas (pavyzdžiui, naudojant asinchroninę sistemos skambučio formą). Norint išvengti tokių situacijų, paprasčiausias būdas sisteminio skambučio pradžioje – nukopijuoti reikiamus duomenis į operacinės sistemos branduolio buferį, kuris nuolat yra RAM atmintyje, ir iš šio buferio išvesti į įrenginį.

Po žodžiu talpykla(pinigai – „pinigai“), kurios etimologijos čia nenagrinėsime, paprastai suprantama kaip greitosios atminties sritis, kurioje yra duomenų kopija, esanti kažkur lėtesnėje atmintyje, skirta paspartinti įrenginio veikimą. skaičiavimo sistema. Su šia sąvoka susidūrėme svarstydami atminties hierarchiją. IN pagrindinė I/O posistemėŠių dviejų sąvokų nereikėtų painioti buferizavimas Ir talpykloje, nors dažnai šioms funkcijoms atlikti skiriama ta pati atminties sritis. Buferyje dažnai yra vienintelis sistemoje esantis duomenų rinkinys, o talpykloje pagal apibrėžimą yra duomenų, esančių kitur, kopija. Pavyzdžiui, buferis, naudojamas pagrindinės posistemės duomenims kopijuoti iš proceso vartotojo vietos į diską, savo ruožtu gali būti naudojamas kaip tų duomenų talpykla, jei bloko modifikavimo ir perskaitymo operacijos atliekamos pakankamai dažnai.

Funkcijos buferizavimas Ir talpykloje neturi būti lokalizuota pagrindinė I/O posistemė. Jie gali būti iš dalies įdiegti tvarkyklėse ir net įrenginių valdikliai, paslaptingas link pagrindinė posistemė.

Spooling ir įrenginio užgrobimas

Apie koncepciją vyniojimas pirmoje savo kurso paskaitoje kalbėjome kaip apie mechanizmą, kuris pirmą kartą leido sujungti realias vienos užduoties I/O operacijas su kitos užduoties vykdymu. Dabar šią sąvoką galime apibrėžti tiksliau. Sakydami ritę turime omenyje buferį, kuriame yra įvesties arba išvesties duomenys į įrenginį, kurio reikėtų vengti tarp skirtingų procesų, susijusių su jo naudojimu. Tiesa, šiuolaikinėse skaičiavimo sistemose spool praktiškai nenaudojamas duomenų įvedimui, o daugiausia skirtas išvesties informacijai kaupti.

Laikykime spausdintuvą išoriniu įrenginiu. Nors spausdintuvas negali spausdinti informacijos, gaunamos iš kelių procesų vienu metu, gali būti pageidautina leisti procesams išvesti į spausdintuvą lygiagrečiai. Norėdami tai padaryti, operacinė sistema, užuot siųsdama informaciją tiesiai į spausdintuvą, kaupia išvesties duomenis disko buferiuose, suskirstytuose į atskirą spool failą kiekvienam procesui. Baigus procesą, atitinkamas ritės failas įtraukiamas į eilę faktiniam spausdinimui. Mechanizmas, užtikrinantis tokius veiksmus, vadinamas sukimu.

Kai kurios operacinės sistemos, užuot naudojusios ritinį, kad pašalintų lenktynių sąlygas, naudoja išskirtinio įrenginių įsigijimo pagal procesus mechanizmą. Jei įrenginys yra nemokamas, vienas iš procesų gali jį išimtinai valdyti. Tokiu atveju visi kiti procesai, bandantys atlikti operacijas šiame įrenginyje, bus blokuojami (perkeliami į lūkesčius), arba gaus informaciją apie negalėjimą atlikti operacijos tol, kol įrenginį užfiksavęs procesas nenutrūks arba operacinei sistemai aiškiai praneš, kad ji atsisako juo naudotis.

Surinkimo ir įrenginio fiksavimo mechanizmo teikimas yra prerogatyva pagrindinis įvesties/išvesties posistemis.

Pertraukimų ir klaidų tvarkymas

Jei dirbdama su išoriniu įrenginiu kompiuterinė sistema nenaudoja savo būsenos apklausos metodo, o naudoja mechanizmą pertraukia, tada kada pertraukia, kaip minėjome anksčiau, procesorius, iš dalies išlaikęs savo būseną, perkelia valdymą į specialią apdorojimo programą pertraukia.

Ta pati apdorojimo procedūra pertraukia gali būti naudojamas keliems I/O įrenginiams (pavyzdžiui, jei šie įrenginiai turi tą pačią liniją pertraukia, einantis iš jų į pertraukimo valdiklis), todėl pirmasis pačios apdorojimo programos veiksmas yra nustatyti, kuris įrenginys išduotas nutraukti. Žinodami įrenginį, galime nustatyti procesą, kuris inicijavo atitinkamą operaciją. Kadangi nutrauktiįvyksta tiek sėkmingo, tiek nesėkmingo vykdymo atveju, kitas dalykas, kurį turime padaryti, tai patikrinti, ar operacija buvo sėkmingai baigta, patikrinus vertę klaidos bitas V statuso registras prietaisai. Kai kuriais atvejais operacinė sistema gali imtis tam tikrų veiksmų, kad kompensuotų įvykusią klaidą. Pavyzdžiui, jei įvyksta diskelio skaitymo klaida, galite pabandyti paleisti komandą kelis kartus. Jei klaidos kompensavimas neįmanomas, operacinė sistema vėliau praneš procesui, pareikalavusiam operacijos (pavyzdžiui, specialiu grąžinimo kodu iš sistemos skambučio). Jei šis procesas buvo užblokuotas prieš užbaigiant operaciją, operacinė sistema jį perkelia į būseną pasirengimas. Jei yra kitų nepatenkintų užklausų į atlaisvintą įrenginį, operacinė sistema gali inicijuoti kitą užklausą, tuo pačiu pranešdama įrenginiui, kad nutraukti apdorotas. Tai iš tikrųjų yra apdorojimas pertraukia baigiasi ir sistema gali pradėti planuoti procesoriaus naudojimą.

Apdorojimo veiksmai pertraukia o kompensacija už atsiradusias klaidas gali būti iš dalies perkelta ant atitinkamo vairuotojo pečių. Norėdami tai padaryti, sąsaja tarp vairuotojas Ir pagrindinis įvesties/išvesties posistemis pridėkite dar vieną funkciją – apdorojimo funkciją pertraukia intr .

Užklausų planavimas

Naudojant neblokuojantis sistemos skambutis Gali pasirodyti, kad norimas įrenginys jau užsiėmęs kai kurių operacijų atlikimu. Šiuo atveju neblokuojantis skambutis gali iš karto grįžti, neįvykdęs prašomų komandų. Organizuojant užklausą atlikti I/O operacijas naudojant blokavimas arba asinchroninis skambutis Jei įrenginys užimtas, tam įrenginiui reikia įrašyti užklausą į eilę. Dėl to kiekvienas įrenginys yra susietas su nepatenkintų užklausų sąrašu iš procesų, kurie yra lūkesčius, o užklausos vykdomos asinchroniškai. valstybė lūkesčius yra padalintas į procesų eilių rinkinį, laukiantį įvairių I/O įrenginių (arba laukiančių įvairių objektų – semaforų, pranešimų eilių, sąlygų kintamųjų monitoriuose ir kt. – būsenų pasikeitimų – žr. 6 paskaitą).

Įvykdžius dabartinę užklausą, operacinė sistema (apdorojant atsirandančią pertraukia) turi nuspręsti, kuris iš sąrašo prašymų tenkintinas toliau, ir inicijuoti jo vykdymą. Lygiai taip pat, kaip norint pasirinkti sekantį procesą vykdyti iš paruoštų sąrašo, reikėjo atlikti trumpalaikį procesų planavimą, taip ir čia reikia planuoti įrenginių panaudojimą, naudojant kažkokį planavimo algoritmą. Tokio planavimo kriterijai ir tikslai mažai skiriasi nuo procesų planavimo kriterijų ir tikslų.

Įrenginio naudojimo planavimo užduotis dažniausiai priskiriama pagrindinis įvesties/išvesties posistemis, tačiau kai kurių įrenginių geriausi planavimo algoritmai gali būti glaudžiai susiję su jų vidinio veikimo detalėmis. Tokiais atvejais planavimo operacija perkeliama į atitinkamą įrenginio tvarkyklę, nes ši informacija yra paslėpta nuo pagrindinės posistemės. Tam į vairuotojo sąsają pridedama dar viena speciali funkcija, kuri parenka kitą užklausą – strategijos funkciją

9. 5 . Principai, kuriais grindžiamas UNIX I/O valdymo posistemis

1. Šis posistemis sukurtas vienodai su duomenų valdymo posistemiu (failų sistema). Vartotojui suteikiamas vieningas prieigos prie vartotojo sąsajos ir failų būdas. Failas UNIX OS yra suprantamas kaip duomenų rinkinys diske, vaizdo terminale ir pan.; bet koks PU laikomas specialiu failu. Kai programinės įrangos procesas prašo išvesti duomenis į specialų failą, OS perima užklausą ir persiunčia duomenis į atitinkamą įrenginį. Duomenų skaitymas iš specialaus failo organizuojamas panašiai – tai duomenų gavimas iš valdymo pulto. Taigi prieigą prie, pavyzdžiui, disko failo ir specialaus ekrano failo suteikia tas pats sistemos iškvietimų rinkinys.

2. Kita UNIX įvesties/išvesties posistemio ypatybė yra ta, kad ji veikia kaip sinchroninė sistema. Bet koks programinės įrangos procesas, kuriam reikia įvesties, sustabdomas toje vietoje, kur ji pateikė užklausą, kol bus baigta įvesties operacija iš nurodyto specialaus failo. Išvedimo metu procesas pristabdomas toje vietoje, kur išvesties prašoma, kol sistema priims išvestį į vartotojo buferį. Toks įvesties-išvesties organizavimas padidina procesoriaus laiko naudojimo efektyvumą kelių programų kompiuterio darbo režimu, nes sumažėja procesoriaus prastovos laikas. Atminkite, kad realaus laiko sistemose (RTS) dažniau naudojamas asinchroninis įvesties-išvesties posistemio veikimo principas, nes tokiu atveju sumažėja RTS reakcijos laikas į įvykius, kuriuos reikia nedelsiant apdoroti.

3. Norint valdyti PU UNIX OS, naudojamos 2 tipų sąsajos su šiais PU: orientuotos į baitus ir į blokus. Į blokus orientuota sąsaja užtikrina ryšį su PU, kurie gali būti adresuojami kaip 512 baitų blokų seka. Tokie PU daugiausia yra VZU. Tokios sąsajos organizavimo pagrindas yra OP palaikoma buferio sistema. Į baitus orientuota sąsaja naudojama pasiekti spausdinimo įrenginį, ekrano klaviatūrą ir kai kuriuos kitus įrenginius ir nenaudoja buferio.

4. Įvesties/išvesties valdymo sistemoje taip pat yra tvarkyklės ir specialių lentelių rinkinys, skirtas loginiam OS branduolio prijungimui prie įvairių įrenginių tvarkyklių. Kiekviena tvarkyklė susideda iš 2 dalių ir gali aptarnauti kelis to paties tipo įrenginius.

Pirmoje tvarkyklės dalyje yra programinės įrangos modulių rinkinys, skirtas specialių failų atidarymo, uždarymo, skaitymo ir rašymo operacijoms atlikti, taip pat specialių valdymo bloko darbo režimų valdymui. Norėdami pradėti dirbti su tam tikru įrenginiu, turite atidaryti arba sukurti specialų failą, susietą su tuo įrenginiu. Failo atidarymas yra susiejimo tarp failo pavadinimo ir kai kurių kintamųjų, saugomų proceso, kuriuo atidaromas failas, atminties srityje, procesas. Šis kintamasis, vadinamas failo deskriptoriaus numeriu, toliau naudojamas atliekant operacijas su atidarytu failu. Atidarius failą, procesui, kuris atliko atidarymą, leidžiama prieiti prie įrenginio. Uždarymo operacija yra priešinga numatytam tikslui ir nutrūksta programinės įrangos proceso ir nurodyto PU ryšiu.

Antroji tvarkyklės dalis yra pertraukimų apdorojimo modulis. Valdant daugumą valdymo blokų UNIX OS, naudojamas pertraukimo metodas. Į baitus orientuotam PU atveju pertraukimas įvyksta po baito perdavimo, į bloką orientuoto PU – po bloko perdavimo. Pertraukimų apdorojimo modulis, kuris yra tvarkyklės dalis, arba nustoja veikti su valdymo bloku, arba toliau dirba su juo, suteikdamas jam naują užduotį.

Kai kurie nurodyti UNIX OS įvesties-išvesties sistemos konstravimo principai buvo įgyvendinti vėliau sukurtose operacinėse sistemose, pavyzdžiui, MS DOS, veikiančiose IBM PC kompiuteryje su 80x86 MP.

Panagrinėkime kitą įvesties-išvesties sistemos kūrimo ypatybę. Kelių programų kompiuterio darbo režime, naudojamame RTOS arba laiko pasidalijimo sistemose, tam pačiam valdymo blokui gali atsirasti užklausų iš skirtingų programų eilė. Norint organizuoti šio valdymo centro gautų paslaugų užklausų nuoseklų vykdymą, OP turi būti sutvarkyta speciali lentelė, kurios turinys nedviprasmiškai rodo gautų užklausų eiliškumą ir turinį kiekvienu laiko momentu; įvykdžius kitą paraišką, duomenys apie ją išbraukiami iš nagrinėjamos lentelės. Tokios lentelės turėtų būti organizuojamos daugumai valdymo blokų, sąveikaujančių su kompiuteriu.