Fire de executie si procese

1.Procese automate

Procesele automate sau batch-urile nu sunt conectate către un terminal.Mai degrabă acestea sunt task-uri care pot fi puse într-o coadă de aşteptare în care îşi aşteaptă execuţia într-o ordine FIFO.Asemenea task-uri pot fi executate folosind una din următoarele criterii:

*La o anumită dată şi oră folosind comanda at.

*La perioade în care încărcarea sistemului este suficient de joasă pentru a accepta job-uri extra utilizând comanda batch.În mod implicit , sarcinile sunt puse într-o coadă de aşteptare până când încărcarea sistemului este mai joasă decât 0.8.

În medii mari, administratorul de sistem preferă prelucrarea pe loturi când cantităţi mari de date trebuiesc procesate sau când task-urile solicită multe resurse de sistem pe un sistem destul de încărcat.Prelucrarea pe loturi este totodată utilizat pentru opitimizarea performanţelor sistemului.

2.Daemon-urile

Daemonii sunt procese de tip server care rulează continuu.În majoritatea cazurilor ele sunt iniţializate la pornirea sistemului şi aşteaptă în background până când serviciul lor este solicitat.

3.Procesele interactive

Acestea sunt iniţializate şi controlate printr-o sesiune de terminal.Cu alte cuvinte trebuie să existe cineva conectat la sistem pentru a porni aceste procese.Nu sunt pornit automat şi nu fac parte din funcţiile sistemului.Aceste procese pot rula în prim plan , ocupând terminalul care a pornit programul şi nu poţi porni alte aplicaţii atâta timp cât aceste procese rulează în prim plan.


Controlul proceselor

(parte din) comandă	Semnificaţie
regular_command	Rulează această comandă în prim plan
command &	Rulează această comandă în plan secundar
Jobs	Arată procesele/comenzile ce rulează în background
Ctrl+Z	Suspendă(stopează,dar nu termină) un proces care rulează în prim plan.
Ctrl+C	Intrerupe(termină şi renunţă) un proces ce rulează în prim plan
%n	Fiecare proces ce se exxecută în plan secundar primeşte un număr asociat cu acesta.Utilizând % putem să ne referim la job folosind nr.
bg	Reactivează un program suspendat din background
fg	Pune jobul înapoi în prim plan.
Kill	Termină un process

Crearea proceselor

Un nou proces este creat , deoarece un proces existent creează o copie a acestuia.Acest proces-copil (child process) prezintă acelaşi mediu ca al părintelui , doar ID-ul procesului este diferit.Această procedură poartă numele de bifurcare din englezul forking.

Dupa procesul de forking , spaţiul adresă a procesului copil este suprascris cu data noului proces.Aceasta se face printr-un apel exec la sistem.Mecanismul fork-şi-exec comută o veche comandă cu una nouă , în timp ce mediul în care noul program se execută rămâne acelaşi , incluzând configuraţia dispozitivelor de intrare şi ieşire , variabilele de mediu si priorităţile.Acest mecanism este folosit pentru a crea toate procesele UNIX , prin urmare se aplică tuturor sistemelor de operare linux.Chiar primul proces , init , cu ID-ul de 1 , este bifurcat în timpul procedurii de boot.

Mecanismul fork-şi-exec este ilustrat în următoarea schemă. Se observă că ID-ul procesului se schimbă după procedura de fork :

Există câteva situaţii când procesul init devine procesul părinte al unui proces din cadrul unui sistem chiar daca acesta nu a fost iniţializat de el.Multe programe , de exemplu, transformă procesele lor in procese de tip daemon astfel încât să poată continua să ruleze când procesul părinte îşi încetează activitatea sau este oprit din rulare.De exemplu cazul unui window manager.Porneşte un proces xterm care generează un shell ce acceptă comenzi.Astfel procesul este pasat câtre procesul init în felul acesta window managerul respinge orice fel de responsabilitate asupra procesului.În urma acestui mecanism este posibil să schimbăm window manager-ul fără a întrerupe aplicaţiile care rulează.

