Back | Home | Next

Real Time RO

ANNA  K5

@

Home
Glossary
Objectives
Formalism
Morphology
Physiology
Connectors
Serialization
Traits
Methods
Claims
Relations
Dictionary
Core UML
Ring1 Apps
Tiger Server
Features
History
ToDo
Authors
API
Images
ToDo
DNA Declarations
Physiology RO
Real Time RO
ANNA as an Eco System RO
HMM Generator
ERP

 

Contents

 TOC \o "1-3" \h \z \u 1        NOTA: PAGEREF _Toc261925383 \h 1

2        Obiectiv. PAGEREF _Toc261925384 \h 1

3        Structura generala a subsistemului de timp real ANNA K5. PAGEREF _Toc261925385 \h 2

4        Preliminari privind sistemul de interlocking fir-resursa. PAGEREF _Toc261925386 \h 3

5        Problema de profunzime legata de fire si blocaj PAGEREF _Toc261925387 \h 3

6        Schema de functionare a lacatului complex obiectual PAGEREF _Toc261925388 \h 4

7        O demonstatie simpla a sistemului de interlocking. PAGEREF _Toc261925389 \h 6

8        Detalii de implementare ale mecanismelor de sincronizare. PAGEREF _Toc261925390 \h 7

8.1         Operatii atomice pe campuri de 32 de biti PAGEREF _Toc261925391 \h 7

8.2         Lacat simplu. PAGEREF _Toc261925392 \h 7

8.3         Lacat cu pompare de mesaje. PAGEREF _Toc261925393 \h 7

8.4         Furca de fire de executie. PAGEREF _Toc261925394 \h 8

8.5         Obiecte indirecte. PAGEREF _Toc261925395 \h 9

8.6         Terminarea firelor PAGEREF _Toc261925396 \h 10

8.7         Functii de lucru cu coada de capacitate fixa. PAGEREF _Toc261925397 \h 10

8.8         Testul de integritate a dispecerului PAGEREF _Toc261925398 \h 11

9        Testele "simple" de concurenta. PAGEREF _Toc261925399 \h 12

10     Problema producator-consumator PAGEREF _Toc261925400 \h 13

11     Problema filozofilor chinezi PAGEREF _Toc261925401 \h 15

 

 

1           NOTA:

Materialul acesta contine informatie privilegiata si confidentiala, proprietate a autorului si a societatii Proxima Centuri Romania SRL. Cititorul/Auditorul ia la cunostinta de sensitivitatea materialului si intelege sa respecte toate drepturile de autor, marca, model si brevet de inventie, drepturi morale si patrimoniale derivate din materialul prezentat.

 

 

2           Obiectiv

 

Sistemul nostru de operare ANNA Kernel 5 este un nou nivel de inteligenta si de constiinta in lumea virtuala. Celula metamorfica a sistemului intruneste mai multe trasaturi esentiale ale vietii reale. Una dintre calitatile sistemului este abilitatea de auto-morfoza, adica aceea de a-si schimba structurile interne in timpul functionarii. Acesta este un pas semnificativ dincolo de aptitudinile si de ambitiile platformei DotNET si ale masinii Java, ambele cu care ne comparam din multe puncte de vedere. Planurile de detaliu pot fi accesate la www.Anna.ProximaCentauri.ro pentru pe baza de cerere sau de invitatie.

 

Metamorfoza structurala necesita menegmentul complet al firelor de executie in termenii intimi ai pozitiei si naturii tuturor campurilor de date aflate pe stive. Aproprierea firelor de executie mostenite de la sistemul de operare inconjurator ne-a obligat sa refacem toata schema de dispecerizare a sistemului gazda (Windows/Linux/MacOS) si sa o inlocuim cu una proprie care sa permita control total asupra zonelor critice. ANNA dovedeste astfel ca este posibil sa refaci intreg sistemul de timp real al unui alt sistem de operare folosind doar una dintre primitivele acestuia: firele, fara semafoare. Se poate demonstra ca este posibila si o reductie complementara pe directia derivarii notiunii de fir de executie pornind doar de la semafoarele sistemului de operare. Lucrand insa cu structuri largi, de sute de mii de obiecte - potential milioane, a cere sistemului de operare gazda sa ne rezerve atatea obiecte scumpe ar fi fost inacceptabil. Firele sunt deocamdata mai putine.

 

Am preluat asadar notiunea de fir am extins-o si am reinventat notiunea de semafor.

 

