1.Memoria cache. Organizarea generala a memoriei cache.

Memoria cache este o memorie rapid realizat cu tehnologie SRAM, aflat ntre memoria principal i procesor, mai lent, se bazeaz pe DRAM. Memoria cache conine copia unor informaii din memoria principal.Poate fi accesat aproape la fel de rapid ca registrele, n mod obinuit, n dou pn la patru cicluri de tact. Odat cu creterea diferenei de performan dintre procesor i memoria principal, ntre memoria cache L1 i memoria principal a fost inserat o memorie cache adiional, de capacitate mai mare, numit cache L2, care poate fi accesat n aproximativ zece cicluri de tact. n prezent este folosit din ce n ce mai des nc un nivel adiional de cache, numit cache L3, aflat ntre cache L2 i memoria principal. Memoria cache L3 poate fi accesat n treizeci sau patruzeci de cicluri de tact. Organizarea general a memoriei cache Considerm c adresa de memorie are m bii. Rezult M = 2

m adrese unice.

Aa cum reiese din figura, o memorie cache este organizat sub forma unui ir de S = 2

s seturi. Fiecare set conine L linii. Fiecare linie conine un bloc de

date B = 2b octei, un bit de validitate i t = m (b + s) bii de etichet. Bitul de

validitate arat dac linia conine sau nu informaie util. Eticheta identific unic un bloc din linia cache. n general, organizarea unei memorii cache poate fi caracterizat de tuplul (S, L, B, m). Capacitatea unei memorii cache, C, este calculat n funcie de dimensiunea agregat a tuturor blocurilor. Biii de etichet i bitul de validitate nu sunt inclui. Astfel, C = S L B. Cnd procesorul dorete s citeasc un cuvnt de la adresa A din memoria principal, trimite adresa A la memoria cache. Dac memoria cache conine o copie a cuvntului de la adresa A, l trimite imediat la procesor. Se pune problema cum tie memoria cache dac conine o copie a cuvntului de la adresa A? Memoria cache este organizat astfel nct s poat gsi cuvntul dorit prin simpla inspectare a biilor din adres. Parametrii S i B genereaz o partiionare a celor m bii de adres n trei cmpuri. Biii s din adresa A reprezint un index n irul de S seturi. Primul set este setul 0, apoi setul 1, .a.m.d. Interpretai ca ntreg fr semn, biii s indic setul n care trebuie stocat cuvntul. Odat cunoscut setul, biii de etichet t din adresa A ne indic linia din set care conine cuvntul. O linie conine cuvntul dac i numai dac bitul de validitate este setat i biii de etichet corespund biilor de etichet din adresa A. Odat identificat linia pe baza etichetei, biii b din adres ne dau deplasamentul cuvntului n blocul B de octei.

2. Memorii cache cu mapare directa

Memoriile cache sunt grupate n diferite clase n funcie de numrul de linii din set. O memorie cache cu exact o singur linie per set (L = 1) se numete memorie cache cu mapare direct. Memoriile cache cu mapare direct sut cel mai simplu de implementat. Presupunem c avem un sistem cu un procesor, o memorie cache i o memorie principal. Atunci cnd procesorul ncearc s citeasc un cuvnt din memoria principal, se verific dac respectivul cuvnt deja nu se afl cumva n memoria cache. Dac memoria cache conine o copie a cuvntului, cuvntul este furnizat procesorului (reuit sau cache hit). n caz contrar, procesorul trebuie s atepte pn cnd memoria cache aduce din memoria principal o copie a blocului care conine cuvntul, iar apoi cuvntul este extras i returnat procesorului (ratare sau cache miss). Procesul pe care l parcurge o memorie cache pentru a determina dac o cerere este reuit sau nu i apoi de a extrage cuvntul, const din trei pai: selecia setului, identificarea liniei i extragerea cuvntului. n primul pas, memoria cache afl indexul setului pe baza biilor s (interpretai ca ntreg fr semn), aflai la mijlocul adresei A. n al doilea pas se identificat linia. Pentru o memorie cu mapare direct acest proces este uor i rapid deoarece exist o singur linie per set. O copie a cuvntului se afl n linie dac bitul de validitate este setat i eticheta din linie corespunde etichetei (biii t) din adres.

n figur att bitul de validitate ct i biii de etichet sunt identici, aadar este o reuit. Pe de alt parte, dac bitul de validitate nu este setat sau biii de etichet nu corespund, avem o ratare. n caz de reuit, cuvntul se afl undeva n bloc. Al treilea pas determin de la ce deplasament n bloc ncepe cuvntul dorit. Deplasamentul este dat de biii b din adres. Blocul este un ir de octei iar biii b au rol de index n acel ir. n cazul unei ratri, memoria cache trebuie s primeasc blocul de la memoria principal i s l introduc n una din liniile prezente n setul dat de biii s. n general, dac setul este plin de linii valide, atunci una din ele trebuie nlocuit (evicted). Pentru o memorie cache cu mapare direct, n care fiecare set conine o singur linie, politica de nlocuire este simpl: noua linie extras nlocuiete linia curent. Principalul dezavantaj al acestei tehnici este c n memoria cache exist o locaie fix pentru orice bloc de memorie. Dac un program face referire n mod repetat la cuvinte din dou blocuri diferite care se mapeaz la aceeai linie, blocurile vor fi interschimbate n mod continuu n memoria cache i rata de reuit va fi redus.

3.Memorii cache cu asociativitate pe seturi

O metod care elimin dezavantajul maprii directe este maparea asociativ. Memoriile cache cu asociativitate pe seturi au L > 1. O memorie cache cu 1 < L < C/B se numete L-way set associative cache. De exemplu, dac fiecare set conine dou linii, memoria cache se numete 2-way set associative cache. Pentru o memorie cache cu asociativitate pe seturi, ca s afle dac cuvntul cerut se afl ntr-un set, procesul de identificare a liniei necesit circuite suplimentare care verific etichetele i biii de validitate pentru mai multe linii n paralel. O memorie convenional este un ir de valori care primete ca intrare o adres i returneaz valoarea stocat la acea adres. O memorie asociativ este un ir de perechi (cheie, valoare) care primete ca intrare cheia i returneaz valoarea din una din perechile (cheie, valoare) corespunztoare cheii date. Astfel, fiecare set dintr-o memorie cache asociativ poate fi considerat o mic memorie asociativ n care cheile sunt formate din concatenarea biilor de etichet i validitate, iar valorile sunt reprezentate de coninutul unui bloc. n