Terminarea proceselor

Atunci când un proces se termină în mod normal (nu este afectat de comanda kill sau interupt) programul returnează părintelui exit status-ul.Exit status-ul este un număr returnat de program oferind rezultatul execuţiei unui program.Acest sistem îşi are originea din limbajul de programare C în cadrul căreia UNIX-ul a fost scris.

Codurile returnate pot fi interpretate de părinte sau în scripturi.Valorile acestea sunt specifice fiecărui program.Această informaţie poate fi găsită de obicei în paginile man al unui program specific., de exemplu comanda grep returnează -1 dacă nu au fost găsite nici un rezultat astfel putând fi afişat mesajul “No files found”.

Semnale

Procesele sfârşesc deoarece primesc un semnal.Există multiple semnale ce pot fi transmise unui proces.Comanda kill –l afişează o listă de semnale.Majoritatea semnalelor sunt pentru uz intern pentru sistem sau pentru programatori când scriu cod.Ca user , îţi vor trebui următoarele semnale :

Numele semnalului	Numărul semnalului	Semnificaţia
SIGTERM	15	Termină procesul într-un mod ordonat
SIGINT	2	Întrerupe procesul.Un proces poate ignora acest semnal
SIGKILL	9	Înterupe procesul.Un proces nu poate ignora acest semnal
SIGHUP	1	Semnal specific daemon-urilor.

Atributele procesului

Cu ajutorul comenzii ps pot fi vizualizate caracteristicile unui proces .

ID-ul procesului sau PID – reprezintă un număr unic de identificare care se referă la proces.Acel număr identifica procesul în sistem.

ID-ul procesului părinte sau PPID : numărul procesului (PID) care a determinat startul acestui proces.

Numărul ‘nice’ – gradul de prietenie al acestui proces referitor la alte procese ( a nu fi confundat cu prioritatea procesului , care este calculat bazat pe numărul ‘nice’ şi gradul de folosinţă CPU recentă a procesului).

Terminal sau TTY: terminalul la care este conectat procesul în sine.

Numele utilizatorului real şi utilizatorului efectiv (RUID şi EUID) : proprietarul procesului .Proprietarul real este userul care emite comanda , userul efectiv este cel care determină accesul la resursele sistemului.

RUID şi EUID sunt de obicei aceleaşi , şi procesul are aceleaşi drepturi de acces ca userului emitent .

Pentru a clarifica acest aspect explicăm următorul exemplu.

theo:~> ls -l /usr/bin/mozilla

-rwxr-xr-x 1 root root 4996 Nov 20 18:28 /usr/bin/mozilla*
theo:~> mozilla &

[1] 26595

theo:~> ps -af

UID PID PPID C STIME TTY TIME CMD

theo 26601 26599 0 15:04 pts/5 00:00:00 /usr/lib/mozilla/mozilla-bin

theo 26613 26569 0 15:04 pts/5 00:00:00 ps -af

Browser-ul mozilla din /usr/bin este deţinut de user-ul root.Când user-ul theo porneşte acest program , procesul în sine şi toate procesele pornite de către procesul iniţial , vor fi deţinute de user-ul theo şi nu de administratorul de sistem.Când mozilla necesită acces la anumite fişiere , acel acces va fi determinat de permisiunile lui theo si nu cele ale root-ului.

Proprietarul real şi cel efectiv al grupului (RGID şi EGID):Proprietarul grupului real al unui proces este grupul primar al utilizatorului care a pornit procesul.Proprietarul efectiv al grupului este de obicei acelaşi , exceptând atunci când modul de acces SGID a fost aplicat unui fişier.

De observat e că ps oferă un statu momentan al proceselor active , este o înregistrare la un singur moment de timp.Programul top afişează o imagine mult mai precisă prin actualizarea rezultatelor oferite de ps (cu o grămadă de opţiuni) , o dată la fiecare 5 secunde , generând o nouă listă de procese .