Lucrarea de fata prezinta succint mecanismele de timp real ale sistemului de operare ANNA K5 si evoca unele probleme de IT pentru care aceste mecanisme au fost concepute.

 

 

3           Structura generala a subsistemului de timp real ANNA K5

 

 

 

 


 

 

4           Preliminari privind sistemul de interlocking fir-resursa

In sistemul ANNA K5 concurenta firelor de executie asupra resurselor este asigurata prin urmatoarele constructii si principii:

1.      Lacatul simplu. Este un dispozitiv cu un camp care ia doua valori: liber/blocat. Asupra sa se actioneaza cu initializare si reset, iar functia specifica se realizeaza prin LockSpinlock care obliga firul curent sa se invarta in jurul campului pana la resetarea valorii.

2.      OBJECT::SpinlockInterlock este o metoda care invarte firul curent in jurul unor stari marcate in campul de stari a clasei OBJECT a sistemului afectand doar un singur obiect.

3.      OBJECT::Lock si OBJECT::Unlock implementeaza lacatul complex si blocant. Lock/Unlock sunt metodele de blocare si deblocare a unui fir de executie asupra unei resurse pentru care acesta intra in competitie cu alte fire.

4.      Orice obiect din sistem este atat resursa cat si lacat complex.

5.      Firul de executie este deasemenea resursa si lacat.

6.      Firele de executie sunt preluate de la sistemul de operare de prim nivel peste care ANNA K5 ruleaza si sunt imediat infasurate de clasa THREAD care asigura integrarea in nucleu.

7.      Un fir de executie poate avea doua origini: interna, atunci cand este creat la dispozitia sistemului nostru, sau externa, atunci cand executia de cod din sistem este ceruta de dispozitive externe precum driverele de echipament care se leaga la ANNA.

8.      Firele de executie straine, zise a fi intrusive, sunt infasurate in clasa THRAD si manageriate unitar ca si cele nascute in interior pe toata durata intrusiunii lor in nucleu.

9.      Numai firele manageriate pot participa in interlocking cu resursele sistemului.

10.  Firele de executie intrinseci se nasc prin functia OBJECT::Fork care cloneaza suficient din contextul apelantului cat sa parametreze blocul de cod invocat in clauza sa directa.

11.  Clasa THREAD poate fi derivata, in maniera cunoscuta in Java si DotNet, tehnica este insa ne necesara. Fork este un model mult mai performant de a obtine paralelism si are avantajul de a nu prolifera tipuri noi si nesemnificative de date la nivel de design.

12.  Firele se termina numai prin propria lor vointa. Firele de executie se intorc catre dispecer.

13.  Resursele pot bloca alte resurse, formand astfel arbori adanci de utilizare.

14.  Firele care n-au reusit sa-si insusasca o resursa cad in proprietatea resursei.

15.  In arborele de interlock se poate afla recursiv orice combinatie de resursa/fir la orice nivel.

16.  Metodele de blocaj de tip Lock sunt parametrabile sa testeze conditia si sa revina cu fals daca executia s-ar bloca. Numim aceste constructii "skipers".

5           Problema de profunzime legata de fire si blocaj

Notiunea de fir de executie este definita pe rand de urmatoarele etaje de procesare:

1.      Hardware: firele se nasc la nivelul procesorului prin structura Task Descriptor Segment.

2.      Firele executa cod apartinand nucleului sistemului de operare (Windows/Linux/etc) la nivel de Kernal. Aici firele capata aptitudini diverse si conext largit fata de ce permite procesorul.

3.      Unele dintre firele nucleului pot castiga aptitudini sporite si sa patrunda in spatiul utilizatorului. Firele se transforma la trecere prin largirea stivelor si reducerea privilegiilor.

4.      Nu este obligatoriu ca firele de executie sa promoveze catre toate nivelele.

5.      ANNA continua acest model si extinde firele lui Windows/Linux/MacOS cu inca doua nivele. Firele intra in ANNA CORE si pot ramane acolo pana la intoarcere, sau pot promova inca un nivel spre GUI-ul lui ANNA format din Enterprise Navigator, Gaius, Edict, etc.

6.      Nu este obligatoriu ca firele de executie sa se nasca la nivelul procesorului. Masina virtuala Java, diversele interpretoare Visual Basic, Internet Information Server, etc, simuleaza concurenta in structuri care-si au originea in spatiul utilizator al masinii virtuale. Aceste fire simulate impart contextul unic al programului de virtualizare.