memoriile cache cu asociativitate pe seturi fiecare linie din set poate conine oricare din blocurile de memorie ce pot fi mapate la acel set. Astfel, memoria cache trebuie s verifice fiecare linie din set, n cutarea unei linii valide (linia a crei etichet corespunde etichetei din adres). Dac memoria cache gsete o astfel de linie, atunci biii b calculeaz deplasamentul pn la cuvntul dorit.

Dac cuvntul nu se afl n niciuna din liniile setului, memoria cache trebuie s aduc blocul care conine cuvntul din memoria principal. Atunci cnd este ncrcat un bloc nou n memoria cache, unul din blocurile existente n aceast memorie trebuie nlocuit. Cea mai simpl politic de nlocuire este s se aleag (aleator) o linie la ntmplare. Alte politici mai sofisticate, n ncercarea de a minimiza probabilitatea ca linia nlocuit s fie necesar n viitorul apropiat, se bazeaz pe principiul proximitii datelor. De exemplu, o politic LFU (Least Frequently Used) nlocuiete linia care a fost adresat de cele mai puine ori ntr-o anumit fereastr de timp. O politic LRU11 (Least Recently Used) nlocuiete linia care a fost cel mai puin recent adresat ntr-o anumit perioad de timp. Toate aceste politici necesit timp i circuite adiionale.

4. Memorii cache complet asociative

O memorie cache complet asociativa jos, const dintr-un singur set (L = C/B) care conine toate liniile. Deoarece exist un singur set, selecia acestuia se face uor. Nu sunt necesari bii s n adres. Adresa este partiionat numai pentru etichet i deplasamentul blocului. Identificarea liniei i selecia cuvntului are loc la fel ca la orice memorie cache cu asociativitate pe seturi, diferena fiind n principal o problem de scalabilitate. Deoarece circuitul cache trebuie s caute multe etichete n paralel, este dificil de realizat o memorie cache asociativ de capacitate mare i rapid. n consecin, memoriile cache complet asociative sunt adecvate (convenabile) pentru memorii cache de dimensiuni mici, cum ar fi TLB din memoria virtual.

5. Tehnica de scriere a memoriilor cache Situatia este mai complicata la scrierea unei memorii cache decat la citire. S presupunem c procesorul scrie un cuvnt deja prezent n memoria cache (write hit). Dup ce memoria cache actualizeaz copia sa, trebuie s decid cum va proceda n continuare, astfel nct s actualizeze i copia cuvntului din memoria principal. Cea mai simpl soluie, cunoscut sub numele de write-through, este s scrie imediat blocul cuvntului n memoria principal. Dei simplu, write-through are dezavantajul c fiecare scriere genereaz trafic pe magistrala de memorie. O alt tehnic, numit write-back, amn actualizarea cuvntului din memoria principal ct mai mult posibil, scriind blocul actualizat n memoria principal numai atunci cnd acesta trebuie nlocuit de algoritmul de nlocuire. Datorit principiului proximitii, write-back poate reduce semnificativ traficul pe magistrala de memorie, dar are dezavantajul unei complexiti adiionale. Memoria cache trebuie s monitorizeze un bit adiional (dirty bit) pentru fiecare linie. Acesta indic dac blocul a fost modificat sau nu. Alt problem apare atunci cnd procesorul scrie un cuvnt, iar acesta nu se afl n cache (write miss). O tehnic, numit write-allocate, ncarc blocul corespunztor din memoria principal i apoi l actualizeaz. Tehnica write allocate ncearc s exploateze proximitatea spaial a scrierilor, dar are dezavantajul c fiecare ratare genereaz un transfer de bloc dinspre memoria principal la cache. Alternativa, numit no-write-allocate, unteaz cache-ul i scrie cuvntul direct n nivelul inferior. Memoriile cache write-through sunt de obicei no-write-allocate. Memoriile cache write-back sunt de obicei write-allocate.

6. Memoria virtuala. Conceptul de memorie virtuala

Memoria principal a unui calculator este organizat sub forma unui ir liniar de octei suprapui, numerotai consecutiv, ncepnd cu zero. Numrul fiecrui octet se numete adres fizic, iar octetul n cauz, locaie de memorie. Adresele fizice permit identificarea fiecrui octet din memorie. Mulimea total a adreselor fizice constituie spaiul de adrese fizice, iar numrul de bii dintr-o locaie de memorie reprezint dimensiunea locaiei sau formatul memoriei. n schimb, procesoarele Intel sunt procesoare de memorie virtual. Instruciunile nu specific locaiile de memorie prin adresele lor fizice, ci prin adrese virtuale. Mulimea total a adreselor virtuale constituie spaiul de adrese virtuale. Adresa virtual este un numr alternativ dat unei locaii fizice de memorie. Procesul de conversie a adreselor virtuale la adrese fizice se numete translatarea adreselor.

Translatarea adreselor are loc prin strnsa cooperare dintre procesor i sistemul de operare. Circuitul hardware din procesor responsabil cu translatarea automat a adreselor, numit unitate de management a memoriei, folosete un tabel de translatare stocat n memorie al crui coninut este gestionat de sistemul de operare. Dimensiunea spaiului de adrese este caracterizat de numrul de bii necesar la reprezentarea celei mai mari adrese. De exemplu, un spaiu de adrese virtuale cu N = 2

n adrese se numete spaiu de adrese de n bii. Sistemele moderne

