Eksāmena uzdevumi

Eksāmenā jārisina jebkuras 2 problēmas no 4 dotajām (pēc jūsu izvēles). Par to pieskaitīs 20% pie jūsu atzīmes par kursu. Visos uzdevumos varat uzskatīt, ka ir runa par Java 1.4.x. (Java versijā 1.5 ir vairākas būtiskas atšķirības, piemēram, jautājumos par kolekcijām, t.i. java.util API). Lūdzu noformēt risinājumus elektroniski un pietiekami lasāmi. Darbu labotāji šoreiz saprot 3 elektronisku dokumentu formātus - HTML, PDF un MS Word. Labu veiksmi!

1. Problēma (Kolekcijas)

Situācijas apraksts

java.util.Set ir interfeiss, kurš dod iespēju strādāt ar Javas objektu kopām - t.i. kolekcijām, kurās elementi neatkārtojas un to secība nav svarīga. Šajā uzdevumā vajadzēs piedāvāt projektējumu, kā iespējami praktiski un vienkārši programmēt java.util.Set klasi ar dažām specifiskām īpašībām (vai arī pamatot, ka šādu klasi uzprogrammēt nav iespējams).

Uzdevums

Piedāvāt projektējumu kopu kolekciju klasei MySet (un tās iespējamām apakšklasēm), kurām būtu minētās īpašības:

  • MySet implementē interfeisu java.util.Set
  • MySet instances var ievietot citās kolekcijās (piemēram, dažādās java.util.* kolekcijās, kuras pieļauj patvaļīgus objektus, kā arī MySet tipa kolekcijās); turklāt šīs MySet instances var droši mainīt pēc pievienošanas citai kolekcijai.
  • MySet tipa kopas var saturēt pašas sevi kā elementus
  • MySet instances var klonēt; klonēšanas rezultātā izveidojas jauna instance, kurai veikta "dziļā kopēšana", t.i. visi šīs instances elementi arī tiek klonēti un tad pievienoti jaunajai MySet instancei. (Šo jāatšķir no "seklās kopēšanas", kad jaunā kopa satur tās pašas objektu references, kuras satur klonējamā/vecā kopa.)
  • MySet pieļauj iespēju mantot - t.i. var nākotnē tikt ieviestas apakšklases, kurām piemīt visas MySet īpašības un vēl kaut kas (piemēram, MySet var rasties vēlme pārdefinēt, ja gribas iekešot dažus nesen aplūkotus elementus, lai optimizētu daudzkārtēju identisku meklēšanu ātrumu, vai uzglabāt kopas elementu iespraušanas secību, utml.).

Risinājumam jāsatur pašas MySet un tās iespējamās apakšklases projektējums. Projektējumu var veidot ar UML diagrammu un/vai neformālu aprakstu palīdzību. Jums jāpaskaidro, kādas metodes tiks programmētas un kā tās var realizēt. Ja jūsu risinājums pārkāpj laba objektorientēta dizaina pamatprincipus, tad arī to vajag izskaidrot. Nav jāraksta pilns visu metožu kods, jo Set interfeiss ir diezgan liels - tikai jāanalizē, kuras metodes un kā ir jāimplementē; netriviālajām no tām pēc savas izvēles var dot vai nu implementāciju Javā, vai UML flow/sequence diagrammu, vai pseidokodu.

2. Problēma (Refaktorizācija)

Situācijas apraksts

Javas programmētājs Buņģis mēdz pārsaukt metodes savos Javas projektos, nemainot to parametru sarakstu un atgriežamo vērtību. Viņš to dara tāpēc, lai metožu nosaukumi atbilstu jaunākajām vārdu piešķiršanas konvencijām (naming conventions). Projektam pēc metodes pārsaukšanas jābūt kompilējamam (ja tas kompilējās pirms pārsaukšanas) un arī programmas uzvedība šīs pārsaukšanas rezultātā nedrīkst mainīties.