7.      Firele virtuale pot ajunge sa cheme biblioteci de nivel scazut care in mod normal sunt disponibile doar firelor concrete. Un proces de thunking are loc la aceasta trecere soldat cu crearea de fire reale.

6           Schema de functionare a lacatului complex obiectual

Prototipul metodelor:

                boolean OBJECT::Lock (int code, int info, OBJECT* owner, boolean multi, int waitFlags)

                void OBJECT::Unlock (boolean recurse, boolean promote, boolean noself)

Doua fire ThreadA si ThreadB concurand pentru resursa comuna "object:

 

thread

A

thread

B

resource

object

HOST_OS::SuspendThread

Firul se auto-suspenda

Interlock.Insert: asteptare indefinita pana la Unlock

OBJECT::SpinlockInterlock

per obiect

 

LockSpinlock:

exclude orice alt Lock/Unlock

OBJECT::Lock

HOST_OS::ResumeThread

Interlock.Remove

OBJECT::

SpinlockInterlock

LockSpinlock

 

OBJECT::Unlock

Rezolvarea functiilor Lock si Unlock implica traversarea a trei nivele energetice:

1.      LockSpinlock este bucla cea mai rapida, foarte stransa in jurul valorii testate, are energia cea mai inalta, tinand toate procesoarele ocupate la 100% pe durata executiei sale. Mecanismul este menit sa fie folosit pentru exluziunea mutuala asupra unor portiuni foarte scurte de cod si numai ca o bariera inter-procesor care sa ordoneze intrarea in urmatorul nivel energetic:

2.      SpinlockInterlock este o bucla rapida de invartire in jurul starii unui singur obiect. Numai firele care concureaza pentru acest obiect vor fi obligate sa se invarta in giratoriu. Orice alte fire isi pot gestiona concurenta asupra altor obiecte pe alte procesoare disponibile. Bucla poate acoperi secvente de cod ceva mai largi si a caror executie sa nu justifice costul mare al unei basculari de intreg context al firelor. Secventa este necesara in a atinge urmatorul nivel energetic, cel mai scazut:

3.      Suspend/Resume. Se ajunge la acest nivel cand se preconizeaza o asteptare mai indelungata sau atunci cand durata este nedeterminata. Procesorul trbuie restituit sistemului tocmai pentru a se putea dedica rezultatului asteptat. Firele care ajung in centrul interlocking-ului vor fi scoase din lista de fire active si plasat in listele resurselor asteptate. Firul care disponibilizeaza o resursa prin intermediul unui Unlock, va re-porni cel mai vechi fir blocat asupra acestei resurse. Firul de-blocat se auto-inlatura din lista resursei si se inregistreaza din nou in lista de fire active ale sistemului. Intre un Lock blocant si Unlock-ul corespunzator nu se pierd cicluri de procesor.

 

In schema de interlocking de mai sus, bobinele de fir rosu reprezinta drumul critic pe care firele A si B le vor parcurge prin excluziune mutuala. Firele ies spre sistemul de operare de nivel inferior prin Suspend si re-intra prin Resume. Zona verde este ne-critica din punctul utilizatorului de vedere. N.B. ca orice asemenea apreciere este subiectiva si inversabila: ce este critic pentru user este qvasi indiferent pentru sistem si vice-versa. Zona verde, cea ne-critica din punctul utilizatorului de vedere este defapt zona critica pentru sistemul nostru de operare.

 

Pe langa functiile majore Lock/Unlock parametrabile in diverse scopuri, mai sunt si urmatoarele abrevieri de convenienta:

 

                OBJECT* OBJECT::IsLocked (OBJECT* owner)

                boolean OBJECT::TryLock ();

                void OBJECT::Lock ()

                void OBJECT::Lock (OBJECT*resource)

                void OBJECT::Unlock ()

                OBJECT*OBJECT::IsLocked ()

 


 

7           O demonstatie simpla a sistemului de interlocking

In captura de mai jos sunt doua ferestre de editare schematica cu firele de executie distincte. In stanga celor doua ferestre este arborele de obiecte ale sistemului de operare evidentiand structura de interlocking fir-obiect. In stanga au fost selectate obiectele TOtpContact si TOtpServer iar in dreapta obiectele TOtpFile si TOtpObject, alese diferit pentru a nu exista inca concurenta.