folosesc un spaiu de adrese virtuale de 64 de bii. Nu este neaprat necesar ca spaiul de adrese fizice s fie egal cu spaiul de adrese virtuale. Putem avea un spaiu de adrese virtuale de n bii i un spaiu de adrese fizice de m bii. Conceptul de spaiu de adrese este important deoarece marcheaz exact distincia dintre obiectele de date (octei) i atributele lor (adrese). Odat recunoscut aceast distincie putem generaliza i permite fiecrui obiect de date s dein mai multe adrese independente, fiecare aparinnd unui spaiu de adrese diferit. Principiul fundamental al mecanismului de memorie virtual este c fiecare octet de memorie este recunoscut att printr-o adres virtual, aleas din spaiul de adrese virtuale, ct i printr-o adres fizic, aleas din spaiul de adrese fizice. Conceptul de memorie virtual Conceptual, o memorie virtual este organizat ca un ir de N locaii de memorie fiecare cu dimensiunea de un octet stocate pe disc. Fiecare octet are o adres virtual unic folosit ca index n ir. Coninutul irului de pe disc este pstrat (cache-uit) n memoria principal. Dup cum tim, datele de pe disc sunt partiionate n blocuri care servesc drept uniti de transfer ntre disc i memoria principal. Mecanismul memoriei virtuale obine acest lucru prin partiionarea memoriei virtuale n blocuri de dimensiune fix numite pagini virtuale. Fiecare pagin virtual are dimensiunea de p octei. Similar, memoria fizic este partiionat tot n blocuri de p octei, numite pagini fizice (cadre de pagin). La un moment dat, setul de pagini virtuale este mprit n trei subseturi disjuncte: Nealocat: paginile care nc nu au fost alocate (sau create) de mecanismul de memorie virtual. Aceste pagini nu au date asociate cu ele i n consecin nu ocup spaiu pe disc. Cached (prezente n memorie): pagini alocate i care n prezent se afl i n memoria principal. Uncached (prezente numai pe disc): pagini alocate dar care nu sunt n memoria principal. Poziia memoriei principale n ierahia de memorie are un impact major asupra felului n care este organizat. Memoria principal este de cel puin 10 ori mai lent dect memoria cache, iar discul este de aproximativ 100000 de ori mai lent dect memoria principal. Procesorul caut datele i instruciunile n ordinea cache, memorie, disc. Lipsa acestora ntr-un nivel superior nseamn aducerea lor din nivelul inferior. E uor de intuit c lipsa datelor n memorie i aducerea lor de pe

disc este un proces mult mai lent dect lipsa datelor n cache i aducerea lor din memoria principal. Mai mult, ne aducem aminte c citirea primului octet de pe disc este de 100000 de ori mai lent dect citirea octeilor succesivi din sector. Organizarea memoriei rezult chiar din evitarea citirii datelor de pe disc.

Din cauza penalitii importante rezultate n urma unei cutri fr succes n memorie i a timpului mare de acces la primul octet, paginile virtuale tind s fie mari, de obicei ntre 4 KB i 2 MB. Din cauza penalitii, memoria principal este complet asociativ, adic paginile virtuale pot fi plasate n orice pagin fizic. Politica de nlocuire a paginilor n memorie are de asemenea o importan mai mare, deoarece penalitatea asociat cu nlocuirea unei pagini virtuale greite este mare. De aceea, algoritmii de nlocuire a paginii lips pentru memoria principal sunt mai compleci dect algoritmii echivaleni folosii pentru cache. n final, din cauza timpului mare de acces la disc, memoria principal folosete ntotdeauna politica write-back n loc de write-through.

7. Memoria virtuala ca unealta pentru managementul memoriei

Pn acum am presupus c exist un singur tabel de pagini care mapeaz un singur spaiu de adrese virtuale la un singur spaiu de adrese fizice. De fapt, sistemele de operare creeaz un tabel de pagini separat, i astfel un spaiu de adrese virtuale separat, pentru fiecare proces. Figura urmtoare arat ideea de baz. n acest exemplu, tabelul de pagini pentru procesul i, mapeaz VP1 la PP2 i VP2 la PP7.

Similar, tabelul de pagini pentru procesul j, mapeaz VP1 la PP7 i VP2 la PP10. Mai multe pagini virtuale pot fi mapate la aceea pagin fizic, rezultnd o pagin fizic partajat. Combinaia dintre demand paging i spaiile de adrese virtuale separate influeneaz profund modul n care este folosit i gestionat memoria. n particular, memoria virtual simplific editarea legturilor i ncrcarea programelor n memorie, partajarea codului i a datelor, i alocarea memoriei pentru aplicaii.

Simplificarea editrii de legturi. Un spaiu de adrese separat permite ca fiecare proces s aib aceeai imagineasupra memoriei, indiferent de unde se afl codul i datele n memoria fizic. n consecin, fiecare proces din Linux are un format similar de memorie. De exemplu, pentru sistemele cu procesoare Intel de 64 de bii, seciunea de cod ncepe ntotdeauna la adresa virtual 0x400000, urmat de seciunea de date globale iniializate i neiniializate, urmate de heap i la vrful memoriei virtuale de stiv. Stiva ocup zona superioar a spaiului de adrese i se extinde n jos, ctre adrese mai mici (crete n jos). Aceast uniformizare simplific foarte mult structura i implementarea editoarelor de legturi, permindu-le s genereze executabile independente de locaia codului sau datelor n memoria fizic. Simplificarea ncrcrii executabilelor n memorie Memoria virtual uureaz procesul de ncrcare n memorie a executabilului i fiierelor obiect partajate. Pentru un executabil cu format ELF, seciunea de cod i date globale iniializate sunt contigue. Pentru ncrcarea acestor seciuni, ncrctorul de program aloc un numr contiguu de pagini virtuale ncepnd cu adresa 0x400000, le marcheaz ca invalide (not cached) i configureaz PTE-urile corespunztoare lor astfel nct s indice ctre locaiile specificate n fiierul obiect. Partea interesant este c ncrctorul de program niciodat nu copiaz de fapt datele de pe disc n memorie. Datele sunt ncrcate n memorie automat de mecanismul de memorie virtual la prima adresare a paginii, adic la apariia unei erori de pagin. Noiunea de mapare a unui set contiguu de pagini virtuale la o locaie arbitrar dintr-un fiier oarecare se numete memory mapping. Simplificarea partajrii datelor Spaiile separate de adrese pun la dispoziia sistemelor de operare un mecanism eficient de gestionare a schimbului de date ntre procesele utilizator i kernel. n general, fiecare proces are propriile zone de cod, date, heap i stiv, care nu sunt partajate cu niciun alt proces. n acest caz, fiecare proces dispune de un tabel de pagini care i mapeaz paginile virtuale la pagini fizice disjuncte. Totui, n unele situaii este dezirabil ca procesele s poat partaja cod i date. De exemplu, fiecare proces trebuie s apeleze aceeai rutin din kernel. n loc ca sistemul de operare s introduc copii separate ale rutinei n spaiul de adrese fizice proprii fiecrui proces, sistemul de operare poate mapa paginile virtuale ale diferitelor procese la aceeai pagin fizic. Simplificarea alocrii memoriei Memoria virtual pune la dispoziia proceselor utilizator un mecanism simplu de alocare a unei zone adiionale de memorie. Cnd un program care ruleaz n spaiul utilizator cere spaiu adiional n heap (rezultatul unui apel malloc), sistemul de operare aloc un numr corespunztor, s zicem, k, de pagini virtuale contigue, i le mapeaz la k pagini fizice arbitrare. Datorit modului de lucru a