12:40pm up 9 days, 6:00, 4 users, load average: 0.21, 0.11, 0.03

89 processes: 86 sleeping, 3 running, 0 zombie, 0 stopped

CPU states: 2.5% user, 1.7% system, 0.0% nice, 95.6% idle

Mem: 255120K av, 239412K used, 15708K free, 756K shrd, 22620K buff

Swap: 1050176K av, 76428K used, 973748K free, 82756K cached

PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND

5005 root 14 0 91572 15M 11580 R 1.9 6.0 7:53 X

19599 jeff 14 0 1024 1024 796 R 1.1 0.4 0:01 top

19100 jeff 9 0 5288 4948 3888 R 0.5 1.9 0:24 gnome-terminal

19328 jeff 9 0 37884 36M 14724 S 0.5 14.8 1:30 mozilla-bin

1 root 8 0 516 472 464 S 0.0 0.1 0:06 init

2 root 9 0 0 0 0 SW 0.0 0.0 0:02 keventd

3 root 9 0 0 0 0 SW 0.0 0.0 0:00 kapm-idled

4 root 19 19 0 0 0 SWN 0.0 0.0 0:00 ksoftirqd_CPU0

5 root 9 0 0 0 0 SW 0.0 0.0 0:33 kswapd

6 root 9 0 0 0 0 SW 0.0 0.0 0:00 kreclaimd

7 root 9 0 0 0 0 SW 0.0 0.0 0:00 bdflush

8 root 9 0 0 0 0 SW 0.0 0.0 0:05 kupdated

9 root -1-20 0 0 0 SW< 0.0 0.0 0:00 mdrecoveryd

13 root 9 0 0 0 0 SW 0.0 0.0 0:01 kjournald

89 root 9 0 0 0 0 SW 0.0 0.0 0:00 khubd

219 root 9 0 0 0 0 SW 0.0 0.0 0:00 kjournald

220 root 9 0 0 0 0 SW 0.0 0.0 0:00 kjournald

Prima linie de top conţine acceşi informaţie afişată de comanda uptime :
jeff:~> uptime

3:30pm, up 12 days, 23:29, 6 users, load average: 0.01, 0.02, 0.00

Datele acestor programe sunt stocate printre altele , în /var/run/utmp (informaţii despre userii momentan conectaţi) şi în fişierul virtual /proc , de exemplu , /proc/loadavg (informaţii de ocupare medie).Există tot felul de aplicaţii grafice pentru a vizualiza aceasta dată cum ar fi Gnome System Monitor şi lavaps.

Relaţiile între procese pot fi vizualizate folosing comanda pstree:

sophie:~> pstree

init-+-amd

|-apmd

|-2*[artsd]

|-atd

|-crond

|-deskguide_apple

|-eth0

|-gdm---gdm-+-X

| `-gnome-session-+-Gnome

| |-ssh-agent

| `-true

|-geyes_applet

|-gkb_applet

|-gnome-name-serv

|-gnome-smproxy

|-gnome-terminal-+-bash---vim

| |-bash

| |-bash---pstree

| |-bash---ssh

| |-bash---mozilla-bin---mozilla-bin---3*[mozilla-bin]

| `-gnome-pty-helper

|-gpm

|-gweather

|-kapm-idled

|-3*[kdeinit]

|-keventd

|-khubd

|-5*[kjournald]

|-klogd

|-lockd---rpciod

|-lpd

|-mdrecoveryd

|-6*[mingetty]

|-8*[nfsd]

|-nscd---nscd---5*[nscd]

|-ntpd

|-3*[oafd]

|-panel

|-portmap

|-rhnsd

|-rpc.mountd

|-rpc.rquotad

|-rpc.statd

|-sawfish

|-screenshooter_a

|-sendmail

|-sshd---sshd---bash---su---bash

|-syslogd

|-tasklist_applet

|-vmnet-bridge

|-xfs

`-xinetd-ipv6