In fereastra dreapta s-a incercat selectarea obiectului TOtpServer apartinand deja procesului stang. Firul de executie "Schematic Editor Pick" pierde competitia pentru resursa comuna TOtpServer si intreg sub-arborele sau de resurse castigate este grefat la nodul resursa in arborele stang. Firul Pick al editorului drept este blocat pana ce resursa comuna devine disponibila.

Fereastra dreapta castiga resursa si primeste inapoi controlul cand stanga o deselecteaza.

 

 

 

8           Detalii de implementare ale mecanismelor de sincronizare

8.1         Operatii atomice pe campuri de 32 de biti

Pe procesoare cu mai multe nuclee operatiile aritmetice cu operanzi nealiniati la granularitatea spatiului de adresare (4 byte pentru intel) trebuiesc protejate cu prefixul LOCK. Avem in principal nevoie de adunare, scadere si setare de flaguri in campuri. Urmatoarele functii au aceasta sarcina:

int LockedIncrement(int*pvalue)

{

  __asm

  {

   MOV  EAX,[pvalue]

   LOCK INC [EAX]

   MOV EAX,[EAX]

  }

}

int LockedDecrement(int*pvalue)

{

  __asm

  {

   MOV  EAX,[pvalue]

   LOCK DEC [EAX]

   MOV EAX,[EAX]

  }

}

void AtomicSetFlags

(

 int*pflags, int value

)

{

  __asm

  {

   MOV  EAX,[value]

   MOV  EDX,[pflags]

   LOCK OR [EDX],EAX

  }

}

void AtomicClearFlags

(

 int*pflags, int value

)

{

  __asm

  {

   MOV  EAX,[value]

   NOT  EAX

   MOV  EDX,[pflags]

   LOCK AND [EDX],EAX

  }

}

8.2         Lacat simplu

Zise si spin-locks, aceste lacate se invart intr-o bucla stransa si consuma CPU 100%. Sunt necesare ca precursor al unor lacate mai elaborate. Trebuie folosite judicios pentru zone critice inguste.

void LockSpinlock(int*pphase,char*pspin)

{

  __asm

  {

   MOV  EBX,[pspin]

   MOV  ECX,[pphase]

   MOV  DL,1

   JMP  __LL0

  __LL1:

   INC  [ECX]

  __LL0:

   MOV AL,0

   LOCK CMPXCHG [EBX],DL

   JNE __LL1

  }

}

Utilizare:

 

{

  ....

  static char spin=0;

  int phase=0;

  LockSpinlock(phase,spin);

  ....

  zona critica

  ....

  spin=0; // release

  .....

}

8.3         Lacat cu pompare de mesaje

void OBJECT::SpinlockInterlock (boolean on, int testval, int setval)

{

  static int nphase=0;

  static char spin=0;

__L1:

  LockSpinlock(&nphase,&spin);

  if (on)

  {

   if (CHECK_TWICE(States&testval))

   {

    spin=0;

    if (THREAD::get_Current()->Flags&(1<<THREAD::flGUI))

     while (HOST_OS::GuiPeekDispatch())

      BreakPoint();

    else

     HOST_OS::Sleep(0);

    goto __L1;

   }

   AtomicSetFlags(&States,setval);

   if (!(States&setval))

    FAULT("Spinlock on didn't hold.");

  }

  else

  {

   AtomicClearFlags(&States,setval);

   if (States&setval)

    FAULT("Spinlock off didn't hold.");

  }

  spin=0;

}

 

8.4         Furca de fire de executie

int OBJECT_BASE::Fork (const char* name, int stackSize, int is_gui)

{

  LockSpinlock(&ForkPhase,(char*)&ForkSpinLock);

  void*start=(void*)&TryStartForkThread;

  static char no_try=0;

  if (no_try)

   start=(void*)DoStartForkThread;

  if (!stackSize)

   stackSize=1*1024*1024;

  tmp_stack_limit=stackSize-0x1000;

  int retval=HOST_OS::ThreadCreate(start,(void*)_EBP,stackSize);

  if (!retval)

  {

   HOST_OS::ApiError("CreateThread");

   ForkSpinLock=0;

  }

  else

   while (ForkSpinLock)

   {

    if (is_gui)

     HOST_OS::GuiPeekDispatch();

    BreakPoint();

   }

  return retval;

}

int DoStartForkThread (OBJECT_BASE*thread,void* stackFrame)