tabelului de pagini, nu este necesar ca sistemul de operare s aloce k pagini fizice contigue.Paginile pot fi mprtiate aleator n memoria fizic.

8. Memoria virtual ca unealt pentru protejarea memoriei Orice procesor modern asigur mijloacele necesare sistemului de operare pentru a controla accesul la memorie. Un proces care ruleaz n spaiul utilizator nu trebuie s i poat modifica seciunea de text, configurat numai cu drepturi de citire, nu trebuie s poat citi ori modifica cod i structuri de date din kernel, nu trebuie s poat citi sau scrie zone de memorie proprii altor procese sau s modifice vreo pagin virtual partajat cu alt proces (dect atunci cnd toate prile implicate permit acest lucru). Din aceste motive, n PTE-uri au fost introdui bii adiionali,cu rol de control al accesului la pagina virtual respectiv. De exemplu, biii de citire i scriere controleaz drepturile de citire i scriere la acea pagin virtual. Dac o instruciune violeaz aceste drepturi, procesorul genereaz o eroare deprotecie general ce ruleaz o rutin n kernel. Interpretoarele de comenzi raporteaz aceast excepie ca segmentation fault.

9. Integrarea memoriilor cache n mecanismul de memorie virtual Memoriile cache sunt accesate prin adrese fizice. Acest lucru permite ca mai multe procese s dein blocuri de date n cache n acelai timp i s partajeze blocuri coninute n aceleai pagini virtuale. Mai mult, memoria cache nu trebuie s verifice drepturile de acces, deoarece acest lucru are loc n timpul procesului de conversie a adreselor. Figura urmtoare arat modul n care memoria cache, adresat prin intermediul adreselor fizice, este integrat n memoria virtual. Ideea principal este c translatarea adreselor are loc nainte de verificarea memoriei cache. n acest fel, i PTE-urile pot fi pstrate n memoria cache, ca orice alte cuvinte de date.

De fiecare dat cnd procesorul genereaz o adres virtual, MMU trebuie s adreseze un PTE pentru a putea converti adresa virtual n adres fizic. n cel mai nefericit caz, acest lucru necesit nc o extragere din memorie, cu un cost substanial de cicluri de ceas. Dac PTE-ul se ntmpl s se afle n cache L1, atunci

costul se reduce la unul sau doua cicluri. Totui, procesoarele ncearc s elimine chiar i acest cost prin includerea n MMU a unei memorii cache ce stocheaz exclusiv PTE-uri, numit TLB (Translation Lookaside Buffer). TLB are capacitate mic, este adresat prin adrese virtuale i fiecare linie reprezintun singur PTE. Existena TLB-ului n ierarhia de memorie virtual presupune c toate conversiile de adrese pot fi efectuate n interiorul MMU, i astfel sunt foarte rapide. Procesorul genereaz o adres virtual, MMU extrage PTE-ul corespunztor din TLB, translateaz adresa virtual la adresa fizic, transmite adresa fizic la memoria cache sau memoria principal, i memoria cache sau memoria principal returneaz cuvntul de date cerut. Dac datele necesare nu sunt prezente n TLB (ratare TLB), MMU trebuie s extrag PTE-ul din nivelul L1 cache. PTE-ul tocmai extras este stocat n TLB, posibil suprascriind o intrare existent.

10. Tabele de pagini cu niveluri multiple Pn acum am presupus c sistemul folosete un singur tabel de pagini pentru translatarea adreselor. Dar dac avem un spaiu de adrese de 32 de bii, pagini de 4 KB i PTE de 4 octei, atunci am avea nevoie de un tabel de pagini de 4 MB12, rezident tot timpul n memorie, chiar dac aplicaia adreseaz numai o mic parte din spaiul de adrese virtuale. Problema este i mai grav pentru sistemele de 64 de bii. Soluia obinuit pentru reducerea dimensiunii tabelului de pagini const din folosirea unei ierarhii de tabele de pagini.

11. Studiu de caz: Intel Core I7 (Nehalem) Linux Chiar dac microarhitectura Nehalem permite spaii de adrese virtuale i fizice de 64 de bii, implementrile Core i7 din prezent folosesc un spaiu de adrese virtuale de 48 de bii (256 TB) i un spaiu de adrese fizice de 52 de bii (4 PB), plus un mod de compatibilitate cu vechile arhitecturi de 32 de bii, caz n care spaiul de adrese virtuale i fizice este de 32 de bii (4 GB). VAS: N = 2

n, n = 48 N = 248 = 256 TB

PAS: M = 2m

, m = 52 M = 252 = 4 PB

Figura anterioar prezint succint sistemul de memorie prezent n Core i7 cu microarhitectur Nehalem. Procesorul conine patru core-uri, o memorie cache L3 de dimensiune mare partajat de toate core-urile i un controler de memorie DDR3. Fiecare core conine o ierarhie de memorii TLB i cache pentru date i instruciuni i un set de legturi QPI pentru comunicarea direct cu celelalte core-uri sau cu puntea I/O extern. Memoriile TLB sunt memorii cu asociativitate pe seturi cu 4 ci i adresate virtual. Memoriile cache L1, L2 i L3 sunt memorii cu asociativitate pe seturi cu 8 ci, cu blocuri de 64 de octei, i adresate fizic. Dimensiunea paginii de memorie poate fi configurat la pornire i poate fi de 4 KB sau 4 MB. Linux folosete implicit pagini de 4 KB.

Translatarea adreselor la Core i7

Figura anterioar prezint pe scurt procesul de translatare a adreselor la Core i7, din momentul n care procesorul genereaz o adres virtual pn cnd primete un cuvnt de date din memorie. Core i7 folosete o ierarhie de tabele de pagini cu patru niveluri. Fiecare proces are propria ierarhie de tabele de pagini. n Linux, pentru un proces care ruleaz, toate tabelele de pagini asociate cu paginile alocate sunt rezidente n memorie, dei arhitectura Core i7 permite acestor tabele de paginis fie swapped in i out. Registrul de control CR3 conine adresa de nceput a tabelului de pagini de la nivelul 1 (L1). Valoarea din CR3 face parte din contextul fiecrui proces i este reactualizat la fiecare comutare de context.

Camp Descriere P (present) Tabelul de pagini de pe nivelul urmtor se afl n memorie (1)

sau nu (0).

R/W (Read/Write) Drepturi de citire sau de citire i scriere pentru toate paginile adresate de acest PTE.

U/S (User/Supervisor)

