66 informatica 1 YU ISSN 0350-5596 i n f o r m a t i ca Časopis izdaja Slovensko društvo Informatika, 61000 Ljubljana, Parmova 41, Jugoslavija Uredniški odbor: T. Aleksie, Beograd; D.' Bitrakov, Skopje; P. DragojloviC, Rijeka; S. HodZar, Ljubljana; B. Horvat, Maribor; A. Mandzić, Sarajevo; S. Mihalic, Varaždin; S. Turk, Zagreb JOURNAL OF COMPUTING AND INFORMATICS YU ISSN 0350-5596 VOLUME 12, 1988-No. 1 VSEBINA Glavni in odgovorni uredni,k: prof. dr. Anton P., Ze 1 ezn i ka r Tehn i fin i ur edn i k : dr. Rudolf Murn Za 1ozn i S k i s ve t ; T. Banovec, Zavod SR Slovenije za statistiko, Vozarski pot 12, 61000 Ljubljana; A. Jerman-Blazi O, Iskra Telematika, Kardeljeva ploSOad 24, 610Ó0 Ljubljana; B. KlemenOiC, Iskra Telematika, 64000 Kranj; S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, 61000 Ljubljana; J. Virant, Fakulteta za elektrotehniko, TrZaSka .25, 6 1 000 Ljubljana. Uredništvo in uprava: Časopis Informatika, Iskra Delta, Stegne 15Q, 61000 Ljubljana, telefon (061) 574 554; teleks 31366 YU Delta. Letna naroönina za delovne organizacije znaSa 24000 din, zU zasebne naroCnike 600 O din, za Studente 2000 din; posamezna Številka 8000 din. Številka Ziro raCuna: 5 0 10 1-678-51841 Hri financiranju časopisa sodeluje Raziskovalna skupno s t Slovenije Na podlagi mnenja Republiškega komiteja za informiranje St. 23-85, z dne 29. 1. 1986, je časopis oproSOen temeljnega davka od prometa proizvodov. Tisk: Tiskarna Kresija, Ljubljana A.P.Ze1eznikar 3 Uvodno predavanje Z. KaCie B. Horvat S. Greif Z. BrezoCnik B. Horvat P. Kolbezen S. Mavric P. Kolbezen I. Pepelnjak J. Virant . . . M. Bradesko L. Pi pan N. Zimic J. Virant ... T. Ka1 i n T. Vidmar 6 Man-Machine Communication: Speaker-Independent Speech Recogn i t i on 13 Proving the Correctness of Digital Hardware Designs Using Prolog 17 Reconfigurable Mu11 i-Micropro-cessor Systems 25 StohastiCni pristop k analizi učinkovitosti veCprpcesors k i h s i s temov 30 Interna struktura Unix zdruZ-1 j i vega 8-b i tnega OS 40 Sistemski uporabniški vmesnik za 8-bitni Unix zdruzljivi OS 44 48 Logično testiranje protokolov Možnosti zaščite programske opreme na mikroračunalnikih D. Mihajlov-ie 52 M. S i f r a r 55 S. Damjanov i C 5 9 L. DordeviC A. P. Ze1ezn i ka r A. P. Ze 1ezn i kar 65 Određivanje vrste reci iz srp-skohrvatskog jezika primenom racunara Računalniška infrastruktura za delovanje KIS in ZTI VAL realizacija n-tog korena koriščenjem paralelnog iterativnog a 1 gor i tina Lastnosti informacije: mala ene i k 1 oped i j a (A) 77 Potopis Parsys Expeditions to New Worlds II Avtorsko stvarno kazalo Časopisa Informatika 11 (1987) aTii d ČASOPIS ZA TEHNOLOGIJO RAČUNALNIŠTVA IN PROBLEME INFORMATIKE ČASOPIS ZA RAČUNARSKU TEHNOLOGIJU I PROBLEME INFORMATIKE SPISANIE ZA TEHNOLOGIJA NA SMETANJETO I PROBLEMI OD OBLASTA NA INFORMATIKATA I i Published by Informatika, Slovene Society for Informatics, Parmova 41, 61000 Ljubljana, Yugoslavia Ed i tor ia1 Board YU ISSN 0350-5596 LETNIK 12,1988-ŠT.1 T, AleksiC, Beograd; D. Bitrakov, Skopje; P. Drago j lev ić , Rijeka; S. HodZar, Ljubljana; B. Horvat, Maribor; A. Mandzic, Sarajevo; &, Mihallc, Varaždin; S. Turk, Zagreb Editor-in-Chief : Prof. Dr. Anton P. Zeleznikar Executive Editor : Dr. Rudolf Murn Publishing Council: T. Banovec, Zavod SR Slovenije za statistiko, Vozarski pot 12, 61000 Ljubljana; A. Jerman-Blaziö, Iskra Telematika, Kardeljeva ploščad 24, 61000 Ljubljana; B. KlemenCič, Iskra Telematika, 64000 Kranj; S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, 61000 Ljubljana J. Virant, Fakulteta za elektrotehniko, TrZaSka 25, 51000 Ljubljana. Headquarters : Informatica, iskra Delta, Stegne 15B, 61000 Ljubljana, Yugoslavia. Phone: 61 57 45 54. Telex: 31366 yu delta Annual Subscription Rate: USI 30 for companies, and US$ 15 for individuals Opinions expressed in the contributions are not necessarily shared by the Editorial Board A.P CONTENTS Zeleznikar 3 An Introductory Lecture 6 Z. KaCiC B. ikorvat S. Greif I I Z. BrezoCnik B. Ho r v a t P. Kolbezen S. Mavric P. Kolbezen I. Pepelnjak J. Vi rant ... t M. Bradesko L. Pipan N. Žimlc J. Virant .., T. Kalin T. Vidmar Man-Machine Communication: Speaker-Independent Speech Recogn i t i on 13 Proving the Correctness of Digital Hardware Designs. Using Prolog 17 Reconfigurable Mul t i-Micropro-cessor Systems 25 Stochastic Approach in Performance Analysis of Multi... 30 Internal Structure of an 8-bit Unix Cotnpat i bl e OS 40 System Command Line Interface for 8-bit Unix Compatible OS 44 Possibilities of Software Protection In Microcomputers 48 Logical Testing of Protocols D. Mihajlovie 52 M. Sifrar 55 S. DamjanoviO 59 L. Dordev i c Computer Aided Word Type Determination in Serbo-Croatian A Computer Supported Bibliographic System VAL Realization of n-th Root Evaluation Using Parallel Iterative Algor i thm A. Zeleznikar A. P^. Zelezn i kar 65 77 Report of a Journey Properties of Information: A Small Encyclopedia (A) Parsys Expeditions to New Worlds II Printed by: tiskarna Kresija, Ljubljana Authors Subject Index of Informatica 11 (1987) UVODNO PREDAVANJE* INFORMATICA 1/88 UDK 681.3.068 Anton P. Železnikar Iskra Delta, Ljubljana Introductory Lecture. This lecture was given to the students of Computer Science Department within the topic of operating systems and compilers, in Maribor, on October 7, 1987. The aim of the lecture was to evoke the motivation of understanding, of mastering, and of designing of really complex and large program systems as they appear in the framework of operating systems and compilers. Stressing the ' import-ance of software engineering and proficient methodologies, the emphasis to the future disciplines concerning artificial intelligence, parallel computer architectures, parallel processing and parallel prograiming, new informational concepts and methodologies, and newr technological environment (optics, blomolecular circuits, etc.) was given. Snov tega članka Je bilo uvodno predavanje Studentom računalništva v okviru predmetov Operacijski sistemi in Prevajalniki na VTS v Mariboru, 7. oktobra 1987. Kamen predavanja Je bila vzpodbuditev motivacije za razumevanje, obvladovanje in razvoj tako kompleksnih programov, kot se pojavljajo v okviru operacijskih sistemov In prevajalnikov. Poudarjena Je bila pomembnost programirne tehnike in strokovnih metodologij v povezavi s prihodnjimi usmeritvami, ki se tlCeJo umetne inteligence, paralelnih računalniških arhitektur, paralelnega procesiranja in paralelnega programiranja, novih informacijskih konceptov In novega tehnološkega okolja (optika, biomolekularna vezja itd.) "Warum dringt das Verstehen nach allen wesenhaften Dimensionen des in iha Sft schließbaren laner in die Möglichkeiten? Neil das Verstehen an iha selbst die existenzlale Struktur hat, die wir den Entwurf nennen. ... Der Entwurfcharakter des Verstehens besagt ferner, dafi dieses das, woraufhin es entwirft, die Möglichkeiten, selbst nicht theaatisch erfaßt. Solches Erfassen beniaat dea Entworfenen gerade seinen Möglichkeitscharakter, zieht es herab zu einen gegebenen, geaeinten Bestand, w&hrend der Entwurf ia Werfen die Möglichkeit als Mögliohkeit sich vorwirft und als solche sein l&st. Das Verstehen ist, als Entwerfen, die Seinsart des Daseins, in dèr es seine Möglichkeiten als Möglichkeiten ist." ... M. Heidegger, Sein und Zeit, S. 145. 1 Glavni namen tega uvodnega predavanja je vzpodbujanje in nastajanje motivacije za razumevanje, obvladovanje in konstruiranje zares zapletenih in obsežnih programov, kot so operacijski sistemi In prevajalniki. ♦ Predavanje je bilo opravljeno kot uvod v predavanja predmetov "Prevajalniki" In "Operacijski sistemi" na VTS Univerze v IVlariboru, dne 7. oktobra 1987 . Obvladovanje konstruiranja te vrste računalniških programov zahteva razen znanih napotkov in priporočil o dobrem in zanesljivem programiranju, kot so npr. pravila programirne tehnike (strukturiranega programiranja, navzdoljnega in navzgornega razvoja programov, jasne programirne konceptuali zac i J e, uporabe specifičnih programirnih orodij pa tudi vztrajnega, trdega in sistematičnega dela). Se specifične metode oziroma metodologijo operacijskih sistemov in prevajalnikov kot specifičnih strokovnih disciplin. Študentje in Študentke te Studijske smeri boste postali^računalniški poklicanci, profesionalci, nekateri od vas pa specialisti oziroma eksperti npr. za operacijske sisteme in prevajalnike. V prihodnosti se bo današnja strokovna podoba teh predmetov bistveno spreminjala, saj bo potrebno tako v operacijske sisteme kot prevajalnike vgrajevati oziroma v-konstruirati inteligenčne mehanizme, hkrati pa bo potrebno upoštevati tudi povsem nove računalniške arhitekture, ki bodo npr. paralelne, paralelnoserlJske, dinamične, tj. spremenljive in nastajalne in tudi tehnološko radikalno nove (anorganska In organska tehnologija). Torej naj velja na zaCetku tega uvoda pregledno opozorilo, da bo kompleksno programiranje v prihodnosti bistveno sooCeno s probiema t i ko ume t ne inteligenee, paralelnih racuna 1 n i S k i li arhitektur, paralelnega procesiranja in programiranja, novih informacijskih konceptov in metodologij in novega tehnološkega okolja (optika, biosubstrati itd.) V tem trenutku računalniškega razvoja so ' na pohodu paralelni računalniki. DanaSnje obdobje teh računalnikov je Se vedno pionirsko in zanesljivo je le to, da so na pohodu in da je vprašanje njihovega dokončnega prodora predvsem v mnoziCnejSem plasma^ju. Zdi se mi pomembno, da kot študentje dojemate tudi tiste razvojne smeri, ki bodo v razdobju vase strokovne dozo-relosti na svojem visku, da pozorno sprejemate informacijo o strokovnem razvoju, ker je ta ijiformacija bistveno različna, domala nerazumljivo in nesmiselno oddaljena od vsakdanje potrošniške, komercialne in računalniško ideološke informacije. Ta pripomba se nanaSa predvsem tudi na kompleksno programsko opremo novih, paralelnih strojev, ki bo v svoji strukturi veliko bolj ume t no int e 11genCna, kot je današnja programska oprema. Strokovno spremljanje računalniškega razvoja, tehnologije in metodologij naj postane tudi vasa lastna intelektualna funkcija, ki izvira iz lastne volje, prepričanja in delavnosti strokovnjaka. Uspehi domaČe računalniške industrije bi lahko bili bistveno vecji. Ce bi v preteklem obdobju v domaČi industriji delovali ti. računalniški intelektualci. Tudi za strokovnjaka je pomembno vprašanje: Kdo je intelektualec? Intelektualec Se ni nekdo, ki Je končal najvišje sole, prebral gore knjig, prejel najvišje nagrade in priznanja, ali tisti, ki ga je konformno okolje razbobnalo za Izvirnega strokovnjaka, ki uspeSno opravlja intelektualni poklic ali upognjen prodaja svoje ideje. Intelektualec ni produkt povprečnega socialnega okolja, temveč ima svoj umni in razumni sistem mišljenja, prepričanja in vedenja neglede na socialni izvor, formalno izobrazbo in mesto v družbeni hierarhiji, interes intelektualne, volje Je, da svet spoznava in osmislja, v njem ustvarjalno deluje, ne pa da ga drži v svoji oblasti in ga izkorišča za svoje ozke potrebe. Računalniški strokovnjak se ne more uveljavljati zgolj s kompentenco, strokovnostjo in ekspertizo, temveč mora znati in si upati z argumenti posegati tudi v tehnološko in poslovno strategijo računalniškega podjetja. Preprosto zaradi tega, ker strokovnost poslovodnih in vodilnih delavcev največkrat bistveno zaostaja za potrebami in zahtevami strokovnega in uspešnega vodenja računalniškega podjetja. Ta drZa (predispozicija) računalniškega strokovnjaka pa zahteva določeno stopnjo intelektualnega asketizma, na katerem temelji v pretcZni meri tehnološka in poslovna uspešnost podjetja v civilno razvitem svetu. V razdobju trajajoče krize je poziv k pozitivnemu intelektualnemu asketizmu nujen, imperativen; kot pridobljena Zivljenska filozofija in delovna navada pa naj bi se prenašal na mlajše rodove in vam ostal osmišljen tudi do konca Življenja. Spominjam se, da sem zacel prevajalnike bržkone pre'davati v solskem letu 1 972/73 na Fakulteti za plektrotehniko v Ljubljani, takoj po svetovnem; kongresu IFIP (International Federation for Infjormation Processing) leta 1971 v Ljubljani. Takiratnl pokongresni cas je bil naklonjen stro-■ kovlnim vsebinskim inovacijam na fakulteti. Z nez'nansko teZavo sem se tedaj lotil pisanja ucb'enika za prevajalnike z metodološko naslo-nitivijo na tedaj strokovno najbolj priznano dello D. Oriesa: Compiler Construction for Digi-tall Computers, J. Wiley, 1971. V okviru podiplomskega studija sem v tedanjem razdobju predaval teorijo formalnih jezikov, ki se je uk-variJala s problematiko formalizacije oziroma avtomatizacije prevajanja. To kar je v tedanjem in tudi v kasnejšem obdobju bilo problematično tako za mene kot za studente. Je bilo pomanjkanje realnih, industrijskih zahtev za izdelavo prevajalnikov. Posledica tega so bile "teoreti-Cnej" vaje, ki jim je manjkala poanta realne nujnosti. Manjkala so tudi bistvena programima oroljja, ki olajšujejo in dandanašnji že domala avtomatizirajo pisanje oziroma programiranje slehernega pre va J a 1 n ll has been achieved. Keywords. Speech recognition, independent speaker, recognition base element, set of features, set of maps, recognition accuracy, feature description, feature overlapping. i 1. Introduction In spite of fast develqpment of computer tecnology, digital signal processing theory, phonetics , linguistics and artiffical intelligence, solution of the problem regarding man - machine communication on the basis of speaker-independent speech recognition, remains entirely the job of the feature. To solve this problem a very good knowledge of all above mentioned fields shall be required . Nowadays commercial speech recognition systems recognize successfully a large vocabulary of words only in the case of isolated word recognition and are mostly dependent on speaker ClOD. In systems which recognize connected speech or even continuous speech the vocabulary of words is much smaller. A special recogni z e si gnal. problem represent systems the speaker-independent which speech In systems which recognize isolated words the extent ' of vocabulary decreases already ( on about 40 words "). Of course, the same recognition accuracy as in the speaker-dependent systems shall be required. Today the speaker-independent continuous speech recognition systems exist as prototypes only and their vocabulary is not greater than 10 words ClOl. The 'complexity', and first of all the great 'heterogeneity' of speakei—independent speech signal represent one of the major obstacles for solving this problem more successfuly. 1 The! speech signal can be recognized on the basis of the so called recognition base elements ( words , syllables, phonemes etc.). This paper describes some problems which appear in the process of speaker-independent speech recognition on the basis of phoneme recognition, and indicates the ways of their solution . 'Features overlapping' of different recognition base elements (i.e. when features were described by feature extraction methods and presented in n-dimensional space ) and great dispersion of features of same base element ( i.'e. when spoken by an independent speaker) represent a great problem in the speaker independent speech recognition process. Features overlapping mostly means recognition error when the classification is made. Speech signal character istics can be described by \Jarious features extraction methods CI ,3,6, 7]. I I Dif-ferences in speech signal features of the same recognition base element ( for an independent speaker) are due to speaker's age, sex t , psychophysical condition , etc [1,2,61. Different feature extraction methods describe speech features in different ways.Consequent 1y, the rate of features overlapping is different and depends upon the method which has been used. To achieve high recognition accuracy of recognition base elements , the features overlapping of different base elements should be as small as possible. So the proper selection ( definition ) of a feature extraction method for particular groups of recognition base elements is an important condition for a good recognition accuracy. In the next sections the feature extraction process of recognition base elements with definition of some mapping rules and features sets shall be described and the basic notion with dismembers of two feature extraction methods - zero - crossing method ( variant a and b) and method of formant frequencies energy classes ( variant a and b ) shall be presented. b) Set of all descriptive features - D D=-CD' ,D=>, ... , ... >, D' - the set of descriptive features described by the i-th description ..... (61 D'r, - the set of descriptive features of the n-th recognition base element described by the i-th description D± m ri 1 (7) D""r. - the set of descriptive features of the m-th articulation of the j-th recognition base element = ... ... D"-r.L.>, (8) 2. Description of recognition base element features We shall try to describe feature extraction process by means of three sets of speech signal features and three sets of map. The three sets of features are : the set of all descriptive features, the set of all selected features and the set of all characteristic features. Each of the sets should be mapped with the following mapping sets : the set of descriptive features maps, the set of selected features maps and the set of characteristic features maps. Such distribution of speech signal features has been assumed to estimate the convinience of a single feature extraction method which shall be used in the feature extraction process. L - the number of windows of the m-th articulation of the j-th recognition base element D"",,! - the set of descriptive features of the 1-th window of the m-th articulation of the n-th recognition base element I .... ... d'"'^!«}, (9) K - the number of descriptive features c) Set of all selected features - S . S={S',S=', ... ... >, (10) S-"- the set of selected features defined by the j-th description Analytic evaluation of the importance of a single feature description and with it a definition of 'optimum' description might also be possible. Let us describe now briefly single sets of features and the sets of maps. A> Sets of features a) Set of the recognition base elements articulation - Jf . ={Ai,A2, ... Ar,, ... AM>, (1) N - the number of different recognition base elements (2) Ar,m -the m-th articulation of the n-th recognition base element S-' = , (11) N - the number of different recognition base elements SJ^ - the set of selected features of the n-th recognition base element defined by the j-th description (12) - the p-th selected feature of the n-th recognition base element defined by the j-th description S-'„„ = , (4) U - the number of elements in the 1-th window d) Set of all characteristic features - C C=, (14) C" - the set of characteristic features defined the u-th description (15) N - the number of different recognition base elements C"r. - the characteristic -feature of the n-th recognition base element defined by u-th descr i pt i on C"„=i. are defined as: (25) Bc=, (21 ) (22) The map g^.^ : D' • C" is surjective. The map is mapping the set of descriptive features D* into the set of characteristic features C" so that the set of all intersection of the elements of set C" is an empty set. wher -d(tj,Tj»,) is the number of intervals in the time class (Tj,Tj*i> Value of P is defined by P= iE d(Tj), J —o 1 (26) The set of all intersections of the elements of selected features set - S-> is not an empty set. That means, that the elements of characteristic features set C" are disjunctive sets . This is not valid for the elements of selected features set S-". If- fDi:J» -► D' and go^rD'- then we may compose foi and a map foi® g<=.^!Jt -► C". ♦ C" are maps, gcij to obtain We shall define such maps , which are mapping the set of recognition base elements articulation into the set of characteristic features. K. is the number of all intervals . The subset of selected features set S^o is composed of elements which represent portion of interj-vals lenght in particular time classes. ... S* nt b (ZCb) (27) Secondly , elements of the selected features set are defined as follows: s'-r,^ (tj , )=- n ( Tj , X j » . > . < Xj + tj ^ . ) /2 W. ( Tj ^ , -1J ) (2B) where is the number o-f intervals in the time class W is the window width Xj, Tj^i are the boundary values a-f the j-th time class. By means o-f -factors iXi /2 and Ctj^i- Tj ) a better evaluation o-f high and low -frequency components should be achieved. C29) b. Method of formant -frequencies energy classes (FFEC) Like the zero-crossing method this method knows various variants as well. ftll variants use the discrete Fourier transf ormation as the mapping rule o-f the descriptive -features C6,9] ; G exp (-j2ltsu/U) ^—o (30) The subset of the descriptive -features set D-""r, is composed of frequency samples. ... <3l> Variant a (FFECa) To define elements of the selected features set the following prescription has been used; where K R m 1 "f m-*- t = ( Z log G^=»(u))/( Z log (u> > j u=f„/R« r=i,2, . ,R (32) is the u-th element in descriptive features set D-""r>i is the m - th element in selected features set S^-r.^ is the resolution factor of DFT is the number of all elements in the descriptive features set D-^^r,! is the number of elements in the selected features set are the boundary values of the m-th formant frequencies class The subset of the selected features set S^r,^ is composed of elements , which represent a portion of maximum frequency components in a single formant frequencies class. (35) Out of it arises a question how efficiency , or better 'convenience' of a single map should be estimated in order to be used in the base element recognition process . For this purpose , the recognition results obtained by the dismembered feature extraction methods mentioned above , will be presented in the next sections. 4. Experimental results of isolated Slovene vowels recognition The recognition of the five isolated Slovene vowels ( /a/,/e/,/i/,/o/ and /u/ ) was carried out by the recognition experiment. One hundred and ten articulations of each vowel, pronounced by 110 different speakers, has been performed. All articulations were recorded in an studio environment. Speakers were of different age categories. Female - male rate was 3/7. The speech signal was passed through a band-pass filter (600 Hz - 3.4kHz) and sampled at 10k Hr with a 12 bit A/D converter. , The time window width (W) was limited to 20 ms. Because of such a great amount of different speakers we might presume that the recognition results (see Table 1 ) are the recognition results of an independent speaker. Elements of the selected features set ( for a single method ) were combined into the feature vector and the number o-f vector elements was 1imited to ten ; Z„„ = Cz(1),z(2) , Classification was multivariate normal covariances 172. ,z(10)3, (36) made on the bassi s of distributions with equal Recognition results for single methods are given in the Table la-b. The selected feature set S",,« is composed of elements , which represent parts of common energy in particular formant frequencies classes. ... s^op«}, (33) Variant b (FFECb) This variant defines elements of the selected features set as follows: M s^r,^(j)=log Z log (34) ns— 1 where is the maximum frequency component in j-th formant frequencies class M is the number of maximum components of all classes and the number of elements in the selected features set Zero - Crossing Method variant a variant b recognized as |>) « E I 0 U A E I 0 U k 56.« 1.0 0.0 1.8 0.0 97.3 0.9 0.0 1.8 0.0 E o.o 71.8 13.7 5.5 9.0 0.9 78.2 10.0 7.3 3.6 I 0.0 5." 90.9 0.0 3.7 0.0 3.7 91.5 0.0 1.8 0 6.1) 2U.5 0.9 62.7 5.5 7.3 22.7 0.0 63.6 6.1 U 1.9 11.8 11.6 10.9 63.6 2.7 11.8 17.3 10.9 57.3 Method or Fo.-oant Frequencies Energy Classes variant a variant b recoitniied as | [»1 * E I 0 U A E I 0 U A 33.6 1.8 0.0 8.2 6.« 97.3 0.0 0.0 2.7 0.( E 6.3 70.0 16.« 2.7 4.6 0.0 92.8 5.« 0.9 ■ 0.9 I 3.6 V6.6 69.0 3.6 7.2 O.O «.5 92.8 0.0 2.7 0 13.8 "•5 1.8 58.1 21.8 1.8 0.0 0.0 92.8 5.« U 5.5 7.2 1.8 10.1 75.« 0.0 0.9 0.0 10.0 89.1 Table la-b: Experimental results of isolated Slovene vowels recognition ■five 5. Efficiency of feature extraction methods We shall now try to estimate efficiency of single maps, or better, their 'convenience' -for the use in the base elements recognition process on the basis of recognition results. By using map rules in the zero-crossing method ( variant a > a somehow better recognition accuracy was achieved only for the vowel /a/ ( 96.4X ) - less for the vowel /i/. For the vowels /e/ , /o/ and /u/ a rather worse recognition accuracy was achieved. The variant b of . the zero-crossing method showed a little bit better recognition results, but the rate of vowels recognition error was rather the same as at the variant a. The reason for a worse recognition accuracy when zero-crossing method was applied , should be searched in the usage of the map of descriptive features. In this method ( for both variants ) the measurement of intervals lenght as mapping rule for mapping the descriptive features was used. Anyhow, this 'function' is 'incapable' to 'ignore' phase changes between particular frequency components in a signal. In other words •f uncti on. it is a phase dependent Human ear is insensitive to phase changes in a speech signal C4], whereas this is not true for the 'simple' measurements of intervals lenght. Two signals with equal frequency components and with different phases sound the same. However, they can be formed in very different subsets of descriptive features , if the rule of the measuring interval lenght between the two successive zero-crossings of the signal was used as the mapping rule. This is of great importance for phase changes at low frequencies (first two formants), which have ussualy the greatest amplitude and as such a greater influence on the zero-crossing rate. Figlia t-ne rirst three elements of the feature vector formed by the zero-crossing method (variant a) and the method of formant frequencies energy classes (variant b) for vowel /e/. They in the frequency the last three vector for all all articulations of the 'describe' low frequencies spectrum. Fig. lb represents elements of the feature articulations of the vowel /e/ , for the both methods. They describe high frequencies in the frequency spectrum. It could be noticed, that the dispersion of the first three elements of the feature vector •formed by the ZCa method (marked by •*■) , is much greather than the dispersion of the feature vect'or elements formed by the FFECb method (they are labeled as . > . ZC» FFECb ZCi FFEa Fig.|la-b : Distribution of the first three a) and the last three b) elements of the feature vector, for vowel FFECb (.) methods. /e/, formed by ZCa C^) and ft rather smaller dispersion could be ^ th^ last three elements o-f the feature vector ■formed by the ZCa method. . in the both cases the dispersion of feature vectors elements formed by the FFECb is very similar. From the above mentioned the importance o-f the Tact of phase changes between single exponents in the frequency spectrum be not^ed - first of all . for low frequences being present in'. a speech signal of an independent speaker. This fact also indicates the recognition results of the voxels /o/ and /u/, ^f ftrst of all the first formant is dominant. From the Fig. 2a it can be also seen, that features description of elements «ith measurement of interval as mapping rule of descriptive features was less successful as with Fourier transformation This should be evident from the ^isp^rsion rate of single feature vector elements , which is greater than the one for the other two Lthods. This is particulary ^''tJZaturl second and the third element . vector (they first of all describe the first formant). Comparision of recognition for variants FFECa and FFECb ( see Table lb Ì and considerations of dispersion rates of vector elements for both variants (Fig. 2 b - ^^^ indication of the fact that common normalized energy of single formant frequencies classes calculated by this variant was a 'worser criteria' than the ratio of normalized energy of maximum components was. This might point out that the common energy contents per single formant frequencies classes for some recognition element change with an independent speaker. It was reflected as an increase of dispersion for almost all elements of the feature vector ( Fig. 2b ). This means a worse recognition accuracy ( Table lb ). 'FFECa method' .025 .05 .075 .1 .125 .15 .175 . 2 . 2 2 5 . 25 ■ 2n Ž ? 'FFECb method' r ■5' 0 . 025 ,05 . 075 .1 .125 .15 .175 .2 .225 .25 Zn Fig. 2a-c : Histograms of the feature elements , for vowel /e/, formed by FFECa b> and FFECb c) methods. . vector ZCa a), '2Ca method' A better recognition accuracy and the smallest features vector elements dispersion was achieved when the mapping rule of method FFECb was used. The mapping rule,of the selected features for this variant 'enables selection' of frequency components. In each class only the maximum component was choosen. In this way only energy of the maximum component for a particular class was described. But because of the fact that ten formant frequencies classes were defined, they are not all maximum frequency components of formants. With this variant the best average recognition accuracy was achieved greater than 92.5 *. 6. Conclusion By the speakei—independent speech recognition such -features maps should be defined that 'di-f-ferences' in speech features, appearing in the case of an Independent speaker shall be expressed as small as possible. That means that such functions should be de-fined where features overlapping was as small as possible. This should be valid for maps of descriptive features < e.g. measurement of intervals lenght - discrete Fourier transformation ) and for maps of selected features ( e.g. variant a - variant b of FFEC method > as well. The mapping rules discussed in our paper showed that the discrete Fourier transformation as the mapping rule for the descriptive features maps and the variant b of the FFEC method as the mapping rule for the selected features maps gave the best recognition results. With above mentioned methods the smallest features overlapping and consequently the best average recognition accuracy has been achieved - i. e. more than 92.S X . References Cn L.R. Rabiner and R. W. Schäfer , Digital Processing of Speech Signals, Prentice --Hall , Englewood Cliffs , NJ , 1978. C23 A. H. Seidman and I. Flores , Handbook of Computers and Computing , Van Nostrand Reinhold Company , New York , 1984. C3] R. De Mori and C.Y. Suen , New Systems and Arhitectures for Automatic Seech Reeogni t ion and Synthesis , Springer — Verlang, Berln, 1985, Chap. 1, pp. 1 - 72 . C4D James C. Anderson , "Improved zero-crossing method enhances digital speech " , EDN Magazine , vol. 27, No. 20 , october 13 1982 , pp. 171 - 174 . C53 R.J. Niederjohn and P.F. Castelaz, "Zero -crossing analysis methods and their use for automatic speech • recognition " ,Proc. IEEE Computer Society Workshop on Pattern Recognition and Artifical Intelligence, 1978 , pp. 274 - 281 . [63 F. Fallside and W.A. Woods, Computer speech processing , Prentice - Hall , Englewood Cliffs , NJ , 1985 C7D J. C. Simon, Spoken Language Generation and Understanding,D. Reidel Publishing Company, 19B0 , pp. 129 - 145 ^ Caa R.J. Senter,Analysis of Data, Scot,Foresman , and Company,111inois , 1969 . C93 I. H. Witten, "Digital storage and analysis of speech". Wireless world, november 1981, pp. 44 - 48 . C103 P. Millich, "Putting speech recognizers to work" , IEEE Spectrum , april 1987 , pp. 55 - 57 . cm Z.Kačić, è.Breif and B.Horvat, "Uspešnost metod opisovanja skupnih znaćilnosti osnovnih elementov govornega signala", Elektrotehniški vestnik , Vol. 53 (1986), No. 3, pp. 121 - 129 . PROVING THE CORRECTNESS OF DIGITAL HARDWARE DESIGNS USING PROLOG UDK 681.3:325.6.08 Z. Brezočnik B. Horvat University of Maribor ABSTRACT. An approach Is presented for automatic formal verification of digital hardware designs using Prolog. Prolog Is used both as a representational language for specifying the structure and the behaviour of a design and also as an inference nechanisin for proving its functional correctness. A design in this model is composed of hierarchicaly organized modules. Each module Is represented as a finite state machine. Validation of design correctness is made by formal proof as an alternative to the traditional approach which utilises simulation. The verification proceeds as follows: a) writing a design specification and a description of its realization in Prolog^ b) 'deriving a design behaviour from the interconnections of its components and showing equivalence between the specified and The system has enough domain specific and knowledge to perform the proofs largely from the lowest transistor Some large designs including their behaviours, c) the derived behaviour, general mathematical automatically. Designs can be handled level up to the architectual levels. a simple computer have already been verified. 1. INTRODUCTION A hardware or software designer must be able to decide whether the design meets its functional specification. Currently three different approaches exist for answering this question. The first approach to enshure functional correctness is to develop the design from the specification by such a methodology that ensures it can't be incorrect. In software design It is exemplified in research of automatic programming. In hardware design automated techniques exist for dealing with elements of designs that are most tedious and prone to human error (such as wire routing or PAL generation). Silicon compilation techniques for automatic generation of complete designs from specifications are under development. This approach Is perhaps the most attractive, but it is also the most difficult to achieve, because it faces an eventual astronomically large search space of design alternatives. A problem of automatic synthesis is so difficult, that useful general purpose systems for automatic synthesis are not expected in the near future. The second and the most common approach to validate a design is an accurate simulation of it and trying It on test cases. In exhaustive simulation every possible combination of inputs should be tried for every possible internal state. The number of all possible input patterns can be extremely large even for simple devices. A multiplier for two 16-blt integers faces over four billion different inputs. It's clear that exhaustive simulation is no longer feasible. We can only select a subset of input patterns and hope to extrapolate from them to determine the correctness or failure of the design. The selection of an adequate subset of test cases is very difficult. Such partial simulation can detect the existence of an error, but can never guarantee that there are no more errors in the design. There is an alternative third approach - a formal verification of a design with mathematical proof. If the formal verification succeds, the design will natch Its specification for all input patterns. Research in formal verification Involves artificial intelligence techniques. It requires a formalism for representing the structure and the behaviour of digital systems and also an inference mechanism, which will expertly manage astronomically large search spaces. A success of the verification depends much on a built-in general mathematical knowledge base. Because of uncompleteness of the simulation and a bad prognosis for the soon automatic synthesis this approach seems to be the most promising in the nearer tern. Wagner was a pioneer with his research in this field. He has used a nonprocedural functional language for digital design description and a theorem prover in a first order predicate logic. The proof must be guided manually. Because of the description language the use is limited to low levels of a design. After that, Gordon has developed his methods for hardware modeling and verification based on different hierarchical levels with an interactive theorem prover (1). Initially., proofs were made manually, but more recently with an interactive theorem prover. In this paper we present our verification system, named VERDIS (2) for formal verification of digital hardware designs using Prolog. VERDIS represents an automatized version of a 14 variant of Gordon's approach. In Falrchild Laboratory for Artificial Intelligence the VERIFY system was developed based on the similar principles (3). VERDIS has successfully verified some experimental designs with . an interesting degree of complexity. 2. DESIGN REPRESENTATION IN VERDIS A digital system in VERDIS is represented as a collection of hierarchically organized nodules and their interconnections. A module is considered as a finite state machine (FSH) (i; It has a finite set of input (X) and output (Z) ports and a finite set of internal state variables (Y). VERDIS supports FSM of types Mealy and Moore and also ordinary decision circuits, if Y={}. A module is either a primitive with no internal structure (basic building block of the design) or composition of the form I I (Ni where the components Ni are themselves modules. The input (output) ports of a compound module are the input (output) ports of its components. Compound modules are formed by linking some output ports of some components to some input ports of other components. External ports of the module are those ports that are not linked. Each port has an associated signal type which specifies the domain for signals passing through it. Signals in digital system are viewed differently according to the conceptual_level in which they are considered: as voltage levels, as logic values ,as bits , as numbers or even as higher-level objects. Signals in VERDIS may have following types: -booole (Boolean truth values true or false) -bit (binary digits 0 and 1 ), -integer(N) (integers in the range 0-2 -^-»»-l ), -integer ( natural numbers), -booleZ, bitZ, integerZCN) and integerZ (high impedance signal types). Structural and signal hierarchy allow more succint description. Signals on a higher hierarchical level don't show unnecessary details of lower-level signals, but cary the same information. - For conciseness the behaviour of the FSM is described by two sets of equations , rather than an exhaustive table: D'^y z 5(x,y) Ä(x,y) x6X, y6Y xsX, ysY, zsZ (2) (3) Equation (2) gives internal states as functions of inputs and current state. Equation (3) gives output signals as functions of inputs and current state. A dictionary of. available functions that can be used in expressions for describing module behaviour currently consists of arithmetic r logic (not,and,or,xor) and branching functions (if,c»se) and also some special functions for such operations as wiring signals on a bus and work with memories (Join-fn, bushfn, rfetch, fetch,store,...). Module definition consists of Prolog facts and rules. In addition to constructs for specifying type of the module, ports, states, components, internal connections and behavioural equations the description language supports several useful constructs: constants, parameters, arrays, bitwise connections and equ operator for calling some predefined modules from the system library. Let's illustrate some constructs mentioned so far j by considering an example of a one-bit multiplier. It's constructed from a collection of 2|-to-l multiplexors, each of which has inputs inx,\ iny, control input etri and output out. I « Definition of a one-bit mult iplier % terns of 2-to-l uultiplexsors in uodulefbitault(N>) . port^(bitmult. linked(bitmult(N>, ctrl(Bimult, 1) , ctrl(mplx(Bitault, I))) t-index(0,I,H). linked(bitmuIt(N), out(mplx(Bitmult, I)), bit(I,out(Bitnult))>s- index(0,I,H}. output_equation(bitault(H), out(Bitmult) t" if(cirl(Bitnult), in(Bitmult), null(Bitmult))). In this example, H is a parameter specifying the |bit wide of the multiplicand (i.e., the most I significant bit represents 2*^). Due to declarative power of Prolog a suitable indexing of part and connections can be usad. The construct index(0,I,N) means simply that I can take any value from 0 to N • 3. THE VERIFICATION PROCESS The jkey principle of VERDIS is that given the behavjiour of components of a system and their intericonnections, it is possible to derive a descrjiption of the behaviour of the whole system. The derived behaviour can then be compa.red with a specification of the intended behaviour of the system. If a design contains an error, a discrepancy between both behaviours can be detected and the design corrected, i Before of the verification some basic checks are made to enshure that nontrlstate outputs are not wired, that connected signals have equivalent types, that every output and state variable has an equation ... . These checks have proved to be very | useful in finding typing and logical mistakes in design specification. On request tor verification of a module VERDIS checks, if the correctness of this module type has been already proved, in which case another proof is not necessary and the verification succeeds immediately. If a module la a primitive, its correctness can be assumed. If the correctness of a module is unknown, VERDIS uses a depth first search to recursively verify each of its part and then a module as a whole. The next step in verifying a module is to derive a behavioural description of a composite module from the behaviours of its components with their interconnections. Each component module has a set of output and a set of state equations. The union of all these equations is In fact an implicitly specified behaviour of a module. It contains Internal variables (signals at parts inside the module and state variables of component modules). The unnecessary internal information should be hidden. With subsequent substitutions of internal variables with behaviour equations of conponent modules all internal variables are eliminated. If any frequently used internal variable has a very complicated equation it may be better not to eliminate it to avoid even larger equations. In such cases VERDIS first derives and evaluates the expression for the immediate variable and refers to it in behaviour equations of the module where needed. The final result of this step is a set of derived output equations and a set of state equations. At this point we can' try to prove that the derived behaviour description of the module is equivalent to the behavioural specification. In most cases a mapping between them is an exact equivalence - isomorphism. We have to show that corresponding equations in both automata are Identical. The proof of identity is generally a hard problem. It requires much mathematical knowledge about functions, which can be used in equations. In more complex cases the correspondence between automata is a homomorphism rather than exact equivalence. A homomorphlsm may have a structural or a behavioural form or both. Structural homomorphism occurs, when automata are functionally identical but different in structural description. Behavioural or temporal homomorphism occurs, when the same automata Is viewed with different time-scales. VERDIS currently works only for isomorphic machines. The derived and the specified behaviour are compared for each output and each state. Proof of design correctness requires the ability to prove that a given . equation (specified behaviour as a left side and derived behaviour as a right side )ìb an Identity. The equation is first checked to see whether it is recognized as a trivial Identity or whether it is a" trivial non-identity. If the equation is not trivial, VERDIS tries to choose the best strategy for proving the indentlty. A strategy selection depends on a form of left and right side of the equation and on function, operators and types of the variables Involved. The repertoire of strategies contains: algebraic simplification. Boolean canonicalIzation and enumeration. Algebraic simplification is the most general strategy, which tries to prove the identity of left and right side of the equation with simplification, expansion and canonicalIzation. Simplification is Implemented with a general recursive Prolog procedure that recursively simplifies a given expression using simplification rules for the Involved operators and functions. Expansion is used when a function is observed on only one side of the equation. The definition of the function is then substituted for its call and the resulting expression is simplified. Canonical1zation tries to deal with combinatorial problems because of commutativlty and associativity of some functions f■>',*,or... ^ . If only Boolean var^lables occur in the equation a more straightforward strategy of Boolean canonicalization Is chosen. During six subsequent steps the left and the right side of equation are transformed to a lexically ordered complete disjunctive normal forms and then compared. It's faster than algebraic simplification. Sometimes no other strategy but enumeration may be applied. An enumeration is made over a minimal necessary number of variables. For a selected set of variables each possible combination of their values is generated and substituted into the equation, which is then simplified to 'true' or 'false'. In some special cases it's not necessary to generate all possible combinations but.only some of then. Partial enumeration may save much computation. VERDIS avoids the use of enumeration, because it's usually very space and time consuming. If VERDIS doesn't have enough knowledge to select a strategy, an interactive mode is entered. Currently a user can insist In the algebraic simplification, in the enumeration on all or just some of the variables and can also simply assume the equation to be true or false. It's always possible to enlarge VERDIS's knowledge base and automatize the strategy selection for such cases. Proving identity of an equation is the main and the most difficult problem in the verification process. The use of any procedural programming language with deterministic organization would not be a natural way for solving this problem. This fact is one of the most significant arguments for realization of VERDIS with the nonprocedural language Prolog. A Prolog program is a pattern directed system. The proof proceeds with an activation of that verification rule which is currently appliable to the left and to the right side of the equation. Such realization has a high degree of modularity. The knowledge base can simply be enlarged by adding new rules without any other changes. 4. TWO COMPLEX EXAMPLES VERDIS has tackled some complex designs including modules d74 and host. d74 is an arithmetic unit( inputs inA, inB, inC and outputs outi and out2J, which is intendend to compute sums of products. out! = inA«inB * inA»inC out2 = inA*inC ^ inB»inC At the top level it contains three multipliers and two adders. The multipliers consist of slices, each of which contains a one-bit multiplier, a shifter and an adder. The adders are built from fulladders, which are built from Invertors and 2-to-l multiplexors. Multiplexors are built from logic gates. The logic gates are themselves described at two levels: at Boolean algebra level and at lower transistor level with tristate signals and stored charge. d74 is parameterized in bit-wide of inputs. An Instance that has a^bit inputs Involves 21 different types of module with nine levels of structural hierarchy. The design contains 1902 primitive parts, including 1016 transistors. The entire listing of the proof trace occupies about 1300 lines. The next example is a register-transfer level description of a simple computer host with eight operations: HALT, JMP, JZRO, ADD, SOB, LD, ST and NOP. The computer is divided into a control section and a data section. The data section is built upon a single 16 bit data bus. Six register ( the program counter, the accumulator, the Instruction register, the argument register, the buffer register and the memory register) and also an arithmetic-logic unit and RAM are connected to the bus. The control section contains a microprogram ROM, a microprogram counter and a microinstruction decoder. VERDIS has proved the correctness of this computer at the microinstruction level. S. DISCUSSION OF THE RESULTS VERDIS is a large Prolog program that occupies about 61 kbytes of code for Interpretation. It currently runs on a VAX 8800 under ISJ Prolog interpreter (4). The main restriction on the complexity of examples which currently can be tackled Is the amount of workspace required by Prolog. To deal with large systems. It Is necessary to verify them a piece at a time or to restart verification when It aborts due to lack of space. Since VERDIS promptly records the progress of verification in the database, restarting does not result in duplication of work. Due to the hierarchical decomposition of design description the work done in proving the correctness of a complete system is linear in terms of the number of types of module in its design, rather than linear in terms of the number of primitive components. For complex designs with many thousands of primitive components, the computational saving can be very great. At present, the program performs only functional verification, with no consideration of timing. It appears relatively straightforward to introduce the notation of time in our description, but adding the appropriate inferential machinery will probably require more effort. However, dealing with truly asynchronous systems requires a rather different approach with revision of the representation and proof mechanism, perhaps In direction of a temporal logic (5). The verification in VERDIS runs largely automatically, what is an advantage in comparison with the Gordon's approach, where the proof has to be guided by a user. VERDIS can be compared with a similar system VERIFY which has been developed in the Fairchlld Laboratory for Artificial Intelligence. VERDIS introduces some useful new elements; possibility of macro calls for predefined modules in the system library; retaining of internal variables with over-complex expressions (i.e. bus output ), new verification strategies of Boolean canonlcalization and partly enumeration, more heuristics in variable selection for the enumeration etc. 6.CONCLUSION VERDIS is our first attempt of formal verification which has already shown that digital designs with an interesting degree of complexity can be handled. It should be tried on many other real designs and it's knowledge base should be enlarged to become a real design tool, but abilities of this approach are yet evident. The decision for Prolog as a description and an implementation language seems to be correct. Pattern matching and backtracking in Prolog are very powerful tools in the verification process. VERDIS is currently interpreted on a VAX 8800 under US Prolog Interpreter(4 ). If we have any Prolog compiler, the speed of execution of the compiled code will increase ten times at least. VERDIS should be only one component of larger system supporting hardware designs. This would integrate programs for design entry, simulation, verification, diagnostics etc. Maribor, November 1986 (3) H. G. Barrow, VERIFY: A Program for Proving Correctness of Digital Hardware Designs, Artificial Intelligence, Vol. 24, No. 1-3, December 1984, 437-491 (4) !j. Stojanovski, US Prolog Reference Manual, Institut Jozef Stefan, Ljubljana, |1986 (5) B.C.Moszkowski, A temporal logic for reasoning about hardware, Procedlngs isixth International Symposium on Computer Hardware Description Languages, Carnegie-Mellon University, Pittsburgh, 1983, 79-90 REFERENCES (1) H. Gordon , J. Herbert, Formal hardware verification methodology and its application to a network interface chip, lEE Proceedings, Vol. 133, Pt. E, No. 5, September 1986, 255-270 (2) Z. Brezocnik , Hardware verification. Master thesis. Tehniška fakulteta. RECONFIGURABLE MULTI-MICROPROCESSOR SYSTEMS INFORMATICA 1/88 UDK 681.519.7 Peter Kolbezen Institut »Jožef Stefan« A communication mechanism based on the exchange o-f the distributed topology in-formation is di3cua«ed. A particular recon-figur— ation technique is treated to handle the exchange o-f topology in-formation and thus to maintain the necessary routing tables. This mechanism handles thfe r econ-f i gur at i on dynamically. Inmos Transputer concepts aro introduced and applicated on tho two-dimensional square interconhection structure. "R«konfIgurabiIni" veCprocasor^ki sistemi. Prispevek obravnava komunikacijski mehanizem, ki Je zasnovan na spremembah topologije komunikacijskih poti med mikroprocesorskimi enotami sistema. Namenjen Je posebni t. im. "rekon-f i gurabi Ini " tehniki, ki obravnava spremembo in-formacije o topologiji in na ta naCin vzdrHuJe potrebne raz predelni ce povezav tnedprocesorskih komunikacij, V predlogu so vpeljani koncepti Inmosovega transputerJ a, kot voz-liÄCnega procesorja v povezovalni dvodimenzionalni kvadratni strukturi. 1. INTRODUCTION Highly parallel computing structures promise to be a major application area -for the milion-transistor chips that will be possible in just a few years. Such computing systems have otruc--tural properties that are suitable -for VLSI implementation. The key attributes o-f VLSI computing structures are - simplicity and regularity - concurrrency and communication - computation intensiva VLSI. The choice o-f an appropriate architecture -for any electronic system is very closely related to the Implementation technology. This is especially true in VLSI. The supervisory overhead incurred in general-purpose supercomputers o-ften makes them too slow and expensive -for real-time and signal and image processing. Progress in VLSI technology has lowered implementation costs -for large array procesaors to an Acceptable level. Algorithmically specialized processors o-ften use di-f-ferent interconnection structures. The matching o-f the structure to the right algorithm has a -fundamental in-fluence on per-formanca and cost e-f-fectiva-nass. An alternative to the design o-f a globally ■ynchronous array is to achieve a sel-f-timed system through the use o-f asynchronous handshaking mechanisms established between neighboring processing elements. These sel-f-timed -implementations are commonly re-ferred to as wavafront «rrays /8,12,21,23,25/. The wave+ront array combines the systolic pipelining principle with the data-flow computing concept. A wave-front array processor may be used either as an attached processor inter-facing with a compatible host machine or as a stand-alone processor equipped with a global control processor. Such system consists o-f the processor array(s), interconnection network(s), a host computer and inter-face unit. Exploitation o-f the data-flow principle makes the extractions of parallelism and programming ■for wave-front arrays relatively simpler. A -family dynamically interconnected or recon-figurable VLSI processor arrays allow an array to support a large-class o-f algorithms. Such structures usually involve signi-ficant hardware overhead, f^econ-f igurabl.l i ty o-f array structures based on switching lattices has been proven to be useful for solving problems related to fault tolerance. Fault tolerance is an important concern in systolic and wavefront arrays because of the large number of processor elements they may have. The paper concludes with suggestion« as to how a recofigurable sistem may be designed with constructing a wavefront array with the family of Inmos Transputers /20/. Transputer chip is an Occam-language-based design that provides hardware support for both concurrent computation and communication. It adopts the now-popular RISC architactura. Its features make it * powerful building block for constructing cofKurrent processing networks. Tha transputer's links are the hardware reprasantation of the channels -for proireas communi cat i an. There is an intimate relationship between transputer channel links and the communications protocol envisaged -for wavefront arrays. 2. ADAPTIVE SYSTEMS The' treatmented reconfi gurations technique in first part of the -first work on this topic is discussed in connections with uniform and dense netvliorks. It is based on Baran's hot-potato routine /2/. A correctness proof of a similar algorithm hi. In practice this is npt always the case. The topology message contains two fields relevant to reconfi gurat i on : identification of destination node i and the shortest distance between the sending node s and node i. A node generates, and may modify, a shortest distance table as shown in f-ig. 1. )3esti- nation 0 1 1 2 . , k . , n-1 Distance D(0) i d(11 d(2) . . . d ( k ) . .. d(n-1) Fig. 1 Shortest distance table at node k The entries are indexed by the node identification: and the entries themselves are the shortest distance between the corresponing destination-node and the local node. 4. HANDLINB INSERTION OF A NEW NODE Now, j suppose that node 1 of Fig. 2 detects a new neighbour, say node 17 in the same figure, and -the rest of the system is uniform with the confi gurati on known and node 17 has no ties with I any other node in the system, except node 1. this is a major change in the network. The topology message exchange propagates until the configurational change has been detected at every node in the system. A recoiving node ne«3ds to send topology messages to its neighbouring nodes only if tha topology message received has changed the previous topology information, i.e. the shortest distance table. This process can best be visualized by a top-down tree, as shown in Fig. 3. 17" : ; 1 ! -------f. .........3-........ +---------f- ; ; ^ 1 -.....---5------------------6--------------- ■ 1 1 1 1 1 1 1 ---------7-------- -----------B-................t 1 1 1 ■ 1 t . t t 1 --11-........ -------------12..........-......t --------13.............14--------- i 1 1 ! — 15---- --------16--------< 1 j -----+ distance and the routing tables alter every time a topolpgy change on a shorter path at— rives. Every change is then fanned through the system. Starting from the ROOT, node 1, there ara five levels of transmission. The system, with the exception of node 17, is expected to settle in five main periods. For node 17, however, (n-1) main periods are required to receive the complete topology information from the ROOT, where-n is the number of nodes in the original network. This is because the ROOT needs to send the shortest path vector to node 17, where each ■path is transmitted in the form of- a topology chč which records the shortest paths only'. For each destination a maximum of m paths can ' be identified, where m is the number of neiglhbours. The DT is an n by m table, where n is network size. FiguV-e 4 shows the DT a node 1 of the 16-nade network given in Fig. 2. In a regularly connlected homogenous network all the distanca tables are of equal sise. An entry d(k,i,J) is the I distance of path (k,i) via tha neighbour X(j)|, where i'=l,2,...,n and j = l,2,...,m. The node's that are not accessible from node k have a correspoding entry of infinity in the table. For ' example, node 1 appears inaccessible from itsellf via any of its neighbours. I The feize of routing table (RT> depends upon the Destination Via neighbouring nodes 2 4 S 13 1 infinity in-finity infinity in-finity 2 1 3 3 3 3 2 2 4 4 16 Fig. 4 Distance table -for node 1 o-f a 16-node network speci-fic routing mechanism being employd. In ■fact, RT is arranged using the distance table. An entry r becomes live( min Idj , j I , j e m "i ,J' TMf : = V], (send topology meeeage). TMi : = TMi (where Y = Xj) for j = 1,2,...,m, except for Xf - c. fi, od; 4. Exit 2. (update distance and routing tables) djj : = 1 where jth neighbour c, Vc : = 1, a r-c : =-- c; 3. (preparate topology tiiessiage) (set distance topology Field of topology message/ ■Ji St (TM^) : - 1, (set destination field of topology niesüagei (Jest (Tn^) : = Ci 4. (send topology message to neighbouring nodes) Xj TM® for j 1,2,...,m and Xj cj 5. (send available topology information to new nei ghbour) (form topology message) dest (TMp : = i for i " 1,2.....n. (send topology change messages to new neighbour) TMi ■• = TMf. 6. Exit. C. Algorithem 3i Handles arrived topology message at node a 1. (detect topology message at local node a) j TH^j arrives č=0> Je CZMV če velja P-CX='.=«o> = = P-CX(tn + i)=Xn-Hl IX(tn)=«n>. tn+l>tn>tn-l->---->to- <3. 1) Ta markovska lastnost pomeni,da je verjetnostno □bnaianje procesa v prihodnosti odvisno samo od tronutnega stanja in ne tudi od zgodovina procesa. Desna stran gornje enaćbe predstavlja prehodno verjetnost med dvema stanjema veriga, ki jo za primer homogene CZMV (kjer so prehodna verjetnosti neodvisne od ćasa opazovanja) lahko zapiéemo v obliki Pij(T) = P{X(t + T>=j IX(t)=l}. (3.2) Vse prehodne verjetnosti verige lahko zapišemo v obliki matrike P(tl) » Cpij(ti)3. Seveda velja enakost Ej Pij0 (3.6) qij predstavlja v primeru i O j časovno gostoto prehodov s katero proces prehaja iz starija i v stanj« j, medtem ko pomeni -qü v primeru i = j časovno gostoto s katera proces zapuSča stanje i. Velja enakost: Ej qij = O, j»S. (3. 7) Iz enačbe 3.4 lahko, s tako de-f ini rani mi qij, pridemo do enačba za verjetnost nekega stanja i v poljubnem trenutku. U'i(t) = Ej(qji«j(t)), jeS. (3.a) Dobili smo torej sistem diferencialnih enačb, katerega reiitev nas vodi k verjetnosti posameznih stanj v poljubnem trenutku t. Zaradi tetavnosti analitičnega reèevanja takega sistema, uporabimo navadno numerične Integracijske metode. Kadar pri neki CZMV obstaja stacionarna porazdelitav verjetnosti, nas ta navadna bolj zanima in je tudi lažje izračunljiva kot porazdelitev v poljubnem času t. Izkaže se, da obstaja stacionarna porazdelitev pri neskrčljivih homogenih CZMV in da je neodvisna od začetno porazdelitve. Stacionarna verjetnost nekega stanja je enaka limitni vrednosti njegove verjetnosti, torej flj = Ilm Ii(t). t-> OO Tedaj tudi velja lim «i(t) =0 t-> OO (3.9) (3. 10) in tako pridemo do sistema linearnih enačb Ej t+T I Wi>t> = pT>. <3. 13) Edini porazdalitvenl zakon, ki zadoSča temu pogoju, je eksponentna porazdelitev. Gostoto verjetnosti te porazdelitve podaja enačba f(t) = a exp(-at), t >= O. <3.14) Lahko bi pokazali, da so časi trajanja posameznih stanj CZMV eksponentno porazdeljani s funkcijo gostote verjetnosti ■fWi =0 <3.15) (3. 16) Analiza vačproceeorskih sistemov s pomočjo pridruženih markavskih verig pomeni toraj predpostavko, da se čase trajanja aktivnih stanj in stanj dostopa obravnava kot eksponentno porazdeljene naključne spremenljivke. 4. siohAstiSna mrežji V nadaljevanju nas zanima vprašanje, kako na osnovi modela večprocesorskega sistema pridemo do pridružene markovske veriga. Direktna pot je lahko zelo zapletena, saj moramo evidentirati vsa stanja sistema in časovne gostote prehodov med njimi. Pomagamo si s stohastičnimi Petrijevimi mrežami (SPM), ki predstavljajo učinkovito orodje za opisovanje sočasnosti in sinhronizacije v paralelnih sistemih. BPM so nekakžna nadgradnja standardnih Petrijevih mrež v tem, da vpeljejo vanje dimenzijo časa kot naključno veličino. SPM je bipartiten gra-f , ki ga sestavlja množica položajev P, množica prehodov T, množica povezav A,' množica prehodnih hitrosti Q in začetna označitev Mq. SPM je torej določena s peterko .p za aktivna stanja in l/Ui, 1 / U21 • • • 1''Up za stanja dostopa. - Ko zahteva nek procesor dostop do skupnega pomnilnika, je ta dostop možen takoj Cbrez zakasnitve), če je skupno vodilo prosto. - Ce skupno vodilo ni prosto, preide procesor v fazo čakanja do sprostitve vodila. - Ko procesor konča s stanjem dostopa, takoj (brez zakasnitve) sprosti skupno vodilo. V analizi bomo predpostavljali popolno Z P, ZP, p, Pj ZP„ Slika 2. Arhitektura večprocesorskega si stema simetrija v sistemu, kar pomeni, da bosta parametra naèega modela srednja vrednost dolžine aktivnega stanja 1/X in srednja vrednost dolžine faze izmenjave 1/u enaka za vse procesorje. Razmerje med njima p = X/u pa imenujmo faktor obremeni jivosti. Točki 2, in 4. pomenita, da smo zanemarili čase, potrebne za dodeljevanje in sproščanje skupnega vodila. To dejanje lahko opravičimo z dejEStvom, da so ti časi navadno veliko krajèi od časov trajanja faz procesiranja in izmenjave. Možno pa je tudi, da čas dodeljevanja in sproščanja vodila prištejemo k času faze izmenjave. Ce torej sistem zadošča gornjim zahtevam, mu lahko priredimo stohastični proces z markovsko ■lastnostjo in opravimo performančno analizo na osnovi analize stacionarnega stanja prirejene markovske verige. Slika 3. SPM večprocesorskega sistema Analize se lotimo s konstruiranjem SPM, ki bo opisovala dogajanje v sistemu. Prikazuje jo slika 3. Število žetonov v položaju pi pomeni število procesorjev v aktivnem stanju, število žetonov v P2 pomeni število procesorjev v stanju čakanja, žetoni v P3 pomenijo procesorje v stanju dostopa, žeton v p^ pa pomeni, da je skupno vodilo prosto. Prehod ti je časoven in predstavlja dogodek, ko žsli eden izmed aktivnih procesorjev poseči v skupni pomnilnik. Ker je gostota teh dogodkov sorazmerna številu aktivnih procesorjev, je prehodna hitrost prehoda tj enaka mjX, kjer je mj število žetonov v p^. Prehod to je takojšen, saj dobi procesor dostop do skupnega pomnilnika takoj, če je le skupno vodilo prosto. Prehod t3 je zopet časoven in ponazarja dogodek, ko nek procesor zaključi stanje dostopa in s tem sprosti skupno vodilo. Začetna označitev naj bo taka, da se v pj nahaja p žetonov (p je število procesorjev v sistemu), v P4 en žeton, v P2 in P3 pa ni nobenega žetona. Ta začetna označitev ustreza stanju sistema, ko so vsi procesorji v aktivnem stanju, skupno vodilo pa je prosto. Iz tako de-finirane stohastićne Petrijeve mreie si zgradimo pripadajoče drevo dosegljivosti (slika 4). Pri graditvi drevesa srna takoj nestabilne označitve in upoètevali le Na primer. Iz označitve (p,O,0,1) v prvem koraku do označitve (p-ki je nestabilna, saj omogoča prehod to, zato takoj nastopi Pi u [p-1,0,1.0 [p-2,1,1,0 px (p-llX , (p-2)K }-{' (o p-l.l.o j Pp = (O,p-1,1,0) pp-1 Slika 5. Diagram prehajanja stanj markovske vsr i Q K Slika 4. Drevo dosegljivosti SPM 6. Zaključek Drevo dosegljivosti SPM nam popolnoma dolaža CZMV s katero bomo ponazorili dogajanje v na^ietn vedprocesorskem sistemu, saj predstavlja doseg 1 j ivostna množica prostor stanj CZMV, prehodne hitrosti drevesa dosegljivosti pa so enake časovnim gostotam prehodov verige. Diagram prehajanja stanj tako dobljene markovske verige prikazuje slika 5. Preden se lotimo reèevanja markovske verige, se moramo odločiti za nek per-f or mančn i pokazatelj, ki nam bo dal dovolj dobro informacijo o učinkovitosti vedprocesorskega sistema. Za ta pokazatelj smo izbrali povprečno število aktivnih" procesorjev (procesorjev v aktivnem stanju) in ga imenovali procesna moč sistema P. Izračunamo jo po enačbi P = Ei ( ITj n^ ( i ) ) , i eS, (4.1) Rezultati predstavi jene stohastične analize ED dobljeni pod predpostavkami, navedenimi v poglavju 5. Te predpostavke so nam omogočile, da smo obravnavali dogajanje v večprocesorskem sistemu kot markovski proces. Čeprav se realni sistemi v splošnem ne podrejajo tem predpostavkam lahko uvidimo, da dajo markovski modeli navadno celo pesimistično oceno o učinkovitosti modeliranega sistema. Zakaj? V realnem sistemu ima porazdelitev časov dostopa navadno manjšo varianco v primeru z eksponentno poraz del i tvi jo. Tedaj je dejanska učinkovitost bolj?.a, kot jo je napovedal naš model. Isto velja v. primeru, ko časi aktivnih stanj in stanj dostopa niso za vse procesorje enaki. Iz tega lahko zaključimo, da-dajejo rezultati, dobljeni na osnovi predstavljene stohastične analize, dovolj dobro oceno o učinkovitosti obravnavanega večprocesorskega sistema. kjer pomeni itj stacionarno verjetnost stanja i CZMV, n^d) pa število aktivnih procesorjev v stanju sistema, ki je ponazorjen z i-tim stanjem CZMV. Za izračun procesne moči rabimo torej stacionarne verjetnosti stanj verige, ki jih dobimo iz analize stacionarnega stanja CZMV. To opravimo z rešitvijo sistema linearnih enačb, ki jih lahko zapišemo direktno iz diagrama prehajanja stanj po enačbah 3.11 in 3.12. Dobimo sistem.p+1 enačb -pXHQ + pTtj = O (4.2) -((p-i))i + |j)irj + (p-i + l)xiij-. 1 + uTj+j = o, i = 1 ... P"1 "O 1 . Splošna rešitev tega sistema je naslednja: k = O... P fO = (Ci,; (f^' (p : / (p-k) I ) ) ~V Uj = tToP

. (4.3) Procesna moč pa je enaka P = (Ctr ! / (n-k) ! ) - 1 ) / < fEi,. ( ! / ( n-k ) I ) ) , k = O... p (4.4) Rezultat analize učinkovitosti našega večprocesorskega sistema je torej enačba, ki podaja odvisnost procesne moči od števila procesorjev in obremeni j ivosti sistema. To pomeni, da lahko na podlagi rezultatov stohastične analize ocenimo učinkovitost sistema v različnem obsegu in pod različnimi delovnimi pogoji." 7. Li teratura 1. Feller W., An Introduction to Probability Theory and Its Applications, Willey, New York, 1966. 2. Holliday M.A., Exact Performance Estimates for Mul ti processor Momory and Bus Interference, IEEE Transactions on Computers, Januar 19B7. 3. Jamnik R., Verjetnostni račun, Mladinska ■knjiga, Ljubljana, 1971. 4. kari in S., A First Course in Stochastic F'rocesses, Academic F'ress, New York, 1975. 5. Marsan M.A. s sodelavci. Modeling Bus Contention and Memory Inter-f erence in a Mul ti processor. System, IEEE Transactions on Computers, Januar 1983. 6. Marsan M.A. s sodel avci ,"■ Performance Models of Multiprocessor ■ Systems, MIT F'ress, Cambridge, London, 1986. 7. Peterson J.L., Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, 19B1. 8. Vidav I., Višja matematika II, DZS, Ljubljana, 1975. . 9. Zuberek W.M., Timed Petri Nets and Preliminary Performance Evaluation, Proc. of the 7th Annual Symposium on Computer Architecture, La Baule, 1980. INERTNA STRUKTURA UNIX ZDRUŽLJIVEGA 8-BITNEGA OPERACIJSKEGA SISTEMA UDK 681.3.06 Ivan Pepeinjak Jernej Virant Marjan Bradeško Nikolaj Zimic Fakulteta za elektrotehniko, Ljubljana Izvleček : Razvoj mikrorafiunalniške tehnologije zahteva uporabo vse zmogljivejših diskovnih enot in tiskalnikov. Takšne zmogljivosti lahko učinkovito izrabimo le v računalniški mreži. Za uspešno implementacijo mreže mikroračunalnikov rabimo operacijski sistem, ki podpira poddirektorije, zaščito datotek ipd. V članku je predstavljen operacijski sistem, ki izpolnjuje vse navedene zahteve, poleg tega je UNIX in CP/M zdručljiv. Opisana- Je struktura datotek na disku in interna zgradba operacijskega sistema. Abstract : The development of computer technology requires use of more and more sophisticated disk units and printers. This resources can be effectively used only in a local area network. To successfully implement microcomputer local area network, an operating system supporting subdirectories, file protection and users separation is needed. In the paper we present an operating system which meets all of the stated requirements along with UNIX and CP/M compatibility. Disk structure and internal data structures used are presented. 1. UVOD 1.1 Opis problema Vse hitrejši razvoj mikroračunalniške tehnologije omogoča prodor mikroračunalnikov v vsa področja družbenega življenja. Kakor hitro pa hočemo mikroračunalnik uporabiti v poslovni sferi, se srečamo s količinskimi problemi : - prisotnost velikih baz podatkov - velika količina izpisov ki jih lahko rešimo samo z zahtevno in še vedno drago tehnologijo (trdi diski, hitri tiskalniki). Poleg tega morajo biti podatkovne baze v takšnih okoljih praviloma deljene med več uporabnikov, ki hkrati dosegajo podatke iz podatkovne baze. Če hočemo rešiti takšen problem je najbolje, da povežemo več mikroračunalnikov v mrežo, znotraj katere si lahko delijo zmogljivosti (trdi disk) in izmenjujejo sporočila. Tako dosežemo večjo hitrost delovanja celotnega sistema (inteligenca Je razdeljena med več delovnih mest) in manjšo ceno sistema na enoto zraoglj ivosti. 1.2 Naša realizacija cenene mikroračunalniške mreže Mikroračunalniške mrežo lahko s stališča programske opreme realiziramo na več načinov : - vsi računalniki lahko zahtevajo podatke z vseh računalnikov - nekateri računalniki so delovne postaje, drugi so strežniki Prvi pristop je zanimiv v primeru, ko imamo na razpolago že obstoječ (dokaj drag) mikroračunalnik s trdim diskom. Ta implementacija ima nekatere slabe lastnosti, saj je operacijski sistem takšnega računalnika zahtevnejši, poleg tega zaradi servisiranja zahtev z drugih vozlišč upade hitrost lokalnega dela. Drugi pristop je boljši v primeru, ko lahko sami razvijemo svoj mikroračunalnik, saj se lahko odločimo za posebno izpeljanko mikroračunalnika, ki vsebuje samo krmilnik za trdi disk in enostaven zaslonski krmilnik za diagnostiko ter tako dosežemo cenejšo izvedbo mikroračunalnika. Delitev vozlišč na strežna vozlišča in delovne postaje poleg tega prinese Se dodatne prednosti, saj se vsako vozlišče ukvarja izključno z eno nalogo, ki jo zaradi tega opravlja bolje in hitreje. Kot osnovo naše mikroračunalniške mreže smo vzeli mikroračunalnik DIALOG z operacijskim sistemom FEDOS (CP/M združljiv operacijski sistem) in mikroprocesorjem ZBO. Ko smo preudarjali, kakšen naj bi bil operacijski sistem strežnega računalnika smo ugotovili naslednje : - operacijski sistem mora podpirati zaščito datotek med uporabniki - operacijski sistem mora podpirati drevesno strukturo kazala datotek Slika 1.1 Struktura mikroračunalniSke mreže V naslednjih razdelkih si bomo zaporedoma ogledali - Strukturo diska, kot Jo podpira FENIX operacijski sistem - notranjo zgradbo FENIX operacijskega sistema Ce smo hoteli v okviru mreže podpirati standardno CP/M programsko opremo, smo morali vsaj logično obdržati CP/M diskovno strukturo in GP/M diskovne funkcije. Tako smo prišli do naslednje strukture mikroračunalniSke mreže : - v strežnem računalniku teče operacijski sistem FENIX, ki podpira večino funkcij, ki Jih mora imeti večuporabniški operacijski sistem (zaščita datotek, drevesna struktura kazala, podpora večih uporabnikov ipd). - v delovnih postajah teče lokalno operacijski sistem FEDOS (CP/M združljiv) in vmesnik na lokalno mrežo DANTE/NET, ki pošilja zahteve preko lokalne mreže strežnemu računalniku 2. STRUKTURA SISTEMA DATOTEK 2.1 Uvod Operacijski sistem, ki podpira hkratno ali zaporedno delo večih uporabnikov, mora zadovoljevati sledeče zahteve : - omogočati mora ločitev datotek različnih uporabnikov, da omogoči vsakemu uporabniku pregled nad njegovimi datotekami in prepreči nehoteno izgubo podatkov zaradi napake v delu enega od uporabnikov - omogočati mora zaščito datotek pred drugimi uporabniki, da bi preprečili zlorabo podatkov ali neunerno povzročeno izgubo podatkov. Poleg teh zahtev mora operacijski sistem izpolnjevati še naslednje zahteve, ki Jih narekuje optlmalnost delovanja računalniškega sistema : - omogočati mora obstoj zelo majhnih datotek, saj Je v razvojnem okolju večina datotek majhna (100 bytov - lOK bytov). Osnovna enota dodeljevanja prostora na disku mora biti torej čim manjša, najbolje en fizični sektor. - omogočati mora obstoj zelo velikih datotek (omejitev mora biti velikost diskovnega pomnilnika), saj podatkovne baze navadno potrebujejo izredno velike datoteke. - v razvojnem okolju Je ugodno, če lahko uporabnik svoje datoteke razdeli v logične skupine. - omogočati mora hiter naključen dostop do datotek. Praktično vsi operacijski sistemi imajo dostop do datotek organiziran preko kazala datotek. Le to vsebuje najmanj dva podatka : - ime datoteke - informacijo o tem, kje se datoteka nahaja na disku Informacija o položaju datoteke na disku je lahko spravljena na tri različne načine : - v kazalu datotek - v posebnem delu diska ■ - deli datoteke so med seboj povezani v verigo Če izberemo tretjo možnost imamo še vedno dve različici : - informacija o nadaljevanju verige Je skrita v vsakem sektorju. - informacija o nadaljevanju verige Je zapisana v posebni tabeli. Vse tri rešitve imajo svoje dobre in slabe lastnosti : 2.1.1 Zapis položaja datoteke v kazalu datotek Dobre lastnosti : - položaj datoteke ugotovimo takoj, ko najdemo ustrezen zapis v kazalu datotek. Tako prihranimo en dostop do diska - takšen način zapisa Je najlažje realizirati Slabe lastnosti : - Velikost zapisa v kazalu datotek Je velika, zato potrebujemo za iskanje zapisa v kazalu več dostopov do diska. - Pojavi se problem velikih datotek, ki Jih navadno rešujemo z uporabo več zapisov v kazalu datotek, kar še povečuje že tako veliko kazalo 2.1.2 Zapis položaja datoteke v posebnem delu diska Dobre lastnosti : - kazalo datotek je majhno, kar omogoča hitro iskanje Slabe lastnosti : - dostop do informacije o položaju datoteke zahteva še en dostop do diska in praviloma tudi premik glave. 2.1.3 Povezava v verigo Dobre lastnosti : - kazalo datotek je majhno - v primeru uporabe posebne tabele so vse informacije o položaju datotek zbrane na enem mestu Slabe lastnosti : - shranjevanje kazalcev v podatkovnih blokih izredno upočasni naključni dostop do datoteke in ga v bistvu degenirira v sekvenčnega - uporaba posebne tabele navadno povzroči probleme zaradi njene velikosti (za 40M bytni disk pri velikosti enote dodeljevanja IK byt ta tabela velika 80K bytov). 2.2 Pregled obstoječih rešitev Oglejmo si sedaj nekatere obstoječe operacijske sisteme, posebno tiste, ki so primerljivi z našim sistemom. 2.2.1 CP/M Operacijski sisteift CP/M ima vse informacije o datotekah zbrane v skupnem kazalu datotek. Informacija o položaju datoteke Je zapisana kar v kazalu datotek, za velike datoteke uporablja CP/M več zapisov v kazalu datotek. Osnovna enota dodeljevanja Je odvisna od velikosti diska in se giblje od IK byt do 8K bytov. Velikost kazala datotek Je omejena, torej Je omejeno tudi skupno Število datotek na celotnem disku. Zaščita datotek Je omejena na Read-Only atribut, ki ga lahko nastavlja vsak uporabnik. Delno Je torej preprečeno nenamerno brisanje datotek, namerne poškodbe podatkov ne moremo preprečiti. Operacijski sistem podpira 16 uporabnikov, vendar ne nudi nobene zaščite med uporabniškimi področj i. 2.2.2 MS-DOS 2.2.3 FILES-11 struktura (RSX-11 in VMS) FXLES-11 struktura Je sorazmerno precej zahtevna diskovna struktura. Omogoča drevesno strukturo datotek, zaščito datotek med uporabniki, omogoča neomejeno število uporabnikov. Vsi parametri diskovne strukture (število datotek, velikost datoteke ipd.) so neomejeni, omejitev je le fizična' velikost diskovne enote. Informacija o položaju datotek na disku je zapisana v posebnih sektorjih (FILE HEADER), ki so zbrani v datoteki (0,0)INDEXF.SYS, kar poenostavi kontrolo pravilnosti diskovne strukture in omogoča iskanje izgubljenih datotek. Operacijski sistem edini med naštetimi podpira verzije datotek. 2.3 Naša izbira strukture datotek Ob izbiri strukture datotek smo se skušali izogniti večini slabih strani vseh sistemov. Tako smo dobili strukturo, ki dokaj optimalno Izpolnjuje večino ciljev, ki smo si jih zadali v začetku tega poglavja, vendar Je omejena z uporabljeno tehnologijo (Z80 procesor in 64K bytov pomnilnika), ki nam Je onemogočala realizacijo bolj zahtevne In bolj optimalne strukture. Velikost sektorja na disku je 1024 bytov, velikost logičnega sektorja, kot ga vidi uporabniški program pa Je 128 bytov, da ohranimo združljivost s CP/M operacijskim sistemom. Ves dostop uporabniškega programa do datotek poteka preko logičnih sektorjev velikosti 128 bytov. Informacija o imenu datotek je zbrana v kazalu datotek. Kazalo datotek Je datoteka tako kot vsaka druga datoteka, zato je lahko kazalo neomejeno veliko. Operacijski sistem podpira drevesno strukturo kazala, vsako vozlišče v drevesni strukturi je spet datoteka. Tako smo dosegli enoten pristop do vseh datotek v operacijskem sistemu, kar poenostavi pisanje sistemskih programov a tudi samega operacijskega sistema. Poleg tega obstajata v vsakem kazalu posebni datoteki . in .. (trenutno in predhodno kazalo), kar še olajša sistematski pristop do drevesne strukture kazala. Za definicijo poti do posameznega vozlišča je uporabljena UNIX sintaksa (npr. /USR/SAMPLE/TEST). Kot vidimo. Je v kazalu datotek zapisano samo ime datoteke, njena zaščita in položaj ostalih informacij o datoteki. S tem dosežemo, da je velikost enega zapisa samo 16 bytov, torej spravimo v en fizičen sektor (IK byt) 64 zapl- Typ« DiiMtory S^n).• 8«« ,, ; Strina O) JOMt thaerlptor t Iot«8«t Prot«cUoa s Ar>«r U.-«) ot nibbi* H«a«rvM Byt« Syt« Operacijski sistem MS-DOS podpira drevesno strukturo kazala, vendar je velikost glavnega kazala fiksna. Ne podpira uporabnikov, prav tako ne podpira zaščite datotek. Osnovna enota dodeljevanja Je odvisna od velikosti diska in se giblje od IK do 4K.: Skupno število datotek na disku ni omejeno. Informacija o položaju datoteke na disku se nahaja v posebni tabeli na začetku diska (FAT), posamezni elementi v tej tabeli so povezani s kazalci. Vsak. element predstavlja en cluster (enoto dodelJ evanj a prostora). Slika 2.1 Struktura zapisa v kazalu datotek sov, kar Je dovolj za večino primerov, torej lahko celotno kazalo večinoma dosežemo z enim samim dostopom do diska, kar bistveno vpliva na hitrost odpiranja datotek. Zaščita datoteke je razdeljena v štiri dele : - uporabnik (USER_ID datoteke je, enak USER_ID uporabnika) - uporabniška skupina (GROUP_ID datoteke je enak GROUP_ID uporabnika) - ostali svet (USER_ID in GROUP_lD datoteke in uporabnika se razlikujeta) - privilegirani sistemski uporabnik (USER_ID = 0). Za takšnega uporabnika sistem ne testira zaščite datotek. Vsaka skupina uporabnikov (OWNER, GROUP, WORLD) Ima v dveh zlogih zaSčlte prirejene 4 bite, ki predstavljajo dovoljenja posamezne skupine uporabnikov : - READ -- uporabnik lahko datoteko bere - WRITE -- uporabnik lahko datoteko piše - EXECUTE -- uporabnik lahko datoteko izvaja - DELETE — uporabnik lahko datoteko briše Za kazala, ki so po definiciji tudi datoteke, je pomen posameznih bitov nekoliko spremenjen ; DESCRIPTOR_POINTER je tabela kazalcev na sektorje, ki vsebujejo razširjen opis datoteke. DATA_POINTER je tabela kazalcev na prvih 256 podatkovnih sektorjev. S takšno zasnovo opisa položaja datoteke na disku smo dosegli naslednje omejitve : - velikost diska največ 64M bytov - velikost, datoteke največ 128M bytov, torej več od velikosti diska, kar pomeni, da Je velikost datoteke dejansko omejena z velikostjo diska. uporabnik lahko bere kazalo uporabnik lahko kreira ali briš^ - READ - WRITE datoteke - EXECUTE — uporabnik lahko odpira datoteke - DELETE — uporabnik lahko briše kazalo Četrta skupina štirih bitov je neuporabljena za zaščito datotek in služi kot opis dodatnih lastnosti datoteke : - DIRECTORY -- datoteka je kazalo - 6YSTEM -- datoteka je sistemska datoteka Z Implementacijo zaščite nad kazali datotek lahko uvedemo nekatere zanimive Izvedbe zaščite datotek : lahko samo pregleduje kazalo, more odpreti datoteke v kazalu - uporabnik vendar ne {READ) - uporabnik lahko odpre datoteko, če pozna njeno ime, vendar ne more izpisati imen datotek (EXECUTE) - uporabnik lahko samo lista kazalo in odpira datoteke (READ in EXECUTE) - uporabnik lahko samo kreira nove datoteke, ko je datoteko enkrat kreiral, je ne more več brati (WRITE). Preprečevanje brisanja datotek dosežemo z ustrezno zaščito datotek pri kreiranju. Informacija o položaju datoteke na disku je zbrana v dveh podatkovnih strukturah : - Za prvih 256K bytov datoteke v opisu datoteke (FILE DESCRIPTOR) — en sektor. V tem sektorju so zbrane tudi vse ostale informacije o datoteki. - Za podatke preko 256K bytov datoteke v razširjenem opisu datoteke (EXTENDED FILE DESCRIPTOR) — en sektor za vsakih 512K bytov Ker ima velika večina danes dostopnih diskov, primernih za vgraditev v mikroračunalnik, kapaciteto manjšo od 64M bytov, ta omejitev velikosti diska ne bi smela predstavljati resne ovire. Ce želimo uporabljati večji disk, ga lahko razdelimo na particije velikosti 64M bytov in ga uporabljamo kot več logičnih diskov velikosti 64M bytov. Zasedenost diska je zapisana v posebni datoteki (/BITMAP.SYS). Z uporabo posebne datoteke dosežemo bistveno manjši zagonski čas sistema v primerjavi s sistemi, ki ob zagonu računalnika gradijo tabelo zasedenosti diska v spominu (CP/M). Poleg tega je gradnja takšne tabele v pogojih drevesne strukture kazala praktično nemogoča, saj bi zasedla preveč spomina. Edina slabost takšne zasnove bitne tabele se pokaže ob izpadu sistema, saj je takrat tabela poškodovana in potrebujemo poseben program, ki jo popravi nazaj v korektno stanje. Za vzpostavitev vseh sistemskih struktur potrebujemo še dva kazalca : - kazalec na opis datoteke / (vrh drevesne strukture kazala) - kazalec na opis datoteke /BITMAP.SYS (za lažje delo, čeprav bi ga lahko dobili iz datoteke /). Ta dva kazalca sta zapisana v HOME BLOCK sektorju diska (sektor 1 v 0. stezi), ki ima sledečo strukturo Typ« How Bloch - toeord VoXiuMi Hum : String «ta : Data »adoioDat» : Data Daacplptar rointar: Array (0..137) oC Intasar Ca(Bj>alatar : Amy (0..aSS) of Intasar Snd } Slika 2.3 Struktura HOME BLOCK sektorja Sektor O v O. stezi Je rezerviran za program, ki naloži operacijski sistem ob zagonu računalnika. Tako je standardna oblika prve steze diska sledeča : ■ Slika 2.2 Struktura opisa datoteke Polja USER_ID in GROUP_ID imajo znan pomen. Polje OPEN_COUNT služi za štetje števila dostopov do datotek, ki Jih hkrati odpre več uporabnikov. Polje LAST_BLOCK pove številko zadnjega logičnega bloka (128 bytov) v datoteki. V opisu datoteke hrani operacijski sistem datum zadnjega dostopa, spreminjanja, kreiranja in arhiviranja. Te datume lahko uporabljamo za kontrolo dostopa do datoteke ali za delno arhiviranje podatkov na disku (arhiviramo samo podatke kjer je UPDATE_DATE > BACKUP_DATE). Datum Je natančen do sekund. Selitor BOOT BtOCK Kod* la Mlaganje operac. aiatana HOMC BtOCK VoluM Kana ROOT DKSOUPTOR PTR i BITMWäDESaUPTOS IPTB ROOT DESCRIPTOR i::::; :Rasalol ina: glavno! kaxalo ::! iBOoraonìBeroi« prvi »aktor glavnoga kazala BITMAP BESOUPTOB . >/:l(;a3&lcl -T)aV'tabalo: xaaada^^ BITMAP HATA Tabela taaađenoatl đitka koda operaciaskeca sistema Slika 2.4 Struktura prve steze diska Za ilustracijo zgoraj navedenih pojmov si oglejmo še primer strukture diska, kl Ima v glavnem kazalu samo dva poddirektorij a /BIN in /USR. Prikazane so vse povezave med podatkovnimi strukturami na disku in način kako operacijski sistem doseže določene podatkovne strukture. HOMEi BLOCK OPIS GLAVNEGA KAZALA h OPIS DATOTETO /USB BlTHAP.Sra U8R BIH Oatkla aatotak* TABELA ZASEDENOSTI DISKA OPIS ■ TABELE : ^ASEDENÖSTI■■: DISKA:■ if.:-!' OPIS ;;OATOTEKE /BIH Slika 2.5 Primer diskovne strukture KAZALO ' RAZŠIRJENI OPIS DATOTEKE BICF1LE.DAT OPIS : : DATOTHKß;;:; KAZALCI NA RArslRJEMIijOPIS SEKTORJI 000 - on? -> SEKTORJI 100 - 2FP SEKTORJI SOO - 4F» SEKTOR 100 SEKTOR lllf 1 SEKTOR 30C ÄllW'ä: SDCTOR 4AB [ SEKTOR OOO I. SEKTOR 002- : :SEKTORJI SO FIZIČNI SEKTORJI NA DISKU (IK) ! i VSi: NASLOVI SO V HDCADECIMAINE« ZAPISU v Slika 2.6 Primer zelo velike datoteke Laataoat CP/K MS-DOS ?IUtS-U FENä vfllikost kaisla onajcna oawjana la datotak glavno kaialo *a ItSX*ll naoMjao« velikost taplsa v kaialu 32 bytov 32 bytov 16 byte» 1« byto» dravesna atruktura kaiala HE DA NB la RSX-11 DA I a VMS M zapla položaja daCotaka na dlaku v kazalu varia» (FAT) V ULK HEADES Mkaiaalna veUkoat datotak« 32H bytaa valikoat diaks vallkoat diaka 6«H bjrtas globina kaiala IBiilii naonajano i ja BM-U naowiano stavilo uporabnikov 16 iliiiiliiiiiiilii MX >a REX-ll naoaajaoo VMS 2Si taacita datotak HE NE DA DA caaovna omaka LA (2) DA (J) DA (4) DA <4} oanovna enota dodeljavanja proatora 2-4K 1-4X O.SK IK Opomba : Otnaka naonajano ponani. la naao priMrJavo nacaa da Ina paranatar lano valika. tako valiko «radnoat. <)a ja Slika 2.7 Primerjava diskovne strukture sistema FENIX z drugimi operacijskimi sistemi 3. Struktura operacijskega sistema FENIX 3.1 Uvod Operacijski sistem FENIX je samostojen program, ki teče v glavnem računalniku mreže DANTE/NET. Njegova edina naloga Je odgovarjati na zahteve drugih računalnikov v mreži. Glavna zanka operacijskega sistema Je zato zasnovana tako Inltlilla* Sy>t«a Kapait 6«t D«tifork neaiag« frocMs »•■•g« ««Dd itatiforh »»ag« Until Shutdown B^qiMst SbutOoiA CIStM Hiiil.t CPU Ce bi hoteli doseči večjo efektivnost dela, bi morali implementirati paralelnost procesov PROCESS_MESSAGE, kar bi pomenilo, da operacijski sistem hkrati streže več dostopom do diska. Operacijski sistem lahko razdelimo v več modulov : - komunikacija z DANTE/NET mrežo - izvajanje DOS funkcij - dodeljevanje in vzdrževanje vmesnikov - krmilnik diskovnih enot Slika 3.1 Glavna zanka operacijskega sistema Uporsbnl.»)«! p»k«t ■.fflBSHlK ZA DSW t Dfjrm/VKI MRZZO VHBSMIK NA Disxowa KNOTB —> OBBB^RVA OOS yuiKciJ roiix odQovor r»br«iil podatki Zahtav« «lanant (tmllKa FCB. XPC3B Bum» ttsvlil« auKreR-j« lX»EUaVAIUS DIRMUCHIK STwnen« Slika 3.2 Razdelitev operacijskega sistema FENIX 3.2 Opis posameznih modulov 3.2.1 Komunikacija z DANTE/NET mrežo Naloga tega modula je sprejem in oddaja paketa v DANTE/NET mrežo. Mreža sama je collision-avoidance mreža tipa Ethernet, uporabljen protokol je SDLC. Paket sam Je sestavljen iz več delov : - krmilne informacije (sprejemnik, - opis DOS funkcije - parametri za DOS funkcijo - kontrolni seštevek oddajnik) Ko modul za komunikacijo z DANTE/NET mrežo sprejme paket, zasede v pomnilniku 256 bytov velik blok, ki ga uporablja za shranjevanje paketa z mreže in za shranjevanje vseh sistemskih spremenljivk, ki Jih potrebuje DOS za obdelavo te DOS funkcije. Ko je paket uspešno sprejet, ga modul preda modulu za obdelov DOS funkcij. Po izvršeni DOS funkciji modul prejme izhodni paket, ki ga pošlje računalniku, ki je zahteval DOS funkcijo. Parametri za DOS funkcijo so lahko : - FCB ID -- številka FCB - Ja, ki opisuje datoteko, s katero hoče uporabnik delati. FCB ID je sestavljen iz dveh bytov : številka FCB - Ja in zaporedna številka dostopa do tega FCB-j a, s pomočjo katere se kontrolira pravilnost dostopa in preprečuje branje datotek drugih uporabnikov - Številka zapisa v datoteki, ki ga hočemo brati ali pisati - Celoten FCB, kot ga podpira CP/M (16 bytov) - Zastavice v CP/M FCB-ju - DMA področje (vsebina zapisa, ki ga beremo ali pišemo) Poleg teh parametrov lahko sistem FEN1X uporabniku še : - status DOS funkcije vrne operacijski 3.2.4 Krmilnik trdega diska Modul skrbi za povezavo ostalega operacijskega sistema z diskovnimi enotami. Modul kliče modul za dodeljevanje in vzdrževanje vmesnikov v sledečih primerih : - ko zahteva branje novega sektorja z diska - ko zahteva zapis sektorja na disk v primeru, ko zmanjka vmesnikov - ko zahteva zapis sektorja na disk ob periodičnem čiščenju sistemskih vmesnikov 3.3 Sistemske podatkovne strukture Operacijski sistem FENIX potrebuje za svoje delovanje naslednje podatkovne strukture : - vmesnike za delo z diskom - opis odprtih datotek (FCB) - opis večkratno odprtih datotek (XFCB) - opis uporabnikov (USER) - opis diskovnih enot Vse dinamične podatkovne strukture (vmesniki za delo z diskom, FCB in XFCB) se dinamično dodeljujejo in odvzemajo ob prezasićenosti sistema. Operacijski sistem vodi za te tri dinamične strukture statistiko njihove uporabe (LRU algoritem), tako, da lahko po potrebi odvzame najmanj uporabljan element. LRU algoritem je realiziran s pomočjo vrste : - ob kreiranju se element postavi na začetek vrste - ob vsakem dostopu operacijski sistem premakne element na začetek vrste - LRU element je element na koncu vrste Opisan algoritem je enostaven za realizacijo in daje dovolj dobre rezulta-fce. 3.3.1 Opis odprtih datotek 3.2.2 Izvajanje DOS funkcij Modul skrbi za izvajanje vseh DOS funkcij, ki jih drugi računalniki zahtevajo po mreži. V inicializaciji podatkovnih struktur modul prepiše podatke o uporabniku v začasne spremenljivke ter določi logični disk, s katerim uporabnik dela in njemu pripadajoči fizični disk in direktorij. ftet network packet Inltlallie dat« «trueture* Zf error then Send reject pecket «Ike Proce** BOS CluictloB Send reeult paeliet Slika 3.3 Osnovna struktura modula za izvajanje DOS funkcij Po končani inicializaciji modul preko tabele kliče ustrezno DOS funkcijo, ki obdela uporabnikovo zahtevo in zgradi paket, ki ga modul preko komunikacijskega modula vrne uporabniku. 3.2.3 Dodeljevanje in vzdrževanje vmesnikov Modul skrbi za dodeljevanje in vzdrževanje vseh dinamičnih sistemskih podatkovnih struktur : - vmesniki za delo z diskom - opis odprte datoteke (FCB) - opis večkratno odprte datoteke (XFCB) Natančen algoritem dodeljevanja teh struktur je opisan v razdelku SISTEMSKE PODATKOVNE STRUKTURE. Type PHe_^Conl:rol_Blocl( - Record Olsc Drive : Byte . rile'Kaoio ! Strinu (8) Ftle~Type , : Strino (3) ■ -Setiuonce^Nuniber:. : Integer Pirat Deäcrlptor : Integer Flrat~Buff«c 1 Byta Current_Be»«lptor Integar Current^Butfer : Byte - ' ''' ■ ; VCB Sefliaphore ; Byte ii Hejct Pointer ■ I Integer ■ Prev^Potntec ; Intarlar ■ ■ • h Protection ; Byta : 'i ■ / »oda ID . Byte ■ i:- PCB_Pl.as» • Byte Kcceea Count : Byte . End : Slika 3.4 Opis odprte datoteke Opis posameznih polj : Disc Drive diskovna enota, na kateri File Name diskovna enota, odprta datoteka ime datoteke je File_Type tip datoteke Sequence_Nurober zaporedna številka uporabe tega elementa. Ko operacijski sistem odvzame FCB uporabniku, ki ga že dolgo ni uporabljal, poveča sequence number in tako onemogoči ponovno uporabljanje odvzetega FCB-ja Fir8t_Desoriptor Številka sektorja na disku, ki vsebuje opis datoteke First_Buffer Številka vmesnika, ki vsebuje opis datoteke ali O, če opisa datoteke ni v spominu Current_Descrlptor Številka sektorja na disku, ki vsebuje razširjeni opis datoteke za zadnji prebrani sektor. Tp polje se uporablja le če beremo datoteke, ki. so večje od 256K . bytov, drugače je enako First_De8criptor Current_Buffer Številka vmesnika, ki vsebuje sektor, na katerega kaže Current_Descriptor. Ce tega sektor J a ni v spominu, vsebuje to polje O. FCB_Seraaphore neuporabljeno Next_Pointer Prev_Pointer Kazalci za algoritma implementacijo LRU Protection bit O — 3 zaščita datoteke, ki je odvisna od zaščite datoteke v opisu datoteke in uporabnika in grupe računalnika, ki je odprl datoteko, bit 4—7 dodatni atributi datoteké Nođe_lD Številka računalnika, odprl datoteko ki Je FCB_Flags Zastavice, ki povedo stanje FCB-ja bit 7 FCB je zaklenjen v spominu bit 6 polje First_Descriptor Je OK bit 5 FCB je neveljaven bit 4 FCB je uporabljen Access_Count Števec dostopov do FCB-Ja. Števec se poveča ob vsakem OPEN ukazu in zmanjša ob vsakem CLOSE ukazu. Ko doseže vrednost števca O, operacijski sistem izvede dokončno CLOSE datoteke. 3.3.1.1 Dodeljevanje FCB-jev Operacijski sistem zahteva nov FCB ob DOS funkciji, ki mora za svoje delo odpreti novo datoteko (OPEN, MAKE, DELETE, RENAME, GET FILE SIZE ipd.). Ce je na razpolago prost FCB, ga modul za dodeljevanje vmesnikov zaseže, vpiše v FCB_FLAGS bit 7 in 4 ter ga vrne DOS modulu. Ce operacijski sistem ne more najti prostega FCB-ja, poišče zadnji FCB v listi, ki ni zaklenjen v spomin, zapre datoteko, ki ji ta FCB pripada in ga vrne DOS modulu. Da bi preprečili dostop do tujih podatkov in zlora^ operacijskega sistema, poveča operacijski sistem ob vsakem OPEN klicu polje SEQUENCE_NUMBER v FCB-ju. Ce hoče uporabniški program brati ali pisati datoteko, mora poleg številke FCB-ja v paketu, ki ga pošlje preko mreže podati še zaporedno številko v FCB-ju. Ce se ti dve številki ne ujemata, je bila datoteka medtem zaprta in uporabniški program mora ponovno izvršiti OPEN klic. Ta protokol je implementiran že v mrežnem delu CP/M operacijskega sistema ha ostalih računalnikih v mreži in je tako za končnega ujJorabnika neviden. Ker bi lahko uporabnik uganil pravilno zaporedno številko v FCB-ju primerja operacijski sistem poleg zaporedne številke še številko vozliSča s katerega je bila datoteka odprta in številko vozlišča s katerega je.prišla zahteva za branje oz. pisanje Operacijski sistem vzdržuje v vsakem FCB-ju polje AccessCount ki šteje število OPEN klicev izvršenih na tem. FCB-ju. Ko je polje Access_Count pri CLOSE klicu enako O, lahko operacijski sistem izvrši dokončen CLOSE datoteke. Operacijski sistem tedaj sprosti FCB, ki je pripravljen za naslednji OPEN klic. Ce več uporabnikov hkrati odpre isto datoteko, vrne operacijski sistem prvemu uporabniku številko FCB-Ja, s katerim je odprl to datoteko, za vse naslednje uporabnik pa uporabi operacijski sistem novo podatkovno strukturo XFCB. Takšen algoritem omogoča vodenje evidence o odpiranju datotek in preprečuje izgubo podatkov zaradi brisanja in hkratnega branja oz. pisanja datoteke (če bi vodili le evidenco o prvem vozlišču, ki Je odprlo datoteko, bi lahko zbrisali datoteko, ki jo dosega več uporabnikov ali pa bi preprečili brisanje datoteke, ki Jo je en uporabnik večkrat odprl). S stališča uporabniškega programa se XFCB ne razlikuje od FCB-ja, razlika Je le v tem, da ima XFCB zaporedno številko od 128 do 255. Opomba Dodeljevanje FCB-jev Je še oteženo zaradi slabega sloga programiranja v večini CP/M programov, ki praviloma ne zapirajo datotek, ki Jih ne rabijo več, tako, da mora operacijski sistem hevristično določati katere datoteke program še uporablja in katere lahko zapre. Napake v tem hevrističnem procesu privedejo do ponovne uporabe zaprte datoteke in ponovnega OPEN klica, ki Je, kot smo že poudarili, neviden za uporabniški program. 3.3.2 XFCB — opis večkrat odprte datoteke Typ« K]it«nd*d FCB Kod« IB rCB ÌB En4 : Sceärd : Bjft« • 9yt. Slika 3.5 Struktura XFCB - Ja Operacijski sistem kreira enega ali več XFCB za vsako datoteko, ki jo hkrati odpre več kot en uporabnik. Prvi uporabnik uporablja za dostop do datoteke številko FCB-ja, vsi naslednji uporabniki uporabljajo za dostop do datoteke številko XFCB-ja, ki kaže na pravilni FCB. S takšnim pristoik>m Je omogočeno vođenje natančne evidence o odpiranju datotek, poleg tega Je število uporabnikov, ki lahko hkrati odprejo eno datoteko neomejeno. 3.3.2.1 Dodeljevanje XFCB : Operacijski sistem dodeli nov XFCB vsakič ko uporabnik poskuša odpreti datoteko, ki jo Je že odprl drug uporabnik. Ce modul za dodeljevanje vmesnikov ugotovi, da ne more dobiti prostega XFCB-ja, odvzame enega od uporabljenih XFCB-jev, zapre FCB, ki ga je ta XFCB naslavljal (in tako zmanjša ACCESS_COUNT) in vrne nov XFCB modulu za obdelavo DOS funkcij. . Ob CLOSE ukazu operacijski sistem sprosti XFCB in izvede CLOSE ukaz na ustreznem FCB-ju. Obdelava odvzetih XFCB-jev, ki jih uporabnik hoče ponovno uporabiti je enaka kot za odvzete FCB-Je. 3.3.3 Vmesnik za delo z diskom ìityp* »i'k Diir(«r • Bacgrđ Driva : Byt« bPyt* fr«» ?pint«)t ; ftjt» C(Mmt ; l^t* Writtan_H«B ; Byte m«8» ! Byt« End : Sllka 3.6 Struktura vmesnika za delo z diskom Polji Drive in LoglcaX_Block opredelita diskovno enoto In zaporedno Številko sektorja na tej enoti. Polji Next_Polnter in Prev_Pointer služIta za implementacijo LRU algoritma? Polja Access_Count služi za štetje števila dostopov do tega vmesnika. Polje Wrltten_F\ag služi"-za indikacijo vpisovanja v ta vmesnik in vsebuje 1 bit za vsak logični blok (128 bytov) znotraj fizičnega sektorja (1 K byte). V polju FLAGS operacijski sistem hrani stanje tega vmesnika : Bit 7 Vmesnik je zaklenjen v spomin Bit 6 Vsebina vmesnika je spremenjena Bit 5 Modul za povezavo z diski piSe vmesnik na disk Bit 4 Vmesnik bo zamenjan Bit 3 Modul za povezavo z diski bere vmesnik z diska Bita 5 in 3 služita za sinhronizacijo med modulom za delo z diskovnimi enotami in ostalimi moduli operacijskega sistema, saj bi se ob uporabi prekinitev in zakasnjenega pisanja na disk zlahka zgodilo, da bi modul za obdelavo DOS funkcij uporabljal vmesnik, ki še ni bil prebran z diska ali ki se ravnokar vpisuje na disk. Bit 4 služi za sinhronizacijo med modul za dodeljevanje vmesnikov in modulom za obdelavo DOS funkcij, saj preprečuje uporabo vmesnika, ki ga bo modul za dodeljevanje vmesnikov zamenjal. Opisi vmesnikov so zbrani v tabeli, ki vsebuje 256 elementov, sami vmesniki se nahajajo v ostanku spomina ali v drugih spominskih bankah v mikroračunalnikih, ki imajo več kot 64K bytbv spomina. 3.3.3.1 Dodeljevanje vmesnikov : Modul za obdelavo DOS funkcij zahteva določen logični blok z diska. Ce je ta blok že v enem od vmesnikov, ga modul za dodeljevanje vmesnikov vrne in ga premakne v LRU vrsti, drugače poišče modul za dodeljevanje vmesnikov prost vmesnik in zahteva branje tega vmesnika z diska. Če modul za dodeljevanje vmesnikov ne more najti prostega vmesnika, poskuša najti popolnoma .zapisan vmesnik (Written_Flag = 255) in ga zapiše na disk, zahteva branje vmesnika in ga vrne. če nobeden od vmesnikov ni popolnoma poln, modul zapiše na disk prvi dostopen vmesnik in zahteva branje novega vmesnika. Če so vsi vmesniki zasedeni (LOCKED), modul sprosti vse vmesnike, ki so bili dodeljeni odprtim datotekam za opis datoteke in označi v vseh FCB-jih, da niso več pravilno nastavljeni. Po tej operaciji modul ponovno poskuša dobiti prazen vmesnik s pomočjo zgornjih treh točk. Če je med iskanjem vmesnika modul za dodeljevanje vmesnikov zašel pregloboko v listo vmesnikov, torej je so vmesniki že precej zasedeni, bo modul zahteval zapis vseh popolnoma vpisanih vmesnikov (Writteh_Flag = 255) na disk. Ce na ta način ne pridobi dovolj vmesnikov, bo modul zahteval še zapis vseh delno napolnjenih vmesnikov na disk. Ob hkratnem delu modula za delo z diskovno enoto in ostalega operacijskega sistema ter dovoljšnjera številu vmesnikov (več kot 128) lahko s tem algoritmom'dovolj zgodaj ugotovimo možno zasičenje sistema in zahtevamo vpis polnih vmesnikov na disk preden pride do popolnega zasičenja sistema. Takšno vpisovanje vmesnikov na disk poteka hkrati z ostalim delom sistema in dela sistema praktično ne prekinja. Zapisovanje vmesnikov na disk ob zasičenju sistema blokira sistem do konca zapisovanja in tako zmanjša hitrost delovanja sistema. 3.3.4 Opis uporabnika Vsako vozlišče, ki se lahko pojavi v mreži, ima v glavnem računalniku ustrezno podatkovno strukturo, ki definira uporabnika, ki dela na tem vozlišču. V tej podatkovni strukturi so zbrani vsi podatki o uporabniku, ki jih operacijski sistem potrebuje za svoje delo : - Ime uporabnika Tjp« U»«r a«:or4 - Hoeort Uiac iidJM' : ìtxlDgi I Byte W.t«l5«t» «»»r tO ä tet«-iu.i:«r&at« Croiip tS'. Byt« Sfe^tlv»-«»«:,» ; Byt« SCCaetlv* Grou« ID: Byt« " lataflor Di»a T«bl« -.'Xnij {0..31) ot Secord ; " , Dl»e Syt« PiiTAt Descriptor : lj»teo«r' Fnitačtion Hod« ; Byte Enđ ; Knđ ! Slika 3.7 Opis uporabnika - USER_ID in GR0UP_1D Sta polJi, ki ju sistem uporablja ob določanju zaščite datoteke proti določenemu uporabniku - ALTERNATE_USER_ID in ALTERNATE_GROUP_ID sta polji, ki ju sistem uporablja za shranjevanje USER_ID In GROUP_ID v primeru, ko uporabnik s pomočjo privilegiranega ukaza menja svoj USER_ID. - EFFECTIVE_USER_ID in EFFECTIVE_GROUP_ID sta polji, ki ju operacijski sistem uporablja za shranjevanje USER_ID in GROUP_ID ob zagonu programa, ki začasno menja USER_ID in GROUP_ID na svoj USER_ID in GROUP_ID. Takšen program lahko izvaja privilegirane funkcije tudi za navadnega uporabnika. - PRIVILEGE_MASK vsebuje definicijo privilegijev, ki jih ima uporabnik, torej seznam vseh zaščitenih operacij, ki jih uporabnik lahko izvaja. - DISC_TABLE' vsebuje preslikavo logičnih diskov v poddirektorije. Vsak element tabele vsebuje opis enega logičnega diska (A: do P: so stalni, ostali ostanejo samo za čas delovanja programa) in sicer : - diskovna enota, kjer se nahaja logični disk - kazalec na opis direktorija, ki ustreza logičnemu disku - zaščita direktorija, kot jo določi operacijski sistem ob OPEN klicu S pomočjo tabele logičnih diskov lahko operacijski sistem zelo enostavno določi s katerim poddirektorijem hoče uporabnik delati, saj mu ni treba ponovno izvajati OPEN ukaza. 3.3.5 Opis diskovne enote type Di«k Deecriptiop - RBcord Oriv« . Byt« : Byt» Volu««_H««e Strina (8) Hoot_De«criptor j jBt*0*r Blt«ap_0«rcript6r Intofler Btt«ap""81»» nlsnount Flag TMt Drrtlna DOS Inlt COsiKnttv eitaap rtm Blt»«p~Count HltMp~Bu(fBr »itMp Pointer» End : »Tt» : Byt« ; I»t*o«r : Inte««r Jnc«««r t Brt« Byt» Integer ; Array (O.,7) of Inteoer Slika 3.8 Opis diskovne enote Opis diskovne enote vsebuje vse informacile ki jih operacijski .sistem potrebuje za deli z diskom : - ime diska (samo za informacijo uporabnika) - kazalec na opis glavnega kazala - kazalec na opis tabele zasedenosti diska in . njena velikost - naslov procedure za - testiranje prisotnosti diska - inicializacijo diska - izvedbo DOS funkcije na tem disku - Polja za vnaprejšnje dodeljevanje prostih sektorjev Naslova procedure za inicializacijo diska in izvedbo DOS funkcije na disku omogočata modularno izvedbo diskovnega operacijskega sistema in celo uporabo večih diskovnih struktur na različnih diskih (npr. CP/M na disku A:, FENIX na disku B:). Operacijski sistem deluje dokaj hitro v primerjavi z drugimi mrežnimi operacijskimi sistemi realiziranimi v 8 bitni tehnologiji precej zaslug za to nosi izredno hitra lokalna mreža DANTE/NET (hitrost prenosa IM bit/s). Ob testiranju se Je operacijski sistem obremenjen s stirimi delovnimi postajami izkazal za hitrejšega kot delo na sami delovni postaji z disketo, torej Je njegova uporaba vsekakor upravičena. Ob razvijanju operacijskega sistema se le rodilo nekaj idej, ki so vredne razmisleka in morda implementacije v naslednji verziji operacijskega sistema : - podpora zaklepanja zapisov v datotekah, ki bi na sistemskem nivoju rešila problem hkratnega dostopa v bazo podatkov. - integracija večih diskovnih pogonov v eno diskovno strukturo kot jo pozna UNIX operacijski sistem (MOUNT in UMOUNT ukaz) - podpora datotek, ki bi se raztezale preko večih diskov. Tako bi lahko dosegli do 128M bytov velike datoteke brez spreminjanja diskovne strukture, ob manjših spremembah pa bi lahko dosegli še bistveno večje datoteke (cca. 4G byte). - implementacija večih diskovnih struktur v okviru enega operacijskega sistema (npr. en CP/M disk in en FENIX disk) - implementacija zahtevnejše diskovne strukture (npr. FILES-Ü level 2) Za implementacijo zadnjih ciljev bi bilo bolje uporabiti modernejšo tehnologijo kot Je Z80 procesor, saj nam Je 8 bitna tehnologija že ob razvijanju FENIX operacijskega sistema postavljala precej omejitev, predvsem zaradi omejitve naslovnega prostora na 64K bytov. 3.3.5.1 Dodeljevanje prostih sektorjev : Ko modul za obdelavo DOS funkcij zahteva prosti sektor na disku, skuša modul za dodeljevanje vmesnikov to zahtevo najprej zadovoljiti s pomočjo vnaprej zavzetih sektorjev v spominu. Ce to ni možno, modul dodeli sektor s pomočjo tabele prostih sektorjev in dodatno zasede še 254 sektorjev, ki jih bo uporabil pri naslednjih zahtevah za dodelitev praznega sektorja. Ta način dodeljevanja spomina precej izboljša dodeljevanje novih sektorjev na disku, saj v trenutku, ko je podatkovni sektor tabele prostih sektorjev v spominu skuša le-tega čimbolje izkoristiti. Tako zahteva dodeljevanje novih sektorjev dostop do diska le na vsakih 256 sektorjev, vmesnik, ki bi drugače hranil tabelo prostih sektorjev pa je lahko v vmesnem času sproščen. Ob brisanju datoteke skuša modul za dodelle-vanje vmesnikov vključiti novo sproščeni vmesnik v seznam vnaprej dodeljenih vmesnikov. Ta operacija uspe le v primeru, ko je seznam dodeljenih vmesnikov dovolj prazen in ko le sprosceni sektor dovolj blizu začetka diska. Ta zadnji pogoj preprečuje vnašanje sektorjev globoko znotraj diska v tabelo vnaprej dodeljenih sektorjev in tako zmanjša gibanje glave po Literatura : (1) Možnosti in nemožnosti mikroračunalnika DIALOG,Elektrotehniški vestnik. April 1987 (2) Peterson, Silbershatz, Operating system Concepts, Addison - Wesley 1983 (3) Comer, Operating System design, the XINU Approach, Prentice - Hall 1984 (4) XENIX operating system, Microsoft 1986 (5) VAX/VMS V4.0 operating system, equipment corporation, 1985 (6) IBM DOS 3.2 Technical Reference Manual IBM Corp., 1985 (7) IBM DOS 2.0 Manual, IBM Corp. 1983 (8) Hyman, Memory resident utilities, interrupts and disk management, MIS 1986 corp.. Digital 4. ZAKLJUČEK Operacijski sistem FENIX smo uspešno implementirali na mikroračunalniku DIALOG z lOM bytnim trdim diskom. Za delo z operacijskim sistemom je bil razvit poseben interpreter ukazov in podporni programi, ki so ekvivalentni UNIX podpornim programom, tako, da celota FENix operacijski sistem in SHELL interpreter ukazov uspešno predstavljata UNIX - združljivo okolje v 8 bitni tehnologiji. • SISTEMSKI UPORABNIŠKI VMESNIK ZA 8-BITNI UNIX ZDRUŽLJIV OPERACIJSKI SISTEM UDK 681.3.06 Marjan Bradeško Ljubo Pipan Ivan Pepelnjak Nikolaj Zimic Fakulteta za elektrotehniko, Ljubljana Izvleček Članek opisuje izboljšavo 8-bitnega operacijskega sistema do te mere, da ga uporabnik z vidika sintakse vidi kot operacijski sistem Unix. Navedene so nekatere splošne značilnosti novega sistema, natančneje pa je opifean visokonivojski sistemski vmesnik, ki je v veliko pomoč uporabniku pri pisanju sistemskih uslužnostnih programov. S tem ima uporabnik sam možnost širiti nabor ukazov, ki predstavljajo vez med njim in operacijskim sistemom. Z že obstoječimi programi in zunanjim videzom predstavlja opisani operacijski sistem korak naprej pri prehajanju na bistveno zmogljivejše in bolj fleksibilne sisteme kot je CP/M, na osnovi katerega sloni nadgradnja, opisana v pričujočem članku. Abstract The paper presents the improvements of an 8-bit operating system to Unix - compatible environment as seen through userlevel command line interface. We are describing some general features of the new operating system along with high - level system interface, which help the system programmers in writing new system utilities. With this aid, the end user can write his own utility programs, which represent the link between end-user and operating system environment. Existing programs can run under simulated CP/M environment, so this operating system represents a significant link between existing 8 bit operating systems and new UNIX - based systems. 1. UVOD Doba 8-bitnih mikroračunalniških sistemov počasi mineva, hkrati z njimi pa se umikajo tudi operacijski sistemi, napisani zanje. Razvoj gre v smeri 16- in 32-bitnih sistemov. Temu ustrezno se prilagajajo tudi operacijski sistemi. Uporabnik, ki bi rad na hitro prešel iz 8-bitnih na novejše sisteme, se znajde pred težavo. Aplikacijska programska oprema je vsa napisana na kožo njegovemu 8-bitnemu operacijskemu sistemu in običajno ni enostavno prenosljiva na nove sisteme. S tem problemom in z eno od uspešnih razrešitev le-tega se bomo ukvarjali v pričujočem članku. Pri našem delu smo izhajali iz 8-bitnega mikroračunalniškega sistema z operacijskim sistemom CP/M. Sisteme smo povezali v lokalno mrežo z enim glavnim računalnikom s trdim diskom kapacitete 20 M. Glavni računalnik skrbi izključno za nadzor mreže, v katero Je lahko povezanih do 16 postaj z dvema gibkima diskoma, ki imata vsak kapaciteto po 800 K. Prenos po mreži poteka po koaksialnem kablu (hitrost 1 Mbit), tako da je dostop iz katerekoli postaje do trdega diska glavnega računalnika hitrejši kot dostop na lokalni gibki disk postaje. S tem smo bistveno izboljšali performanse samega mikroračunalnika. S spremembo operacijskega sistema pa smo dobili sistem, ki navzven daje povsem drugačen videz od 8-bitnih sistemov. Uporabnik ga namreč z vidika sintakse vidi kot operacijski sistem UNIX, ki pa je že domena 16-in 32-bitnih sistemov. Pri vsem tem je v ozadju še vedno CP/M, tako da uporabnikova aplikacijska oprema ne potrebuje nobenih sprememb, hkrati pa je sistem zaradi povezave v mrežo in Unix-ove sintakse bistveno bolj fleksibilen. Operacijski sistem na glavnem računalniku je povsem nov, na postajah pa je le modificiran CP/M. Pred BDOS Je namreč dodan modul, ki ugotovi, če Je neka sistemska funkcija rešljiva v okviru postaje, ali pa je potrebna intervencija glavnega računalnika. V tem primeru postaja pošlje zahtevo po servisiranju NDOS (Network DOS) funkcije v mrežo. Operacijski sistem na glavnem računalniku je večuporabnlški in večposlovni, servisiranje zahtev je rešeno s čakalnimi vrstami. Tudi podatkovne strukture na trdem disku so drugačne od CP/M struktur. Spremenjen je FCB (Fila Control Block) in zaradi drevesne strukture direktorijev tudi directory entry. Direktoriji so namreč datoteke, katerih elementi so imena datotek v direktoriju in kazalci na opise (des-kriptorje) teh datotek. Operacijski sistem CP/M dela z datotekami na fizifinih diskih A: oziroma B: (v primeru dveh pogonov), naš sistem pa za delo z datotekami uvaja logične diske. Če torej hočemo nek direktorij brati oziroma kaj pisati po njemu, mu moramo najprej prirediti enega od logičnih diskov. Šele potem so nam dostopne datoteke, ki se na njem nahajajo. Logični diski so vsi s številkami 3-32 (diski C:, D:, itd). Poleg standardnih Unix-ovih poddirektorijev /bin, /usr, /etc in /tmp imamo še dva poddirek-torija /Ica - 'local A:' - CP/M diskovni pogon A: /Icb - 'local B:' - CP/M diskovni pogon B: V same podrobnosti jedra operacijskega sistema se tukaj ne bomo spuščali, ponovno poudarimo le to, da lahko poganjamo vso aplikacijsko programsko opremo, ki teče pod CP/M. Povejmo še, da za uspešno prehajanje med podatkovnimi strukturami CP/M postaje in glavnim računalnikom skrbita posebni proceduri Input Formatter in , Output Handler operacijskega sistema na glavnem računalniku. Pri našem opisu bomo ostali na nivoju vmesnika med uporabnikom in sistemom, kajti prav tu Je najbolj fleksibilno mesto. Uporabnik ima namreč možnost širiti sistem s sistemskimi uslužnostnimi programi, ki jih je zaradi ustreznih orodij, ki Jih ponuja nov sistem, zelo enostavno pisati. Podali bomo opis vmesnika, nekaterih sistemskih parametrov in na kratko naSteli In opisali doslej napisane sistemske uslužnostne programe. Uporabniški vmesnik Je napisan v visokoni-vojskem programskem Jeziku Turbo Pascal kot knjižnica uporabnih procedur, ki jo vključimo s stikalom ( $I ime_knjižnlc6 ) v naš program. Izraz program bo odslej krajši izraz za sistemski uslužnostnl program. 2. OBDELAVA UKAZNE VRSTICE Interpreter ukazne vrstice (Command Line Interpreter) ni več sestavni del jedra operacijskega sistema, pač pa omogoča povezavo uporabnika s samim sistemom. V operacijskem sistemu CP/M se omenjeni interpreter imenuje CCP (Console Command Processor), pri Unixu pa je to Shell. Shell prebere ukazno vrstico, ugotovi, za kateri ukaz gre in nato kliče ustrezni program, ki izvede ukaz v skladu s parametri v ostanku ukazne vrstice. Omeniti velja, da so tako kot pri CCP tudi v Shell nekateri ukazi že vgrajeni in Jih ni potrebno zaganjati kot ukazne datoteke (podaljšek .COM). Vsaka ukazna vrstica vsebuje ime ukaza, zastavice za morebitne opcije, argumente k zastavici in ostale ukazne argumente. 2,1 Inicializacija Ob vstopu v nek program nimamo na voljo nobenih podatkov o ukazni vrstici, natančneje o njenem ostanku (command tail). Začetek vsake ukazne vrstice je vedno ime ukaza - programa. Ta program mora potem, ko se zažene, dobiti vse informacije, potrebne za uspešno izvrštev ukaza. Vse informacije pripravi procedura INIT, ki jo pokličemo z: INIT (flags_'with_arguments) kjer Je flags_with_arguments niz dolžine 20 znakov, v katerem navedemo zastavice (drugo poleg druge) za opcije, ki v tem ukazu zahtevajo tudi argument. Omenjena procedura zgradi množico zastavic (vključno z morebitnimi argu- menti'), ki Jih najde v ukazni vrstici, zgradi pa tudi seznam ostalih argumentov in izvede primerjanje vzorcev (pattern matching), če Je to potrebno - v primeru, da ukaz deluje nad več datotekami. Kot primer si poglejmo začetek programa tali, ki izpiše zadnjih n vrstic (znakov, blokov) datoteke ali pa preskoči prvih n vrstic (znakov, blokov) datoteke in Jo nato izpiše do konca. Ukaz tali ima lahko štiri opcije (p, 1, b, c), od katerih tri zahtevajo argumente (1-število vrstic, b-število blokov in c-število znakov). Slika 2.1 Inicializacija branja opcij 2.2 Zastavice za opcije V različnih programih nastopajo najrazličnejše opcije. Procedura INIT zgradi ustrezne strukture, ki Jih lahko pregledujemo z nekaterimi funkcijami in procedurami. Za testiranje prisotnosti neke opcije (zastavice za opcijo) je na voljo funkcija TEST_FLAG, ki vrne vrednost true, če je opcija v ukazni vrstici prisotna, sicer pa false. Za testiranje vrednosti argumenta, ki ga neka opcija zahteva, pa Je na voljo funkcija FLAG_VALUE, ki vrne niz dolžine 40 znakov, če je argument prisoten in prazen niz, če argumenta ni (v primeru, da želimo argument pri opciji, ki ga sploh ne zahteva). Pokličemo Ju z : TEST_FLAG (flag) in FLAG_VALUE (flag) kjer je flag ena od zastavic tipa char. Kot primer si spet vzemimo del programa tail. begin ir TEE* TLUB Cb') tbsn Mb :> FLAG VAU/B ('b') Nila Block« StrToInt (NI» : iBiiililiiiilllB^^^ Slika 2.2 Testiranje zastavic Gornji primer preveri, če je prisotna opcija b (število blokov) in v niz Nb vrne število blokov. 2.3 Argumenti V ukazni vrstici se poleg opcij ih njihovih argumentov pojavljajo še razni drugi argtunenti kot so npr. poti, imena datotek, itd. Programerju so dostopni preko spremenljivke ARGC, ki pove, koliko Je teh argumentov, in funkcije ARGV, ki Jo pokličemo z : ARGV (Arg_No) Spremenljivka Arg_No Je celoštevilska in pomeni zaporedno številko argumenta v ukazni vrstici, ki ga vrne funkcija ARGV. Sem seveda štejejo tudi argumenti, ki Jih generira proces primerjanja vzorcev, v primeru, da ukaz deluje nad več datotekami, ki Jih podamo kot vzorec. Kadar so argumenti datoteke, dostikrat rabimo tudi funkcijo GET_PROT, ki n^ vrne ustrezno zaščito datoteke (ki smo jo dobili s funkcijo ARGV) kot celo število. Ce gre za lokalni CP/M direktorij, je zaščita -1, sicer pa velja naslednja shema : Za izločanje imena datoteke iz podane poti obstaja Se druga funkcija, katere opis bo podan kasneje. Slika 2.3 Zaščita datoteke štirje biti (1 nibble) imajo pri tipu datoteke (Type) naslednji pomen) : bito - datoteka je/ni direktorij biti,2,3 - nepomembni Pomen bitov pri zaščiti datoteke (World, Group, User) pa je naslednji : bito Read navadno datoteko lahko beremo, ne moremo pa Je izvajati kot program (onemogočen zagon podatkovne datoteke) biti Write navadno datoteko lahko spreminjamo; direktorij lahko spreminjamo (REN, DEL) bit2 Execute datoteko lahko izvajamo kot program,-v direktoriju lahko odpiramo datoteke bits Delete datoteko lahko brišemo Uporabo zgoraj opisanih funkcij pokaže naslednji del programa, ki izpiše vse argumente in pri tistih, ki so direktoriji, to posebej označi. Omeniti velja še, da funkcija Argv vrača celoten argument tudi v primeru, da Je argument neka pot z vzorcem. Primer : IliKli^liilliiiliiiiiipiiiii it AROC o o then cat Arg Ho 1 to ABGC do begin Wrlt«~(MOV (AmHo)) ; it GET TBOT and IlOOO 0 than Hrle« ('«DIK)') Writ*}» : ^iiiil^lli^BliÄSüii^^lBI Slika 2.4 Branje zaščite datotek /usr/includo/*.pas Argv po primerjanju vzorcev vrača arg\unente v obliki : /usr/include/fol.pas /usr/include/tail.pas /usr/include/head.pas 3. DELO Z LOGICiJIIMI DISKI Kot smo že večkrat omenili, moramo direktorije prirediti logičnim diskom, če hočemo delati z njimi oziroma z datotekami na njih. Zato je v knjižnici na voljo nekaj procedur oziroma funkcij, ki omogočajo omenjene akcije. Imena vseh procedur se prično z ASG (assign). ASG_FILE je inačica ukaza ASSIGN v programskem jeziku Pascal. ASG_FILE priredi ime neki datoteki. Razlika med ASSIGN v Pascalu in ASG_Fiie je v tem, da prvi zna delati le z imeni datotek v CP/M formatu, slednji pa z opisi celotne poti v drevesni strukturi. ASG_FXLE kliče funkcijo ASG_PATH, ki je uporabna zato, ker kot rezultat vrne celo število, ki je številka logičnega diska, kateremu je omenjena funkcija priredila pot, ki smo Jo podali kot argument. Ime datoteke iz opisa poti pa izloči funkcija ASG_PATH_EXTRACT, ki vrne celo število, ki povečano za ena pomeni položaj prvega znaka imena datoteke v opisu poti. Omenjene procedure oziroma funkcije kličemo z : ASG_FILE (f, path) ASG_PATH (path) ASG_PATH_EXTRACT (path) kjer Je path niz dolžine 255, f pa neka datoteka, ki Ji prirejamo ime. Omenjene funkcije pojasni spodnji primer. Program odpre za branje datoteko primer.pas na poddirektoriju /usr/include in izpiše njeno ime. Obenem izpiše, kateremu logičnemu disku je priredil pot /usr/work. bAQln path '/UMt/looludé/priJMr.p»«" ; A90r 1>IU ((< p«tii) t t«»»t 1« J >» AftO Mttjonwwt !p«t»(J ! - ■ «rii:«ln T'»!!«,* Copjr t|>«Uj. Suon ?55)) , i' U'ASOA««. 5->/IM«r/W*>Jf; ; '\ Writ«l» T'tdBletl ai«l« » Cht i» » «*)) : Slika 3.1 Prirejanje logičnega diska Program da kot rezultat naslednji Izpis : File = primer.pas V primeru, da smo na enem od CP/M diskov, pa Argv vrača argumente v standardni CP/M obliki đisk:ime_đatoteke. Običajno potrebujemo le CP/M format imena datoteke, zato obstaja funkcija ARGV_RAW, ki iz celotnega opisa poti izloči le ime. datoteke, ki ji spredaj doda logični disk,-kateremu je prirejen direktorij, na katerem se datoteka nahaja. Zgornji primer po uporabi funkcije ARGV_RAW nad vsemi argumenti izgleda takole : F:£cl.pas F:tail.pas Frhead.pas kjer je F: logični disk, kateremu je prirejen poddirektorij /usr/include. Logical disk => F Uporabniku je na voljo še ena pomembna funkcija, ki mu omogoča klicanja BDOS funkcij (CP/M BDOS in vseh dodatnih), ki delujejo nad datotekami. Funkcijo pokličemo z : FILE_BDOS (code, f) kjer je code številka BDOS funkcije, f pa datoteka, nad katero izvajamo omenjeno funkcijo. Funkcija FILE_BDOS tudi sama skrbi za obravnavo napak. Ostale BDOS funkcije kličemo preko- standardne procedure BDOS v Turbo Pascalu. S tem imamo pri pisanju uslužnostnih programov poleg viskonivojskega vmesnika na voljo tudi direktne klice funkcij na nižjem nivoju. l5T Malce ditectory 193 Rcaov* directory 194 Asal(rn iD^lcal điak X9S Desaslgri diete 19G Duplicete Feb 197 C«t protection 198 need descriptor 199 Write deecriptor 200 Change tile protection 210 Sync eystem 241 Shut don «yateni 243 Xebooc uaer systoa 243 Read ey»tem memory 244 Set Ueer Iti Kratak opia odpre nov direktorij ' Đdetrani direktorij dlreVtdriJu priredi podani logični diak (v extent polju ii'-jrpiföetij'fer^ vrne odprt KB ):• direktorij, kateream J» prirejen nelt logični diak foBogoceno branje direktorija) T randooi record polju PCB^Ja vrne laacito datoteke prebere deekriptor odprte datoteke v trenuten DMA oioogoca vpi» nove vaaWo» v neketere polje deekriptorja (aprameiab* datuu aadnjaga dòsega ipd.) Onogoe« spreainjanie laacita datoteke oaiogoca lapia vcebijie vaeh diakovnih -vneenikov na diak xakljuct delo operacijaHega «iatex operecijaki aiatea poetaj« sporoči glavneani računalniku, da je postaji končala i delon oaiogoca direktno branje nekaterih podatkovnih struktur Kistana nastavi kodo uporabnika in grup«, ki Jim« odalej pripadamo Slika 3.2 Dodatne DOS funkcije Dodatne, tako imenovane DOS funkcije podajamo zato, da zaokrožimo celoto orodij, ki so' na voljo programerju pri pisanju sistemskih uslužnostnih programov. Za pravilno uporabo teh funkcij je potreben še dodaten ppis nekaterih sistemskih struktur, ki pa jih tu rie bomo navajali. Omeniti velja, da so nekatere od gornjih funkcij dostopne samo priviligiranemu uporabniku sistema SuperUser, ki edini tudi lahko zakljuSi delo operacijskega sistema. Z vsemi zgoraj naštetimi pripomočki smo napisali množico uslužnostnih programov (okrog 45), ki so povsem podobni ukazom operacijskega sis-tisma Unix. Unix-ove ukaze si lahko vsak bralec pogleda v enem od mnogih priročnikov, ki zanj obstajajo. Povejmo še to, da zaradi specifične konfiguracije našega sistema ni bilo možno pri vsakem ukazu implementirati vseh opcij, ki so na voljo v Unix-ovi originalni verziji. Literatura : (1) Možnosti in nemožnosti mikroračunalnika DIALOG,Elektrotehniški vestnik, April 1987 (2) Peterson, Silbershatz, Operating system Concepts, Addison - Wesley 1983 (3) Comer, Operating System design, the XINU Approach, Prentice - Hall 1984 (4) XENIX operating system, Microsoft corp., 1985 (5) IBM DOS 3.2 Technical Reference Manual, IBM Corp., 1985 (6) IBM DOS 2.0 Manual, IBM Corp. 1983 4. Zaključek Kaj smo z zgoraj opisano rešitvijo dosegli ? Predvsem preprosto, zmogljivo konfiguracijo lokalne mreže in ob majhnih stroških prehod na okolje zahtevnejših in bistveno zmogljivejših operacijskih 'sistemov z možnostjo preproste nadaljne širitve programske podpore samemu sistemu. Uporabnik, ki že ima mikroračunalnik, mora vanj vgraditi le ploščico, ki mu omogoča povezavo v mrežo in dokupiti nov operacijski sistem z vsemi orodji, ki mu omogočajo širitev. Konfiguracija Je zelo primerna za manjše pisarne ali obrate, na njej pa,teče vsa aplikacijska programska oprema, ki js bila doslej napisana ža njegov stari operacijski sistem CP/M. Uporabnik bo ob uporabi take konfigura cij e počasi prešel na nove, zmogljivejše sisteme in ko se bo nekoč znašel pred 32-bitnim strojem z novim operacijskim sistemom, ne bo imel posebnih težav s prehodom nanj. MOŽNOSTI ZAŠČITE PROGRAMSKE OPREME NA MIKRORAČUNALNIKIH UDK 681.3:06:003.6 Nikolaj Zimlc Jernej Virant Marjan Bradeško Ivan Pepelnjak Fakulteta za elektrotehniko, Ljubljana IzvleCek : V članku so opisane možnosti zaščite programske opreme na obstoječih mikroračunalnikih. Predstavljene so najpogosteje uporabljene zaščite, stopnja zaščite, ki jo nudijo, napadi nanje in obramba programske opreme pred napadom. Abstract : The paper presents possible protection of software on existing microcomputers. The most often used protection schemes are explained, together with level of protection they enable, the attacks on these schemes and the possibilities of software defense against such attacks. 1. NAČINI ZAŠČITE PROTI KOPIRANJU 1.1 Uvod Nedovoljeno kopiranje programov na osebnih in hiSnih računalnikih se je začelo s kopiranjem igj;ic. Te zaSSite so prebijali mladi nade-budneži, ki so to počeli bolj iz zadovoljstva pred prepovedanim kot pa iz ekonomskih razlogov. S povečanjem moči osebih računalnikov se Je pojavila tudi zahtevna programska oprema, ki lahkostane tuđi nekajkrat več kot strojna oprema. Zato Je zaščita programov postala resen problem. Z množičnim prodorom osebnih računalnikov se je razmahnilo tudi nedovoljeno kopiranje ali bolje rečeno kraja programov. S krajo programov Je povzročena ogromna škoda avtorjem in proizvajalčem teh programov. Avtorji so se s problemom nedovoljenega kopiranja spopadli na različne načine: - pri prbgramih z velikim številom prodanih kosov so, znižali ceno, tako da kraja programa postane skoraj nesmisel. - programom so vzdignili ceno, tako da so z nakupom enega kosa plačane tudi morebitne koplje, - programe so zaščitili na razne načine in tako otežili, če že ne preprečili kopiranje. Pri ukradenih programih se pojavljajo še dodatni problemi, kot so garancija in vzdrževanje programov. Pri ukradenih programih ni vzdrževanja, zato so neuporabni za resno delo. 1.2 Problemi zaSčite programov proti kopiranju na osebnih računalnikih Pri osebnih računalnikih ni več običajnih zaščit programske opreme, ki so prisotne na velikih računalnikih. Pri osebnih računalnikih ima uporabnik vse privilegije in ima dostop do celotnega pomnilnika in do vseh perifernih enot. Procesor tudi nima svoje serijske številke, po kateri bi programska oprema ločila računalnike med seboj. Samo kopiranje mora biti s strani sistema dovoljeno, da si lahko uporabnik naredi 'back up' programske opreme. Te zmožnosti omogočajo uporabniku tudi nedovoljeno kopiranje pogramske opreme. Rezultat je enostavno prenašanje programske opreme z enega računalnika na drug računalnik. Programska oprema pač nima možnosti ugotoviti na katerem računalniku se izvaja. 1.3 Načini zaščite programske opreme proti kopiranju Proizvajalci programske opreme so začeli s programskim paketom prodajati še dodatek, ki ga je zelo težko prekopirati. Pri cenejših verzijah programske opreme Je to kar disketa, ki se razlikuje od običajne diskete in Jo programska oprema lahko preverja. To so na primer poškodbe magnetnega materiala na točno določenem mestu ali pa nestandarden zapis na disketi. Pri dražjih paketih se k programski opremi doda modul. Modul se običajno priključi na zunanje vhode. Programska oprema Je pisana tako, da brez modula ne deluje. Modul Je običajno zalit v epoksi smolo, kar-otežuje kopiranje modula. 1.3.1 Zaščita na diskéti Disketa Je običajno medij, na katerem se prodaja program. Ista disketa lahko služi še kakor ključ, brez katerega program ne deluje pravilno. Tak način zaščite Je dokaj poceni, saj zahteva samo spremembo na disketi. Običajna disketa je organizirana po sledeh, to je 40 ali 80 koncentričnih krogov. Vsaka sled je logično razdeljena na sektorje. Pred vsakim sektorjem je poseben zapis (id field), v katerem je kodirana številka sledi, številka strani, številka sektorja in dolžina sektorja. S strani procesorja se v kontroler gibkega diska zapiše samo številka sektorja, sledi in strani, kontroler pa sam poskrbi, da se bodo podatki pisali ali brali iz pravilnega mesta na disketi. Dodatni zapisi, ki skrbijo za pravilen dostop do sektorja, so običajno procesorju nevidni, lahko pa se jih z direktnim dostopom do kontrolerja prebere. Na disketo se lahko poleg običajnih informacij zapiše dodaten id field, ki pa mu ne sledi sektor. To pomeni, da Je na disketi podatek o dodatnem sektorju, ki pa ne obstaja. Pri normalni uporabi diskete z dodanim id field-om se le tega ne-opazi. Služi samo za kontrolo pri kopiranju. Pri običajnem formatiranju se dodaten id field ne zapiše, kar prograunski paket kasneje preveri in 'ugotovi', da ni pognan iz originalne diskete. Naslednja možnost je zapis ene sledi več kot je običajno. Disketne enote običajno omogočajo formatiranje diskete na večje število sledi, kot je standardno. Ker operacijski sistem dodatnih sledi ne uporablja, so le te iz uporabniškega stališča povsem nevidne. Enostavno pa se lahko uporabijo za shranjevanje dodatnih informacij, ki služijo za zaščito proti kopiranju. Zaščita diskete Je možna tudi z odstranitvijo magnetnga materiala z diskete. To se običajno naredi z laserjem. To so tako imenovane laserske luknje. Glavna prednost laserskih lukenj pred raznimi zapisi na disketi je v težjem kopiranju, aaj je potreben fizičen poseg na disketo. Programska oprema preverja napako na disketi. Ce napaka ni na pričakovanem mestu, programska oprema ne deluje pravilno. Preverjanje napake se izvede s pisanjem in branjem sekvence podatkov na poškodovan sektor. Ker Je magnetni medij poškodovan, so prebrani podatki spremenjeni. Seveda so podatki spremenjeni točno na določenem mestu. Boljša metoda zaščite je z dvema laserskima luknjama na istem sektorju. To pomeni, da imamo na enem sektorju dve točno določeni napaki. S pisanjem in branjem poškodovanega sektorja lahko izmerimo razdaljo med luknjami na približno 5% natančno. Natančnost meritve nam določa hitrost vrtenja diskete, ki pa ni popolnoma enaka pri vseh disketnih enotah. Dolžina se izmeri s preštevanjem pravilno prebranih zlogov med dvema napakama. Na mestu napake disk kontroler izgubi sinhronizacijo, zato so lahko podatki med dvema napakama pomaknjeni v levo ali desno. Programska oprema tako preverja, če je napaka na sektorju in če je razdalja med dvema napakama pravilna. Disketo, ki je zaščitena z lasersko luknjo, lahko poljubno formatiramo, ne da bi izgubili ključ zaščite. To pomeni, da si lahko naredimo poljubno število kopij, ki služijo kot back up. Te kopije pa so neuporabne brez originalne diskete, ki je zaščitena z lasersko luknjo. Programsko opremo lahko prekopiramo na trdi disk, seveda pa ne deluje brez originalne diskete. 1.3.2 Zaščita z dodatnim moduiom Nekateri novejši moduli se priključujejo med računalnik in tiskalnik. Ta modul se sproži ob točno določeni sekvencl in ne moti običajnega dela s tiskalnikom. V mudulu je običajno nekaj integriranih vezij, ki so zalita v smolo. Ta modul je za uporabnika črna škatla, brez katere programska oprema ne deluje. Modul je običajno avtomat, ki na sprejeto sekvenco podatkov odgovori s točno - določeno sekvenco, ki jo preverja programska oprema, Sekvenca se običajno generira s psevdo naključnim generatorjem. Zaščita je s stališča kopiranja modula dokaj zanesljiva, saj je pri daljši sekvencl praktično nemogoče ugotoviti način prekodlranja vhodne v izhodnò sekvenco. 1.3.3 Zaščita programskih paketov na trdem disku Določeno programsko opremo je možno Instalirati na trdi disk, tako da le ta ne potrebuje diskete s ključem za normalno delo. Običajno se programsko opremo instalira na trdi disk'z zaščiteno disketo. Na disketi se pri inštalaciji zmanjša števec tako, da Je z eno zaščiteno disketo možno instalirati samo omejeno število kopij. Števec inštalacij se lahko poveča samo v primeru, da se po posebnem postopku onemogoči prej instalirano kopijo na trdem disku. Tak način dela omogoča, da se Inštalacijsko disketo, ki je zaščitena, uporablja samo pri inštalaciji. Drugače pa ta disketa služi kot. back up. Pri inštalaciji na trdi disk se običajno v programsko opremo zapišejo informacije o fizičnem položaju le te na trdem disku. Pri kopiranju je praktično skoraj nemogoče prekopirati programsko opremo na fizično enake lokacije. Prazen prostor na trdem disku, ki se lahko uporabi za kopiranje, se spreminja pri vsakem brisanju ali pisanju na disk. Tako je samo pri praznem disku enostavno določiti, kam se bodo podatki pri kopiranju pisali. 1.4 Problemi uporabnika pri zaščitenih programskih paketih Zaščita programskih paketov lahko pri neprevidni zaščiti postane dvorezen meč za legalnega uporabnika. To pomeni, da se lahko zaščita obrne proti uporabniku, ki je programski paket kupil. Problemi nastanejo, če se poškoduje disketa, ki služi kot ključ za pravilno delovanje programa. To pomeni avtomatsko nekajdnevno neuporabnost programskega paketa. Proizvajalci namreč zamenjajo poškodovano disketo, na kateri je zakodiran ključ, z novo. Problemi se pojavljajo tudi pri dodatnih modulih. Ce je modul slabo priključen al'1 če pride do napake pri komunikaciji z modulom, se lahko sproži zaščita, ki je vgrajena v programski paket. To ima za posledico prekinitev programa ali pa njegovo nepravilno delovanje, kar pa zmanjšuje zanesljivost, programske opreme. Zaradi zmanjševanja zanesljivosti delovanja programskega paketa se običajno zaščita postavi samo na začetek programa. To seveda olajšuje napad na zaščito in zmanjšuje zanesljivost zaščite. Pri dražjih paketih se poleg programske opreme doda modul. Modul se običajno priključi na serijski, paralelni vmesnik ali med tipkovnico in računalnik. 2. NAPADI NA ZAŠČITENE PROGRRAME 2.1 Možnosti 'popravljanja' zaščitenih programov Pri zaščitenih programih vedno obstaja rutina ali skupina rutin, ki preverjajo prisotnost zaščite. Če ključ, ki je na disketi ali pa v posebnem modulu, ne obstaja, se program običajno prekine ali pa ne deluje pravilno. Eden izmed možnih napadov na zaščito je onemogočitev prej omenjenih rutin. Seveda pa je dokaj zapleteno najti rutine, ki tvorijo zaščito programa. Avtorji rutin seveda poskušajo te rutine čimbolj zakriti. Rutine imajo seveda nekaj značilnosti, ki olajšujejo iskanje. Glavne značilnosti rutin, ki skrbijo za zaščito so: - prve razlike med delovanjem programa pri originalnem ključu in brez, se pojavijo prav v njih. - te rutina kličejo periferne enote, na katere je priključena zaščita (krmilnik gibkega diska, serijski in paralelni izhod, ...). - včasih vektorji prekinitev kažejo na te rutine, posebno v primeru, če periferne enote delujejo pod prekinitvami. Zanesljivost programske opreme, proti napadu se lahko poveča s testiranjem okolja. To pomeni, da programska oprema odkrije programe, ki nadzirajo delovanje programske opreme. Ce program odkrije, da je 'opazovan' ima možnost, da zavede opazovalca. 2.2 Možnosti kopiranja zaščitenih disket Diskete so običajno zaščitene na tri načine: - z nestandardnim zpisom. - s povečanjem števila sledi. - z odstranitvijo magnetnega materiala (tako imenovane laserske luknje) Običajni programi za kopiranje disket ne prepišejo skritih zapisov na disketi. Te lahko prekopirajo programi, ki 'pričakujejo' skrite zapise in naredijo popolno kopijo, ne glede na to, kaj je zapisano na disketi. Dokaj enostavno je tudi prekopirati sledi, ki jih običajno ni. Seveda pa moramo prej odkriti, da je programska oprema zaščitena na ta način. Ce je disketa zaščitena z laserskimi luknjami, je le to dokaj težko prekopirati brez drage opreme. Seveda pa ni nujno, da poškodbo povzročimo z laserjem. To poškodbo se lahko povzroči z ostrim predmetom. Pomemben je le fizičen položaj poškodbe in njena širina. Prva dva primera zaščite je možno prekopirati popolnoma programsko, brez fizičnega posega v računalnik ali na disketo. Prekopirajo jih tudi aparature, ki so narejene za hitro kopiranje programske opreme. Take aparature namreč ne preverjajo zapisa na disketi, ampak delajo popolno kopijo. 2.3 Možnosti programskega simuliranja zaščitene diskete Napako na disketi, ki Je povzročena z laser-em, je možno programsko simulirati. To pomeni, a programska oprema ne dobi odgovora z diska ampak iz posebnega programa, ki simulira napako. Disketo z zaščito lahko programsko analiziramo in izdelamo algoritem po katerem se spremeni zapisani sektor. Ce Je na sektorju enojna napaka, je začetek sektorja pravilen, nato pa sledi mesto napake. Na mesta napake je prebrana vrednost nesmiselna. Po fizični napaki na disketi spet sledijo podatki, ki so bili zapisani. Ti podatki so zaradi izgube sinhronizacije lahko pomaknjeni. Premik je mišljen na nivoju bita. Ce je na enem sektorju več laserskih lukenj, pomeni, da imamo več področij, kjer so prebrani podatki popolnoma nedefinirani. Točno določena pa je razdalja med laserskimi luknjami. Razdalja se lahko izmeri s številom zlogov med dvema napakama. Z laserskimi luknjami zaščiten program lahko prelisičimo s spremembo programa, ki bere sektor. To pomeni, da moramo napisati program, ki simulira zaščiten sektor. Ta program inštaliramo kot del sistema tako, da zaščitena programska oprema ne opazi spremenjenega branja diskete. Seveda pa se ta program aktivira samo v primeru branja in pisanja na sektor z laserskimi luknjami. V vseh ostalih primerih je branje in pisanje običajno. 2.4 Možnosti kopiranja dodatnih modulov Dodatni moduli so običajno vezja, ki so zalita v epoksi smolo. To pomeni da nimamo vpogleda v notranjo zgradbo vezja. Sam algoritem Je lahko zakodiran tudi v integrirana vezja, kot so naprimer PAL, EPLD, GAL vezja. Ta vezja lahko zaščitimo proti kopiranju s programiranjem posebnega bita v Integriranem vezju. To pomeni, da ne moremo prebrati podatkov za programiranje. Podatke za programiranje lahko dobimo le z analizo delovanja Integriranega vezja. Analiza delovanja integiranih vezij oziroma modulov je dokaj zamudna zaradi velikega števila možnih kombinacij. To število lahko povečamo s številom notranjih stanj flip-flo-pov. Če imamo v modulu ali v Integriranem vezju 10 flip-flopov, je število notanjh stanj 2 na 10. potenco. Same module oziroma integrirana vezja je dokaj težko prekopirati. Lažje je odkriti rutine, ki uporabljajo modul in Jih spremeniti. 2.5 Možnosti uporabe programskih debugerjev Debuger je program, ki Je namenjen ugotavljanju napak v programski opremi. Omogoča nam spremljanje izvajanja programa. Tako lahko spremljamo izvajanje progràma z .zaščito in brez nje. Iz spremljanja lahko ugotovimo, kje je jedro zaščite in ga zaobiđemo. Z debugerjem lahko išščemo instrukcijo, ki so vezane na delovanje zaščite. To so naprimer instrukcije za branje in pisanje, kanala, na katerega je priključen modul za zaščito. V opazovani program lahko postavimo preki-nitvene točke, v katerih opazujemo stanje pomnilnika in registrov. Iz podatkov na skladu lahko ugotovimo, od kje je bil določen podprogram klican. Opazujemo lahko tudi komunikacijo z dodatnimi moduli. Z dobljenimi podatki lahko napišemo program za analizo modula. Po drugi strani pa lahko odkrijemo algoritem, ki skrbi za preverjanje modula. Ta algoritem mora biti ekvivalenten algoritmu v modulu. Iz algoritma se lahko brez večjh problemov Izdela modul. Nekateri programski paketi imajo vgrajeno preverjanje okolice v kateri delujejo. To pomeni, da lahko odkrijejo, če delujejo pod kakšnim dodatnim programom, ki opazuje njihovo delovanje. Ce odkrijejo, da so opazovani, se ria ustrezen način 'branijo'. Spremenijo način delovanja tako, da kar najbolj otežijo spremljanje dogajanj v računalniku. 2.6 Možnosti uporabe etnulatorjev EmulaterJi so najnevarnejši za zaščitena programe. Njihovo prisotnost Je programsko nemogoče odkriti, ker sonda emulatorja zamenjuje procesor računalnika. Emulator omogoča v realnem času spremljanje programa oziroma dogajanj v pomnilniku ali perifernih enotah. Z emulatorjem dokaj enostavno odkrijemo razliko v delovanju programa, ki ima ključ (modul ali zaščitemo disketo) ali je brez. 3. MOŽNOST UPORABE KRIPTOGRAFIJE Pri običajnih programskih paketih je problem, da mora zaščita delovati tudi proti nedovoljeni uporabi legalnega uporabnika. To pomeni, da uporabnik programski paket normalno uporablja, ne smo pa ga prekopirati v smislu nedovoljene nadaljnje kopije. Pri uporabi kriptograflje mora biti ključ za uporabo programa skrit tudi pred legalnim uporabnikom. To pomeni, da mora biti skrit na disketi ali dodatnem modulu. Rezultat je, da je tak način zaščite popolnoma enakovreden prej opisanim načinom. Nekoliko se spremeni način napada, ki mu cilj postane iskanje ključa za dešifriranje programske opreme. Druga možnost bi bila uporaba modula, v katerem bi bil vgrajen postopek in kjuč za dešifriranje programske opreme. Tudi ta možnost je neuporabna, ker modul lahko služi za dešifriranje programske opreme, ki se dešifrirana lahko poljubno kopira. 4. ZAKLJUČEK Zaščita programske opreme ne prenese resnejših napadov. Popolnoma pa zadostuje za preprečevanje kopiranja uporabnikom, ki niso vešči v sistemskem programiranju. Postavlja se tudi vprašanje smiselnosti kopiranja programov. Pri nedovoljeni kopiji je pravilno delovanje programske opreme vprašljivo. Hkrati nam odpade tudi vzdrževanje s strani prodajalca. To sta dva dejavnika, ki govorita v prid nakupil programske opreme, saj se resnejše delo ne more izvajati na programski opremi za katero ne odgovarja avtor. Na Zahodu so strogi zakoni, ki ščitijo avtorje pred krajo programske opreme, vendar Je kraj le preveč, da bi lahko zaupali samo zakonu . Na nivoju osebnih računalnikov ni zanesljive zaSčlte programske opreme. Zaščita je odvisna le od iznajdljivosti avtorjev na eni strani in 'lopovov' na drugi strani. Seveda pa to ne pomeni, da lahko vsakdo v kratkem času prebije zaščito v programski opremi. LOGIČNO TESTIRANJE PROTOKOLOV (pregled) UDK 681.3.066 Tomaž Kalin Tone Vidmar Fakulteta za elektrotehniko, Ljubljana POVZETEKi Namen prispevka je predstaviti sploèno vsebino problematike logičnega testiranja komunikacijskih protokolov, seznaniti bralca z trenutnim stanjem reéevanja problematike v svetu in na kratko predstaviti naé prispevek k temu. Ta se nanaéa predvsem na popolnejèo sintakso testnega modela komunikacijskega protokola (robni pogoji testiranja), arhitekturo in struktura testnega modela ter razvoj t. i. rekurzivne testne metode kompleksnih komunikacijskih sistemov. KJUCNE BESEDE« protokol, logično testiranje, modeliranje komun i c i r an j a (si stemi, protokol a sistem, kjer I. VSEBINA PROBLEMA Komunikacijski protokol je predpis (opis, standard), ki opredeljuje, v konteksu komunikacijskega podsistema način med porazdeljenimi procesi aplikacijami). Implementacija predstavlja prav tako porazdeljen ima vsak element (proces) določeno lokalnost (nič dogodki) in interakcijo z okolico (oddaja, sprejem komunikacijskih sporočil). Opis protokola je po tem torej opis porazdeljenega sistema. V sploènem gre lahko za porazdelitev večih procesov, ki pa se po pravilu grupirajo v dve večji podgrupi procesov P(N) in P»(N), ki predstavljata komunicirajoči točki povezani z prenosnim medijem. "N" ponenl protokolarni nivo komunikacijskega sistema (konkretno lahko tudi v smislu protokolarnega modela OSI). V eksploataciji porazdeljenega sistema, ki je podprt z komunikacijskim podsistemom (P(N),P*(N>) lahko pride do različnih de-fektov (nedefiniran sprejem protokolarnega sporočila, smrtni objem -dead lock-, preseženje pomnilniàkih kapacitet prenosnega kanala -over flow-, dvounmost postopka posameznih komunikacijskih faz -vspostavlj anje, prenos podatkov, ruienje zveze-...). Metode logičnega testiranja . ao namenjene odkrivanju in odpravljanju takih napak v protokolarnem predpisu. Tu nikakor ne gre za pristope, ki so podobni simulacijskim pristopom, vendar pa so rezultati podobni. Povdariti je treba, da je vložek dela za izvedbo testa na osnovi si mulacijskih pristopov neprimerno večji, kot pa pri pristopu z logičnim testiranjem, kar je pomembna prednost za tak način testiranja. Pri tem pa je poleg same testne metode izredno pomembno kako se protokolarni predpis formalno opièe (formalen opis porazdeljenega sistema). In ne nazadnje Je treba povdariti, da je postavitev testnega modela in interpretaciJa rezultatov testiranja prav tako parameter, ki bistveno vpliva na celotno uporabnost logičnega testiranja. Na osnovi povedanega problematika logičnega testiranja protokolov razpade na tri bistvene delei -formalen opis protokola, struktura testnega modela ter izbira testne metode-. Opis protokola v naravnem jeziku formalno in interpretacijsko ni korekten in je neprimeren za kakršnokoli avtomatsko obdelavo. Dejstvo je, da je večina standardov in različnih specifikacij podana v taki obliki. Tak opis je samo na prvi pogled enostaven in primeren. Ob postopku razvoja tehnologije od specifikacije k implementaciji pa se pokažejo sledeče pomanklj ivostiI -ne zagotavlja enoumnega opisovanja protokol arni h konstruktov, enostavno otkrivanje nepotrebnih deklaracij ni možno, ne omogoča preverjanja in potrjevanja funkcionalnosti protokola, ne podpira tehnologije razvoja implementacije, ne nakazuje okvirov i mpl ejmentac i J e, ne omogoča uporabe testnega orodja-. Iz vsega nažtetega sledi, da je med standardom in implementacijo protokola ali poljubnega algoritma (procesa) velika in pomembna vrzel, ki vsebuje éirok spekter problemov in možnih reéitev. Produkcija kompatibilnih implementacij protokola predstavlja jedro problema, ki ga iz različnih zornih kotov in smeri poskušajo reševati različne raziskovalne in razvojne skupine. Ne glede na to, da OSI protokolni model dokaj dobro struktur ira in lokalizira določene probleme specifikacije, je način formalnega opisovanja porazdeljenega sistema *e vedno ključen ko se govori o logičnem testiranju protokolov. Danes uporabljajo za specifikacijo protoV'.dl arni h standardov največkrat strukture končnega avtomata, Petrijeve mreže, abstraktne podatkovne tipe, posebne jezike za specifikacijo, vièje programske jezike in podobno. IBM, Švica, je:"H. RUDIN: Automated Protocol Validation: Some Practical Exsamples, Proceeding o-f the Sixt Internat i onal Con-ference on Computer Communication". V članku je podan hierarhični design in strukturiran pristop k reševanju problema, na originalen način, neodvisen od vseh do sedaj podanih re-ferenc. Tip napak, ki jih metoda odkriva,., je prikazan na primeru nivoja X.25, ki je imel v verziji 1976 določene logične nepravilnosti. Po standardu je bila ta nekorektnost definicije tretirana kot interna proceduralna napaka, kar pa je nesprejemljivo glede na celoten standard, ki tako situacijo očitno dopušča. V kasnejših verzijah standarda X.25 so to napako korigirali. Poleg tega postopek omogoča odkrivanje pasusov, ki se nikoli ne zgodijo, protokol pa jih predvideva" (dead koad), in situacije 'dead lock", to je primer, ko vsi čakajo na sprejem, ki ne bo nikoli izvržen. V članku je za odkrivanje teh napak opisan koncept 'perturbaci je', ki generira tesno drevesno strukturo. Ta članek nas je spodbudil, da smo poiskali vse re+erence v zvesi s tfem člankom, ki so sledeče: "Pitro Za-firopulo, "Protocol Validation by Duologue- Matrix Analysis", IEEE Transactions on Communications, Vol. Com-26, Dec. 1980", "Pitro Zafiropulo, Colin H. West, Harry Rudin S< Daniel Brand,"Towards Analysing and Synthesizing Protocols", Transactions on Communications, Vol. Coffl-28, April 1980", "Harry Rudin, Colin H. West, "A Validation Technique -for Tihtly Coupled Protocols", IEEE Transactions on Computers, Vol. C-31, July 1982", "Colin H. West, "General Technique -for Communication Protocol Validation", IBM J. RES. Vol. 22, July 1978". Ta grupa člankov nam je bila poleg ie prej naètetlh, ki se nanaéajo predvsem na speci-f i kaci j ske probleme, osnova za razvoj t. i. rekurz.ivne testne metode. Poleg teh pa je potrebno naéteti tudi sledeče:"Phi 1 i p M. Merlin, "Specification and Validation of Protocols", IEEE Transaction on Communi catins, Vol. CDm-27, Mar. 1979","George V. Bochman, "A General Transition Model for Protocol and Communications Services", IEEE Transactions on Communications, Vol. Com-20, April 1980", "Georg V. Bochman, "Experience with Formal Specification Using EFMS Model", IEEE Transactions on Communications, Vol. Com-30, Dec. 1982", "Andre A. S. Danthim, "Protocol Representation with FMS", IEEE Transaction on Communications, Vol. Com-28, April 1980, "Seorg V. Bochman, "Finit State Description of Communication Protocols", Computer Network Protocols, Liege -'Bel g i j a, februar 197B", "J. Hartmanis, R. E. Stearns, Algebraic Structure Theory of Sequential Machines, Prentice - Hall 1966". Naéa posebna pozornost je bila posvećena tudi možnosti uporabe Petrijevih mrei, saj imajo te prav posebne možnosti. Petrijeve mreže (PN Petri Nets) so formalen model informacijskih tokov sistema. Namenjene so predstavljanju dogodkov ali procesov, ki v določenem trenutku postanejo konkurenti. Začetnik razvoja Je C.A. Petri, ki je prva dela objavil 1965. Dokončna potrditev so dobile v okviru dveh konferenc (Concurent Systems and Parallel Computation, Woods Hole 1970 in Conmference on Petri Nets and Related Methods, 1975). V Evropi so jih največ razvijali na 'Institut fur Inf ormat ionssystem-f orschunig ' v Bonnu. Na tem področju je veliko storjenega, vendar pa dostopne literature, ki bi združevala- vse rezultate teorije, ni. Večino informacij je treba ' iskati v člankih ali publikacijah lokalnega dosega (doktorati). Edina pregledna informacija js dana v članku 'Petri Nets' in knjigi 'Petri Net Theory and the Modelling of Systems' avtorja J.L. Petersona. Studij tega področja nam je koristil predvsem za spoznavanje tehnik modeliranja porazdeljenih sistemov, čeprav smo se v nadaljevanju dela njihovi uporabi odrekli. Vse do sedaj naèteto se nanaša na deterministične metode logičnega testiranja. V zadnjem času se pojavljajo tudi novi trendi z uporabo hevrističnih metod, vendar pa imajo trenutno prve èe vedno boljèe in za prakso sprejemljivejše rezultate. NAS PRISPEVEK K OPISANI PROBLEMATIKI Nova spoznanja in predlagane izboljšave testnih postopkov so rezultat študija, ki se je začel leta 19B3. V tem času je poleg pričakovanih rezultatov (seznanjanje s problemom in njegovo razumevanje, opredelitev obstoječega stanja v svetu,...) nastalo tudi več verzij programskih paketov za logično testiranje protokolov ( prvi v razvojnem oddelku za komunikacije v DELTI ), kar pa je bilo odločilnega pomena in potreben pogoj za globlje spoznavanje z opisano problematiko testiranja. Končen rezultat dela je "logični protokolarni analizator" - LPA, ki Je v svoji današnji obliki realiziran v okvirih manjšega osebnega računalnika. Zanimivo je omeniti, da je prva izvedba testnega postopka, ki je nastala na osnovi podatkov iz navedene literature, zasedla zmogljivosti večjega mini računalnika. Ta podatek lahko delno ilustrira napredek v razvoju tehnologije testiranja in kvaliteto izvedbe LPA-ja. Poleg tega je obstoječa verzija LPA-ja po kvantitativnih in kvalitativnih lastnostih testiranja neprimerno boljša od prvih izvedb, iz katerih se je razvila. LPA je danes po funkcionalnosti in namenu uporabe primerljiv s klasičnimi logičnimi analizatorji za programsko ali strojno opremo, s tem da gre tu za logično testiranje interakcije med posameznimi elementi porazdeljenega sistema. Poleg testne metode kot osnove izvedbe LPA-ja (namenjena je logičnemu testiranju interakcije v najožjem smislu) je razvita celotna "tehnologija" razvoja komunikacijske opreme, ki je zasnovana tako, da je programabi1 na in funkcionalno povezana z izvedbo izbrane testne metode. Bistveni prispevek našega dela je, poleg vključitve testne metode v celovit - postopek razvoja komunikacijskih sistemov in določene izboljšave same metode, možnost testiranja izvedbeno odvisnih sistemov oziroma testiranje protokolarnega para v njegovem izvedbenem okolju. Zasnova testnega modela in njegova sintaksa sta zato pomembna parametra testne metode, saj bistvena vplivata na kvaliteto in kvantitativne zahteve samega testiranja; predvsem na zahteve po računal niških zmogljivostih same izvedbe testnega postopka. Poleg tega Je testni model bistven za dosego drugega zastavljenega cilja, to je vpeljave robnih pogojev v postopek testiranja. Zavedati se je namreč treba, da robni pogoji, kot so vrsta kanala, prioriteta oddaje/sprejema, možnost kolizijskih dogodkov na prenosnem mediju, vrste sporočil in podobni, bistvena vplivajo na logično in -izvedbeno strukturo določenega komunikacijskega nivoja. Podan je rekurzivni postopek testiranja na osnovi prediaganega testnega modela. Testni model je predstavljen kot mreža avtomatov. Zadano strukturo med seboj povezanih avtomatov je podan postopek paralelno/seri jske kompozicije in minimizacije, katere rezultat je avtomat prenosnega medija v širšem smislu. Prenosni medij v širšem smislu je element modela, ki vsebuje lastnosti fizičnega prenosnega medija II. PREGLED OBSTOJECEQ STANJA Namen tega poglavja je na kratko predstaviti dogajanja na tem podroćju v svetu in sistematizirati probleme, ki se reèujejo v 'prostoru' med danim opisom protokola in njegovo implementacijo. Članki, ki nimajo eksplicitno navedenega izvora so iz zbornika kon-ferencB ' EUTEKD B3' (European Telain-formatics Conference'), ki je bila organizirana v okviru projekta COST 11 bis, To nI kompletna in-formaci ja, vendar pa dokaj dobro zajema probleme in načine njihovega reèevanja predevem v evropskem prostoru, ki pa ta trenutek ne predstavlja neppmemben del vaeh svetovnih dogajanj. Nasprotno, z sprejetjem razvoja komunikacijskih sistemov pod okrilje državnih administracij Je Evropa postala celo vodilna za določena področja. Tu imamo v mislih celo vrsto javnih servisov, ki «o standardi ziranl in velika podporo, ki se v Evropi daje razvoju sistemov v okviru t.i. ISDN (Integreated System Digital Network). Uvoflna referenca, ki sistematizira pristop, je članek "S. AUFONZETTI, A Reference Model for a Protocol Entity".V tem delu je podan formalen pristop k razčlenjevanju problema (protokola) na particije in segmente, glede na kriterije kot so t- implementacijska odvisnost, funkcionalna celovitost in avtonomnost, delavne faze protokola, hierarhična porazdelitev, tip procesiranja, dinamičnost in statičnost podatkovnih struktur. Podana je struktura modela posameznega protokolarnega nivoja in terminologija, ki se je držijo v Evropi vsi, ki se ukvarjajo s problematiko tega tipa. Nakazan je način povezovanja segmentov in interpretaci ja rezultatov pri odkrivanju t.i. 'dead lock' situacije . V delu se navaja cela vrsta pomembnejiih referenc, ki lahko služijo kot vodilo pri bodočem delu. Druga referenca nakazuje konkretno reèitev na osnovi podanega modela: "J.P. Ansard, VALIDOCi A Protokol ar and PDIL - A Language for Protocol Description and Implementation". Clanek opisuje rezultate ene od kompletnejžih reèitev, ki vodijo od specifikacije do implementacije. Sistem je realiziran na institutu INRIA, Rocquencourt - Fraricija. Sistematizira njihov pristop in opisuje glavne elemente produktov in postopek dela, predvsem pa se iz članka čuti obsežnost, kompleksnost in vsa potrebna &irina razvojnega dela, da se pride do uporabnega produkta. Tretja pomembnejša referenca je po vsebini podobna predhodnjii"Bengt JONSSDN: An Extended State Machine Approach to Specification, Validation and Testing of Protocols". Delo opisuje interaktiven sistem za opisovanje objektov (protokolarnih nivojev, N-entities) v obliki končnih avtomatov. Sistem sestavljata dva produkta, testni del CADIE in speci fi kaci J ski jezik ASYL. Postopki preverjanja in testiranja niso predstavljeni, čeprav so navedeni kot deli celotnega sistema. Četrta referenca ne opisuje razvitega sistema do nivoja uporabnosti, konkretneje pa opisuje specifikacijo in povezovanje posameznih modulov specifikacije. Menimo, da je to eno od uporabnejèih del z"O. E. MARTIKAINENi Modular SpecifIcatlonof OSI Subsystems: Specifikacije s pomočjo Petrljevlh mrež so redkejèe, vsi pa jim priznavajo kompletnejèe predstavitvene možnosti, predsvem zaradi enostavnega opazovanja časovnih parametrov in sinhronlzaciJskih postopkov v protokolarni specifikaciji. Osnovni članek s tega področja podaja bistvene probleme sintakse za specifikacijo In reèitev v zvezi s , sinhronizacijo oddajnika in sprejemnika:"E. ECKART, P. PRINDTH; Automated Proofing of Communication Protocosls Against Communication Services, Proceedings of the SiKt International Conference on Computer Communi cat1 on". Vmesni članek med specifikacijo in proučevanjem problemov s pomočjo posebnih programskih jezikov Je delo: "J. M. AYACKE, J. P. COURTIAT, LC/li A Specification and Implementation Language for Protocols". Določena grupa člankov se ukvarja s specifikacijskimi problemi v okviru posebnih programskih jezikov. Osnovna referenca, ki detalnejèfe opisuje in sistematizira področje med opisom protokola in specifikacijo je:"J.P. ANSARTs Protocol», Standards, Specification, Implementation, Testing". Podaja uvod v področje specifikacije s pomočjo algebrajskih Jezikov in procesne algebre. Take reéltve so primerne, zlasti ker:-zagotavljajo. korektno in enoumno specifikacijo, ki omogoča enostavno sintaktično in semantično kontrolo. Teorija nudi orodja, ki omogočajo enostavnejée strukturi ranj e problema ter obvlada probleme nedeterminiranosti protokola tudi v distrlbuiranem okolju. Podoben članek je;"Ed BRINKBMAi An Algebraic Language for the pecification of the Temporla Order of Events In Services and Protocols". Posebno pozornost zasluži članek, ki opisuje formalen pristop preverjanja protokolov in iiče določene možnosti v okvirju hardwarske Implementacije 1e-teh;"Miguel G. HOFFMAN: Hardware Implementation of Communication Protocols: A Formal Appeoach, Proceedings of the 7th Annual Symposium of Computer Architecture Sledeči članek uporablja podobne definicije kot so navedene v prvem s tem, da nakazuje reàitve s pomočjo specifIkacljskega jezika in posebnega algoritma preverjanja (CCS - Calculus of Comunicatio Systems)i"A.F. SCOLLO: SDL and CCS Based Description of Communication Entities". Teoretična osnova za poljubno specifikacijo v okvirju formalnih zapisov, ki vsebuje primer formalizacije fragmenta Teletex-ovega servisa, je članek: "W. ORTH: Formulizel Definition and Analysing of Protocols". 2e v dosedaj naètetlh delih so vsebovani postopki, ki opisujejo testiranje protokolov, ki so vključeni v .celovito reèitev problema specifikacija - implementacija. Obstaja pa nekaj del, ki se poudarjeno ukvarjajo samo s testiranjem."J.P. ANSART, STQ, CERBERE and BENEPI: Three ' tools for Implementation Testing". Delo podaja kriterije testiranja in opisuje tri sisteme za testiranje. To so izredno dragi produkti. Za njihov razvoj so bila vložena znatna sredstva. Dva podobna članka, ki se ukvarjata 5 specifikacijo standarda s poudarkom na testiranju protokolov v okvirju OSI referenčnega modela, sta;"D. RYNER: Protocol Implementation Assessment, National Physical Laboratory, UK, Proceedings of the Sixth International Conference on Computer Communication","R.W.S. HALL and D. RYNER: Protocol Product Testing - Some Comparisons". Posebno zanimivo in pregledno Je delo, kl opisuje praktične rezultate v 1aboratorlj i h in nižjih komunikacijskih nivojev, kakor jih zaznava testirani komunikacijski nivo. De-finiran je postopek, katerega rezultat sta vmesnika med dvema komunikacijskima nivojema. Za izhodiète Je uporabljena struktura avtomata prenosnega medija, dobljenega po paralelno-serijski kompoziciji avtomatne mreže modela. Ta postopek je pomemben rezultat, saj predstavlja avtomati z i ran korak k snovanju izvedbeno odvisne strukture komunikacijskega sistema. □pisana probiematika^ v naäem okolju èe vedno nima pravega mesta, ne glede na perspektivni razvoj računalniških, komunikacijskih, teleinformacijakih in porazdeljenih sistemov. Metoda je uporabna za analizo obstoječe komunikacijske opreme, prav tako pa lahko predstavlja osnovo za avtomati z i rano načrtovanje protokolarni h predpisov oziroma celovite komunikacijske opreme. V določenih razvojnih delovnih okoljih bistveno pripomore h korektnosti in učinkovitosti pri premagovanju problemov, ki se pojavljajo med opisom in izvedbo komunikacijskih sistemov. Sam pristop, kot tudi tehnologija testiranja in načrtovanje komunikacijskih sistemov s pomočjo LPA-ja, so bili ver i-f i cirani na tako kompleksnem sistemu, kot je telefonska centrala ISKRA-2000. Z LPA-jem Je bil testiran tudi "obroč z žetonom", razvit na Institutu Jose-f Ste+an, kjer je bilo testiranje opravljeno s strani samih izvajalcev. To pomeni, da ima LPA že sedaj dovolj prijazen uporabniški vmesnik in, da je vsebina testiranja za uporabnike transparentna, kar jim omogoča, da se posvetijo reševanjem izvedbenih, ne pa logičnih problemov protokola. Na osnovi analize sistemov z LPA-jem so bile razložene določene lastnosti in pojavi v eksploataciji sistemov, ki si jih razvijalci in vzdrževalci sistemov popreje niso znali dobro pojasniti. V nadaljevanju dela bomo LPA iz 1aboratori j ski h okvirov postavili razvijalcu na delovno mesto s čimer bo LPA postal uporabno orodje s podobnimi e-fekti kot Jih imajo klasični logični anal i zatorj i,brez katerih danes marsikateri projekt nI već izvedljiv. ODREDJIVANJE VRSTE REČI IZ SRPSKOHRVATSKOG JEZIKA PRIMENOM RAČUNARA UDK 681.3.06:808.61 Mlhajlovlć Dragan INDOK-Služba Skupštine SAPV Odradjlvanje vrata reél iz srpakohrvatakog jezika prinenon raaunara ima značaja za autoaatsko indeksiranje tekstualnih dokumanata, odabir lekaika za Baatavljanje tezaurusa i druga lingvistička istraživanja. Osnovni princip odredjivanja vrste re&i predstavlja einjenica da re&i sa jednakost koDbinacijoa slova na svom kraju pripadaju po pravilu istoj vrsti reel. O radu se razmatra naein odredjivanja vrste reči iz srpskohrvatskog jazika na osnovu kombinacije slova na kraju reči i zadatog reinika. Prikazani su eksperimentalno dobljeni rezultati. COMPUTER AIDED WORD TYPE DETERMINATION IN SERBO-CROATION is of importance in the process of automatic indexing of textual documents, corpus of words creation in the proces of thesaurus determination and lingvistics research. Word type determination is based on the fact that words with identical combination of letters ending them belong, as a rule, to the same word type. The paper discusses the method of word type determination in serbo-croati on based on letter combinations ending the words and the given vocabulary. Results of experiments are also shown. 1. UVOD Odredjivanje vrste reči prlmenom računara, posebno prepoznavanje imenica i prideva iz taksta na prirodnom jeziku ima značaja u automatskom indeksiranju, odabiru leksike za sastavljanja tezaurusa i druga lingvistička istcalivanja. Osnovni princip odredjivanja vrata rači predstavlja činjenica da reči sa jednakom kombinacijom slova od kraja prema počatku rači pripadaju po pravilu istoj vrsti rači. Na primer, rači SAGLASNOST, SIGURNOST i ZAVISNOST imaju istu kombinaciju slova od kraja prema početku reči, NOST 1 pripadaju imenicama. Na osnovu navedenog principa mogu se graditi različiti sistemi rečnlčkog Ili tabelarnog tipa. Kada se odredi broj slova na osnovu kojeg če se izvraiti odredjivanja vrsta rači, na osnovu dovoljno ulaznih podataka (reči sa ručno odradjenom vrstom reči) za svaku prisutnu kombinaciju slova od kraja prema početku reči u rečnik ili tabelu upisuje se kombinacija slova 1 oznaka vrste reči. Odredjivanje vrste zadate reči svodi se na pronalaženju u rečniku ili tabeli kombinacije slova koja je ista sa kmbinacijom slova od kraja prema početku zadate rečl i da se vrsta reči pridružena toj kombinaciji u rečniku ili tabeli uzme za vrsu zadate reči. Očigledno ja da se na osnovu jednog slova sa kraja reči ne moie vršiti upotrebljivo prepoznavanja imenica i prideva. Tačan odgovor na to,.koji je minimalan broj slova iz kraja rači dovoljan za odredjivanja vrste reči ne moia sa dati. Moia se postaviti sledeča tvrdnja; Sto je broj slova na osnovu kojeg sa vrai odredjivanje vrsta reči večl to je i rezultat pouzdaniji. Za razliku od metoda sa fiksnim brojem slova uzetih od kraja prema početku reči koje su prlmenjene u ruskom jeziku /1/, za odredjivanje vrste reči u srpskohrvatskom jeziku u ovom radu izložen je sa mogućnoiču broja slova od ručno utvrdjena za formiranje ču računara tako ji zavréeci po rečnika traba da rači na osnovu ja prema počatku istiti kao kriče se dodavati u metod korižčenja rečnika izjednačavanja .promenljivog kraja prema početku reči. U rečniku je za svaku reč njena vrsta. Izbor reči rečnika može se izvrtitl pomo da se dobiju *to raznovrsni svim vrstama rači. Sastsv obezbedi odredjivanje vrsta minimalno dva slova od kra rači. Ovaj uslov moia sa kor terij izbora novih reči koje rečnik. 2.ODREDJIVANJE VRSTE REćI SRPSKOHRVATSKOM JEZIKU Odredjivanje vrste zadate rači sastoji sa u tome da se u rečniku pronadje rei koja se sa zadatom alaie sa maksimalnim brojem slova od kraja prema početku rečl i njena vrsta uzme za vrstu zadate rečl. Ukoliko sa reč čiju vrstu odredjujemo nalazi u rečniku tada je potrebno uzeti pridruženu oznaku vrata rači iz rečnika. Kada se reč čiju vratu odredjujemo na nalzi u rečniku tada sa za njenu vratu uzima vrsta one rači iz rečnika koja sa sa njom slaže u najvačam broju alova od kraja prema početku rači. Intereaantno je razmotriti pogodnu organizaciju rečnika za brzo odredjivanje vrste nepoznate reči. Na slici 1. data je logička struktura zapisa rečnika. Postoje samo oni zapisi koji su neophodni za organizovanje rečnika. Zapis 1-vog nivoa odnosi se na prva slova inverto-vanih rečl (poslednja slovo rači), zapisi prctpositdnj* slovo r«ci posltdnjt slovo Nci A B A B 2 ......... H S 2 ■■ H S 2 A B Z -r-i—I—r D B 2 -1—r -1—r « B 2 • ■—f-1- l-wi nivo 2-ii nivo 3-ci nivo 4-ti nivo SliU i, LogicU sruktura zapisi r»cniW 2-gog nlvoa odnose se na drugo slovo inve vane reči (pretpos1ednJe slovo reći) Maksimaln broj spregnutih zapisa za jedan veći od broja slova u najduioj reči. U svakom zapisu postoji 30 polja za s A,B,...Z,4 1 jedno polje (sa adresom 31 blanko. Polja u zapisu sadrie adresu za sledećeg slova invertovane reči. Ako sadriaj k-tog polja zapisa na nivou n nul znači da ne postoji reč čije n-to slov kraja prema početku reči daje adresu polj Polje blanko znaka u zapisu sadrii oz vrste reči koja nas dovodi do tog po Raspored polja u zapisu može se pogodno brati tako da se nekom funkcijom numer kod slova transforni Ce u adresu polja. fi B C I rto-itd. ja lova ) za pisa je a to 0 od a k. naku 1 ja. oda-ički Slila 2. Priner zapisa rećnika Na slici 2. llustrovani su zapisi rečnika nakon toga dto su upisane sledaće imenice: NOVAC, KOLAC, RAT. Na primer, od reči NOVAC Invertovana. reč je CAVON. Zapis na 1-on nivou u polju C sadrži adresu zapisa na 2-gom nivou. Zapis na 2-gom nivou u polju A sadrii adresu zapisa na 3-ćem nivou itd. Princip odredjivanja vrste reči je praćenje spregnutih zapisa u rečniku dok je to moguće na osnovu slova invertovane reči Siju vrstu odredjujemo. Ako se reč čiju vrstu odredju-jemo nalazi u rečniku tada se praćenje spregnutih zapisa izvodi do blanko znaka i čitanja Informacije o vrsti reči koju smo toj reci ručno pridružili. Kada se praćenje spregnu--tih zapisa ne može vKe izvoditi na osnovu slova invertovane reči čiju vrstu odredjujemo može postojati vi*e načina za nastavak algoritma. Jedan od načina je nastavak prolaženja spregnutim zapisima tako da to bude najkraći put preko prvog mogućeg polja zapisa. Informacija u prvom zapisu sa sadržajem polJa(31) različitim od nule pridružuje se kao vrsta reči za analiziranu reč. Nije istraživano da li neki drugi način nastavka prolaženja spregnutim zapisima daje bolje rezultate. Odredjivanje vrste reči rečnika ilustrovanog na slici preko zapisa sa adresama 1, 2, 3, i, 5, 6. U zapisu sa adresom 6 u polju 31 (blanko) pročitamo vrstu reči I-imenica. 3. DOBIJENI REZULTATI Za proveru opisanog načina odredjivanja vrste rečl i to imenica, prideva, glagola 1 brojeva formiran je rečnik od 2320 Imenica, 1530 prideva, 550 glagola i 50 brojeva. Pored ovog rečnika formiran je i rečnik od 978 reći (ne 1nformat1vne reč 1 :pr1lozi , predloži, zamenice, veznici, rečce 1 uzvici) čiju vrstu odredjujemo na osnovu konsultovanja tog rečnika. Formirana su dva rečnika da bi se sprečllo u prvom redu eventualno pogrefno odredjivanje vrste reći koja je imenica, pridev, glagol ili broj kao prilog, predlog, zamenica, veznik, izvik 111 rečca. Prilikom odredjivanja vrste nepoznate reči prvo se proverava da li je reč sadržana u neiformatl-vnom rečniku. Vrsta rečl koja je sadržana- u ne Informat1vnom rečniku odredjuje.se iz tog reenika. Vrsta rečl koja nije sadržana u ne informativnom rečniku odredjuje se pored-jenjem slova od kraja prema početku rečl. UDOVAC pomoću 2 Izvodi se Tabela 1 ursta reči ALGORITMOM OPREDJTEN OBLIK d irektno u reSniku NA OSNOUU zaurSetaka POGREŠNO ODRED^ENIH OBLIKA i Men i oe 923 1193 43 devi 416 8 47 19 srl «STO 1 i lee 264 br>o Jevi 19 I UKUPNÖ" 1518 2 3Q8 71 Vrsta neinformativne re£l koja nije sadržana u nelnformatlvnom refinlku odrsdjuje se pogreino. Analiziran je prirodan tekst od 19200 reel. Od toga 1430 reel su neinforiBativne,a 17770 reel su Inf orniatlvne. Razlleltih oblika informativnih resi bilo jè 3826. Rezultati odredjlvanja vrste reel za 3826 oblika Informativnih reei ilustrovanl su u tabeli 1. Od 3826 razlleltih oblika informativnih reel direktno u ceiniku utvrdjena je vrsta reel za 1518 reel. Za preostalih 2308 razlleltih oblika informativnih reel, vrsta je odredjena na osnovu slova od kraja prema poeetku reel. Stepen taenostl odredjlvanja vrste 230B razlleltih oblika informativnih reel ilustro-van je na slici 3. Oznake na slici 3. imaju sledeea znaeanja: A - pravilno odredjena vrsta reel, I - reel koje su nepravilno svrstane u Imenice, P - reel koja su nepravilno svrstane u prl-deve, G - reel koje su nepravilno svrstane u glagole, B - reel koje su nepravilno svrstane u brojeve . Na primer, vrsta imenica pravilno je odredjena u 96.4% slueajeva. Reelma koje su imenice, u 1.9% slueajeva odredjena je vrsta glagola i u 1.7% slueajeva vrsta prideva. INĐ4ICE PRIDEUI G P 1.7X Gli^GOLI Z.ÌY. P 0.8-/. 0.95% 6 e.95>! B 8.83'/! 4.ZAKLJUČAK Slika 3, TaSnost odredjivanja vrste reci Pokazano je da se vrsta reel u srpskohrva-tskom jeziku mote odrediti sa velikom taeno*eu prlmenom raeunara na osnovu slova od kraja prema poeotku analizirane reel i poznatog reenlka. Poveeanje taenostl pravilnog odredjlvanja vrste reel može se lzvr«itl proéirivanjem poznatog refinika kao i prlmenom dodatnih kriterija. Kao dodatni kriterij za odredjivanje vrste reel iz prirodnog teksta može biti poznat redosled vrsta reel u reeenlcl. LITERATURA! /1/ Vlšnjakova S.M. Vydelenie su«eestvltel■nyh i prilagatel'nyh pri avtomatleeskom analize teksta, NTI, ser 2., br. 3., pp. 15-18, 1976. RAČUNALNIŠKA INFRASTRUKTURA ZA DELOVANJE KIS IN ZTI UDK 681.3:655 Marija ŠIfrar Univerza v Mariboru, Računalniški center Prispevek govori na sploèno o strategiji in tehnologiji pri natrtovanju uatrazne računalniške infrastrukture kot osnove za delovanje knjižničnega in-formaci Jskega sistema ter sistema znanstvenega in tehničnega in-formiranja. Podan je sploSen opis in kriteriji, ki jih mora potrebna računalniška strojna, programska in komunikacijska oprema izpolnjevati. This paper discusses strategies and technologies for developing infrastructure required to support a -functionally unified bibliographic in-formation system. Some general descriptions and speci-fications -for particular components such as hardware, so-ftware and communications are considered. Prehod na naV (avtomatiziran) način poslovanja knjižnic in specializiranih i n-f ormaci jski h centrov zahteva izgradnjo odnosno dostopnost ustrezne in-f rastrukture. In-f rastrukturo predstavljajo poleg podatkovnih resursov (baz podatkov) tudi potrebna strojna računalniška, komunikacijska in programska oprema, ki omogoča gradnjo, vzdrževanje, manipulacijo, shranjevanje, iskanje in posredovanje informacij. V svetu in pri nas Število podatkovnih baz nenehno naraSča. Pri načrtovanju infrastrukture je potrebno nameniti posebno skrb izgradnji novih in omogočiti učinkovit dostop do obstoječih podatkovnih zbirk tako doma kot v tujini. Programska, strojna računalniSka in komunikacijska oprema morajo omogočati postopen, prehod k avtomatizaciji enotnega knjižničnega Informacijskega sistema ter sistema znanstvenega in tehničnega informiranja. Oprema mora biti takSna, da jo je možno uporabljati za različna opravila knjižnično informacijske dejavnosti in dejavnosti specializiranih informacijskih centrov npr. za online katalogizacijo, medknjižnično izposoje, poizvedovanje v domačih in tujih bibliografskih bazah podatkov različnih ponudnikov, naročanje in nabavo gradiva, izposojo, finančna poslovanje itd. STROJNA RAČUNALNIŠKA OPREMA Za razvoj knjižničnih informacijskih sistemov kot tudi sistema znanstvenega in tehničnega informiranja je ustrezna računalniška podprtost izredno pomembna. Najboljši uporabniški vmesnik izgubi na vrednosti ob nezanesljivi računalniški podpori in slabih odzivnih časih. Kompliciran in neprijazen .trr-stopek komuniciranja odvrne uporabnika od uporabe, direktnega (online) sistema. Pri planiranju razporeditve računalniških kapacitet je treba upoStevati lokacijo posameznih podatkovnih resursov ter dostopnost in način posredovanja uslug končnim uporabni kom. Za delovanje knjižničnega informacijskega sistema ter sistema znanstvenega in tehničnega informiranja se lahko uporablja računalniška strojna oprema različnih zmogljivosti in sicer veliki računalniški sistemi ter manjSi podsistemi običajno v obliki mini- in mikra računalnikov ter terminalov. Ključnega pomena pa Je razvit komunikacijski sistem, ki omogoča, da imajo uporabniki preko svojega terminala ali mikroračunalnika dostop do vseh baz podatkov v mreži. Zmogljivejši računalniški sistemi Osnovno računalniško strojno opremo za uspeSno delovanje knjižničnega informacijskega sistema ter sistema znanstvenega in tehničnega informiranja predstavlja zmogljivejši centralni sistem, na katerega je možno ob ustrezni komunikacijski strojni in programski opremi priključiti zadostno Število terminalov ali podsistemov (neinteligentni-, inteligentni terminali, mini- in mikroračunalniki). Velik zmogljivejši računalniški sistem, mora omogočati vnos in vzdrževanje skupne bibliografske baze podatkov ter dostop, iskanje in posredovanje podatkov. Na centralnem sistemu Je potrebno hraniti baze podatkov osnovnih bibliografskih zapisov kot tudi ustreznih pomožnih datotek indeksov za iskanje podatkov. Na večjem sistemu je smiselno vzdrževanja razlićnih baz podatkov specializiranih in-formaci jski h centrov. Podatke Je smiselno hraniti na vel i kern sistemu iz već razlogov: 1. Količina podatkov (vsije diskovne kapacitete ipd.). Programsko opremo za vzdrtevanje baze podatkov je tako enostavneje vzdrževati, saj sa vse spremembe in dopolnitve vnesejo na enem mestu. 3. Tudi vse spremijajoće datoteke t.i. indeksne datoteke za potrebe iskanja, ki se neprestana spreminjajo, je zaradi lažjega vzdrževanja potrebno hraniti za vge uporabnike na eni lokaciji (na enem sistemu) . 4. Možnost komuniciranja oziroma povezovanja z ostalimi velikimi radunai niékimi sistemi in podsistemi. Podsistemi Kot podsistem lahko služijo prav tako radunalniéki sistemi razliCnih zmogljivosti, viasih pa so to samo običajni terminali. Na izbira ustrezne opreme vpliva veliko -faktorjev. Uporaba mikroračunalnikov kot podsistema pa je zelo pogosta in velikokrat tudi ekonomična. Mikroračunalnike lahko uporabljamo tako, da delujejo samostojno ali pa kot terminali na centralnem računalniškem sistemu, kar je odvisno od vrste opravila in od same organiziranosti celotnega sistema. Samostojno Jih je možno uporabljati za postopek obdelave bibl iogra-fskih podatkov (katalogizacijo) t.j. vnosa, spreminjanja in brisanja podatkov. Za vzajemno online katalogizacijo, kjer več institucij združeno vzdržuje skupno bibliogra-fsko bazo podatkov, ki se hrani na centralnem računal niikem sistemu, so primerni mikroračunalniki z vgrajenim terminalskim emulatorjem. Pri distribuiranem načinu vnosa podatkov, ki prehaja vse bolj v rabo, je uporaba mikroračunalnikov za ta opravila, ekonomična. Na ta način uporabniki manj obremenjujejo komunikacijsko linija in centralni procesor. Na glavni računalnik se priključijo le kadar iščejo zapise ali pa jih vn«4«jo v centralno bibliografsko baio podatkov. Istočasno takéen način obdelave podatkov pripomore k izboljšanju odzivnega časa pri iskanju v bibl iogra-fski bazi podatkov ter k zmanjéanju stroékov obdelave bi bi i ogra-f skega gradiva, saj tako porabijo manj procesorskega časa in nižji so tudi stroéki komunikacij. Prihranki sc občutni še zlasti tedaj, ko morajc knjižnice in specializirani in-formaci jski centri vrèiti katalogizacijo na najeti računalniški opremi. Ustrezni pcdsistemi (npr. mini- ali mikroračunalniki) se lahko uporabljajo tudi za opravljanje ostalih -funkcij knjižničnega in-formaci jskega sistema ter sistema znanstvenega in tehničnega i n-f armiran ja, ki sc lokalnega značaja npr. izposoja, naročanje in nabava bibl i ogra-f skega gradiva, -finančno in knjigovodsko paslav.anje itd. Mikroračunalniki so primerni tudi kot orodje za iskanje podatkov v bazah podatkov različnih ponudnikov pri nas in v tujini, hranjenih na velikih sistemih. Zato potrebujemo posebno komunikacijsko programsko opremo, ki omogoča komuniciranje mikroračunalnika s programskim sistemom na velikem računalniku, ki manipulira z bazo podatkov. Prednosti uporabe lokalne programske opreme za iskanje v komercialnih '3a.:ah podatkov je zmanjšanje stroSkov iskanja ter možnost nadaljne lokalne obdelave zadetkov. Uporaba različnih ftSCII terminalov in (mikro)računalni kov pripomore h kompleksnosti komunikacijskega sistema. Zaradi raznolikosti terminalske opreme različnih proiz vaj al cev mora biti ustrezno prirejena komunikacijska programska oprema. Sistem mora poznati npr. Število znakov v vrstici, Število vrstic na ekranu, za vsak tip terminala sekvenco za brisanje ekrana itd. Za priključitev Številne ASCII terminalske opreme Je potrebna poskrbeti za ustrezni način preklapljanja med sistemi, izbiro optimalne podatkovne poti in vključitev v lokalne računalniške mreže. Poleg .izbire tipa terminalov, je treba upoštevati Se druge kriterije. Procedure za vključitev v sistem in dialogi z računalnikom morajo biti čimbolj preprosti. Sporočila sistema marajo biti enostavna in takSna, da pomagajo uporabniku. Sistem mora biti neobčutljiv na aktivnosti na oddaljenih lokacijah. Iz tega razloga niso pri poroči j i ve verige povezanih terminalov, kjer motnja kjerkoli v verigi povzroči izpad vseh terminalov. PROBRAMSKA OPREMA Programska oprema za opravljanje osnovne knjižnične ter re-feralne dejavnosti se deli v funkcionalnem smislu na; - programsko opremo za vnos in vzdrževanje (ažuriranje) bibl iogra-fskih baz podatkov (on-line katalog) in povezuje fazo naročanja, to Je delno obdelavo bibliografskega gradiva, ter končno obdelavo (katalogizacijo, klasifikacijo oziroma indeksiranje) prispelega bibliografskega gradiva, - programsko opremo za iskanje, posredovanje in izkazovanje podatkov v bibliografskih bazah podatkov posameznih knjižnic ter bazah podatkov ostalih velikih ponudnikov baz podatkov (informacijskih servisov), - dodatne programske module npr. za izposojo in medknjižnično izposojo, finančno poslovanje, itd. Osnovni kriterij, ki ga mora pogramska oprema izpolnjevati je modularnost. Sistem mora biti zastavljen in zgrajen tako, da ga je možna postopoma dograjevati, dodajati posamezne funkcije z namenom, da se ugodi vsem potrebam in željam osebja pri opravljanju vsakodnevnih nalog in končnih uporabnikov pri koriščenju uslug knjižnic. Zahteve, ki jih mora programski sistem izpolnjevati : - povezovati mora module programirane za "host" račualnik in module za mikroračunalnike, - istočasno ga lahko uporablja več uporabnikov (multi-user), - mora biti uporabniSko prijazen, ta pomeni prilagojen uporabi začetnikov ter bolj izkuSenih uporabnikov on-line sistemov, V svetu obstaja veliko komercialnih programskih paketov, veliko institucij pa je za svoje potrebe izdelalo lastne programske sisteme. Običajno so programskimi sistemi, ki so jih razvile posamezne institucije za lastne potrebe bolj konverzacijsko orientirani medtem, ko so tipični komercialni programski sistemi transakcijsko orientirani. KonverzaciJsko orientirani sistemi dopuSčajo cdprt dialog. Veliko teksta v obliki sporoćil posreduje programski sistem. Pogoj za vzpostavitev uporabniško prijaznega sistema, Je vzpostavitev zelo intenzivnega konverzaciJskega modula. Pri nas so razviti programski produkti, ki pokrivajo le posamezne -funkcije. Nastajali so Iz zahtev, ki so Jih narekovale trenutne potrebe in ne temeljijo na enotnih merilih. Komunikacijska programska oprema Je za uspeéno delovanje knjižnična in-formaci jskega sistema in sistema znanstvenega in tehniCnega informiranja ključnega pomena. Vse podatke, ki jih uporabnik vtipka na svojem terminalu, mora pravilno posredovati aplikativnemu programu (npr. on-line katalogu na host računalniku) in pockrbi tudi za to, da programski sistem vrne odgovor ustreznemu terminalu. Teoretično bi za to- lahko poskrbela aplikativna programska bprama za opravljanje ostalih -funkcij Itnjižničnega poslovanja. To bi zahtevala zelo tesno interakcijo z operacijskim sistemom in računalniško strojno opremo, kar je zelo težko doseči pri uporabi viSJih programskih Jezikov, v katerih je običajno napisana aplikativna programska oprema. V tem primeru Je pisanja programske opreme bolj zahtevno in razvoj Opreme terja več časa in kadra. MREŽE ZA PRENOS PODATKOV Planirati je treba sistem, ki bo omogočil postopno priključitev velikega žtevila terminalske opreme. Tradicionalne telefonske zveze nudijo omejeno itevilo podatkovnih poti na linijo. To narekuje potrebo po povečanju étevila tele-fonskih linij na eni lokaciji in dodatno strojno opremo, ki kontrolira pretok podatkov na obeh koncih, kar pomeni občutno povečanje stroékov in vzpostavljanje, redundantnih podatkovnih poti. - Mreža v kateri je povezanih preko tisoč terminalov mora imeti Številne alternativne podatkovne poti, ki potekajo preko različnih medijev za prenos podatkov z vgrajeno zmožnostjo avtomatskega odkrivanja motenj oziroma napak ter ponovne vzpostavitve poti. Pri načrtovanju produkcijske mreže je poudarek na zanesljivosti, operativnosti, možnosti razéiritve in ekonomičnost. - Mediji za prenos podatkov morajo biti Širokopasovni, zanesljivi in ekonomični. Sateliti in terestrični mikrovalovi so zanimivi mediji za daljinske povezave. Za lokalni prenos podatkov npr. na območju kompleksa univerze, so poleg tradicionalnih tele-fonskih zank, direktnih kabelskih povezav (lokalna računalniška mreža) primerni tudi radijski in visokofrekvenčni (21-22 gigahertz) mikrovalovi. - Zahteva po zanesljivosti in možnosti razSiritve narekuje implementacijo tehnika paketnega preklapljanja podatkov, kjer so podatki združeni v pakete. TakSen sistem je tudi JUPAK. Paket je podatkovna enota, ki se prenaSa po mreži (v tem primeru so to in-f ormaci je, ki jih on-line katalog (programski sistem) poSilja uporabniku ali pa so to odgovori, ki jih uporabnik tipka na terminalu). Od pošiljatelja do prejemnika jih vodi in kontrolira pot ustrezna strojna in programska oprema. Vsak paket je opremljen z adreso pošiljatelja in naslovnika. 2 dodano in-formacijo o naslovu poèiljtelja in prejemnika paketov adost^ijs jc za priključitev več ter'minalav na procesor le sna vrata. Mreža s paketnim preklapljanjem zahteva uporabo ustrezne strojne in programske opreme ter implementacijo protokolov, ki omogočajo izbiro optimalne poti, kontrolo nad potekom prenosa podatkov, odpravo napak oziroma motenj pri prenosu podatkov ter odkritje in Izognitev neoperativnih poti. Protokoli slulijo kot specifikacije za interno deloyanje računalniške mreže ter delovanje eksternih vmesnikov do te mreže. Protokoli opredeljujejo definicije funkcij, ki Jih morajo posamezne komponente računalniške mreže opraviti. ISO referenčni model predvideva sedem nivojev protokolov za medsebojno sporazumevanje med različnimi računalniškimi sistemi. NajviSji nivo je aplikacijski nivo, ki je Se vedno predmet dogovarjanj in razprav. APLIKACIJSKI PROTOKOLI (za potrebo knjižničnega informacijskega sistema ter sistema znanstvenega in tehničnega informiranja) Ker Je protokol standard, lahko vsak sistem znotraj računalniških mrež komunicira s katerimkoli drugim sistemom znotraj mrež, ki podpirajo isti protokol. To dopuSča lociranje funkcij tam, kjer Je to najbolj primerno In sicer v tehnološkem pogledu (zmogljivost računalniških sistemov, stroSkl telekomunikacij) In z vidika upravljanja računalniških mrež (kateri računalniški sistem, kdo upravlja z računalniškim sistemom, itd.). V ZDA razvrščajo aplikacijske protokole za te namene v tri spi očne razredei - protokoli za iskanje informacij v bazah podatkov (za sporazumevanje med računalniškimi sistemi različnih knjižnic, ter drugih posrednikov infortnacij ter med posredniki teh informacij in uporabniki), - protokoli za poslovanje (za izmenjavo podatkov informaciJsklmi centri podatkov), med knjižnicami, ter ponudniki baz - protokoli za operativno delovanje aplikacij (služijo za povezovanje različnih aplikacij s področja avtomatizacije poslovanja knjižnic ter specializiranih informacijskih centrov). Protokol za iskahje informacij predpisuje način iskanja in izmenjavo zapisov med računalniki. Pri tem velja poudariti naslednje: UspeSna določitev protokolov za iskanje in posredovanje informacij Je odvisna od implementacije sploSno veljavnega standardiziranega (statičnega) opisa datoteke. Za knjige je ta zahteva Izpolnjena z MARC (MAchlne Readable Cataloguing) standardi. To je standardiziran bibliografski opis knjige za izmenjavo zapisov v računalniško čitljivi Obliki. Za druge vrste dokumentov npr. elektronski dokumenti (članki in knjigo), ki vsebujejo tekst v celoti (izvlečki, poročila, podatki o izposji Itd.) to trenutno Se ni reSeno. Poleg protokolov za iskanje in posredovanje informacij je treba razviti Se Številne aplikacijske protokole z vidika knjižničnega poslovanja. Priprave za standardizacijo postopka naročanja in nabave knjig in serijskih publikacij so že v teku. Nekateri postopki kot npr. -fakturiranje, pa se reäuje na sploèni ravni skupaj s poslovnimi aplikacijami. Protokoli za servise kot Je elektronska poäta pa so bili razvitj skupaj s prizadevanji za standardizacijo na področju računalniškega omreževanja. Protokoli so potrebni tudi za standardizacijo operativnega poslovanja knjižnične dejavnosti in informacijskih centrov. To ée posebaj velja za izposojo. V primeru-, ko je sistem za izposojo direktno povezan z on-line katalogom knjiinice, je potrebno priskrbeti sredstava za ugotavljanje statusa bibliografske enote, podaljšanje in vračila ter izvedbe dejanske transakcije izposoje, katere rezultat Je knjiga, ki se požje s poäto. V zvezi z načrtovanjem protokolov za izposojo je potrebno reèiti èe vrsto nejasnosti glede zaédite, legalizacije, določitve privilegijev ter pri postopku povezovanja podatkov o knjigi v on-line katalogu in podatkov v datoteki podatkov potrebnih za izposojo. INTEGRIRANI ALI MRE2NI SISTEMI Integrirani sistemi so zaprti sistemi. Mrežni sistemi so odprti, neskončno razöirljivi. V razvitem svetu je večina računalniških mreč medsebojna povezanih'. Povezati se Je možno s tisočerimi računalniki. Seveda Je treba poznati proceduro za vzpostavitev zveze. Na ta način bodo v svetu kmalu povezane vse večje knjižnice in in-formaci j ski centri na aplikacijskem nivoju. Obstaja možnost, ' da institucije na lokalnem nivoju vzpostavljajo Integrirane sisteme, ki predstavljajo vozlišča v celotni mreži. Vendar je tudi na lokalnem nivoju smotrno uporabiti mrežni pristop in opravljati razne funkcije na različnih računalniških sistemih. DOSEDANJE IZKUŠNJE V SLOVENIJI Vpliv aplikacijskih protokolov Implementacija aplikacijskih protokolov popolnoma eliminira vprašanje standardizaciJe poizvedovalnega jezika za on-line kataloge in podobne sisteme. Vendar je o standardizaciji na tem področju še prezgodaj govoriti, ker Je razvijanje uporabniških vmesnikov še vedno bolj umetnost kot pa inženiring. Orodja in izrazoslovje te vrste še niso dokončno definirana. Ca bodo protokoli implementirani, bo lahko uporabnik komuniciral s katerimkoli on-line katalogom (ali več on-line katalogi) z uporabo kakršnegakoli poizvedovalnega Jezika, ki je instaliran skupaj z lokalnim on-line katalogom ali pa na osebnem računalniku. Nikoli ni potrebna poznati ukazov več kot enega poizvedovalnega jezika. Lokalni računalniški sistem (osebni računalnik ali on-line katalog na host) na katerega se uporabnik prijavi komunicira na uporabnikovo zahtevo z vsemi oddaljenimi sistemi, prevede neopazna za uporabnika lokalni poizvedovalni Jezik v skupen splošno poznan iskalni Jezik aplikacijskega protokola. Ker prenaša protokol zapise v predpisanem, splošno poznanem formatu, je možno na ta način izpeljati tudi številne dodatne postopke. Na host sistemu se lahko instalirajo posebne rutine za odločitev o tem v katerem računalniškem sistemu bo iskal želeno informacijo in v kakšnem vrstnem redu. Zadetki dobljeni z več oddaljenih sistemov se primerjajo med seboj in združijo. Na ta način se odpravijo nepotrebni duplikati. Smiselna Je implementirati program za ugotavljanje najcenejše poti za dostop do ustreznih podatkovnih baz. Princip je podoben kot pri vzpostavljanju medkrajevnih telefonskih razgovorov, kjer se upošteva dnevni čas, vrsta baze podatkov, cenik, popusti na količino ipd. Programski sistem na host bo lahko vzpostavil zvezo s številnimi oddaljenimi servisi za posredovanje baz podatkov, da bi ugodil uporabnikovi zahtevi. Knjižnice v Sloveniji razpolagajo s različno programska opremo (vnos in ažuriranje kataloga knjig po polnem in skrajšanem bibliografskem opiau{ vnos, ažuriranje, iskanje in izkazovanje podatkov v bazah specializiranih informacijskih centrov, izposoja knjig, iskanje gradiva v online katalogu, iskanje podatkov v drugih online sistemih, itd.), ki ni grajena po enotnih merilih. Baze podatkov, ki se vzdržujejo, ne uporabljajo enotnega formata zapisa. Trenutno imajo le nekatere knjižnice ip informacijski centri skromno strojno opremo in sicer različne tipe mikroračunalni kov in terminalov. Kot host sistemi se koristijo računalniški sistemi RRC, RCUL in RCUM. Dosedanje izkušnje so pokazale, da bo v prihodnje potrebna širša in bolj usklajena akcija za izboljšanje situacije na področju avtomatizacije knjižničnega poslovanja ter sistema znanstvenega in tehničnega informiranja. Pri tem bi moralo sodelovati čim več knjižnic in ostalih institucij. Z ozirom na knjižnični fond, razpoložljiva finančna sredstva ter glede na število in strokovna usposobljenost delavcev v posameznih institucijah, bi bilo smotrno združiti sredstva in napore tako za vsklajeno nabavo strojne računalniške in komunikacijske opreme ter za razvoj programske opreme. V naslednjem obdobju bi bilo potrebno povezati knjižnice in informacijske centre v enoten knjižnično-informačijski sistem in omogočiti njihovo vključitev v svetovno izmenjavo znanstveno tehničnih informacij. VAL REALIZACIJA IZRAČUNAVANJA N-TOG KORENA KORIŠČENJEM PARALELNOG ITERATIVNOG ALGORITMA VAL REALIZATION OF N-TH ROOT EVALUATION USING PARALLEL ITERATIVE ALGORITHM UDK 681.3.06:519.6 Slavoljub Damjanović HE »Đerdap«, Kladovo Lazar Đorđević, dr. Elektronski fakultet, Niš SADRŽAJ: U ovom radu prikazana je programsk«. realizacija izračunavanja n-tog korena u višem dataflow jeziku VAL, primenom paralelnog iterativnog algoritma. Izložene su osnovne karakteristike ovog jezika, koji po semantici pripada klasi funkcionalnih jezika, a po sintaksi je sličan Pascal-u. Opisane su vrednosti i tipovi podataka koji se koriste u VAL-u, kao i njegove najznačajnije programske strukture. Wjegova efikasnost za paralelno programiranje iskorišćena je na primeru izračunavanja n-to.g korena. ABSTRACT: This paper presents the program realization of n-th rooth evaluation in the high-level dataflow language VAL, using parallel iterative algorithm. The basic terms of the language are reviewed, which is by semantic a functional 'language and by syn-taoc alike Pascal. Data values and types used in VAL are described, as well as his the most important program structures. His efficiency for parallel programming is utilized in the n-th root evaluation example. 1. UVOD Klasični pristupi za razvoj multiprocesorsk-ih arhitektura postali su neadekvatni, uglavnom zbog teškoća u raspodeli posla između velikog broja procesora i u sinhronizaciji njihovih operacija. Postalo je očigledno da se, radi iskorišcenja masovnog paralelizma, moraju razviti novi modeli■računara koji treba da ispune sledeča dva zahteva: 1) Korisnik mora biti u stanju da opiše re-šavane probleme na način pogodan za paralelnu obradu. 2) Računar mora biti u stanju da iskorišćava unutrašnji paralelizam sadržan u problemima koji se rešavaju. Dataflow računarski sistemi efikasno rešavaju oba ova problema koriščenjem dataflow, programskog jezika visokog nivoa, prevođenjem programa pisanog njime u dataflow graf, i njegovim izvršavanjem na paralelnom raču-naru. Dataflow jezici su uvedeni da bi se omogućilo jednostavno i lako programiranje u multiprocesorskim dataflow sistemima, jer su klasični konkurentni jezici neadekvatni za izražavanje različitih oblika konkurentnosti koji postoje u programima. Viši dataflow jezik VAL (Value-Oriented Algoritmic Language--algoritamski jezik orijentisan prema vrednosti) /1/ projektovan je baš sa ciljem da se njime mogu izraziti svi nivoi i tipovi konkurentnosti na jednostavan i jasan način. 2. PK0ÜRAK3KI JEZIK VAL 2.1. Osnovne napomene o VAL-u Dataflow programski jezik VAL, po semantici, pripada klasi funkcionalnih ili aplikativnih jezika kod kojih se sva obrada vrsi primenom funkcija nad vrednostima. On- je funkcionalan u pravom matematičkom smislu te reči. Svaki programski modul predstavlja funkciju koja prihvata neke ulazne podatke i čiji je jedini zadatak da generiše neki skup rezultalja. Klasični jezici koriste ove pojmove: naredba i tekuće stanje računanja koje se može predstaviti skupom promenljivih i njihovim trenutnim vrednostima u memoriji. Stanje se menja promenom vrednosti promenljivih. Umesto naredbi i promenljivih, u VAL-u se koriste izrazi i vrednosti. VAL je jezik orijentisan prema vrednosti, jer^je svaka aktivnost u VAL programu neki izraz čije izračunavanje generiše skup vrednosti. Svaka vrednost se direktno šalje drugim izrazima kojima je potrebna kao argument tj. ne memorise se, pa ne postoji promenljiva kojoj bi se ta vrednost dodelila. Radi pogodne notacije u programu, vrednost se može "vezati" za neki identifikator (ime) vrednosti, ali njihova veza mor» ostati stalna u ćelom opsegu važnosti imena vrednosti, '^ato identifikator nije promenlj-iva, jer promenljiva menja svoju vrednost a identifikator ne /2/. U VAL-u svakom podatku mora biti specificiran njegov tip, dok proveru tipa operanada za svaku operaciju vrši VAL.prevodilac. Po sintaksi VAL je sličan Pascal-u, a po semantici funkcionalnim jezicima kao što su LISP i FFP. 2.2. Vrednosti i tipovi podataka Ulazni i izlazni podaci VAL izraza i funkcija su vrednosti. Skup svih vrednosti koje VAL programi mogu prihvatiti ili generisati predstavlja domen vrednosti VAL jezika. On se deli na više poddomena koji predstavljaju tipove podataka VAL-:a. Postoje elementarni tipovi u koje spadaju skal&rne vrednosti:nu-Ita vj-ednost NIL, logj.čke, celobrojne, realne i znakovne vrednosti;strukturni tipovi: nizovi i slof::ovi, i unioni tipovi (unije). Specifikacija tipa je sintaksna konstrukcija kojom se specificira tip nekog podatka. Specifikacij« elementarnog tipa je samo ime tipa: null, booliaw, INTEGER, REAL i CHaR.^C-TER. Specifikacija nizovnog tipa specificira tip svih elemenata niza. Dužina niza nije poznata u vreme prevođenja programa već se određuje u toku njegovog izvršavanja, pri izvršavanju operacije kreiranja niza. Primer: ARRAY C ARRAY [ REAL]] ; Vrednost niza tipa ARRAY M sastoji se iz dve komponente: l) Opsega (LO, ill) gde su LO i HI celi brojevi i LO^HI+l, To su granice niza. Ako je L0=HI+1, niz nema elemenata; 2) Sekv-ence od HI-LO+1 elemenata tipa T. Specifikacija slogovnog tipa specificira imena polja sloga i tip svakog polja. Imena polja unutar jednog sloga r.oraju biti različita Ako je nekolikim imenima polja pridružen isti tip, sva ta polja su tog tipa. Primer: RECORD Cl, J : INTEGER; TEMP: HE.vL] ; Ako su Ni,..., Kk imena polja, a Tl,...,Tk specifikacije tipova, tada REC0RD[1}1 : TI,.. ,, Nk : Tk] specificira slogovni tip. Vrednost slogovnog tipa je skup od k parova:{(Hl, VI),...,( Nk,Vk )( , gde je Vi vrednost tipa Ti. ^ Specifikacija unionog tipa specificira imena oznaka i-tip svake oznake. Imena oznaka unutar jedne unije moraju biti različita. Ako je nekolikim imenima oznaka pridružen isti tipi sve te oznake su tog tipa. Ako je izostavljena specifikacija tipa iza imena oznake, usvaja se nulti tip NULL. Primer: ONEOF [THIS : ARRAY[INTEGEH] ;THAT: RECORD DC, D : REALU ; Ako su NI,---, Nk imena oznaka, a Tl,^.,Tk specifikacije tipova, tada ONEOF [NI : TI,.., ; Nk : Tk] specificira unioni tip. Vrednost unionog tipa je samo jedna vrednost, jednog od nekoliko alternativnih tipova Tl,...,Tk, kojoj je pridružena oznaka, koja ukazuje kog je tipa ta vrednost, tj. vrednost unionog ti-' pa je par (Ni, Vi), gde je KiiSxRUCT petlji. Formiranje svih vrsta, i od njih cele matrice, vrši se paralelno. FGRhLL uvodi jedno ili više, indeksnih imena vrednosti, cèlog tipa (iEen.i ispred reči liO i nekoliko opcionih privremenih imena vrednosti (imena u deklaracijama i definicijama). Obe vrednosti izraza iza reči IN su ce-log tipa. To su donja i gornja granica indeksa. FORALL konstrukcija funkcioniše tako što indeks dobi ja-vrednost svakog broja izme-dju svojih granica, izvrše se definicije privremenih imena vrednosti, i izračunavaju se svi delovi tela konstrukcije. Ako je dato više indeksa, ovo se vrši za sve moguće kombinacije vrednosti tih indeksa. . U CONSTRUCT delu, izr.iz u telu konstrukcije se izračunava za svaku vrednost indeksa, i za svaku komponentu tog izraza formira se niz čije su granice jednake granicama indeksa a čiji su elementi jednaki izračunatim vrednostima. Ako je dato više indeksa, formiraju se više-dimenzioni nizovi, pri čemu prvi indeks indeksira najspoljniji niz. U EVaL delu, operacija mora biti jedna od sledečih: PLUS, TII-DiS, nIN, HaX, Oß ili AI^D. Izraz iza reči EV^ izračunava se za svaku vrednost indeksa, a data operacija se izvršava nad celim skupom generisanih vrednosti. Ako je datò više indeksa, data operacija se izvršava nad skupom vrednosti generisanih za sve moguće kombinacije vrednosti indeksa. 2.4. Definicija i poziv f\mkcije VrtL program se sastoji iz više modula koji se posebno prevode. Način njihovog povezivanja u kompletii izvršni program i smešta-nja u programsku biblioteku zavisi od konkretne implementacije'. Svaki modul definiše jednu spoljašnju i jednu ili više \inutrašnjih funkcija. SvakM funkcija se definiše pomoću definicije funkcije koja se sastoji iz sledečih komponenti: 1) Rezervi sana reč raNCTICK. 2) Zaglavlje funkcije koju čine ime funkcije, deklaracije formalnih argumenata i specifikacije tipova povratnih vrednosti. 5) Definicije programski-definisanih tipova čija se imena mogu koristiti u celoj definiciji funkcije, uključujući i njeno sopstve-no zaglavlje. Ovde se takodje nalaze i EXTE-RI0). Broj iteracija iterativnog postupka zavisi od reda konvergencije formule i izabrane startne vrednosti. Formulama brže konvergencije računa se u manji braj iteracija ali one u sebi imaju više operacija sa aspekta mašinskog vremena. Zbog toga se traži kompromis izmedju brzine računanja i zauzetosti memorije. Pri stvaranju standardnih programa z« računare postavlja se zahtev da se brzo računa, ali 9* što manje zauzetosti memorije. Ako je početna vrednost korena suviše udaljena od tačne vrednosti, izračunate približne vrednosti korena sporo konvergiraju ka tačnoj vrednosti, pa je za izračunavanje potreban veliki broj iterativnih koraka, ako se startna vrednost pažljivo bira, broj iteracija se može svesti na dovoljno nali broj a da se tražena tačnost zadovolji. U ovom radu prikazana je realizacija brzog i tačnog izračunavanja n-tog korena u VAl-u. metod prikazan u radu /5/. U njemu se, polazeći od izabrane početne približne vrednosti korena, primenom odre-djene rekurentne formule formira niz približnih vrednosti korena koje postepeno konvergiraju ka tačnoj vrednosti. Konvergencija niza se obezbedjuje izborom odgovarajuće početne približne vrednosti korena i rekurentne formule. U primenjenoj rekure-. ntnoj formuli figuriše i jedan parametar p za ubrzavanje konvergencije, koji smanjuje broj iterativnih koraka potrebnih da se do-dje do tačne vrednosti korena. Algoritam za izračunavanje n-tog korena bazira se na činjenici da se svaki realan broj a>l može predstaviti u notaciji pokretnog zareza u obliku (j.l.),' gde je x mantisa, k eksponent, a b brojna osnova računara. a=b**kiex (l/b=1.0 THEN ITER A2:=A2sR-, K2:=K2+1 ENDITEH ELSE A2, K2, 1 EI^DIF EKDFOH ENDIF EN DLET ENDTOK for K, L, i, LI : integer; Alf, AO, BO, AB, Al, BI, XA, YO, Yül, YOG, Y, EPS : REjiL; an:=heal(h); EPS:=0.1E-15; A0:=2.03eAN+1.0; B0:=AN+1.0; AB :=A0»B0; A1:=6.0*AI^k(2.0*B0-A0)/(A*B) ; B1 : = 2. OjtAN* ( 2. 0*A0-3.0«B0 ) / ( a*B ) ; XA, K, L:=P0KZ;AR(B, A); I:=K/N; L1:=(K-N*I)*L; Y0: = (Al3eXA+Bl)}eEXP(B, Ljtl); Y01: = IF H=0 THEN 1.0 ELSE EXP((Aljel.0/B+Bl), -Ll) ENDIF; YOG :=Y0kY01; Y:=Y00 DO LET TO, Tl, T2, YY : REaL; TO:=EX?(Y, N); T1:=T0-A; T2:=N*T0; YY: = forall j in cl. YYl : REAL:=Y*(l.0-Tl/(T2+P[J]}eTl)) EVaL PLUS YYl ENDALL A.O IN IF ABSCYY, Y) <.EPS THEIJ YY . ELSE I TEK Y:=1'Y EKDITER ENDIF EI-IDLET E^JDP0R EiraPUN ■ 31. 2. L»WBence Livermore National Lab., Livermore, California, March 1, 1985-A/ J. B. Dennis et al, "Modeling the Weather with a Dataflow Supercomputer", IEEE Trans. Computers, Vol.53, No.7, July 1984, 592-602. /5/ L. N. Djordjević, "On N-th Root Evaluation by Iterative Ketpds with Parame- ters", Informatica, No.4-, 1977, 60*62. /6/ M. S, Milićević, "Početne aprokaimacije u iterativnom izračunavanju n-tog korena i formiranje poboljšanog algoritma", Automatika, Zagreb, 1974. LASTNOSTI INFORMACIJE: MALA ENCIKLOPEDIJA (A) INFORMATICA 1/88 UDK 681.3.007 Anton P. Železnikar Iskra Delta, Ljubljana Properties of Information: A Small Encyclopedia This encyclopedia presents a first trial in approaching the thlnlid'é.: '■■and? '. , ■ ■ "e e o n om 1 c a i,. va nd; ■ e li i tura L? e 1 r e ùm s t ä n ^ ■ ces'on^'the':;ó'ther, s'idé?- ' ■■.- ■ 'V-..- 7 -- if . .-vss ■ ■ ' ■. ■• ■ - v U . .. i- . . irV" > i . i Figiire ,4'0;: 'Engineers ,are aIways 1 il<é J " horses '- 'of the' modern high-tech. , " company;',; ;They.' ,h'ave '.to draw; the , ' V V c.ompariy/V . .earr^iage^"^ are;r . -more' of.tenVth when the'' J'carriage's moving/to . s low and; not, - ' " in .the ap'propir i ate i-nnoyat iye dl recr-; ' -'.- -tibn;. The 'horse ■ cul ture of .Old - . Tucson ..- may sound nò t • on 1 y V h 1 s t or 1 ^ J-,;.;,-cal ^.buü-also instructive. ' reconfigure in one processor cycle. Using this switch, GFll can be organized in any one of a number of different topologies, such as a rectangular mesh of any dimension and size, any torus, a hexagonal mesh, or some irregular organization fitted to a single problem. A central contr instructions to the swltch, and computer. GFll Is multiple-data (S receive the same The SIMD archit simplicity, high of synchronizati due to sharing of oiler is used to broadcast all of the processors and to also to communicate with host a modified single-instruction IMD) machine: all processors instruction at the same time, ecture has the advantages of perfdrmance due to elimination on overhead, and reduced cost the controller. A typical calculation in QCD, for example, an evaluation of the masses of the proton, neutron, and a few related particles, is estimated to require 3 times 10 to power 17 arithmetic operations. With a 100 megaflop machine this calculation would take 100 years. By a parallel application of its '576 processors, GFll is capable of completing such a calculation in about orie year. QCD Is only one example of a class of scientific problems that can be structured for computation on GFll. Furthermore, Dr Oklopdzija prepared a lecture for us on IBM's new supercomputer TF-1 (Terraflop 1), a 10 to power 12 floating point operations per second supercomputer, incorporating special purpose custom-built VLSI arithmetic processor. The visit to IBM RC was pleasant and Impressive. When living the RC, the photo of my questioning staying on Figure 37 was made. However, my thinking hairs still pointed to the RC direction (Figure 38). 11. Have I really done nothing in the last two years? The question I have to answer concerns a critical phase of our social and cultural development. My answer I's a trial how to exclude several unpleasant, ill-meaning, and unintelligible Idle talks concerning my activity in the last two years. These talks are coming into existence at various unprofessional levels and are propagated by several nonprofessionals. Why I have to answer such non-proflclent rumors at all? First, I have to agree that my intellectual action In. developing a new philosophy of information and in organizing and advising research and development to Parsys project were hardly recognized as useful and prospective under existing subcultural managerial and scientific cl ir cums tances . According to my own measures, in the last two years, I have attained much more than in the previous 20 years of my life when I was living in safety at a "national" scientific Institute. Let me explicate only two substantial, already mentioned and developmentally crucial activities: establishing a new philosophy of Information as a starting-point for future investigations of intelligent machines and the Initial pushing, professional concentration, and organizational help of the Parsys project. Since autumn 1985 I have visited Japan twice and USA with the intention to bring new research and technological orientations in the corporative discourse of national computer industry. There was never doubt, at least from my view of understanding the scientific and would be was doing how this technological trends of development that novel orientations are a necessity for industrial or even for national survival. Besides my main activities (research and consulting work), I have performed regular activity as academic lecturer, adviser, editor, author, and organizer to mention several of my factual activities. In this respect, I extremely pleased to hear again how I nothing in the last two years and slogan can be understood from the managerial or subcultural point of view. 12. Conclusion What is the moral of this long, straining, and fruitful two year journey into the world of information, intelligence, and parallel processing? Do we, the actors of different adventurous and exhaustive expeditions into the unknown and by knowledge populated areas, have anything to regret? Ref erences (LLG) T. Durham: Language Through,the Looking Glass. Computing, July 10, 1986. (B&T) M. Heidegger: Being and Time. Harper & Row, Pubi., New York (1962). (OWI) A. P. Zeleznikar: On the Way to Information. Informatica 11 (1987), No. 1, 418. (IDI) A. P. Zeleznikar: Information Determinations I. Informatica 11 (1987), No. 2, 3-17, (POI) A. P. Zeleznikar: Principles of Information. Informatica 11 (1987), No. 3, 9-17. (PS) A. P. Zeleznikar: Parsys Expeditions to New World. Informatica 11 (1987), No. 3, 76-80.. (ID2) À. P. Zeleznikar: Information Determination II. Informatica 11 (1987), No. 4, 8-25. (RP) The Research Program at CSLI. Center for the Study of Language and Information, Ventura Hall, Stanford University, CA 94305. (TW) Thomas J. Watson Research Center. IBM, York town Heights, New York 10598. AVTORSKO STVARNO KAZALO ČASOPISA INFORMATICA, LETNIK 11 (1987) Članki Alaglć Mara and S. Alaglć: Categorical Approach to the Relational Model of Data. Informatica 11 ( 1987 ), No. 3, pp. 3 - 8. Barle J., J. Qrad, and D. KrstiC: A Production Problem Interactive Prototype of Linear Programme. Informatica 11 (1987), No. 3, pp. 29 -31 . Barle T. in Eli De 11dZakova-Drenik : Ugotovitve ob preizkusu demonstracijske verzije programskega paketa Micro-Optrans. Informatica 11 ( 1987 ) , St. 2, str. 66 - 68. Brajak P.: Designing a Cofigurable Intelligent Memory Module (RIMM) for Performance Enhancement to Large Scale, General Purpose Parallel Processor. Informatica 11 (1987), No. 1, pp. 19 - 53. Brodnik A., M. Spegel in T. Lasbaher: Programiranje z Modulo-2, prvi del. Informatica 11 ( 1987 ) , st. 2, str. 78 - 82. Brodnik A., M. Spegel in T. Lasbaher: Programiranje z Modulo-2, drugi del. Informatica 11 ( 1987 ) , St. 4, str. 69 - 76. Fajfar D. and M. Lokar; Analysis of Buffered Multistage Interconnection Network for Parallel Processors. Informatica 11 (1987), No. 4, pp. 3 - 7 . FlUpl« B.: Implementing Pascal-like Constructs: An Exercise in Prolog Programming. Informatica 11 (1987), No. 2, pp. 27 - 30. Freyder J. D. 1nformat1ca 11 Reasoning Simulation Programs. (1987), No. 3, pp. 32 - 37. Grad J. and M. A. Jenkins: Decision Support Systems: Tools, Expectations and Realities. Informatica 11 (1987), No. 3, pp. 18 - 24. Ipavec Marija: Produkt za upravljanje relacijske baze podatkov - VAX Rdb/VMS. Informatica 11 (1987), st. 2, str. 69 - 73. JanoS T.: Jedno proširenje biblioteke Ratfor-a potprogramima za obradu alfanumeričkih veličina. Informatica 11 (1987), St. 2, str. 53 - 56. Jeram Sonja: Computation May Hinge on Biological Materials. Informatica 11 (1987), No. 3, pp. 72 - 75. Jerman-BIaziÖ Borka; Izbira kodne strukture v 6. nivoju referenčnega modela OSI za potrebe prenosa in izmenjave podatkov. Informatica 11 (1987), St. 1, str. 83 - 87. Jerman-Blazi e Borka In Monika Kapus-Kolar: Komunikacijski in aplikacijski procesi v visjlh nivojih referenčnega modela OSI. Informatica 11 ( 1987 ) , St. 4, str. 84 - 88. Jockovic M. B. and D. M. tion of the Busline Crew informalica 1 1 (1987 ) , No. VelaSeviC: One Solu-Scheduling Problem. 4, pp. 35 - 39. KoCovie.P.: Geometrijsko modeliranje upotrebom Euleròvih formula. Informatica 11 (1987), St. 1, str. 67 - 72. Kocovic P.: A Relational Database for Represeni ta t i on of Machining Parts. Informatica 1 1 ( 1987 ) , No. 2, pp. 18 - 26. Kolbezen P.: Language Considerations of Parallel Processing Systems. Part One: Concurrent Microprocessing Sstems. Informatica 11 (1987), No. 2, pp. 31 - 35. Kolbezen P.: Language Considerations of Parallel Processing Systems. Part Two: Survey and Analysis of Concurrent Languages. Informatica 1 1 ( 1987 ) , No. 2, pp. 36 - 43. Kolbezen P., arhi tekture. 60 - 68. S. Mavric I Informalica n B. Mihoviloviö: RISC 11 (1987), St. 3, str. MeJ.a M.: Nekatere izkušnje pri uvajanju Prologa v pouk računalništva na srednjih solah. Informatica Il (1987), st. 3, str. 69 - 71. MalekoviC M.: Normalne forme u relacionim bazama podataka: logicke osnove. Informatica 11 ( 1 987 ), St. 1, str. 78 - 82. Markovic P.: Implikacija organizacije nervnih sistema na računarske sisteme. Informatica 11 (1987), St. 4, str. 77 - 83. Mihovilovic B., P. Kolbezen in J. Sile: Komunikacijski procesi v transputerskih sistemih. Informatica 11 (1987), St. 2, str. 74 - 77. Mihovilovic B., P. Kolbezen, and J. Sile: A Paradigm of Transputer System Implementation. Informatica 11 (1987), No. 4, pp. 54 - 58. OjsterSek M., V. Zumer, P. Kokol, and A. Zorman: A Simulation of Dataflow Computer Models and a Model of Fault Tolerant Dataflow Computer. Informatica 11 (1987), No. 4, pp. 59 - 63. PreSern S.: A Selected Survey puter Systems. Informatica 11 pp. 40 - 53. of Parallel Com-(1987), No. 4, Rugelj J. in M. Vidmar; Pregled arhitektur ter uporabljenih ISO standardov v MAP/TOP lokalnih mrežah. Informatica 11 (1987), st. 3, str. 54 -59. Semulic B.: Modeliranje informacijskih sistemov z upoštevanjem elementov dinamike realnega pojava. Informatica 11 (1987), St. 3, str. 41 -45. Smilevski M.: Metodološki pristup deflnisanju informaci on i h sadržaja baze podataka. Informatica 11 (1987), St. 1, str. 54 - 60. SCavniCar I.: Model informacijskega sistema za podporo kadrovski dejavnosti. Informatica 11 ( 1987 ) , St. 2. str. 44 - 52. Sile J. and B. RobiC: The Review of Some Data Flow Computer Architecture. Informatica 11 (1987), No. 1, pp. 61 - 66. Silc J. and B. RobiC: Data Flow Based Parallel Inference Machine. Informatica 11 (1987), No. 4, pp. 27 - 34. Temeljotov A., D. Mrdakoviö, D. PavSelj in D. Cuk: Občasna notranja diagnostika mikroračunalnika EPM-850. Informatica 11 (1987), st. 1, str. 73 - 77. Tercelj A.: Fraktali - Grafične skrivnosti računalniških umetnikov. Informatica 11 (1987), st.3, str. 46-50, Vidojkoviö D. i V. JovanovlC: ^ezik za specifikaciju infoloskog modela. Informatica 11 (1987), St. 2, str. 60-65. Vogel L.: Komun i ka'c i j sk 1 vmesnik SPI-11. Informatica 11 (1987), No. 3, pp. 38 - 40. Zeleznikar A. P.; Informatici na pot. Informatica 11 (1987), St. I, str. 3. Zeleznikar A. P.: Na poti k informaciji (On the Way to Information). Informatica 11(1987), St. I , str. 4 - 18. Zpleznikar A. P.: Information Determinations 1. Informatica 11 (1987), No. 2, pp. 3 - 17. Zeleznikar A. P.: Raziskave računalnikov in informacije v naslednjem desetletju. Informatica II (1987), St. 2, str. 57 - 59. Zeleznikar A. P.: Principles of Information. Informatica 11 (1987), No, 3, pp. 9 - 17. ZeleznikarA. P.: Artificial Intelligence Experiences Its Own Blindness. Informatica 11 (1987)i No. 3, pp. 25 - 28. Zeleznikar A. P.: Research of Computers and Information in the Next Decade. Informatica 11 ( 1987 ) , No. 3, pp. 51 - 53. Zeleznikar A. P.: Information Determinations II. Informatica 11 (1987), No. 4, pp. 8-25. ZivkoviC D.: Alternativni postupak određivanja tipova entiteta i akcija u JSD metodi projekto-vanja 1nformaci oni h sistema. Informatica 11 (1987), St. 4, str. 64 - 68. Novice In zanimivosti Ali bo fizika izrinila matematiko s prvega mesta med znanostmi (I. SCavniCar). Informatica 1 1 ( 1 987 ), St. 2, str. 83 - 84 . Report of Journey Zeleznikar A. P.: Parsys Expeditions to New Worlds. Informatica 11 (1987), No. 3, pp. 76 - 80. Nove knjige T. Winograd and F. Flores: Understanding Computers and Cognition: A New Foundation for Design. Informatica 11 (1987), St. I, str. 88 -89 (recenzent A. P. Zeleznikar). sma bralcev L. Omejec: Kritika danka B. Vilfana, V. Mahni-Ca in T. MohoriCa. Informatica 11 (1987), St. 1 , str. 90 - 91 . B. Vilfan, V. MahnlC in T. MohoriC: Odgovor na kritiko Članka avtorjev. Informatica 11 (1987), st. 1, str. 90.