Osobiste, szkoła etc., Programowanie (IDE, UML, Wzorce...), Programowanie (Moje Projekty), Programowanie (PHP, Java...), Techblog

Lock-free: stos

27 grudnia, 2008 o 21:28:12 Dodaj komentarz Poziom: 0 Permalink

Ostatnio bawię się w rozwijanie własnego systemu operacyjnego. Wspaniała sprawa jeśli ktoś myśli, że wszystko wie ;)

W trakcie wyszło na jaw, że muszę zaimplementować synchronizowany zbiór (dokładniej rzecz biorąc - nieużywanych stron). Ale czekanie na mutexie nie wydaje się optymalną strategią. Poszukałem więc algorytmów lock-free. Na początek przyszedł stos.

Operacje

Podstawowy zdejmowania jest taki:

loop saved_head = head if saved_head == null return null end if cmp_and_swap(head, saved_head, saved_head.next) return saved_head.data end end

A wkładania taki:

node = malloc(); do saved_head = head node.next = saved_head while(!cmp_and_swap(head, saved_head, node))

Implementacja w assemblerze x86

Assembler x86 ma przydatną instrukcję. Dostajemy nie tyle wiadomość czy operacja się udała tylko ustawioną flagę zero jeśli się udała oraz nową wartość w eax.

W poniższym kodzie zakładam, że wskaźnik na następny element jest pierwszym polem węzła.

  1.  
  2.         ; edx - adres wskaźnika na pierwszy element
  3.         mov eax, [edx]
  4. spin:
  5.         test eax, eax
  6.         jz end                          ; Jeśli stos pusty kończymy
  7.         mov ecx, [eax]                  ; Pobieramy nowy początek
  8.         lock                            ; Atomicznie
  9.         cmpxchg [edx], ecx              ; Jeśli się nie zmieniło to zamieniamy
  10.         jnz spin                        ; A jeśli się zmieniło to do w eax jest nowy początek
  11. end:
  12.  

Na koniec mamy w akumulatorze zdjęty właśnie węzeł.

  1.  
  2.         ; ecx - węzeł, który wkładamy
  3.         ; edx - adres wskaźnika na pierwszy element
  4.         mov eax, [edx]
  5. spin:
  6.         mov [ecx], eax
  7.         lock
  8.         cmpxchg [edx], ecx
  9.         jnz spin
  10.  

Implementacja w C

Implementacja w C zamiast w inline assembler ma mało zalet. IMHO kod jest mniej czytelny a i tak jest mniej przenośny. Na dodatek gcc nie potrafi kodu dobrze zoptymalizować (nie wie o zmienionych flagach etc.).

  1.  
  2. struct stack_node {
  3.   struct stack_node *next;
  4.   void *data;
  5. };
  6.  
  7. struct stack {
  8.   volatile struct stack_node *head;
  9. };
  10.  
  11. struct stack_node *
  12. pop(struct stack *stack)
  13. {
  14.   struct stack_node *head;
  15.  
  16.   do
  17.     {
  18.       head = stack->head;
  19.       if (head == NULL)
  20.         break;
  21.     }
  22.   while(!cmp_and_swap(&stack->head, head, head->next));
  23.  
  24.   return head;
  25. }
  26.  
  27. void
  28. push (struct stack *stack, struct stack_node *head)
  29. {
  30.   do
  31.     {
  32.       head->next = stack->head;
  33.     }
  34.   while(!cmp_and_swap(&stack->head, head->next, head));
  35. }
  36.  

Na co trzeba zwrócić uwagę

Jeśli nie mamy GC to jest problem co zrobić z wskaźnikiem. Nie można go po prostu zwolnić bo nie wiemy czy właśnie ktoś go nie próbuje użyć. Pozostawienie go 'bez opieki' to wyciek pamięci. Rozwiązanie które znalazłem jest proste - należy mieć osobny stos (no dobrze - nie musi być stos ale to już mamy zaimplementowane) na którym odkładamy wolne węzły.

Źródła

Wzorowałem się na fragmentach kodu (a właściwie na postach o tych fragmentach) z OmniThreadLibrary - bibliotece na licencji BSD.

Na potrzeby projektu stworzyłem nagłówek. Podobne rozwiązanie znalazłem w którymś kernelu *BSD:

  1. #define STACK(name, data...)                    \
  2.   struct name ##_node                           \
  3.   {                                             \
  4.     struct name ## _node *next;                 \
  5.     data;                                       \
  6.   };                                            \
  7.   struct name                                   \
  8.   {                                             \
  9.     volatile struct name ## _node *head;        \
  10.   };
  11.  
  12. #define STACK_POP(stack, node)                                          \
  13.   __asm__ __volatile__ ("\n"                                            \
  14.                         "1:\n"                                          \
  15.                         "\ttest %%eax, %%eax\n"                         \
  16.                         "\tjz 1f\n"                                     \
  17.                         "\tmov (%%eax), %%ecx\n"                        \
  18.                         "\tlock cmpxchg %%ecx, %0\n"                    \
  19.                         "\tjnz 1b\n"                                    \
  20.                         "1:"                                            \
  21.                         : "=m"(stack.head), "=a" (node)                 \
  22.                         : "m"(stack.head), "a" (stack.head)             \
  23.                         : "%ecx" );                                     \
  24. #define STACK_PUSH(stack, node)                                         \
  25.  __asm__ __volatile__ ("\n"                                             \
  26.                        "1:\n"                                           \
  27.                        "\tmov %%eax, (%%ebx)\n"                         \
  28.                        "\tlock cmpxchg %%ebx, %0\n"                     \
  29.                        "\tjnz 1b\t"                                     \
  30.                        : "=m"(stack.head), "=m"(node->next)             \
  31.                        : "m" (stack.head), "b"(node),                   \
  32.                        "a" (stack.head));                               \
  33.  
  34.  