Drepturi de acces n mod utilizator sau kernel (supervizor) pentru toate paginile adresate de acest PTE.

WT (Write-through) Politica cache la scriere pentru tabelul de pagini de pe nivelul urmtor (write-through sau write-back).

CD (Caching Disabled)

Tabelul de pagini de pe nivelul urmtor poate fi pstrat n memorie sau nu.

A (Accessed) Bit de referin

PS (Page Size) Dimensiunea paginii de memorie, 4 KB sau 4 MB

Base addr Cei mai semnificativi 40 de bii ai adresei fizice de nceput a tabelului de pe nivelul urmtor.

XD (eXecution Disabled)

Activeaz sau dezactiveaz extragerea de instruciuni pentru toate paginile adresabile de acest PTE.

Figura urmtoare arat formatul unui PTE din tabelul de pagini de nivel 4. Cnd P = 1, cmpul de adres conine un PPN de 40 de bii ce indic nceputul unei pagini din memoria fizic. Din nou, acest lucru impune paginilor de memorie un aliniament de 4 KB. Fiecare PTE are trei bii de permisiuni care controleaz accesul la pagina de memorie. Bitul R/W determin dac coninutul paginii de memorie poate fi numai citit sau i citit i scris. Bitul U/S, determin dac pagina de memorie poate fi accesat de un proces care ruleaz n spaiul utilizator. n acest fel sunt protejate codul i datele kernelului de programele utilizatorului. Bitul XD (execute disabled), introdus la procesoarele de 64 de bii, poate dezactiva extragerea de instruciuni din anumite pagini de memorie.

Camp Descriere

P (present) Pagina de memorie se afl (este rezident) n memorie (1) sau nu (0).

R/W (Read/Write) Drepturi de citire sau de citire i scriere pentru pagina de memorie.

U/S (User/Supervisor)

Drepturi de acces n mod utilizator sau kernel (supervizor) pentru pagina de memorie.

WT (Write-through)

Politica cache la scriere pentru pagina de memorie (write-through sau write-back).

CD (Caching Disabled)

Pagina de memorie poate fi pstrat n memorie sau nu.

A (Accessed) Bit de referin (setat de MMU la citiri i scrieri, ters de software).

D (Dirty Bit) Semnalizeaz c pagina de memorie a fost modificat (setat de MMU la scrieri, ters de software)

G (Global Page) Pagin global (nu o scoate din TLB la comutrile de proces)

Base addr Cei mai semnificativi 40 de bii ai adresei fizice de nceput a paginii de memorie.

XD (eXecution Disabled)

Activeaz sau dezactiveaz extragerea de instruciuni din pagina de memorie

Aceast funcionalitate este foarte important deoarece permite kernelului s restricioneze execuia numai la paginile text (segmentul de text era ala cu codul programului) care au permisiuni exclusive de citire. Pe msur ce MMU translateaz fiecare adres virtual, actualizeaz totodat i ali doi bii care pot fi folosii de rutina de tratare a unei erori de pagin. Bitul de referin A este setat de MMU de fiecare dat cnd acceseaz o pagin. Kernelul poate utiliza acest bit n algoritmul de nlocuire a paginilor. MMU seteaz D de fiecare dat cnd scrie ntr-o pagin de memorie. O pagin care a fost modificat se numete pagin murdar. Bitul D arat kernelului dac trebuie sau nu s salveze pe disc o pagin victim nainte de a copia n locul acesteia alta nou. Kernelul reiniializeaz acest bit printr-o instruciune executat n mod kernel

12. Mecanismul de memorie virtuala in Linux Scopul acestei seciuni este s descrie mecanismul de memorie virtual n Linux ndeajuns pentru a ne face o idee de modul n care un sistem de operare real organizeaz memoria virtual i cum gestioneaz acesta erorile de pagin. Linux creeaz un spaiu de adrese virtuale de forma de mai sus pentru fiecare program lansat n execuie.Deoarece tim cum funcioneaz translatarea adreselor, putem s nelegem i organizarea memoriei virtuale kernel, care se afl deasupra stivei procesului. Memoria virtual kernel conine codul i structurile de date din kernel. Unele regiuni din memoria virtual kernel sunt mapate la pagini fizice accesibile tuturor proceselor. De exemplu, fiecare proces partajeaz codul i structurile globale de date ale kernelului. Linux mapeaz i un set de pagini virtuale contigue (cu dimensiunea egal cu cantitatea total de memorie RAM din

sistem) la setul corespunztor de pagini fizice contigue. Acest lucru d posibilitatea

kernelului s acceseze orice locaie din memoria fizic, de exemplu atunci cnd are nevoie s acceseze tabelele de pagini sau s realizeze operaiuni de memory I/O cu dispozitivele mapate la anumite locaii fizice de memorie. Alte regiuni din memoria virtual kernel conin date specifice fiecrui proces n parte. Exemplele includ tabelele de pagini, stiva pe care o folosete kernelul cnd execut cod n contextul unui proces i diferite structuri de date care monitorizeaz structura curent a spaiului de adrese virtuale.

13. Zonele constitutive ale memoriei virtuale in Linux Linux organizeaz memoria virtual ca pe o colecie de zone (numite i segmente).O zon reprezint o bucat contigu de de memorie virtual existent (alocat) ale crei pagini au ceva n comun. De exemplu, segmentul de cod, segmentul de date, heap, segmentul bibliotecilor partajate i stiva procesului sunt toate zone distincte. Fiecare pagin virtual alocat aparine unei asemenea zone i orice pagin virtual care nu aparine unei zone nseamn c nu exist i nu poate fi adresat de proces. Conceptul de zon este important deoarece permite spaiului de adrese virtuale s conin blocuri libere (guri). Kernelul ine evidena paginilor virtuale care nu exist, astfel nct aceste pagini nu consum resurse suplimentare de memorie, spaiu pe disc sau structuri de date din kernel. Figura urmtoare schieaz structurile de date prezente n kernel cu ajutorul crora acesta controleaz zonele de memorie virtual ale unui proces. Kernelul creeaz o structur de proces (task_struct n codul surs) distinct pentru fiecare proces din sistem. Elementele acesteia conin toate informaiile necesare kernelului s ruleze procesul (de exemplu, identificatorul de proces, adresa de nceput a stivei de proces, numele fiierului executabil i indicatorul de program). Una din intrrile structurii de proces adreseaz structura (mm_struct) care descrie starea curent a memoriei virtuale. Aceasta conine dou cmpuri importante. pgd, care conine adresa de baz a tabelului de pagini L1 (page global directory) mmap, care indic nceputul unei liste de structuri de zon (vm_area_structs), fiecare coninnd informaii legate de o anumit zon din spaiul curent de adrese virtuale. Atunci cnd kernelul lanseaz un proces n execuie, stocheaz adresa din pgd nregistrul de control CR3. Printre informaiile prezente n structura de zon (vm_area_struct) proprie unei anumite zone sunt: vm_start: adresa de nceput a zonei; vm_end: adresa de sfrit a zonei; vm_prot: descrie drepturile de citire/scriere pentru toate paginile aflate n acea zon; vm_flags: (printre alte lucruri) specific dac paginile din zon sunt partajate cu alte procese sau nu;