2. Algoritmi de gestiune de procese si de fire de executie
2.1 Algoritmi de alocare a timpului de procesor

Andrei Stefanescu (433 A)

2.1.1 Algoritmi “standard”
2.1.1.1 Round-Robin (Ordonare circulara)

Este algoritmul cel mai vechi, cel mai simplu si cel mai fiabil. El nu este insă utilizabil in nucleele de timp real. Se studiaza doar pentru ca pune in evidenta problemele care apar in medii de timp real.

Fiecare task poseda o cuanta de timp, pe perioada careia el este autorizat sa ocupe procesorul. Cand cuanta se scurge, procesorul este rechizitionat si alocat altui task din coada. Daca taskul se termina inaintea sfarsitului cuantei sale, timpul ramas este alocat altui task. Atunci cand sistemul cuprinde procese cu frecventa mica sau cu probabilitatea mare de a se bloca, puterea procesorului este atribuita aproape in intregime taskului in executie. In caz contrar, daca sistemul are procese efectuand putine intrari/iesiri, puterea procesorului se imparte la numarul de taskuri prezente in coada.

Este asemănător cu algoritmul F.C.F.S (First Come First Served) dar procesul curent poate fi întrerupt oricând de către S.O. dacă ii expiră cuanta de timp).

2.1.1.2 Shortest job first
Algoritmul măsoară durata rafalei de instrucţiuni pentru fiecare proces şi încearcă să promoveze pe procesor procesele cu cea mai scurtă rafală. Poate fi şi preemptiv (procesul curent poate fi întrerupt oricând de către S.O. , dacă ii expiră cuanta de timp) şi nepreemptiv (procesul nu poate fi întrerupt oricând de către S.O., acesta cedează controlul de bunăvoie la terminarea rafalei de instrucţiuni sau la intrarea in zona de aşteptare; in cazul unor erori, un proces poate bloca întregul S.O.). Dar in mare parte este nepreemptiv

Duratele de execuţie a proceselor sunt cunoscute în avans si dacă mai multe procese sunt “gata de execuţie” simultan, planificatorul alege (pentru a trecere “în execuţie”) procesul cu cea mai mică durată de execuţie.

Exemplu:

Algoritmul SJF este optimal din punctul de vedere al duratei medii a unui ciclu de servire numai în cazul în care toate joburile care trebuie servite sunt disponibile simultan.

Exemplu de joburi nedisponibile simultan:

A(3) B(5) – disponibile la momentul 0

C(1) D(1) – disponibile la momentul 4

Dacă se foloseşte algoritmul SJF, se obţine mean turnaround time = 5,5.

