Programare: Tema 1 - Planificarea sarcinilor

Cu această temă exersăm folosirea deciziei (operatorul condiţional) pentru scrierea unor funcţii simple a căror expresie de calcul depinde de intervalele de valori în care se află parametrii de intrare. Vom modela prin program o problemă simplă de planificare: sunt de efectuat mai multe sarcini, fiecare de durată cunoscută, pentru care nu e posibilă execuţia lor concomitentă.

Situaţia poate apărea pe un procesor care trebuie să execute mai multe programe, într-un flux de producţie, in viaţa de zi cu zi, etc. Se pune problema de a calcula momentul în care e terminată execuţia fiecărei sarcini, în funcţie de timpii la care au fost făcute solicitările.

În general, se pot alege diverse criterii de decizie: luând în considerare ordinea solicitărilor, prioritatea acestora, durata executiei sau termenul limită. Discutăm planificarea bazată pe prioritate: în momentul deciziei asupra următoarei sarcini de executat se alege cea de prioritate maximă între toate cele solicitate (se presupune că fiecare sarcină are asociată o prioritate cunoscută). Pot apărea două subcazuri:

o sarcină odată începută e dusă la sfârşit, chiar dacă în timpul execuţiei ei apar solicitări pentru sarcini de prioritate mai mare (planificare non-preemptivă)
în cazul apariţiei unei sarcini de prioritate mai mare, execuţia sarcinii curente e întreruptă şi reluată din punctul curent în momentul în care nu mai sunt alte solicitări mai prioritare (planificare preemptivă)

Presupunem în cele ce urmează ca planificarea se face dinamic, adică nu se cunosc dinainte momentele la care se solicită execuţia diverselor sarcini.

Exemplu: Presupunem că avem de planificat următoarele sarcini:

Sarcina Durata Prioritate Moment
solicitare
J1 10 1 5
J2 7 2 8
J3 8 3 12
În cazul planificării non-preemptive, sarcinile vor fi executate în felul următor:

Sarcina	Durata	Prioritate	Moment solicitare
J1	10	1	5
J2	7	2	8
J3	8	3	12

                      
                              -----------------
                              |               |--------------
          --------------------|       J3      |      J2     |
          |        J1         |               |             |
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|--> t
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
                ^       ^
	        J2      J3

Solicitările pentru sarcinile J2 şi J3 apar în timpul execuţiei lui J1, dar aceasta nu poate fi întreruptă. La încheierea lui J1 (t = 5 + 10 = 15), se dă în execuţie solicitarea existentă de prioritate maximă, J3, iar la terminarea acesteia se executa J2. În cazul planificării preemptive, aceleaşi sarcini se execută în felul următor:

                      
                        -----------------
                --------|               |----- 
          ------|  J2   |       J3      |  J2 |-------------|
          |  J1 |       |               |     |     J1      |
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|--> t
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
                ^       ^
	        J2      J3

La apariţia lui J2 (t = 8), e oprit J1 şi se trece la execuţia lui J2, acesta fiind prioritar. La fel, la apariţia lui J3 se opreşte J2 şi se începe execuţia lui J3. La terminarea lui J3, sarcina cea mai prioritară e J2, din care au mai rămas de executat 3 unităţi de timp. În final, se execută cele 7 unităţi de timp rămase din J1.

Problema de rezolvat

Fiind dat un tabel ca şi cel de mai sus, cu 2-3 sarcini, şi 1-2 dintre caracteristici parametri variabili (restul fiind daţi ca si constante), să se scrie pentru fiecare sarcină câte o funcţie care determină timpul la care se încheie execuţia sa. În programul principal, alegând câte o valoare pentru fiecare parametru, să se afişeze rezultatele, împreună cu câte un mesaj explicativ.

Exemple:

Sarcina Durata Prioritate Moment
solicitare
J1 10 1 x
J2 3 2 12
pentru planificare non-preemptivă

Sarcina Durata Prioritate Moment
solicitare
J1 6 1 x
J2 4 2 y
pentru planificare preemptivă

Sarcina	Durata	Prioritate	Moment solicitare
J1	10	1	x
J2	3	2	12

Sarcina	Durata	Prioritate	Moment solicitare
J1	6	1	x
J2	4	2	y

Marius Minea

Last modified: Sun Mar 54 17:38:25 EET 2006