vm_next: adresa urmtoarei structuri de zon din list.

14. Gestionarea exceptiei de eroare de pagina in Linux S presupunem c MMU genereaz o eroare de pagin cnd ncearc s translateze o adres virtual A. Eroarea de pagin transfer controlul la o rutin de tratare din kernel care realizeaz urmtorii pai:

Este adresa A legal? Cu alte cuvinte, adresa A se afl ntr-o zon definit de o structur de zon? Pentru a afla rspunsul, rutina de tratare a erorii de pagin caut n lista de structuri de zon, comparnd A cu vm_start i vm_end din fiecare structur de zon n parte. Dac instruciunea nu este legitim, rutina de tratare generaz o eroare de segment (segmentation fault), care termin procesul. Situaia este etichetat 1 n Figura de mai jos.

Este permis accesul la acea adres de memorie? Cu alte cuvinte, are procesul dreptul s citeasc, scrie, execute paginile din aceast zon? De

exemplu, eroarea de pagin a fost rezultatul unei ncercri de a scrie ntr-o pagin cu drepturi exclusive de citire din segmentul de text, sau rezultatul unei ncercri efectuate de un proces ce ruleaz n spaiul utilizator de a citi un cuvnt din memoria virtual kernel? Dac accesul este ilegal, atunci rutina de tratare a erorii genereaz o excepie de protecie care termin procesul. Aceasta este situaia notat cu 2 din figura de mai jos.

3. n acest punct, kernelul tie c eroarea de pagin a fost rezultatul unei operaii legale. Selecteaz o pagin victim, dac a fost modificat (bitul dirty setat) scrie pagina victim pe disc (page out), ncarc noua pagin (page in) i actualizeaz

tabelul de pagini. La revenirea din rutina de tratare, procesorul reexecut instruciunea care a generat eroarea, care trimite iar adresa A la MMU. De aceast dat, MMU translateaz A fr s genereze o eroare de pagin.

15. Maparea memoriei in Linux Linux iniializeaz coninutul unei zone de memorie virtual prin asociere cu un obiect de pe disc, proces cunoscut sub numele de maparea de memorie (memory mapping). Zonele pot fi mapate la unul din dou tipuri de obiecte:

Fiier obinuit din sistemul de fiiere. O zon poate fi mapat la o seciune contigu dintr-un fiier obinuit aflat pe disc, cum ar fi un fiier executabil. Seciunea fiierului este mprit n buci egale cu dimensiunea unei pagini de memorie, coninutul fiecrei buci reprezentnd coninutul iniial al unei pagini virtuale. Datorit mecanismului de cerere paginare (demand paging), niciuneia din aceste pagini virtuale nu i este de fapt alocat vreo pagin n memoria fizic pn cnd procesorul nu folosete (atinge) pagina (de exemplu, genereaz o adres virtual inclus n regiunea paginii virtuale respective). Dac zona este mai mare dect seciunea de fiier, atunci ea este completat cu zero.

Fiier anonim (anonymous file). O zon poate mapat la un fiier anonim, creat de kernel, care conine numai bii de zero. Prima dat cndprocesorul ncearc s accese o pagin virtual dintr-o astfel de zon, kernelul gsete n memorie o pagin victim, dac este murdar o scrie pe disc, rescrie pagina victim cu bii de zero i actualizeaz bitul P din tabelul de pagini. Observai c nu sunt transferate date ntre disc i memorie. Din acest motiv, paginile prezente n zone mapate la fiiere anonime sunt numite cteodat i pagini demand-zero (demand-zero pages). n oricare din cazuri, odat iniializat, o pagin virtual este swapped out i in ntre memorie i un fiier swap special controlat de kernel. Fiierul swap este cunoscut i ca spaiu swap sau zon swap.

Important de reinut este c la orice moment de timp, spaiul swap limiteaz numrul total de pagini virtuale care poate fi alocat de procesele care ruleaz n prezent. Obiecte partajate i private Aa cum am vzut, memoria virtuale ne permite s oferim fiecrui proces propriul spaiu de adrese virtuale protejat de accesul neautorizat al altor procese. Totui, multe procese au zone identice de cod. De exemplu, fiecare proces care ruleaz interpretorul de comenzi are aceeai zon de text. Mai mult, multe programe trebuie s acceseze copii identice de funcii de bibliotec. Ar fi extrem de ineficient ca fiecare proces s conin n memoria fizic copii duplicat ale acestor secvene de cod. Maparea de memorie ofer un mecanism eficient de control al modului n care obiectele sunt partajate ntre mai multe procese. Un obiect poate fi mapat ntr-o zon de memorie virtual ca obiect partajat sau obiect privat. Dac un proces mapeaz un obiect partajat ntr-una din zonele sale de adrese virtuale, atunci toate scrierile pe care le aduce acelei zone sunt vizibile oricrui alt proces care de asemenea a mapat obiectul partajat n memoria sa virtual. Mai mult, modificrile sunt de asemenea vizibile n obiectul original de pe disc. Pe de alt parte, modificrile aduse unei zone mapate la un obiect privat, nu sunt vizibile altor procese, i scrierile pe care le face procesul n zon nu sunt vizibile n obiectul de pe disc. O zon de memorie virtual n care este mapat un obiect partajat se numete de obicei zon partajat. Similar pentru o zon privat.

16. PROCESE Programele sunt formate din instruciuni, iar procesorul ndeplinete secvena de pai specificat de acele instruciuni. Fiecare secven de pai rulat una dup alta se numete fir de execuie. Cele mai simple programe au un singur fir de execuie, adic instruciuni care ar trebui executate una dup alta ntr-o singur secven. Dar ntlnim i programe cu mai multe fire de execuie. Totodat, n sistem pot aprea mai multe fire de execuie prin rularea mai multor programe sau prin rularea aceluiai program mai mult de o singur dat.