{

  GetTlsData(); // result in EAX

  _EDX=_EAX;

  _ECX=_ESP;

  ((int*)_EDX)[1]=_ECX;

  _ECX-=tmp_stack_limit;

  ((int*)_EDX)[2]=_ECX;

  OBJECT_BASE::uKernel.CreateForkThread(thread,((char**)stackFrame)[2]);

  // Create a return path for exiting the thread

  *--((int*)_ESP)=(unsigned long)&DoReturn+3; // A dangerous assumption

  *--((int*)_ESP)=_EBP;

  _EAX=(unsigned long)stackFrame;

  _EBP=_ESP;

  _ECX=_EAX;

  _EDX=*(unsigned long*)_EAX;

  _ECX-=_EDX;

  _ECX=-_ECX;

  _EDX=_ESP;

  _EDX-=_ECX;

  _ESP=_EDX;

  memcpy((void*)_EDX,(void*)_EAX,_ECX);

  *(unsigned long*)_ESP=_EBP;

  OBJECT_BASE::ForkSpinLock=false;

  return 0; // the result of fork is 0 for the child thread.

  //  RETADDR2 to system dispatcher

  //  EBP2 of the dispatcher

  //  Our locals

  //  RETADDR to EndForkThread

  //  EBP of ours

  // *Locals of fork caller    | copy

  // *Arguments to fork        | copy

  // *RETADDR1 after fork call | copy

  // *EBP1 before fork         | copy

}

8.5         Obiecte indirecte

class ThreadWrapper

{

  int reentry;

  char thread[512];

public:

  ThreadWrapper(const char*name);

  ~ThreadWrapper();

};

ThreadWrapper::ThreadWrapper(const char*name)

{

  unsigned long *data=(unsigned long*)GetTlsData();

  if (data)

  {

   reentry=true;

   return;

  }

  reentry=false;

  BASE_ThreadAttach();

  data=(unsigned long*)GetTlsData();

  if (data)

  {

   data[1]=_EBP;

   data[2]=(unsigned long)RawGetStackLimit();

   OBJECT_BASE::uKernel.CreateForkThread((OBJECT_BASE*)thread,name);

  }

}

ThreadWrapper::~ThreadWrapper()

{

  if (reentry)

   return;

  unsigned long *data=(unsigned long*)GetTlsData();

  if (data)

  {

   OBJECT_BASE*thread=(OBJECT_BASE*)OBJECT_BASE::uKernel.CurrentThread();

   if (thread)

    thread->Free();

  }

  BASE_ThreadDetach();

}

8.6         Terminarea firelor

void THREAD::Free ()

{

  ObjectClient Proxy(this);

  THREAD*th=(THREAD*)Proxy.GetServer();

  if (!th)

   return;

  th->Flags|=(1<<flCancelled);

  while (th=(THREAD*)Proxy.GetServer())

   HOST_OS::Sleep(0);

}

8.7         Functii de lucru cu coada de capacitate fixa

void STREE::AddChild (STREE* child, int flags)

{

  THREAD*thread=THREAD::get_Current();

  ((OBJECT*)Object)->SpinlockInterlock

   (true,(1<<OBJECT::stInLock)|(1<<OBJECT::stInUnlock),(1<<OBJECT::stInLock));

  LockedIncrement(&OBJECT::enqueues);

  ((OBJECT*)Object)->OBJECT::CheckClosures(0);

  child->Insert(this);

  STREE_BASE*stn;

  if (flags)

  for (STREE_BASE*st=((OBJECT*)Object)->Interlock.Children;st;st=stn)

  {

   stn=st->get_Next();

   int _code;

   int _info;

   THREAD*th=(THREAD*)st->Object;

   bool isthread=th->OBJECT::GetLockInfo(_code,_info)&&_code!=NODE::selThread;

   if (isthread&&_code==0&&_info==2)

   {

    if (!(th->Flags&(1<<THREAD::flBlocked)))

     continue;

    if (th->States&((1<<THREAD::stInLock)|(1<<THREAD::stInUnlock)))

     continue;

    int fake_states=0;

    AtomicSetFlags(&Object->States,(1<<OBJECT::stInUnlock));

    if (!th->THREAD::Resume(&fake_states,(1<<THREAD::stInLock)))

    {

     AtomicClearFlags(&Object->States,(1<<OBJECT::stInUnlock));

     st=((OBJECT*)Object)->Interlock.Children;

     continue;

    }

    break;

   }

  }

  unsigned int MaxCount=(1<<Magnitude)-1;

  if (flags&&FlatCount>=MaxCount)

  {

   thread->Flags|=1<<THREAD::flBlocked;

   thread->Interlock.Insert(&((OBJECT*)Object)->Interlock);

   thread->SetLockInfo(0,1,0);

   LockedIncrement(&OBJECT::interqueues);

   thread->Suspend(0,&Object->States,(1<<OBJECT::stInLock));

   while (Object->States&(1<<OBJECT::stInUnlock))

    BreakPoint();

   thread->Interlock.Index=((OBJECT*)MicroKernel)->Interlock.FlatCount;

   thread->Interlock.Insert((STREE*)&((OBJECT*)MicroKernel)->Interlock);

   LockedDecrement(&OBJECT::interqueues);

  }

  ((OBJECT*)Object)->OBJECT::CheckClosures(0);

  ((OBJECT*)Object)->SpinlockInterlock(false,0,(1<<OBJECT::stInLock));

}

 