Buņģis ir izdomājis sekojošu algoritmu, kurš viņaprāt ļauj pilnīgi droši izmainīt Javas metodes nosaukumu no vārda method1(paramlist) uz method2(paramlist) klasē A. (Šeit paramlist apzīmē pārsaucamās metodes formālo parametru sarakstu.)

  1. Atrast klases "A" virsklasi, kura atrodas visaugstāk klašu mantošanas hierarhijā, un kurā implementēta metode method1(paramlist). Šo virsklasi apzīmējam ar TopAncestor (ja tādas nav, tad TopAncestor=A).
  2. Klasei TopAncestor atrast visas viņas apakšklases (bērnu, mazbērnu, ... klases), kuras pārdefinē metodi method1(paramlist). Apzīmēt visu šo klašu kopu ar RenamingSet. (Šī kopa satur arī pašu klasi TopAncestor un, protams, arī klasi A.).
  3. Katrai klasei B no kopas RenamingSet veikt soļus 4.-7.:
  4. Deklarēt jauno metodi method2(paramlist) ar to pašu atgriežamo vērtību, kas ir method1(paramlist), un pārkopē šajā jaunajā metodē vecās metodes "method1" ķermeni.
  5. Izmainīt vecās metodes method1(paramlist) ķermeni, par sekojošo:
    return method2(paramlist); 
    
  6. Atrast visas vecās metodes method1 references (vietas, kur tā tiek izsaukta), un izmainīt tās tā, lai tai vietā tiktu saukta jaunā metode method2 ar tiem pašiem aktuālajiem argumentiem.
  7. Izmest veco metodi method1(paramlist).

Ir viens gadījums, kad Buņģa algoritms ir, acīmredzot, jāmodificē - ja kādā no klasēm, kur tiek pārsaukta metode method1(paramlist) rodas vārdu kolīzija, t.i. tur jau eksistē method2(paramlist) un pārsaukšanu nevar izdarīt, iepriekš nemainot method2 nosaukumu.

Uzdevums

Pieņemsim, ka nevienā no klasēm, kuras ietilpst kopā RenamingSet sākotnēji nav metode method2(paramlist), t.i. vārdu konflikti nerodas.

  1. Vai eksistē arī citi gadījumi, kad Buņģa piedāvātais algoritms nestrādās? T.i., pildot to soli pa solim, pēc kāda soļa radīsies stāvoklis, kad:
    • Kārtējo algoritma soli nevar korekti izpildīt
      VAI
    • Projektu pēc kāda soļa veikšanas nevar sakompilēt
      VAI
    • Pēc kāda soļa mainās programmas uzvedība
    Atbildi pamatot, t.i. vai nu uzrakstīt, kāpēc Buņģa algoritms strādā vienmēr, vai arī neformāli (bez Javas koda!) aprakstīt dažus pretpiemērus, t.i. 1-3 situācijas, kad tas nestrādās.
  2. Pretpiemēru gadījumā katrai šādai situācijai uzrakstīt arī interesantos koda fragmentus, kā arī minēt modifikācijas, kuras būtu nepieciešamas Buņģa algoritmā, lai to varētu pildīt tā, lai nenotiktu neviena no punktā "A" aprakstītajām sliktajām situācijām (t.i. pēc katra soļa izpildes projekts joprojām kompilējas un tā uzvedība nemainās.)

3. Problēma (Pavedieni)

Situācijas apraksts (pusdienojošie filozofi)

Galds ar filozofiem

Pie apaļa galda sēž N filozofi (klases Phil instances), t.i. katram filozofam ir kaimiņš pa kreisi un pa labi. Filozofus piestartē un vada atsevišķa klase PhilController. Kad kontroles klasē tiek izsaukta metode getHungry(int n), uzstādās izsalkuma bits n-tajam filozofam (n var pieņemt vērtības no 0 līdz N-1). Izsalkušais filozofs pēc kāda laika savā metodē run() cenšas izpildīt metodes pickLeft(), pickRight(), eat(), releaseRight(), releaseLeft(). Šīs funkcijas jāizsauc tā, lai ievērotu sekojošo stāvokļu diagrammu:

Stāvokļu diagramma

public class Phil implements Runnable {
	private PhilController controller;

	private int philID;

	public Phil(PhilController cntrl, int id) {
		controller = cntrl;
		philID = id;
	}

	public void run() {  // run() pilda muuzhiigo ciklu
        ... // regulāri apskatās kontroliera masīvu "is_hungry"
	    ... // te var saukt pickXxx(), eat(), releaseXxx() metodes
	}

    public void pickLeft() {
	    ...
	}

	public void pickRight() {
	    ...
	}