Programul conine instruciuni, n timp ce firul de execuie se refer la execuia acelor instruciuni. Chiar i pentru programele cu un singur fir de execuie, aceast distincie se pstreaz. Dac un program conine o bucl, atunci un program foarte scurt poate da natere unui fir de execuie foarte lung. De asemenea, rularea aceluiai program de zece ori va determina apariia a zece fire de execuie, toate executnd acelai program. Firele de execuie nu provin numai de la programele utilizatorului. Un fir de execuie poate fi rulat chiar de kernel. Kernelul ndeplinete anumite sarcini eseniale rulrii corecte prin intermediul firelor de execuie kernel. Fiecare fir de execuie are un timp de via, de la execuia primei sale instruciuni pn la execuia ultimei instruciuni. Dac dou fire de execuie ruleaz n acelai timp, spunem c firele de execuie sunt concurente. Unul din scopurile fundamentale ale sistemului de operare este s permit mai multor fire de execuie s ruleze concurent pe acelai calculator. Altfel spus, atenia calculatorului trebuie mprit astfel nct un nou fir de execuie s poat rula nainte de finalizarea primului fir de execuie. Totui, de obicei, utilizatorii vor dori s ruleze concurent un numr de fire de execuie care depete numrul de procesoare prezente n sistem. De aceea, sistemul de operare trebuie s mpart accesul la fiecare procesor ntre mai multe fire de execuie. Pe de alt parte, sistemul de operare trebuie s izoleze firele de execuie unul de altul, astfel nct, dac se ntmpl s scriem un document i n acelai timp s accesm o pagin web, o greeal de programare din navigatorul web s nu suprascrie o parte din document, de exemplu. Acest lucru se realizeaz prin ncapsularea firelor de execuie n medii de lucru separate, protejate unul de altul, numite procese. Definiia clasic a unui proces este aceea de instan a unui program aflat n execuie. Fiecare program din sistem ruleaz n contextul unui proces. Contextul const din informaiile necesare programului s ruleze corect. Aceste informaii includ codul i datele programului stocate n memorie, stiva, coninutul registrelor de uz general din procesor, indicatorul de instruciune, variabilele mediului de lucru i descriptorii de fiier pentru fiierele deschise de program. Procesul pune la dispoziia aplicaiilor dou abstractizri principale: Un spaiu de adrese privat care creeaz iluzia c programul are acces exclusiv la memorie. Execuia independent a instruciunilor programului care creeaz iluzia c programul are acces exclusiv la procesor. Prin aceste abstractizri, procesul izoleaz execuia unui program de execuia programelor concurente. Un proces d fiecrui program iluzia c are acces exclusiv la spaiul de adrese din sistem. Un proces ofer fiecrui program propriul spaiu de adrese privat. Acest spaiu este privat n sensul c un octet de memorie asociat unei anumite adrese din spaiu, n general nu poate fi citit sau scris de niciun alt proces. Dar dei coninutul memoriei asociate cu fiecare spaiu privat de adrese este n general diferit, fiecare astfel de spaiu are aceeai organizare (structur) general, cea din Figura 1.3. Fiecare proces are aceeai imagine asupra memoriei, cunoscut ca spaiul de adrese virtuale. Spaiul de adrese virtuale pentru

procesele din Linux este artat n Figura 1.3 i este divizat n dou: utilizator i kernel (nucleu).

n Linux, spaiul de adrese kernel este rezervat pentru codul i datele comune tuturor proceselor. Kernelul rezid permanent n memorie. Regiunea superioar a spaiului de adrese este rezervat pentru kernel. Aplicaiile nu pot citi sau scrie coninutul acestei zone sau s apeleze direct funcii definite n codul kernel. Spaiului de adrese utilizator pstreaz codul i datele definite de procese. Spaiul de adrese virtuale vzut de fiecare proces const dintr-un numr de zone bine definite, fiecare cu un scop specific: Codul i datele programului. Codul ncepe de la aceeai adres fix pentru toate procesele, urmat de locaiile de date ce corespund variabilelor C globale. Zonele de cod i date sunt iniializate direct din coninutul fiierului obiect executabil. Heap (variabile alocate dinamic). Spre deosebire de zonele de cod i date, de dimensiune fix odat ce procesul a nceput s ruleze, heap i poate modifica dimensiunea dinamic n funcie de apelurile malloc i free. Bibliotecile partajate. Aproape de mijlocul spaiului de adrese se afl o zon care conine codul i datele pentru bibliotecile partajate, cum ar fi bibliotecile standard C sau biblioteca de funcii matematice. Stiva. La vrful spaiului utilizator se afl stiva utilizator (procesului) folosit de compilator pentru implementarea apelurilor de funcie. La fel ca heap, stiva i modific dimensiunea dinamic n timpul execuiei unui program. n particular, de fiecare dat cnd apelm o funcie, stiva crete. De fiecare dat cnd revenim dintr-o funcie, stiva descrete.

17. Planificarea accesului la procesor Pentru ca sistemul de operare s poat rula mai mult de un fir de execuie per processor, sistemul trebuie s implementeze un mecanism de comutare a firelor de execuie. n particular, trebuie s existe o cale de a opri la un moment dat secvena de instruciuni a unui fir de execuie, de a executa pentru un timp alte fire de execuie, i apoi de a relua rularea firului de execuie originar de unde a rmas. Dou posibiliti: 1. Firele de execuie conin explicit din cnd n cnd o instruciune care comut temporar la alt fir de execuie (cooperative multitasking). 2. Firele de execuie sunt oprite de sistemele de operare fr a fi nevoie s ncorporeze cod de comutare (preemptive multitasking). Pentru a fi capabil s comute ntre fire de execuie, sistemul de operare trebuie s dein informaii despre fiecare fir de execuie, de exemplu s tie de la ce instruciune trebuie s reia execuia acelui fir de execuie (altfel spus, trebuie s cunoatem coninutul registrului indicator de instruciune). Dac aceast informaie este stocat ntr-un bloc de memorie individual pentru fiecare fir de execuie, atunci putem folosi adresele acelor zone de memorie pentru a ne referi la firele de execuie. Blocul de memorie care conine informaie cu privire la firul de execuie se numete blocul de control al firului de execuie sau blocul de control al sarcinii de execuie (TCB Thread/Task Control Block). Astfel, un alt fel de a spune c folosim adresele acestor blocuri este s spunem c folosim pointeri (indicatori) la blocurile de control al firelor de execuie pentru a le adresa. Pe lng coninutul indicatorului de instruciune, informaia de stare a execuiei include i coninutul celorlalte registre din procesor. Alt parte important din informaia necesar execuiei programului o reprezint zona de memorie folosit la stocarea stivei, mpreun cu registrul indicator de stiv care precizeaz adresa de memorie ce reprezint vrfului curent al stivei. Cnd un fir de execuie i reia execuia, trebuie s gseasc stiva n aceeai stare ca atunci cnd a fost ntrerupt. Obinem acest lucru dnd fiecrui fir de execuie propria stiv. Altfel spus, configurm o zon de memorie destinat stivei pentru fiecare fir de execuie n parte. Cnd este rulat un fir de execuie A, registrul indicator de stiv va indica undeva n spaiul de stiv al firului de execuie A, artnd ct din acea zon este ocupat n acel moment. nainte de a comuta la firul de execuie B, indicatorul de stiv al firului de execuie A trebuie salvat, la fel ca pe oricare alt registru, i s ncrcm n el indicatorul de stiv al firului de execuie B. n acest fel, n timpul execuiei firului de execuie B, indicatorul de stiv va glisa n sus i jos n cadrul spaiului de stiv al firului de execuie B, n concordan cu instruciunile de introducere i extragere din stiv prezente n codul B. Prin faptul c dispunem de stive separate i c putem comuta indicatorii de stiv, putem salva toate celelalte registre prin introducerea lor n stiv nainte de trecerea la cellalt proces i extragerea lor din stiv dup comutare.