STREE* STREE::GetChild (STREE* parent, int flags)

{

  THREAD*thread=THREAD::get_Current();

  ((OBJECT*)Object)->SpinlockInterlock(true,(1<<OBJECT::stInLock)|(1<<OBJECT::stInUnlock),(1<<OBJECT::stInUnlock));

  LockedIncrement(&OBJECT::dequeues);

  ((OBJECT*)Object)->OBJECT::CheckClosures(0);

  if (flags&&!Children)

  {

   thread->Flags|=1<<THREAD::flBlocked;

   thread->Interlock.Insert(&((OBJECT*)Object)->Interlock);

   thread->SetLockInfo(0,2,0);

   LockedIncrement(&OBJECT::interqueues);

   thread->VLock();

   thread->Suspend(0,&Object->States,(1<<OBJECT::stInUnlock));

   while (Object->States&(1<<OBJECT::stInLock))

    BreakPoint();

   thread->Interlock.Index=((OBJECT*)MicroKernel)->Interlock.FlatCount;

   thread->Interlock.Insert((STREE*)&((OBJECT*)MicroKernel)->Interlock);

   LockedDecrement(&OBJECT::interqueues);

   thread->VUnlock();

  }

  STREE*child=(STREE*)get_First();

  if (child)

   child->Insert(parent);

  STREE_BASE*stn;

  if (flags)

  for (STREE_BASE*st=((OBJECT*)Object)->Interlock.Children;st;st=stn)

  {

   stn=st->get_Next();

   int _code;

   int _info;

   THREAD*th=(THREAD*)st->Object;

   bool isthread=th->OBJECT::GetLockInfo(_code,_info)&&_code!=NODE::selThread;

   if (isthread&&_code==0&&_info==1)

   {

    if (!(th->Flags&(1<<THREAD::flBlocked)))

     continue;

    if (th->States&((1<<THREAD::stInLock)|(1<<THREAD::stInUnlock)))

     continue;

    int fake_states=0;

    AtomicSetFlags(&Object->States,(1<<OBJECT::stInLock));

    if (!th->THREAD::Resume(&fake_states,(1<<THREAD::stInLock)))

    {

     AtomicClearFlags(&Object->States,(1<<OBJECT::stInLock));

     st=((OBJECT*)Object)->Interlock.Children;

     continue;

    }

    break;

   }

  }

  ((OBJECT*)Object)->OBJECT::CheckClosures(0);

  ((OBJECT*)Object)->SpinlockInterlock(false,0,(1<<OBJECT::stInUnlock));

  return child;

}

 

8.8         Testul de integritate a dispecerului

boolean OBJECT::CheckClosures (int flags)