	public void eat() {
        ...
        Thread.sleep(...); // eeshana allazh turpinaas nenoteiktu laiku
	    ...
		controller.is_hungry[philID] = false; // pēc ēšanas izsalkuma vairs nav
		Thread.sleep(...); // lai daudzpavedienu programmā pārbaudītu 
		                   // lielāku daļu no stāvokļu telpas, varat uzskatīt, 
						   // ka gulēšanas komandas (pasniedzējs) 
						   // var iespraust jebkurā vietā. 
	}

	public void releaseLeft() {
	    ...
	}

	public void releaseRight() {
	    ...
	}
}
public class PhilController {
    public static final int N = ...; // te ierakstīts kāds vesels skaitlis

    private Phil[] philosophers = new Phil[N]; 

	public boolean[] is_hungry = new boolean[N];

    // kontrolieris uzstāda n-taa filozofa izsalkumu
    public void getHungry(int n) {
        is_hungry[n] = true;
	}

	public static void main(String args[]) {
		PhilController controller = new PhilController();
		controller.setup();
		java.util.Random random = new java.util.Random(); 
		int count = 0; // skaita, cik kljuust izsalkushi
        while (true) { // forever
            int rnd = random.nextInt(N); 
			if (!is_hungry[rnd]) {
                is_hungry[rnd] = true;
				count++; 
            }
            Thread.sleep(...); // gulj nenoteiktu laiku
			// lai Phil pavedieni vareetu darboties
		}
	}

	public void setup() {
        for (int i = 0; i < N; i++) {
            philosophers[i] = new Phil(this, i);
        }
        for (int i = 0; i < N; i++) {
            philosophers[i].start(); 
        }
    }
}

Visas 5 augšminētās Phil metodes (pickXxx(), releaseXxx(), eat()) drīkst gaidīt gan ar Thread.sleep(), gan ar wait(). Laika posmā starp n-tā filozofa pickLeft() un releaseLeft() veidojas kritiskā sekcija ar (n-1)-ā filozofa darbībām starp pickRight(), releaseRight(), t.i. no diviem blakusesošiem filozofiem tikai viens drīkst lietot kopīgo dakšiņu. Tātad tie jāsinhronizē ar wait() un notify() vai notifyAll.

Uzdevums

Uzrakstiet kodu 5 Phil metodēm (pickXxx(), releaseXxx(), eat()) un arī metodei run() tā, lai izpildītos sekojošās īpašības to svarīguma secībā (t.i. nav jēgas censties apmierināt īpašību ar tālāku kārtas numuru, kamēr nav apmierināta īpašība ar iepriekšējo kārtas numuru). Kontroliera klasē šim nolūkam varat ieviest cik patīk daudzas palīgklases.

  • Kods ir korekts un pareizi sinhronizēts. T.i. 5 metodes tiek izsauktas pareizā secībā (filozofa uzvedība atbilst augšminētajai 3 stāvokļu diagrammai). Divu blakusesošu filozofu eat() metodes ir savstarpējas kritiskās sekcjas, t.i. to koda izpilde nedrīkst pārklāties.
  • Tiek izmantotas filozofu ēšanas paralēlisma radītā efektivitāte, t.i. tie filozofi, kuri nesēž blakus var ēst vienlaikus, ja viņi abi ir izsalkuši. Pretējā gadījumā visas turpmākās uzdevuma prasības varētu izpildīt vienkāršs "round-robin" algoritms - filozofu ēdināšana rindas secībā.
  • Neiestājas strupceļš (deadlock), t.i. nevar rasties riņķveidīga gaidīšana uz resursiem. Piemēram, nevar būt tā, ka katrs filozofs ir pacēlis savu kreiso dakšiņu un bezgalīgi gaida, kamēr viņa labās puses kaimiņš noliks savu kreiso dakšiņu, utt. pa apli.
  • Neiestājas dzīvais strupceļš (livelock), t.i. vismaz dažiem filozofiem izdodas regulāri paēst un count mainīgais neierobežoti aug. Nerodas situācijas, kur ēšana pēc kāda laika apstājas, jo filozofi neizsaukdami metodi eat() tikai paceļ un atbrīvo savas dakšiņas, t.i. bezgalīgi pārvietojas starp stāvokļiem 1 un 2 stāvokļu diagrammā.
  • Nenotiek badošanās (starving), t.i. ir garantija, ka KATRS filozofs izsauks metodi eat() neierobežotu skaitu reižu, ja vien pietiekoši bieži kļūs izsalcis.
  • Pieņemot, ka pavedienu pamodināšana metodē wait() ir dārga un filozofu ir daudz (t.i. N ir ļoti liels), realizēt filozofu pamodināšanas shēmu tā, lai paēdušais filozofs pamodinātu tikai konstantu skaitu citu filozofu (piemēram savus abus kaimiņus), nevis pilnīgi visus citus filozofus, kuri izsalkuši gaida (t.i. izsaucot vienkāršu notifyAll() uz visiem kopīga objekta). Tātad, realizējot M paēšanas reizes, pavedienu pamodināšana no metodes wait() notiek lineāru skaitu reižu (O(M)), nevis kvadrātisku skaitu reižu (O(M2)).