Varianta preemptiva a algoritmului SJF este Shortest Remainning Time Next (SRTN. Durata totală de servire a unui proces trebuie să fie cunoscută în avans. Planificatorul de procese alege (pentru a trece în execuţie) procesul a cărui durată reziduală de servire este cea mai mică. La sosirea unui nou job, durata totală de servire a acestuia este comparată cu durata reziduală de servire a procesului aflat în curs de servire. Dacă durata totală de servire a noului job este mai mică, atunci procesul aflat în curs de servire este suspendat şi este trecut în execuţie noul proces.

Algoritmul SJF favorizează procesele de scurta durata in defavoarea celor de lunga durata. Dezavantajul acestui algoritm este ca necesita o cunoaştere precisa a timpului de rulare al unui proces , iar acesta informaţie nu este disponibila de obicei.

2.1.1.3 Priority scheduling (Ordonare bazata pe priorităţi)

Ordonarea circulara presupune ca toate taskurile au aceeaşi prioritate. In comanda unui proces industrial, aceasta situaţie este rareori un caz general. Adesea taskurile trebuiesc aranjate in funcţie de priorităţile sarcinilor de îndeplinit. Astfel apare ordonarea bazata pe priorităţi, având un singur task pe nivel de prioritate.

Principiul este simplu. Fiecare task primeşte, la crearea sa, un nivel de prioritate. Planificatorul lansează taskul cel mai prioritar, aflat in starea GATA DE EXECUTIE. Este conservat acest task atâta timp cat nu se blochează sau termina. Daca vreo întrerupere lansează un task material care activează la rândul sau un task logic, planificatorul trebuie apelat la sfârşitul taskului material pentru a compara priorităţile taskurilor in curs. Daca taskul curent este mai puţin prioritar, decât cel activat de rutina de întrerupere, o comutare trebuie sa aibă loc.

Asignarea priorităţilor:

-static: priorităţi asignate în conformitate cu ierarhia utilizatorilor proprietari

-dinamic: atunci când trebuie îndeplinite anumite obiective

ex: se setează prioritatea unui proces la 1/f, cu f = procentul consumat din cuanta anterioară

Variante combinate:-Procesele pot fi grupate în clase de priorităţi

-Se utilizează un algoritm de planificare bazat pe priorităţi la nivelul claselor

-Se utilizează un algoritm RR în cadrul fiecărei clase

Dacă nu se ajustează priorităţile claselor, există pericolul ca procesele din clasele mai puţin prioritare să nu se execute niciodată.

Are ca dezavantaj blocarea indefinită sau înfometare. O soluţie la problema înfometării ar fi îmbătrânirea= o metodă de a creşte prioritatea proceselor care aşteaptă de mult timp in coadă.

2.1.1.4 Multiple priority queues (Ordonare bazate pe priorităţi cu cozi multiple)

Este o varianta a ordonării pe baza de prioritate. Principiul consta in a combina ordonarea circulara (Round Robin) cu cea bazata pe prioritari (Priority scheduling). In acest mod, mai multe taskuri pot avea acelaşi nivel de prioritate. Daca mai multe taskuri sunt prezente in coada cea mai prioritara, aceste taskuri sunt in execuţie, după modelul roundrobin, de fiecare data se rulează in maniera round-robin doar procesele din clasa de prioritate maxima (ignorându-se restul claselor); când aceasta nu mai conţine procese, se procedează la fel cu clasa următoare. Daca nu este decât un singur task pe nivel de prioritate, modelul este cel bazat pe priorităţi.

Procesele se împart pe mai multe categorii şi fiecare categorie are propriul ei algoritm de planificare şi propria coadă de procese. Exemplu: procese background, procese sistem,procese pe loturi.

Priorităţile proceselor trebuie ajustate din când in când (si mutateastfel dintr-o clasa in alta), altfel exista risc de înfometare pentru procesele din clasele inferioare.

Exemple:

1. Sistemul CTSS efectua lent comutarea intre procese, deoarece nu putea tine in memorie decât un proces; proiectanţii au constatat ca era mai eficient sa se dea proceselor limitate de calcule o cuanta mare de timp din când in când decât o cuanta mica frecvent, deoarece se reduce swapping-ul; nu se puteau da insa cuante mari tuturor proceselor, deoarece se marea prea mult timpul de răspuns pentru cererile scurte (am văzut).

Soluţia: S-au creat de clase de prioritate; procesele din clasa maxima erau rulate pentru 1 cuanta, cele din clasa următoare pentru 2 cuante, cele din clasa următoare pentru 4 cuante, etc; când un proces isi folosea in întregime cuanta, era mutat o clasa mai jos; când era apăsat Enter de la un terminal, procesul care ţinea de terminalul respectiv era mutat in prima clasa.

De ex. un proces care ar necesita 100 cuante pentru calcule ar primi prima data 1 cuanta, după care ar fi mutat pe disc, apoi 2 cuante, după care ar fi mutat pe disc, s.a.m.d. 4, 8, 16, 32 si in final 64 (din care ar mai folosi doar 37) cuante, fiind swapat in total de 7 ori in loc de 100 in cazul folosirii unui algoritm round-robin pur; totodată, pe măsura ce cobora in clasele de priorităţi, ar fi executat din ce in ce mai rar, păstrând procesorul pentru procese interactive scurte. A doua regula preîntâmpina situaţia când un proces era pedepsit constant daca la inceput avea nevoie sa execute mai mult timp calcule, chiar daca ulterior devenea interactiv

(apăsarea lui Enter implica presupunerea ca procesul e pe cale sa devina interactiv). La un moment dat insa un utilizator cu un proces puternic orientat pe calcule a observat ca apăsând Enter la întâmplare la interval de câteva secunde isi scurtează considerabil timpul de răspuns.
2. Sistemul XDS 940 (construit la Berkley) folosea 4 clase de priorităţi, numite (in ordinea descrescătoare a priorităţilor): terminale, I/O, cuante scurte, cuante lungi. Cand un proces care astepta date de la terminal era activat, era trecut in clasa 1; când un proces blocat in aşteptarea discului devenea ready, era trecut in clasa 2; când un proces era in execuţie când i-a expirat cuanta era trecut in clasa 3; când un proces isi folosea cuanta integral de mai multe ori la rând fără sa se blocheze (in aşteptarea terminalului sau a altor operaţii de I/O), era trecut in clasa 4. Astfel erau favorizate procesele interactive in pofida celor de fundal.
2.1.1.5 Inheritance scheduling
Acest este un algoritm descris intr-o hartie de la CMU. Procesele pot da timpul procesorului proceselor „copil” si sa se comporte cum ar fi programate de ei insisi. In acest fel , mai multe tipuri de planificari pot fi implementate : o planificare pentru procese in timp real , o planificare pentru procese interactive , o planificare pentru un lot de prelucrare, etc. Planificatorul de baza implementat de S.O. planifica procesele. |Cat timp procesele individuale ar putea oferi un altfel de planificare , planificarea de baza foloseste formulare MPQ.
2.1.1.6 Lottery scheduling (Planificarea in sistem de loterie)
Acest algoritm atribuie proceselor bilete de loterie pentru diverse resurse (de exemplu pentru timpul alocat pe procesor); atunci când trebuie luata o decizie de planificare se alege un bilet la întâmplare iar procesul care deţine biletul primeşte resursa (de exemplu in planificarea proceselor la procesor , sistemul poate desfăşura o loterie de 50 de ori pe secunda iar fiecare câştigător sa primească 20 milisecunde timp alocat pe procesor).

Procesele importante pot primi mai multe bilete; numărul de bilete primite de un proces la creare influenţează timpul sau de răspuns; de ex. daca exista 100 bilete pentru procesor si un proces deţine 20 bilete, va avea 20 % şansa de a câştiga la fiecare loterie, deci pe termen lung va obţine circa 20 % din timpul procesorului. Procesele cooperante pot schimba bilete intre ele; de ex. când un proces client trimite un mesaj unui proces server si apoi se blochează, poate trimite toate biletele sale serverului pentru a mari şansele acestuia de a se executa in continuare; in absenta clienţilor serverele nu au nevoie de bilete.

Cotoc Ginel Dragos ( 433 A )

2.1.2 Algoritmi folositi in sistemele de operare moderne
2.1.2.1 Multilevel Feedback Queue (Windows NT)
Planificatorul Multilevel Feedback Queue a fost pentru prima data dezvoltat de Corbato in 1962 intr-un sistem cunoscut sub numele de Compatible Time-Sharing System (CTSS), acest lucru ia adus lui Corbato la acordarea premiului Turing.

MLFQ urmareste rezolvarea a doua probleme. Prima se refera la optimizarea timpuli de intoarcere (turnaround time), care e facuta prin rularea srcinilor simple la inceput. A doua problema se refera la faptul ca MLFQ ar dori sa faca un sistem sa se simta sensibil la utilizatori interactivi, minimizand astfel timpul de raspuns (response time); din nefericire algoritmi precum Round Robin reduc timpul de raspuns dar sunt ineficienti cand vine vorba de timpul de intoarcere.

Problema se rezuma la cum sa proiectezi un planificator care sa minimizeze timpul de raspuns.