{

  boolean retval=true;

  static int spin_phase=0;

  static char spin=0;

  LockSpinlock(&spin_phase,&spin);

  int th_count=THREAD_Type(AbstractKernel)->TypeInfo.FlatCount;

  flags|=1; // Posting debug messages to the GUI may deadlock.

  if (CHECK_TWICE(th_count<THREAD::RunningThreads))

   retval=false;

  if (CHECK_TWICE(THREAD::suspends<THREAD::resumes))

   retval=false;

  if (CHECK_TWICE(OBJECT::locks<OBJECT::unlocks))

   retval=false;

  if (CHECK_TWICE(OBJECT::enqueues<OBJECT::dequeues-THREAD::RunningThreads))

   retval=false;

  if (CHECK_TWICE(OBJECT::dequeues<OBJECT::enqueues-THREAD::RunningThreads))

   retval=false;

  if (CHECK_TWICE(TYPE::locks<TYPE::unlocks))

   retval=false;

  if (CHECK_TWICE(TYPE::locks-TYPE::unlocks-OBJECT::overlocks-

      OBJECT::interlocks>THREAD::RunningThreads))

   retval=false;

  if (CHECK_TWICE(THREAD::interlocks<0))

   retval=false;

  if (CHECK_TWICE(THREAD::RunningThreads<THREAD::interlocks))

   retval=false;

  if (CHECK_TWICE(OBJECT::locks-OBJECT::overlocks<0))

   retval=false;

  if (CHECK_TWICE(STREAM::opened<STREAM::closed))

   retval=false;

  if (CHECK_TWICE(OBJECT::locks-OBJECT::unlocks-OBJECT::overlocks-

      OBJECT::interlocks>THREAD::RunningThreads))

   retval=false;

  if (flags&(1<<2))

   if (!retval)

    FAULT("Closure errors");

  spin=0;

  return retval;

}

9           Testele "simple" de concurenta

   case CAT_ABSTRACT::tsThreadsContentdingOverSemaphore:

   {

    while (true)

    {

     sema4->Lock();

     if (pause)

      HOST_OS::Sleep(pause);

     sema4->Unlock();

     TEST_EXIT_CONDITION

    }

    break;

   }

   case CAT_ABSTRACT::tsThreadsContendingOverMemory1:

   case CAT_ABSTRACT::tsThreadsContendingOverMemory2:

   {

    int data_sizes[]={0,8,16,32,64,128,256,512,1024,2*1024,3*1024,4*1024};

    NODE*    nodes[]={0,0, 0, 0, 0,  0,  0,  0,   0,     0,     0,     0};

    int nodes_count=sizeof(data_sizes)/sizeof(data_sizes[0]);

    int phase=0;

    static int phase_insert_remove=0;

    static char spin_insert_remove=0;

    TREE*n;

    while (true)

    {

     static int nphase=0;

     static char spin=0;

     for (int i=0;i<nodes_count;i++)

     {

      if (nodes[i])

       continue;

      char namebuf[100];

      sprintf(namebuf,"N%0.4d",nphase++);

      if (code==CAT_ABSTRACT::tsThreadsContendingOverMemory1)

       n=NODE::INIT(th,0,namebuf,NODE_Type(th),0);

      else

      {

       n=(NODE*)NODE_Type(th)->CreateInstance(data_sizes[phase++%nodes_count],0)

       n->set_Name(namebuf);

       n->Insert(th,NORMAL);

      }

      nodes[i]=(NODE*)n;

      if (pause)

       HOST_OS::Sleep(pause);

     }

     current_time=start_time;

     HOST_OS::SetTimeReference(current_time);

     int delete_count=current_time&3;

     while (delete_count--)

     {

      int ni=(current_time+delete_count)%nodes_count;

      n=nodes[ni];

      if (!n)

       continue;

      nodes[ni]=0;

      n->Free();

      if (pause)

       HOST_OS::Sleep(pause);

     }

     TEST_EXIT_CONDITION

    }

    for (int i=0;i<nodes_count;i++)

    {

     if (!nodes[i])

      continue;

     nodes[i]->Free();

    }

    break;

   }

10       Problema producator-consumator

void CAT_SCHOOL::LoadHTML (STREAM* s, TREE* umbrella)

{

  THREAD*producer=THREAD::get_Current();

  CAT_SCHOOL*school=CAT_SCHOOL_Type(AbstractKernel);

  school->InitEnvironment(s,umbrella);

  STREAM*local_s=s;

  TREE*local_umbrella=umbrella;

  if (!(Options&(1<<ofProducerConsumer)))

  {

   if (school->Produce(s,umbrella))

    school->Consume(local_s,local_umbrella);

  }

  else

  {

   static THREAD*consummer=0;

   if (consummer==0)

   {

    static int phase=0;

    char thread_name[1000];

    sprintf(thread_name,"Archiver_%0.4d(%s)",phase++,school->Name);

    int pid=OBJECT_BASE::Fork(thread_name,0);

    if (pid==0)

    {

     consummer=THREAD::get_Current();

     while (!(consummer->Flags&(1<<THREAD::flCancelled)))

      school->Consume(local_s,local_umbrella);

     consummer=0;

     return;

    }

   }

   school->Produce(s,umbrella);

   if (consummer)

    if (producer->Flags&(1<<THREAD::flCancelled))

      consummer->Free();

  }

}

 