18. Planificatorul Componenta sistemului de operare care se ocup cu comutarea accesului la procesor ntre diferitele fire de execuie se numete planificator. Planificatorul alege firul de execuie care trebuie s ruleze n continuare. i alte resurse de sistem pot avea nevoie de un mecanism de planificare; de exemplu, dac mai multe firede execuie citesc date aflate pe acelai disc, este nevoie de un planificator de acces la disc. n continuare prin planificator nelegem planificatorul folosit pentru accesul la procesor. Planificatorul trebuie s maximizeze performana i s permit utilizatorului s controleze sistemul. Fiecare din aceste obiective poate fi caracterizat mai n detaliu. Performan ridicat poate nsemna satisfacerea unui numr ct mai mare de fire de execuie (high throughput) sau timp de rspuns mic (fast response time). Controlul utilizatorului asupra sistemului poate fi exprimat n termeni de prioritate. Pentru obinerea unui throughput mare planificatorul trebuie s gseasc fiecrui procesor un fir de execuie rulabil n orice moment. Dar lucrurile nu sunt att de simple. Un calculator conine i alte componente pe lng procesoare, de exemplu dispozitive de intrare-ieire (discuri, interfee de reea), memorie principal, memorii cache. Planificatorul poate maximiza throughput-ul numai folosind eficient toate aceste resurse. Aadar, pe lng procesor, planificatorul trebuie s in i discul ocupat tot timpul. Mecanismul de funcionare a memoriilor cache poate influena planificarea orientat pe throughput. Se obine performan redus cnd un fir de execuie este planificat pe alt procesor fa de cel pe care a rulat ultima dat. Ambele cazuri au de a face cu faptul c memoria cache este rescris i datele trebuie readuse din memoria principal. De aceea, pentru a maximiza throughput-ul, planificatorul trebuie s pstreze o afinitate la procesor (processor affinity) specific fiecrui fir de execuie. Altfel spus, planificatorul trebuie s planifice firul de execuie pe acelai procesor ct timp nu apar alte motive mai importante. Timpul de rspuns se refer la timpul care trece de la apariia evenimentului (cum ar fi apsarea unei taste) pn la finalizarea rspunsului (afiarea caracterului pe ecran). Sistemele destinate interaciunii directe cu utilizatorul tind s fie optimizate pentru timp de rspuns mic, chiar dac asta nseamn throughput redus (de exemplu, comutri de context frecvente, nefavorabile pentru throughtput, pot fi necesare pentru optimizarea timpului de rspuns) n timp ce serverele sunt optimizate pentru throughput mare i timp de rspuns tolerabil. Obinerea unui throughput-ul mare sau a unui timp de rspuns rapid nu implic neaprat controlul utilizatorului asupra planificatorului; un planificator poate lua deciziile corecte de unul singur. Pe de alt parte, utilizatorul poate dori s modifice prioritatea unui fir de execuie n funcie de dorinele sale.

19. Starile firului de executie Un fir de execuie obinuit are momente cnd ateapt apariia unui anumit eveniment. ntr-un sistem care ruleaz un singur fir de execuie, este plauzibil ca n timpul de ateptare s se execute o bucl care verific continuu apariia evenimentului n cauz. Aceast abordare se numete busy waiting. Pe de alt parte, ntr-un sistem de operare de uz general mai multe fire de execuie vor cere accesul concurent la procesor. n acest caz, busy waiting nu este o strategie foarte util deoarece ocuparea procesorului cu o bucl de ateptare nseamn c alte fire de execuie nu vor avea parte de procesor. n consecin, sistemul de operare ofer firelor de execuie alte posibiliti de a atepta apariia unui eveniment. Sistemul de operare ine evidena firelor de execuie care pot profita util de accesul la procesor i a celor care ateapt apariia unui eveniment. Acest lucru se face prin stocarea firelor de execuie rulabile ntr-o structur de date numit coad de rulare, iar a celor aflate n ateptare ntr-o coad de ateptare13. Dei aceste structuri de date sunt convenional numite cozi, nu este neaprat necesar s se comporte dup principiul FIFO, ci pot avea aspectul unor liste de fire de execuie ce ateapt trecerea unui anumit timp. Un alt exemplu de coad de ateptare ar putea fi un set de fire de execuie care ateapt s primeasc date de la placa de reea. n loc s intre ntr-o bucl de ateptare, un fir de execuie care trebuie s ateapte apariia unui anumit eveniment anun sistemul de operare. Sistemul de operare ndeprteaz firul de execuie din coada de rulare i l ntroduce n coada de ateptare corespunztoare. Deoarece planificatorul ia n considerare numai firele de execuie aflate n coada de rulare, nu va selecta niciodat un fir de execuie aflat n ateptare. Pe baza informaiei de mai sus putem distinge trei stri n care se poate afla un fir de execuie la un moment dat: Rulabil (runnable), dar care nc nu ruleaz i ateapt accesul la procesor; Aflat n rulare (running) pe un procesor; n ateptarea (waiting) unui anumit eveniment.