PS. Będę szukał informacji na temat innych struktur LF. Czy jest zainteresowanie?

PPS. Spróbuje upchnąć wpis na techblogu. Może się uda...

Otagowano: ,

Komentarze do wpisu

Możesz śledzić odpowiedzi poprzez kanał RSS. Możesz dodać komentarz lub zostawić ślad (trackback) ze swojego bloga.

#

Avilar

Fajna sprawa, jakbyś w przystępny sposób opisał jak stworzyć kawałek kodu który się sam zabootuje byłoby super. Pamiętam że gdzieś coś takiego czytałem ale nie bardzo pamiętam gdzie. Poza tam bardzo mało osób pisze tu o systemach od tej strony.

Tak trzymać.

27 grudnia 2008, 22:41:58

#

Paweł Dziepak

@Avilar: Pewnie chodziło Ci o ten tekst: http://binboy.sphere.pl/index.php?show=43

@Użytkownik: Pierwszy fragment w assemblerze x86 -> zgubiłeś ‘p’ w cmpxchg.
Osobiście jeszcze nie zajmowałem się zagadnieniami związanymi z synchronizacją, ale muszę przyznać, że zaimponowały mi możliwości jakie skrywa cmpxchg. Słyszałem, że ta instrukcja jest często wykorzystywana do takich zadań jednak nie pomyślałem, że cały mechanizm jest aż taki piękny w swej prostocie :P

No i prawie sakramentalne pytanie jeżeli chodzi o każdy amatorski kernel: monolit czy mikrojądro?

27 grudnia 2008, 23:30:15

#

Uzytkownik

@Avilar: Mogę napisać cosik o NIOS. Ale sam się uczę. Na razie próbuje rozwiązać inicjalizację podsystemu pamięci (pierwszy podsystem).

Jeśli chodzi o większą ilość informacji to jest OSDev i kilka innych źródeł. Ale zazwyczaj są albo niekompletne (jak zrobić tak by się bootowały) albo strasznie oschłe i nieprzystępne.

@Pawel Dziepak: Kod zajmuje prawieże mniej niż w C i jest w dodatku.. czystszy.

Jądro z założenia ma być mikrojądrem. Dlatego 2 pierwszymi podystemami mają być pamięć i wielozadaniowość (scheduling i IPC). A postaram się, żeby np. video było modułem w userspace ładowanym przez gruba.

27 grudnia 2008, 23:53:10

#

Paweł Dziepak

Tu już nawet nie chodzi o to czy implementacja w C czy w assemblerze x86 (czy jakimkolwiek innym), bo niezależnie od tego i tak instrukcja cmpxchg zostanie użyta.
Inna sprawa, że pewne niskopoziomowe rzeczy lepiej jest zrobić w assemblerze. Sam niedawno robiłem takie porządki w moim kodzie, szczególnie w miejscach gdzie wykorzystałem wcześniej inline assembler.

Z tego co mówisz to będzie to takie bardziej „prawdziwe” mikrojądro czyli coś w stylu L4.
Jeszcze co do serwerów/modułów, wszystkie chcesz ładować przez gruba, czy tylko te które będą potrzebne kernelowi do samodzielnego załadowania kolejnych?

28 grudnia 2008, 00:05:05

#

Uzytkownik

Hmm. Z implementacji w C niewiele da się wykroić poza zwykłe C&S. Generalnie mam niechęć do asm ale tutaj pokazał swoje kły.

Na razie wszystko przez GRUBa jako biblioteki ELF czy binarki ELF czy cokolwiek bądź. Potem (a właściwie jeśli ;), po zaimplementowaniu obsługi dysku i FS to ładowanie będzie z dysku/sieci/cokolwiek podsystem VFS wymyśli.

Pytanie tylko czy skorzystać z implementacji ELF czy odpowiednika w sposób bezpośredni czy bardziej potraktować to jako biblioteki (jądro wywołuje odpowiednie funkcje działające w RINGu 3 w swojej przestrzeni adresowej).

28 grudnia 2008, 00:21:06

#

Uzytkownik

PS. Na sensowniejsze wypowiedzi trzeba poczekać do jutra. Dobranoc ;)

28 grudnia 2008, 00:21:40

Dodaj komentarz

Textile Lite włączony ( szczegółowy opis znaczników ):

« Poprzedni wpis

Następny wpis »