Jūsu risinājumam jābūt robustam, t.i. neatkarīgam no programmas izpildes ātruma un konkrētās JVM pavadienu plānotāja uzvedības. Tātad risinājumam jāpaliek spēkā arī tad, ja pēc tam kāds nejaucenis ierakstītu Jūsu kodā patvaļīgās vietās Thread.yield() vai Thread.sleep(...). Nedrīkst arī paļauties uz pavedienu prioritātēm, t.i., ka pavediens ar augstāku prioritāti izpildīsies pirmais, ja tas gaida kopā ar pavedienu ar zemāku prioritāti, jo pavedienu prioritātes nenozīmē vienu un to pašu visām JVM.

4. Problēma (Web prezentācijas slāņa projektēšanas šabloni)

Situācijas apraksts (sinhronizācijas žetoni)

Lai izvairītos no potenciāli bīstamas formas datu apstrādes atkārtošanas gadījumā, kad Web aplikācijas klients nospiež pogu "Refresh", ir izdomāti "sinhronizācijas žetoni" (sk. zīmējumu). Šajā projektēšanas šablonā klients katrā atbildē saņem no Web servera žetonu - unikālu stringu, kura vērtību Web serveris glabā klienta sesijas heštabulā, bet klients to saņem kā slēpto formas lauku vai kā pārlūkprogrammas sesijas sīkdatni (session cookie, t.i. "cookie", kurš dzīvo kamēr ir atvērts dotais pārlūkprogrammas logs).

Pieņemam, ka visus klienta pieprasījumus vispirms saņem Web aplikācijas kontrolieris - servlets, kurš izsauc nepieciešamās formu apstrādes darbības, bet pēc tam izsauc "forward" uz kādu JSP lapu (sk. zīmējumu). Ja izrādās, ka klients divreiz mēģina lietot to pašu žetonu, tad kontroles servlets šo pieprasījumu noraida.

Uzdevums

Pieņemsim, ka Web aplikācija visas formas nosūta ar metodi GET. Atbildēt uz sekojošiem jautājumiem:

  • Kuru HTTP atgriešanās kodu jāsūta Web aplikācijas klientam, lai, viņam nospiežot pogu "Refresh", netiktu izsaukta neviena JSP lapa, bet tomēr viņam arī pēc "Refresh" nospiešanas būtu pārlūkprogrammā ielādēts tas pats skats, kuru uzģenerēja pēdējā no JSP lapām, kura izpildījās.
  • Kāds ir minimālais sinhronizācijas žetonu garums bitos, lai Web aplikācija varētu nodrošināt to, ka klients nosūta N formas paredzētajā secībā, teiksim, f1.jsp, f2.jsp, ..., fN.jsp. Turpretī ikreiz, kad klients nospiež pogas "Back" un "Refresh", vai arī mēģina izvēlēties kādu virknē neiederīgu JSP lapu tieši (teiksim, no savām grāmatzīmēm), to Web aplikācija pamana un tās biznesa loģika neizpildās. (Pieņemam, ka risinājumam ar žetoniem nav jāizsargājas pret ļauniem klientiem, kuri mēģinātu viltot žetonus, lai pildītu aplikāciju tai neparedzētā secībā.)
  • Uzzīmēt sinhronizācijas žetonu risinājumam atbilstošu klašu projektējumu kā klašu UML diagrammu (kontroles servlets, žetonu apstrādes klases, utml.). Uzzīmēt "sequence" UML diagrammu, kura apraksta šo klašu sadarbību tad, kad Web aplikācija apstrādā kārtējo Web klienta pieprasījumu.

Bibliogrāfija


Lapa mainīta 2005-01-15 03:35:58