Mecanismul producator/consumator cu producatori si consumatori multiplii este aplicat in captura urmatoare intr-un proces de incarcare a doua dictionare cu texte importate pe 3 fire de executie. Firele de incarcare si cele de arhivare concureaza pentru resurse precum SCHOOL, QUEUE, dictionarul "Romanian Legal Archive", alocatorul de memorie ABSTRACT, compilatorul HTML.

11       Problema filozofilor chinezi

int THREAD::TestThreads (int pause,int count)

{

  THREAD*th=(THREAD*)THREAD::get_Current();

  int local_pause=pause;

  if (count>0) // main thread

  {

   THREAD*first=0;

   THREAD*last=0;

   for (int i=0;i<count;i++)

   {

    char ThreadName[100];

    sprintf(ThreadName,"TestTh%0.2d",i);

    if (Fork(ThreadName,stack_size))

     continue;

    THREAD*child=(THREAD*)get_Current();

    if (!first)

     first=child;

    else

     CAT_MORPH_Type->CreateLine(child,last,0);

    last=child;

    child->V_Size.x=child->V_Size.y=32;

    child->V_Origin=point(100*sin(2*M_PI/i),100*cos(2*M_PI/i));

    child->Insert(th,NORMAL);

    TestThreads(local_pause,0);

    return 0; // Exit spawned child

   }

   if (first!=last)

    CAT_MORPH_Type->CreateLine(last,first,0);

   do

   {

    current_time=start_time;

    HOST_OS::SetTimeReference(current_time);

    HOST_OS::Sleep(2000);

   }

   while (current_time-start_time<2*1000);

   return 0; // Exit test

  }

  while (true) // child thread

  {

   LINE*forks[2]={th->GetLine(FROM,0),th->GetLine(TO,0)};

   if (forks[0]&&forks[1])

   {

    int pick=random(2);

    if (forks[(pick+0)%2]->TryLock())

    {

     if (forks[(pick+1)%2]->TryLock())

     {

      forks[0]->EndpointStyle[LINE::FROM]=LINE::esEllipse;

      forks[1]->EndpointStyle[LINE::TO]=LINE::esEllipse;

      th->Angle.y++;

      point p=th->V_Origin;

      double radius=th->Angle.y;

      double angle=M_PI*th->Angle.x/360;

      p=point((int)(radius*sin(angle)),(int)(radius*cos(angle)));

      th->V_Origin=p;

      if (pause) HOST_OS::Sleep(pause*random(threads));

      forks[0]->EndpointStyle[LINE::FROM]=LINE::esNone;

      forks[1]->EndpointStyle[LINE::TO]=LINE::esNone;

      forks[(pick+1)%2]->Unlock();

     }

     forks[(pick+0)%2]->Unlock();

    }

   }

   if (pause) HOST_OS::Sleep(pause*random(threads));

   TEST_EXIT_CONDITION

  }

  return 0;

}

 

Pornita mai mult ca un exercitiu, implementarea problemei filozofilor chinezi a devenit o unealta importanta de diagnostic a sistemului de timp real si a calitatii dispecerului.


Algoritmul alege aleator furculitele si pauzele. Filozoful care apuca sa manance se "ingrasa" si se indeparteaza de centrul mesei.

 

Liniile despartitoare sunt furculitele. Filozoful incearca sa-si insusasca furculitele prin TryLock pe respectivele linii (resurse obiectuale) Liniile se inrosesc pe editorul schematic si au cate un cerculet catre filozof. Nu toti filozofii sunt surprinsi mancand la o trecere de esantionare pe care editorul schematic of face asupra structurii.

 

Filozofii pornesc la distanta egala de centru si unii capata relativ repede un avantaj fata de ceilalti. Calitatea si impartialitatea dispecerului se manifesta dupa cateva minute de rulare, cand avantajul se schimba si in general se niveleaza. Figura circulara initiala trebuie sa se regaseasca si spre finalul testului dupa cum demonstreaza urmatoarea captura:

 


 

 

Home

Home | Feedback | Contents | Search

Send mail to webmaster@ProximaCentauri.ro with questions or comments about this web site.
All principles and artwork exposed on this site or by our software products is our intellectual property. 
Copyright 2006 Proxima Centauri Romania SRL. Last modified: 05/27/09