http://pdziepak.quarnos.org/Wpisy z dziennika internetowego Jogger, wspomaganego przez JabberaTue, 07 Feb 2012 14:55:15 +0100JoggerPLhttp://pdziepak.quarnos.org/2011/12/21/hazard-pointers/Implementacja nieblokujących struktur danych często stwarza problemy często niespotykane przy okazji opracowywania jakichkolwiek innych algorytmów. Całkowicie zasadnie, najpopularniejszymi przykładami w opracowaniach na ten temat jest problem ABA i jego pochodne. Oczywiście, do dnia dzisiejszego powstało wiele sposobów radzenia sobie z nim. Jednym z ciekawszych są tak zwane hazard pointers. Problem ABA Na początek warto jednak przybliżyć (lub przypomnieć) dlaczego problem ABA jest problemem i o co w ogóle w nim chodzi. Bardzo często operacje na strukturach danych lock-free wyglądają w uproszczeniu tak: Pobierz z pamięci dzielonej adres obiektu A ze wskaźnika head. Wykonaj odpowiednie operacje na obiekcie A, np. odczytaj dane oraz adres kolejnego obiektu B. Jeśli head wskazuje dalej na ten sam obiekt (tj. adres jest ten sam) przypisz do niego pobrany punkt wyżej adres obiektu B. Zwolnij pamięć po obiekcie A Jak widać jest to uproszczona implementacja ściągania elementu z nieblokującego stosu zaimplementowanego przy pomocy listy jednokierunkowej. Teraz, czas na problem ABA. Popatrzmy co się stanie jeśli w trakcie wykonywania pkt. 2 wątek zostanie wywłaszczony i w międzyczasie inny wątek (lub wątki) ściągnie ten element ze stosu i zwolni po nim pamięć, a następnie doda inny obiekt który zostanie umieszczony pod tym samym adresem. W takiej sytuacji pierwszy wątek po wznowieniu i dotarciu do pkt. 3 uzna że head wskazuje na ten sam obiekt co w pkt. 1 i uaktualni go (najprawdopodobniej) niepoprawnym adresem kolejnego obiektu. Dodatkowo jako wspomniane wcześniej "pochodne problemu ABA" rozumiem sytuacje gdy wątek będzie chciał odczytać dane z obiektu który w międzyczasie przestał istnieć. Hazard pointers Zasada działania tego mechanizmu jest dosyć prosta. Każdy wątek posiada wskaźnik, właśnie tytułowy hazard pointer, na obiekt który aktualnie przetwarza oraz prywatną (tj. używaną tylko przez wątek który jest jej właścicielem) listę obiektów które powinny zostać usunięte. Hazard pointers są ułożone w listę jednokierunkową możliwą do przeglądania przez każdego. Teraz, dodatkowo, w pierwszym kroku adres obiektu A z head algorytm musi umieścić w hazard pointer jego wątku, po czym sprawdzić czy head nadal wskazuje na obiekt A (przed uaktualnieniem hazard pointera problem ABA jeszcze ma się dobrze). Jeśli tak to obiekt A jest bezpieczny i możemy na nim pracować. Gdy skończymy, po prostu zerujemy nasz hazard pointer. Kolejne zmiany potrzebne są w pkt. 4. Zamiast po prostu zwalniać pamięć po zdjętym ze stosu elemencie jego adres jest umieszczony na liście obiektów do usunięcia. Następnie usunięte zostają wszystkie obiekty obecne na tej liście i nieobecne na liście hazard pointerów. Jest to bezpieczne ponieważ każdy przetwarzany lub z innego powodu potrzebny obiekt albo nie trafił jeszcze na tę listę, albo zaraz na nią trafi ale jeszcze jest zabezpieczony hazard pointerem. Wszystkie obiekty które już powinny być usunięte, ale ktoś ich jeszcze używa zostaną zwolnione przy następnej okazji. Podsumowanie Hazard pointers w dość prosty sposób zapewniają, że żaden obiekt nie zostanie usunięty w trakcie gdy jest przetwarzany przez inny wątek. Jest to rozwiązanie bardzo uniwersalne. Można je z powodzeniem stosować w konkretnych strukturach danych, a także jest świetnym uzupełnieniem innych ogólnych rozwiązań jak np. RCU, co zostało opisane w [1]. Pewną wspomnianą tam niedogodnością, dotyczącą nie tylko RCU, jest fakt, że każde użycie hazard pointera jest lock-free, a co za tym idzie tracą na tym operacje wait-free takie jak np. odczyt w przypadku RCU. [1] A. Alexandrescu, M. Michael, Lock-Free Data Structures with Hazard PointersWed, 21 Dec 2011 02:58:20 +0100http://pdziepak.quarnos.org/2011/12/21/hazard-pointers/ProgramowanieTechbloglock-freewait-freercuhazard pointerhttp://pdziepak.quarnos.org/2011/10/11/tifnit-cz-ii/Tym razem druga porcja zdjęć z wioski Tifnit. Tue, 11 Oct 2011 23:41:41 +0200http://pdziepak.quarnos.org/2011/10/11/tifnit-cz-ii/Fotografiatifnitmarokozdjęciahttp://pdziepak.quarnos.org/2011/10/01/essaouira-cz-ii-port/Kolejne zdjęcia z Essaouiry, tym razem więcej fotografii portu i jego okolic. Sat, 01 Oct 2011 18:55:20 +0200http://pdziepak.quarnos.org/2011/10/01/essaouira-cz-ii-port/Fotografiaessaouiraas-sawiramarokozdjęciahttp://pdziepak.quarnos.org/2011/09/26/marrakesz-cz-ii/Kolejna porcja zdjęć z Czerwonego Miasta. Mon, 26 Sep 2011 19:41:47 +0200http://pdziepak.quarnos.org/2011/09/26/marrakesz-cz-ii/Fotografiamarrakeszmarokozdjęciahttp://pdziepak.quarnos.org/2011/09/17/blokady-czytelnicy-pisarze-2-0/Blokady typu czytelnicy-pisarze są opisane chyba w każdym podręczniku traktującym o systemach operacyjnych czy synchronizacji dostępu do danych. Jest to proste rozwiązanie które jednak w praktyce nie okazało się być w pełni satysfakcjonujące. W wyniku prób pozbycia się pewnych wad tych blokad w Linuksie (i nie tylko) zagościły także dwie alternatywy tego rozwiązania: seqlocks i RCU. Reader-writer lock (RWL) Tradycyjnym sposobem synchronizacji w przypadku dostępu do danych, które są często jedynie czytane, bez wprowadzania żadnych modyfikacji jest stosowanie blokad typu czytelnicy-pisarze. Ogólnie rzecz ujmując ta metoda polega na tym, że dostęp do danych ma albo jeden wątek zapisujący albo dowolna ilość wątków odczytujących. Blokady typu czytelnicy-pisarze są bardzo podstawowym mechanizmem, którego niektóre wady wymusiły opracowanie alternatywnych rozwiązań bardziej odpowiednich w konkretnych zastosowaniach. Sequential locks (seqlocks) Przy dużej ilości czytelników w RWL wątki modyfikujące dane mogą zostać zagłodzone. W celu rozwiązania tego problemu opracowano blokady sekwencyjne, w których pisarze nie są blokowani przez czytelników. Seqlocks składają się z dwóch elementów, zwykłej blokady mającej na celu wykluczenie jednoczesnego dostępu do danych dwóch pisarzy oraz licznika. Pisarz przy zakładaniu oraz zwalnianiu blokady zwiększa licznik o jeden. Czytelnik przy zakładaniu oraz zwalnianiu swojej blokady odczytuje ten licznik. Jeżeli w obu przypadkach wartość jest taka sama i parzysta oznacza to że odczyt się powiódł i można kontynuować pracę. Jeśli zaś wartości są różne lub nieparzyste dane były odczytywane w trakcie ich modyfikacji i należy ponowić odczyt. Blokady tego typu zwiększają priorytet pisarzy kosztem czytelników. W odróżnieniu od standardowych RWL teraz to czytelnicy mogą zostać zagłodzeni jeżeli przez pisarzy nie będzie udawać im się wykonać poprawnego odczytu danych. Read-copy-update (RCU) Mechanizm read-copy-update jest próbą rozwiązania problemu głodzenia pisarzy (RWL) lub czytelników (seqlock). Wątek zamierzający zmodyfikować współdzielony obszar pamięci wskazywany przez dany wskaźnik wykonuje następujące operacje: kopiuje dane, wprowadza modyfikacje do kopii, uaktualnia wskaźnik tak aby wskazywał na kopię. Dzięki temu, że modyfikacja wskaźnika jest operacją atomową, więc czytelnicy odczytają albo jego nową, albo starą wartość. W tym momencie pozostaje jedynie w odpowiednim momencie zwolnić pamięć zajmowaną przez stare dane, aby było to możliwe każdy czytelnik powiadamia kiedy zaczyna lub kończy czytać. Powstało wiele implementacji usprawniających ten konkretny etap, od prostych liczników referencji po bardziej wyspecjalizowane mechanizmy korzystające ze specyfiki środowiska w jakim pracują (chodzi głównie o jądro Linuksa). Największym problemem RCU jest konieczność kopiowania danych, co może być problemem przy dużej ilości pisarzy. Implementacja RCU w Linuksie dostarcza interfejsu ułatwiającego wykonywanie operacji na listach bez konieczności kopiowania całej struktury danych, ale oczywiście nie zawsze jest to możliwe w przypadku innych struktur.Sat, 17 Sep 2011 21:45:16 +0200http://pdziepak.quarnos.org/2011/09/17/blokady-czytelnicy-pisarze-2-0/ProgramowanieSystemy operacyjneTechblogsynchronizacjablokadyczytelnicypisarzeseqlockrcureadcopyupdatehttp://pdziepak.quarnos.org/2011/09/13/hurghada/Hurghada, miasto kojarzące się zwykle jako spory ośrodek turystyczny wygląda zupełnie inaczej w starszej części, rzadziej odwiedzanej przez turystów. Tue, 13 Sep 2011 18:34:45 +0200http://pdziepak.quarnos.org/2011/09/13/hurghada/Fotografiahurghadaegiptzdjęciahttp://pdziepak.quarnos.org/2011/09/11/asuan/Asuan, jedno z najsuchszych zamieszkanych miejsc na świecie, paradoksalnie wybudowana na południe od miasta Wysoka Tama Asuańska utworzyła jeden z największych na świecie sztucznych zbiorników wodnych, Jezioro Nasera. Sun, 11 Sep 2011 22:59:19 +0200http://pdziepak.quarnos.org/2011/09/11/asuan/Fotografiaasuanegiptzdjęciahttp://pdziepak.quarnos.org/2011/09/07/tifnit/Tifnit, niewielka wioska rybacka położona na południe od Agadiru, większość domostw nie posiada elektryczności, a asfaltowa droga kończy się kilkaset metrów wcześniej co uniemożliwia autom podjechanie do samych zabudowań. Wed, 07 Sep 2011 16:06:11 +0200http://pdziepak.quarnos.org/2011/09/07/tifnit/Fotografiatifnitmarokozdjęciahttp://pdziepak.quarnos.org/2011/09/05/agadir/Agadir, mgliste miasto zniszczone niemal całkowicie na skutek trzęsienia ziemi w 1960, odbudowane rok później straciło nieco swój tradycyjny wygląd jaki można by po nim oczekiwać widząc inne duże miasta Maroka. Mon, 05 Sep 2011 16:50:34 +0200http://pdziepak.quarnos.org/2011/09/05/agadir/Fotografiaagadirmarokozdjęciahttp://pdziepak.quarnos.org/2011/09/04/essaouira/Essaouira, As-Sawira, miasto dawniej funkcjonujące jako port Marrakeszu. Sun, 04 Sep 2011 16:09:15 +0200http://pdziepak.quarnos.org/2011/09/04/essaouira/Fotografiaessaouiraas-sawiramarokozdjęciahttp://pdziepak.quarnos.org/2011/09/03/marrakesz/Marrakesz, Czerwone Miasto, w dzień oraz w nocy, w pełni swojej wielkości na placu Dżamaa al-Fina. Sat, 03 Sep 2011 14:32:42 +0200http://pdziepak.quarnos.org/2011/09/03/marrakesz/Fotografiamarrakeszmarokozdjęciahttp://pdziepak.quarnos.org/2009/11/10/the-ancient-blob/FreeSpace is a 10-year-old game and despite the fact SCP developers have been doing great work since 2002 there are still many parts of code that were left unchanged. That means there is a great variety of antipatterns. Some of them are being solved while the others are so complex that their refactorization will require large amount of work. One of these antipatterns, easily found in FSO, is The Blob. The Blob Class is a class that has a huge number of members and is given many, loosely related responsibilities. It is a procedural design, therefore, it is considered as antipattern and an existence of such thing in any object-oritented code is a problem. More elaborated description of The Blob is available here. FreeSpace used to support both DirectX and OpenGL, after 2002 the majority of new features was implemented only in OpenGL thus DirectX code became outdated soon and eventually was removed from the code. Unfortunately, the original mechanism that allowed the engine to support two APIs is still present in the code. In OOP the best way to design the code that implements the one interface in two different ways is to take advantage from virtual member functions. The original FreeSpace developers did the same, but without the "object-oriented" part. They created structure screen that consist of over 100 function pointers (the whole structure has 277 lines of code). Actually, they implemented some kind of virtual functions table that was filled at start-up with the addresses of appropriate functions. What's more, this structure also stores data required by rendering functions, such as screen resolution, fog settings, alpha blending configuration, etc. In addition to that, it still grows, new graphics functions are being added to the list. The situation, probably won't improve until somebody rewrites a large amount of graphics code in OOP manner. {geshi lang="c"} typedef struct screen { uint signature; int max_w, max_h; /* lots of things here */ bool recording_state_block; int current_state_block; void (*gf_start_state_block)(); int (*gf_end_state_block)(); void (*gf_set_state_block)(int); //switch onscreen, offscreen void (*gf_flip)(); /* lots of things here */ void (*gf_gradient)(int x1, int y1, int x2, int y2, bool resize); void (*gf_circle)(int x, int y, int r, bool resize); void (*gf_curve)(int x, int y, int r, int direction); /* lots of things here */ void (*gf_render_buffer)(int, int, ushort*, uint*, int); int (*gf_make_flat_buffer)(poly_list*); int (*gf_make_line_buffer)(line_list*); /* lots of things here */ } screen; {/geshi}It is not surprising that ten years ago programmers didn't thought about OOP and used C to create a computer game. In procedural design such structure is not a "pure evil" as much as in object-oriented design. Unfortunately, nobody bothered to improve that part of FSO code and structure screen still scares unsuspecting people. Nevertheless, such nasty parts of code may be very interesting (especially for the coders that don't remember the "good old days"). They show how much changed the techniques programmers use and give an general idea how much it will change. Procedural programming ten years ago, object-oriented now and something completely new in the next 10 years (maybe something that will evolve from data-driven component design that is more and more popular among game developers). Tue, 10 Nov 2009 16:59:00 +0100http://pdziepak.quarnos.org/2009/11/10/the-ancient-blob/FreeSpace Source Code ProjectProgramowanieProjektyTechblogblobantipatternoopproceduraldesignobjectscpfsohttp://pdziepak.quarnos.org/2009/11/09/post-processing/When I finished adding support of subtractive shaders to FSO engine (described in my previous post) I decided to implement post-processing. It usually doesn't require many changes in existing code. That was good since I wasn't familiar with the majority of FSO source code at that time. The other reason was that it is easy to achieve satisfactory results adding a few very simple post-processing effects. However, most of them will be used only in cutscenes rendered by the engine. How does it work? The main idea of post-processing is really simple. The scene has to be rendered to a texture first and then drawn to the back buffer. During the second step various additional effects may be applied, hence the name - these computations are performed when the scene is already rendered. It allows to implement a wide range of effects from the completely useless ones like ASCII-art rendering to things like HDR, depth of field, motion blur, light shafts, etc. Simple effects Initially my patch introduced only a few simple effects, that were implemented entirely in shaders code. To work properly they needed nothing but the scene texture and intensity values. Currently four simple effects are supported: contrast saturation film grain distortion noise These effects are similar to the filters that can be found in many graphics editors. In fact, they work in exactly the same way - apply appropriate computations to the static 2D image. Exposure, gamma, contrast, hue, saturation and many other properties can be applied without any problems as well as different types of noises, blurs and many other things. However, blur is usually implemented in a bit more complicated way in order to minimize the performance loss. Effects management All these effects enlisted above have their entries in post_processing.tbl file in order to give the engine the information it needs to apply and control them. The following is an example entry: $Name: saturation $Uniform: saturation $Define: FLAG_SATURATION $AlwaysOn: false $Default: 1.0 $Div: 100 $Add: 0 Name - general name of the effect used for identification purposes. It is mostly used in FRED. If there are more than one effect with the same name the behaviour is undefined. Uniform - name of the uniform variable in the shader, that specifies the intensity of the effect. Define - name of the preprocessor definition that allows disabling and enabling the effect when needed. AlwaysOn - determines if the effect is always active or applied only when current intensity differs from the default intensity. Default - the default effect intensity. Div - divisor Add - adder The value of current intensity that is passed to the shader is counted using the equation: intensity = given_intensity / divisor + adder When given_intensity is the value set by user in mission code or additional scripts. In the following posts I'm going to describe other, more advanced effects that are achieved using post-processing. There also will be (already promised) description of the new shaders manager. Mon, 09 Nov 2009 15:34:36 +0100http://pdziepak.quarnos.org/2009/11/09/post-processing/FreeSpace Source Code ProjectGame DevelopmentProjektyTechblogpostprocessinggamedevfreespacescpfsohttp://pdziepak.quarnos.org/2009/11/06/freespace-source-code-project/It has been a long time since my last post here. Many things have changed, most notably the language in which this devlog is written. I considered switching to English a few months ago, when my blog was still active, but I didn't found enough reasons for that. Now, the situation is different. In September I joined FreeSpace Source Code Project. The main goal of this project is to keep FreeSpace, almost 10-year-old game, up to date, by improving every aspect of the game. It wouldn't be possible if Volition, Inc., the studio that created FreeSpace, hadn't given fans the whole source code in 2002. Since then, it is an open source project, not completely free (it can't be sold or used commercially in any other way), though. The website of SCP is a bit outdated, but you may find many interesting things on one of the biggest FreeSpace forum: HardLight.net or on the Polish FreeSpace website: FreeSpace.pl. I've started contributing to SCP by improving the way in which shaders source code was stored and managed. There were dozens of *.sdr files containing shaders with different features implemented. The ones with normal mapping, the ones with environment mapping, the ones with glow maps, etc. Each possible combination of feature had to be in a separate file, that's why SCP developers ended up with over 60 (if I recognize correctly) shaders, which shared very much with each other. I decided to introduce subtractive shader. This technique consists in creating one shader (one vertex shader and one fragment shader to be exact) with all the features implemented. Then according to the current needs parts of the code can be enabled or disabled using GLSL preprocessor instructions #define and #ifdef. . It was easy to implement in the rendering engine and only a bit harder to create one unified shader. I don't want to describe here in details how shaders are managed in FSO, because it is also improved by my next patch which I will describe soon in my next post. Fri, 06 Nov 2009 18:37:09 +0100http://pdziepak.quarnos.org/2009/11/06/freespace-source-code-project/FreeSpace Source Code ProjectProjektyfreespacegamedevgame developmentshaderhttp://pdziepak.quarnos.org/2009/03/31/very-concurrent-garbage-collection/Jednym z głównych problemów związanych z wykorzystaniem garbage collectora jest możliwość dość drastycznego spadku wydajności w nieoczekiwanych momentach. Z tego powodu odśmiecanie pamięci zwykle nie może zostać zastosowane w systemach czasu rzeczywistego, a także w innych sytuacjach gdzie wydajność programu jest istotna. Twórcy systemu Inferno stworzyli algorytm Very Concurrent Garbage Collection (VCGC), którego zadaniem jest zminimalizowanie tych problemów. Równoległe przetwarzanie System Inferno jest systemem rozproszonym. Powoduje to, że programowanie równoległe jest zalecanie i potrafi przynieść dość duży wzrost wydajności. Dlatego też istotą VGCG jest możliwość wykonywania procesu odśmiecania na wielu wątkach. Każdy z trzech elementów garbage collectora typu mark & sweep (jakim jest VGCG) jest całkowicie niezależny od pozostałych i może działać w oddzielnym wątku bez potrzeby używania dodatkowych mechanizmów synchronizacji. Niezależność poszczególnych operacji związanych z odśmiecaniem pozwala przenieść je na inny procesor dzięki czemu właściwe wykonywanie programu nie jest w żaden sposób dodatkowo spowalniane i działa tak samo wydajnie jak w sytuacji gdy garbage collector nie jest używany. Mark & sweep Najpopularniejszym rodzajem algorytmów odśmiecania pamięci jest mark & sweep. Polega on na zlokalizowaniu i oznaczeniu wszystkich używanych obszarów pamięci (czyli takich do których istnieją odwołania) a następnie zwolnieniu pozostałego miejsca. Zwykle garbage collector tego typu składa się z trzech elementów: mutator - właściwy kod programu, w nim znajduje się kod zajmujący się przydzielaniem pamięci na żądanie aplikacji marker - wyszukuje i oznacza nieużywane obiekty w pamięci sweeper - zwalnia obiekty które marker uznał za nieużywane Epoki Czas działania programu jest podzielony na epoki. Podczas każdej z nich w osobnych wątkach uruchomione zostają poszczególne elementy garbage collectora (muatator, marker i sweeper). Dodatkowo każdej epoce jest przyporządkowany jeden z trzech kolorów: COLOR(epoch) = epoch mod 3. Przydzielanie pamięci Pamięć jest przydzielana przy użyciu free lists. Jest to lista wskazujących na siebie wolnych bloków pamięci. Dzięki temu, że każdy wolny blok zawiera wskaźnik na następny, nie ma potrzeby tworzenia dodatkowych struktur danych do przechowywania tego typu informacji. Każdy przydzielany w ten sposób obiekt jest oznaczony kolorem aktualnie trwającej epoki. Marker W każdej epoce marker porusza się po wskazujących na siebie obiektach. Jeżeli kolor obiektu jest inny niż kolor aktualnej epoki marker uaktualnia go a następnie rekursywnie przegląda wszystkie bloki na które wskazuje dany obiekt. Gdy marker zakończy działanie wszystkie używane obiekty mają kolor danej epoki. Warto zauważyć że mutator i marker w żaden sposób nie wpływają na swoje działanie. Mutator oznacza wszystkie nowe obiekty kolorem aktualnej epoki, a ten jest przez markera ignorowany. Istotny jest także fakt, że marker nigdy nie spotka bloku oznaczonego kolorem innym niż kolor aktualnej, bądź poprzedniej epoki. Sweeper Sweeper przegląda listę przydzielonych bloków w poszukiwaniu obiektów oznaczonych kolorem epoki COLOR(epoch-2). Jeśli natrafi na taki obszar pamięci to jest on zwalniany. Jest to operacja całkowicie bezpieczna ponieważ ani marker ani mutator nie mają dostępu do obiektów oznaczonych takim kolorem. W przypadku natrafienia przez sweeper bloków o innym kolorze są one ignorowane, ponieważ wciąż mogą być w użyciu przez pozostałe elementy programu. Zakończenie epoki Gdy sweeper i marker zakończą pracę program przechodzi do kolejnej epoki o nowym kolorze i cały proces zaczyna się od nowa. Dzięki całkowitej niezależności poszczególnych elementów od siebie mutator, marker i sweeper mogą działać równolegle bez potrzeby wprowadzania blokad, co korzystnie wpływa na wydajność systemu. Podsumowanie Obecnie bardzo wiele języków programowania oferuje wbudowany garbage collector dlatego rozwój algorytmów tego typu nie jest niczym dziwnym. Dlatego taż warto dowiedzieć się na jakiego rodzaju rozwiązania można w tej dziedzinie natrafić. Tue, 31 Mar 2009 21:38:33 +0200http://pdziepak.quarnos.org/2009/03/31/very-concurrent-garbage-collection/ProgramowanieSystemy operacyjneSystemy rozproszoneTechbloggrabage collectorodśmiecanie pamięciinfernomark and sweepmutatormarkersweeperhttp://pdziepak.quarnos.org/2009/03/24/inferno-plan-9-i-maszyny-wirtualne/Historia Uniksa sięga końca lat 60 XX wieku. Tymczasem wiele systemów operacyjnych wciąż opiera się na przyjętych w nim, często już nieaktualnych, założeniach. Oczywiście takie systemy jak Solaris czy rodzina *BSD wprowadzają dużo dodatkowych technologii, ale wciąż są w pewien sposób ograniczane przez swoich poprzedników i oparte na nich standardy. Jest to główną przyczyną powstawania systemów eksperymentalnych. Brak zgodności ze standardami czy brak nacisku na niektóre aspekty (najczęściej jest to wydajność) powodują, że z reguły nie nadają się one do użytku codziennego, czy to jako serwer czy jako desktop. W żaden sposób nie zmniejsza to jednak wartości takich projektów. Są nimi, między innymi rozwijane przez Bell Labs systemy Plan 9 oraz Inferno, które w założeniu mają być następcami Uniksa. Zasoby i pliki W systemach Inferno i Plan 9 każdy zasób jest reprezentowany przez plik. Przypomina to założenia projektowe Uniksa ale jest na to kładziony jeszcze większy nacisk. Każde urządzenie, proces, sieć, połączenie sieciowe czy nawet otwarte okno jest osobnym plikiem. Dodatkowo zawartość tych plików może być generowana dynamicznie w zależności od stanu zasobu lub konkretnego klienta. Wyspecjalizowane sterowniki najczęściej są reprezentowane przez katalog zawierający pliki data i ctl. Pierwszy z nich służy do operacji wejścia-wyjścia, podczas gdy drugi jest używany do konfiguracji i kontroli urządzenia. Innym ciekawym przykładem jest nawiązywanie połączeń TCP, które odbywa się poprzez serię zapisów do odpowiednich plików reprezentujących konkretny sterownik. Także, wszelkie usługi i serwery są reprezentowane jako pliki. Jeżeli program w celu nawiązania połączenia internetowego potrzebuje adresu IP serwera obsługującego daną domenę otwiera plik reprezentujący usługę DNS i za jego pomocą uzyskuje odpowiednie informacje. Najczęściej dzieje się to poprzez wpisanie do pliku nazwy domeny, a następnie odczytanie adresu IP. To rozwiązanie jest szczególnie wygodne, zwracając uwagę na fakt, że zarówno lokalne i jak i zdalne zasoby są w ten sposób reprezentowane. Wspomniany serwer DNS wcale nie musi działać na tym samym komputerze. Prawa dostępu do plików pozwalają jednocześnie dokładnie określić prawa dostępu do poszczególnych usług, zasobów i urządzeń. Natomiast przechowywanie wszystkich obiektów (także np. połączeń sieciowych czy procesów) w postaci plików upraszcza wewnętrzną budowę systemu. Jedyny sztywno zapisany interfejs dotyczy samej obsługi systemu plików podczas gdy cała reszta jest oparta na plikach. Styx Traktowanie każdego zasobu czy usługi jako osobnego pliku wymaga odpowiedniego protokołu usprawniającego komunikację w systemach rozproszonych. Jego zadanie jest zbliżone do NFS, lecz można wskazać pewne wyraźne różnice. Przede wszystkim NFS jest przystosowany głównie do obsługi zwykłych plików, a nie np. generowanych w procfs. Styx jest przystosowany do obsługi każdego rodzaju plików. Każde odwołanie się klienta do systemu plików jest tłumaczone na szereg komunikatów protokołu Styx. Dla zapewnienia bezpieczeństwa wspierana jest autoryzacja klientów przy pomocy certyfikatów, a także szyfrowanie transmisji. Jest to mechanizm całkowicie niewidoczny dla aplikacji korzystających z protokołu Styx. Limbo Programy dla systemów Plan 9 oraz Inferno są pisane w specjalnie do tego zaprojektowanym języku programowania Limbo. Jest on kompilowany do kodu pośredniego wykonywanego następnie przez maszynę wirtualną Dis. Limbo jest także językiem bezpiecznym oferującym silną kontrolę zgodności typów. Limbo oferuje także kanały jako mechanizm komunikacji między procesami. Każdy kanał ma ściśle określony typ. Wymiana danych jest synchronizowana: proces, który chce wysłać lub odebrać dane musi czekać na gotowość drugiego procesu. Możliwe jest także utworzenie buforowanych kanałów które nie wymagają blokowania procesów z nich korzystających. Programy są zbudowane z modułów. Każdy moduł oferuje określony publiczny interfejs. Możliwe jest załadowanie wielokrotnie tego samego modułu z różnymi implementacjami. Kod jest wykonywany przez procesy, które przypominają swoim wyglądem i zachowaniem wątki w innych systemach operacyjnych. Dis Do uruchamiania programów napisanych w języku Limbo Inferno używa maszyny wirtualnej Dis. Podczas gdy większość języków programowania tego typu, domyślnie używa stosowych maszyn wirtualnych, Dis jest maszyną rejestrową. Twórcy tłumaczą to nieznacznie wyższą wydajnością oraz łatwością przystosowania maszyny do działania na innej platformie sprzętowej. Uważają, także że maszyna wirtualna powinna jak najbardziej przypominać architektury na których pracuje. Kod może być przez Dis kompilowany just-in-time lub interpretowany przez odpowiednią bibliotekę. Niezależnie od tego jest on umieszczony w osobnym obszarze pamięci do którego nie można uzyskać dostępu żadną z instrukcji oferowanych przez Dis. Dane są podzielone na globalne, wspólne dla całego kodu zawartego w danym module oraz lokalne dla danej funkcji, umieszczone na stosie. Dostęp do nich uzyskuje się korzystając z adresów bazowych zawartych odpowiednio w rejestrach mp (module pointer) i fp (frame pointer). Można także podawać bezpośrednie adresy w przestrzeni danych programu, nie korzystając z tych rejestrów. Dis oferuje zestaw instrukcji podobny do procesorów CISC. Różni się on głównie o wiele wyższym poziomem abstrakcji. Oprócz podstawowych instrukcji takich jak jmp czy mov oferowany jest także zestaw instrukcji wspomagający operacje na tablicach, alokację pamięci, czy ładowanie modułów. Format plików Dis obsługuje własny format plików wykonywalnych, stworzony specjalnie po to aby dostosować się do jego szczególnych właściwości. Każdy taki plik wykonywany przez maszynę wirtualną składa się z sześciu części: nagłówek - zawiera sygnaturę pozwalającą rozpoznać format pliku, a także sprawdzić czy jest podpisany (i ewentualnie zawiera także podpis). Z tej sekcji Dis odczytuje wszystkie wymagania programu odnośnie środowiska w jakim będzie uruchomiony. Możliwe opcje to np. wymuszenie kompilacji JIT lub interpretacji kodu. Inne informacje przechowywane w nagłówku to rozmiary pozostałych sekcji oraz punkt wejścia programu. kod - jest to sekcja zawierająca ciąg instrukcji maszyny wirtualnej. Każda instrukcja składa się z opcode, sposobu adresowania i trzech argumentów. sekcja typów - umieszczone są w niej deskryptory umożliwiające lokalizację wszelkich wskaźników i referencji w każdym obiekcie. Każdy deskryptor zawiera mapę bitową w której każdy bit reprezentuje jedno słowo. Jeżeli bit jest ustawiony oznacza to, że dane słowo jest wskaźnikiem na inny obiekt. dane - ta sekcja zawiera dane dostępne później przy użyciu rejestru mp. Każdy wpis w tej sekcji opisuje rodzaj danych, ich położenie, typ i ewentualnie ilość obiektów. nazwa modułu sekcja linków - jest to sekcja używana do dynamicznej konsolidacji modułów. Zawiera informacje o wszystkich eksportowanych funkcjach: nazwę, wskaźnik oraz informację o typie argumentów. Odśmiecanie Przechowywane informacje o typach pozwalają na realizację systemu odśmiecania pamięci. W celu polepszenia wydajności składa się on z dwóch mechanizmów. Pierwszy z nich to zwykłe zliczanie referencji - proste i stosunkowo szybkie. Nie nadaje się jednak do usuwania obiektów wzajemnie do siebie odwołujących się. Z tego powodu jest także stosowany algorytm Very Concurrent Garbage Collection (VCGC). Pozwala on na zrównoleglenie procesu odśmiecania i tym samym wykorzystania faktu, że Inferno jest systemem rozproszonym. Dzięki temu, że odśmiecanie nie przerywa działania głównego programu możliwe jest zbudowanie systemu czasu rzeczywistego. Sam algorytm VCGC jest tematem na osobny artykuł. Dis umożliwia wykorzystywanie zliczania referencji, VCGC lub hybrydy obu tych rozwiązań. Podsumowanie Inferno i Plan 9 mają za zadanie rozwinąć technologie mogące zastąpić Uniksa. Pod pewnymi względami kontynuują przyjęte w nim założenia ("wszystko jest plikiem"), lecz z drugiej strony maszyna wirtualna jest odmienną technologią wykorzystywaną w wielu nowoczesnych językach programowania. Są to systemy niewątpliwie bardzo ciekawe i warto im się bliżej przyjrzeć. Tue, 24 Mar 2009 21:52:32 +0100http://pdziepak.quarnos.org/2009/03/24/inferno-plan-9-i-maszyny-wirtualne/ProgramowanieSystemy operacyjneSystemy rozproszoneTechbloginfernoplan 9styxdismaszyna wirtualnabell labslimbogarbage collectorodśmiecanieplikiunixhttp://pdziepak.quarnos.org/2009/03/17/programowanie-aspektowe/Jednym z niepożądanych zjawisk dość często pojawiających się przy tworzeniu aplikacji w oparciu o programowanie zorientowane obiektowo jest nadmierny rozrost metod. Najczęściej muszą one wykonać szereg dodatkowych operacji (sprawdzenie uprawnień, poprawności danych, logowanie czynności, itp.) zanim przystąpią do wykonywania głównego zadania. Często można sobie z tym poradzić uwzględniając takie ewentualności w projekcie aplikacji, zwykle nie jest to jednak idealne rozwiązanie. W tym celu powstała idea programowania zorientowanego aspektowo, które jest przystosowane właśnie do radzenia sobie z tego typu problemami. Podstawowe założenia Programowanie zorientowane aspektowo w żadnej swojej formie nie wyklucza programowania obiektowego. Właściwie to jest jego uzupełnieniem dostarczającym dodatkowe elementy pozwalające inaczej spojrzeć na projekt aplikacji. Aspektowe języki programowania pozwalają na wskazanie miejsc w kodzie obiektowym w których mają zostać wykonane dodatkowe operacje. Istnieje wiele implementacji tego, lecz zdecydowanie najbardziej popularny jest AspectJ stworzony dla Javy. Wprowadza on następujące elementy: pointcut - ogólny opis miejsca przecięcia kodu w którym mają zostać wykonane operacje definiowane przez aspekt. W większości sytuacji jest to wywołanie lub wykonanie kodu funkcji składowej, ale możliwe jest także zdefiniowanie pointcuta przy każdej operacji wykonanej przez metody w danej klasie. Pointcuty mogą także dotyczyć każdego dostępu do pola lub tworzeniu obiektu. joinpoint - konkretne miejsce przecięcia kodu w którym zostaną wstawione dodatkowe operacje definiowane przez dany aspekt. advice - definiuję operację jaka ma zostać wykonana w joinpointach. Kod opisany w advices jest najczęściej wstawiany przed lub po wywołaniu metody w klasie, ale także w przypadku rzucenia wyjątku lub oryginalna funkcja składowa zostaje całkowicie przez niego zastąpiona. W przypadku AspectJ a także wielu innych języków aspekt jest traktowany jak klasa. Oprócz wyżej opisanych elementów może zawierać funkcje składowe lub pola. Mogą być tworzone ich instancje, ale najczęściej aspekt jest singletonem. Dodatkowo można utworzyć hierarchię aspektów korzystając z dziedziczenia. Wiele implementacji pozwala także na istnienie abstrakcyjnych aspektów oraz wirtualnych pointcutów. Realizacja W przypadku Javy i AspectJ aspekty są realizowane w czasie kompilacji z niewielkim wsparciem refleksyjności dzięki czemu nie wpływają w dużym stopniu na wydajność. W przypadku AspectC++ w związku brakiem wsparcia dynamicznego metaprogramowania ze strony C++ kod aspektowy (napisany w AspectC++) jest najpierw tłumaczony do kodu obiektowego (C++) i dopiero wtedy kompilowany. Bibliotek wprowadzająca aspekty w C# LOOM.NET wykonuje wszystkie operacje z tym związane podczas działania programu, podobnie rzecz się ma w przypadku modułu Perla Aspect. Generalnie sposób realizacji jest inny dla różnych bibliotek i także powinien być świadomym wyborem ponieważ, może w dość dużym stopniu wpłynąć na wydajność programu. Zastosowanie Najbardziej oczywistymi zastosowaniami programowania aspektowego to wszelkiej maści loggery i narzędzia diagnostyczne. Można także użyć ich do kontrolowania zgodności otrzymanych danych z kontraktami, ale należy pamiętać, że wiele zalet aspektów jest zauważalna dopiero wtedy gdy odnoszą się do tych samych operacji wykonywanych w wielu metodach. Przykładem może być realizacja wzorca Obserwator, gdzie każda zmiana stanu obiektu obserwowanego wymaga poinformowania o niej obiekty obserwujące. W tym przypadku najlepszym rozwiązaniem jest wstawienie po wywołaniu każdej metody (nie oznaczonej jako const) klasy obiektu obserwowanego wywołania metody uaktualniającej obiekty obserwujące. Przykład Warto przedstawić prosty przykład użycia aspektów w realizacji wzorca Obserwator. Zwykłe podejście wymagałoby czegoś podobnego do kodu poniżej: {geshi lang="java"} class Obserwowany { // ... public void metoda1(int wartość) { // ... operacje ... uaktualnijObserwatorów(); } public void metoda2(string tekst) { // ... operacje ... uaktualnijObserwatorów(); } } {/geshi}W przypadku AspectJ kod realizujący te same funkcje mógłby wyglądać następująco: {geshi lang="java"} class Obserwowany { // ... public void metoda1(int wartość) { // ... operacje ... } public void metoda2(string tekst) { // ... operacje ... } } aspect WzorzecObserwator { pointcut operacja() : execution(public * Obserwowany.*(..)); after() : operacja() { uaktualnijObserwatorów(); } } {/geshi}Ten przykład bardzo dobrze prezentuje główne założenie aspektów. Jest nim pozbycie się często powtarzanego kodu niezwiązanego z głównym przeznaczeniem metody z jej kodu. Taka izolacja ma na celu sprawienie kodu bardziej przejrzystym i ułatwienie wprowadzenia ewentualnych zmian. Problemy Głównym problemem związanym z programowaniem aspektowym jest fakt, że sam pomysł jest stosunkowo młody i w związku z tym wsparcie jest wciąż niewielkie. O ile ze znalezieniem odpowiednich narzędzi nie powinno być problemów to kwestia przyzwyczajenia programistów i to, że języki modelowania takie jak UML nie zostały stworzone z myślą o aspektach sprawiają, że wciąż nie zyskało dużej popularności. Podsumowanie Programowanie aspektowe, mimo że z niskopoziomowego punktu widzenia nie zmienia praktycznie niczego, to bez wątpienia jest w stanie wprowadzić pewne uporządkowanie w miejscu gdzie typowe programowanie obiektowe pozostawiło dużą swobodę. Rozwiązanie ciekawe, ale jest tylko jednym z wielu sposobów na ominięcie pewnych problemów co sprawia, że nie odnosi, jak na razie, spektakularnych sukcesów. Tue, 17 Mar 2009 20:53:43 +0100http://pdziepak.quarnos.org/2009/03/17/programowanie-aspektowe/ProgramowanieTechblogprogramowanie aspektoweaspektpointcutjoinpointadviceweaveraspectjaspectc++programowanie obiektoweobiektklasaobserwatorhttp://pdziepak.quarnos.org/2009/03/10/choices/Jedną z cech systemów operacyjnych na którą zwykle kładzie się duży nacisk jest ich niezawodność i stabilność. W tym celu starano się rozwijać mikrojądra, które dzięki większej izolacji poszczególnych elementów systemu zmniejszają podatność na błędy. Także wykorzystanie bezpiecznych języków (jak np. w Singularity) jest pewnym krokiem w kierunku zwiększenia niezawodności systemów. Innym projektem wykorzystującym pewne ciekawe mechanizmy jest eksperymentalny system operacyjny Choices rozwijany na Uniwersytecie Illinois w Urbana-Champaign. Ogólna budowa Choices jest napisanym w C++ systemem operacyjnym zorientowanym obiektowo. Jako całość jest tworzony z wielu odrębnych obiektów współpracujących ze sobą. Składa się z frameworków definiujących poszczególne aspekty jego działalności. Dziedziczenie jest wykorzystywane do łatwego przenoszenia systemu na inne platformy i do stosowania zależnych od sprzętu optymalizacji. Choices wspiera SPARC, x86 oraz ARM, a także istnieje możliwość jego uruchomienia w trybie użytkownika na Solarisie i Linuksie. Wyjątki procesora Chocies korzysta z dobrodziejstw języków programowania wysokiego poziomu także w przypadku wyjątków procesora. Każde przerwanie jest obsługiwane przez InterruptManagera. Przekazuje on stosowne informacje do odpowiednich elementów systemu operacyjnego, lub jeżeli przerwanie jest wyjątkiem procesora zgłasza błąd. InterruptManager rzuca wtedy wyjątek C++ (model jego obsługi nie ma znaczenia), w taki sposób, aby stos wskazywał, że został on rzucony z miejsca w którym wystąpił wyjątek procesora. Dzięki temu kod obsługi wyjątków może zlokalizować błędną operację i wykonać odpowiednie czynności. Odzyskiwanie po awarii Choices wspiera mechanizmy odzyskiwania stanu programu (bądź jądra) w przypadku ewentualnych błędów spowodowanych wadliwym kodem lub nieprawidłowym funkcjonowaniem sprzętu. przeładowanie kodu - jest to mechanizm uaktywniający się, gdy procesor zasygnalizuje próbę wykonania nieprawidłowej operacji, które są najczęściej oznaką błędu sprzętowego związanego z pamięcią operacyjną. W tej sytuacji wadliwa instrukcja jest ponownie ładowana z innego źródła danych (np. obrazu jądra trzymanego w pamięci flash). Dodatkowo, możliwe są okresowe kontrole poprawności kodu opierające się na zgodności sum kontrolnych. Ten mechanizm może być zastosowany jedynie do kodu, który nie jest generowany run-time. mikrorestart jest wykonywany najczęściej gdy błąd wystąpi podczas wykonywania funkcji dostarczanej przez komponent. Polega na ponownym załadowaniu, przygotowaniu do działania i kolejnej próbie wywołania funkcji. W odróżnieniu od poprzedniego mechanizmu, mikrorestart skupia się głównie na próbie odzyskania uszkodzonych struktur danych, gdzie pomocne są także opisane w dalszej części artykułu Server State Regions. automatyczny restart usługi - dotyczy głównie serwerów działających jako procesy w trybie użytkownika. Polega właściwie na tym samym co mikrorestart, z tym, że także próbuje radzić sobie z ewentualnymi problemami wynikającymi z utrzymywanych przez proces blokad oraz dostępu do pamięci współdzielonej. W celu umożliwienia skutecznego restartu usługi, Choices monitoruje wszystkie blokady utrzymywane przez procesy. W sytuacji gdy proces ulegnie awarii, blokady są zwalniane, tak aby nie powodowały problemów po wznowieniu działania programu. transakcje - jest to sposób radzenia sobie z ewentualnymi błędami szeroko wykorzystywany w bazach danych. Transakcje polegają na zachowaniu kopii danych, tak aby można było całkowicie anulować wykonywaną operację, jeżeli którykolwiek z jej elementów się nie powiedzie. Innymi słowy, w przypadku napotkania błędu, dane pozostają niezmienione. Dzięki temu ewentualne błędy, nie mogą naruszyć integralności danych. Kontrolowane restarty Innym istotnym mechanizmem, co prawda jeszcze niezaimplementowanym, są policy-driven restarts. Dają programistom możliwość dokładnego opisania sposobu ponownego uruchamiania programu, tak aby dostosować go do konkretnych potrzeb. Możliwe jest także zdefiniowanie pewnych operacji jako reakcję na określony błąd zastępującą zwykły restart programu. Server State Regions Część mikrojąder jest zaprojektowana w taki sposób, że każdy serwer przetrzymuje wszystkie potrzebne mu dane na temat każdego z klientów. Jest to rozwiązanie proste i wygodne zarówno dla jądra jak i poszczególnych serwerów działających w przestrzeni użytkownika. Sprawia to jednak, że działanie programu jest uzależnione od przypisanych mu danych obecnych w usługach z których korzysta. W rezultacie, mimo izolacji poszczególnych komponentów, błąd w kodzie serwera wciąż może doprowadzić do błędu aplikacji z niego korzystających. Rozwiązanie tego problemu, jakie zastosowano w Choices polega na przeniesieniu wszystkich danych aplikacji poza przestrzeń adresową serwera. Tworzy się w ten sposób tak zwane Server State Regions, obszary pamięci przechowujące wymagane przez konkretną usługę dane na temat aplikacji. SSR pomimo że są tworzone z pamięci dostępnej klientom, są dla nich ze względów bezpieczeństwa niedostępne. Dzięki temu, serwer może bezpiecznie umieścić w nich wszystkie informacje jakie dotyczą konkretnych aplikacji. Gdy aplikacja po raz pierwszy skorzysta z usług oferowanych przez dany serwer, zostanie utworzony dla niej osobny SSR. Następnie przy każdym wywołaniu funkcji serwera odpowiedni SSR jest tymczasowo mapowany do jego przestrzeni adresowej1. Po wykonaniu wszystkich potrzebnych operacji i powrocie do kodu aplikacji serwer ponownie traci dostęp do SSR. W przypadku awarii serwera zostaje on automatycznie uruchomiony ponownie. Dzięki SSR błąd serwera może naruszyć poprawność danych co najwyżej jednej aplikacji, podczas gdy wszystkie pozostałe nie odczują żadnych skutków awarii. Dodatkowo po restarcie serwer może uzyskać informacje na temat swojego poprzedniego stanu i spróbować naprawić ewentualne błędy w przetwarzanym SSR. Zastosowanie SSR ma także szereg dodatkowych zaleta. Wykorzystywanie pamięci aplikacji do tworzenia SSR znacząco ogranicza możliwe sposoby przeprowadzenia ataku DoS na serwer. SSR są także niezależne od klienta, dzięki czemu mogą zostać wykorzystane do odzyskania dawnego stanu aplikacji przed jej ewentualną awarią. Oczywiście wymaga to dodatkowego wsparcia ze strony klienta i nie jest wspierane przez jądro w takim stopniu jak odzyskiwanie serwera, ale pozwala np. na niezerwanie połączeń TCP w przypadku błędu klienta. 1 Warto zaznaczyć, że nie wpływa to w znaczący sposób na wydajność, ponieważ każde wywołanie funkcji udostępnianych przez serwer i tak powoduje unieważnienie TLB. Podsumowanie Choices nie jest projektem przeznaczonym do użytku. Należy na niego patrzeć jak na system edukacyjny i eksperymentalny, który łączy w sobie wiele różnych mechanizmów zapewniających większą niezawodność. Wiele z tych rozwiązań zostało już zastosowanych w innych mikrojądrach, ale w Choices stara się stworzyć z nich spójny system współpracujących ze sobą elementów. Projekt niestety zdaje się być obecnie martwy, ostatnie aktualizacje jego strony miały miejsce latem 2007 r. Innym problemem jest fakt, że wiele mechanizmów zostało szczegółowo opisanych, ale nie są jeszcze zaimplementowane. Tue, 10 Mar 2009 17:34:35 +0100http://pdziepak.quarnos.org/2009/03/10/choices/Systemy operacyjneTechblogchoicesmikrojądromicrorebootwyjątekserwerserver state regionssrtransakcjemikrorestarthttp://pdziepak.quarnos.org/2009/03/03/singularity/Większość obecnych systemów operacyjnych w mniejszym lub większym stopniu bazuje na dość podobnych założeniach. Nawet jeżeli architektura jądra znacząco się różni (jądra monolityczne, mikrojądra) to i tak wiele pozostałych elementów pozostaje w niewiele zmienionej formie. Istnieją jednak pewne eksperymentalne projekty, mające na celu sprawdzić, jak nowe koncepcje sprawują się w praktyce. Jednym z nich jest rozwijany przez Microsoft Research system operacyjny Singularity. C# i Sing# Projekt jest w przeważającej większości napisany w C#. Według danych Microsoftu 95% kodu mikrojądra jest napisana w tym języku. Pozostałe to assembler x86 oraz C++ wykorzystane przy niskopoziomowej obsłudze pewnych podstawowych elementów systemu, o czym później. W tym miejscu nie można nie wspomnieć o Sing#. Jest to zestaw rozszerzeń do C# wspierający wiele dodatkowych mechanizmów często wykorzystywanych w kodzie Singularity. Dodatkowe elementy zawarte w Sing# to między innymi: kontrakty - pozwalają na zachowanie bezpieczeństwa typologicznego podczas komunikacji międzyprocesowej realizowanej przez kanały (channels). Kontrakty definiują jakie wiadomości mogą być przesyłane, typy oraz wymagania co do wartości ich argumentów oraz kierunek w jakim są wysyłane. Kontrakty pozwalają także na ustalenie oczekiwanych komunikatów na każdym etapie transmisji. endpoints - każdy kontrakt definiuje endpointy przeznaczone dla obu stron komunikacji. Zawierają one wszystkie metody opisane w kontrakcie jako możliwe wiadomości i służa do wygodnego ich odbierania i wysyłania. exchange heap - Sing# pozwala na alokację obiektów w specjalnym miejscu przestrzeni adresowej zwanym stertą wymiany (exchange heap), która jest wykorzystywana przez wszelkie rodzaje komunikacji międzyprocesowej. Dodatkowo wykonywane są wszystkie informacje związane z zachowaniem informacji o właścicielu danego obiektu. konstrukcja switch-receive - razem z endpointami pozwala na wygodne odbieranie wiadomości opierając się na standardowej konstrukcji switch. {geshi lang=csharp}switch receive { case endpoint.Message1() : ... break; case endpoint.Message2() : ... break; }{/geshi}Bezpieczeństwo C# (a także wszystkie rozszerzenia związane z Sing#) jest językiem bezpiecznym pod wieloma względami, na czym bazują główne założenia systemu Singularity. Można rozróżnić dwa obszary w których ograniczona została możliwość występowania błędów: bezpieczeństwo typów zapewnia, że wszystkie operacje wykonywane na obiekcie są zgodne z jego typem bezpieczeństwo pamięci zapewnia, że wszystkie odwołania do pamięci są poprawne. Wiąże się to z zerowymi wskaźnikami, odwołaniom poza rozmiar tablicy lub do nieistniejących obiektów. Bartok Programy pisane w C# lub innych językach związanych z platformą .NET zwykle są tłumaczone do pośredniego (także bezpiecznego) języka MSIL. Zadaniem kompilatora Bartok, będącego jedną z najważniejszych części Singularity jest tłumaczenie MSIL do kodu natywnego, zachowując przy tym bezpieczeństwo kodu. Odpowiednie optymalizacje pozwalają na stworzenie jak najbardziej wydajnego kodu wykorzystującego wszystkie możliwości danego komputera, co chociaż w pewnym stopniu jest w stanie zrekompensować straty wydajności spowodowane procedurami wsparcia runtime. Jednolite procesy Zapewnienie pełnego bezpieczeństwa kodu natywnego wymaga od Singularity wprowadzenie jeszcze dodatkowych ograniczeń w stosunku do procesów (a także i jądra): Kod programu nie może zostać zmodyfikowany w trakcie jego działania. Wyklucza to kompilację just-in-time (obecną np. na platformie .NET), a wszystkie dynamicznie konsolidowane biblioteki muszą zostać załadowane przed rozpoczęciem pracy programu. Żaden obiekt nie może należeć do więcej niż jednego procesu w tym samym czasie. To ograniczenie ułatwia synchronizację między procesami upraszczając sposób komunikacji między nimi. Wymaga to między innymi udziału systemu operacyjnego w większości operacji mogących stanowić zagrożenie i tym samym wymusza użycie mechanizmów typu wspomniane wcześniej kontrakty. Istotne jest, że jądro także podlega tym ograniczeniom. Dzięki tym ograniczeniom możliwe jest także zastosowanie refleksyjności czasu kompilacji (Compile Time Reflection). Żaden element kodu nie może zostać zmieniony w trakcie działania programu, dlatego też refleksyjność realizowana podczas kompilacji (czyli de facto w ostatnim momencie w którym kod może się zmienić) jest w zupełności wystarczająca. Ochrona pamięci Najczęstszym obecnie stosowanym mechanizmem mającym za zadanie ochronę przestrzeni adresowej poszczególnych procesów jest stronicowanie. Jako element realizowany sprzętowo HIP wiąże się z pewnymi spadkami wydajności, szczególnie w przypadku komunikacji międzyprocesowej, która wymaga operacjach na katalogu/tablicy stron skutkujących unieważnieniem TLB. Także wywłaszczenie procesu w większości sytuacji unieważnia przynajmniej część wpisów w TLB. Przez bardzo długi czas była to jedna z ważniejszych przyczyn małej popularności mikrojąder. Każdy program (a także i kernel) w Singularity jest napisany w bezpiecznym języku programowania. Nie może on samodzielnie utworzyć lub unieważnić referencji do obiektów w pamięci a także wykonać żadnych innych operacji, które mogłyby zagrozić bezpieczeństwu systemu. Jedynie alokacja pamięci oraz garbage collector nie spełniają tej zasady, ale są to mechanizmy dostarczane przez system operacyjny i tym samym w pełni zaufane. Skoro sam język programowania ogranicza programistę do podobnego stopnia jak HIP, sprzętowa ochrona pamięci staje się niepotrzebna. Jej rolę pełnią wszystkie funkcje kontrolne wsparcia runtime, które tym samym tworzą SIP. Wiąże się z tym także założenie, że każdy obiekt może należeć tylko do jednej przestrzeni adresowej. Z tego powodu pamięć współdzielona, a także wszelkie inne sposoby komunikacji międzyprocesowej inne niż kanały (channels) są niedozwolone. Komunikacja międzyprocesowa Komunikacja międzyprocesowa w Singularity opiera się na kanałach (channels). Wykorzystują one dodatkowe elementy Sing# opisane wcześniej: kontrakty i endpointy. Dzięki nim utrzymane jest bezpieczeństwo operacji związanych w komunikacją. Cała komunikacja odbywa się przy pomocy endpointów które dostarczają odpowiedni interfejs dla obu uczestników transmisji. Dane przekazywane są przy użyciu sterty wymiany (exchange heap). W tym miejscu nie funkcjonuje garbage collector, zamiast niego wykorzystywane są liczniki referencji. Jest to obszar pamięci do którego ma dostęp każdy proces, ale zgodnie z zasadami dotyczącymi bezpieczeństwa każdy obiekt przez cały czas ma przyporządkowanego mu właściciela. Przekazanie obiektu odbywa się przez dostarczenie endpointowi odbiorcy wskaźnika na przesyłany obiekt (wewnątrz sterty wymiany). Sterta wymiany ma też ograniczenia co do obiektów znajdujących się w niej. Przede wszystkim muszą być one wymiennego typu czyli nie mogą zawierać żadnych referencji do innych, nieprzesyłanych obiektów. Podsumowanie Singularity jest bez wątpienia bardzo ciekawym, ale też i bardzo rozbudowanym projektem. Ten artykuł opisuje jedynie najbardziej istotne cechy tego systemu, sprawiające, że wyróżnia się on na tle obecnie często stosowanych systemów. Jest to projekt eksperymentalny w którym nie wszystkie rzeczy są jeszcze w pełni ukończone, ale mimo to już zawiera wiele interesujących rozwiązań. Najprawdopodobniej, w najbliższym czasie pojawi się kolejny artykuł opisujący mniej popularne ale wciąż bardzo istotne elementy systemu Singularity. Być może także pokuszę się o dokładniejsze opisanie któregoś z mechanizmów, bo projekty eksperymentalne zawsze warte są szczególnej uwagi. Tue, 03 Mar 2009 21:57:57 +0100http://pdziepak.quarnos.org/2009/03/03/singularity/Systemy operacyjneTechblogsingularitysingcmikrojądrosipmicrosoftcontractendpointsafemsilbartokhttp://pdziepak.quarnos.org/2009/02/24/obiekty-klasy-i-metody-w-objective-c/Programowanie zorientowane obiektowo w czystym C, mimo że możliwe, rzadko kiedy jest proste i przyjemne, a powstały kod jest zwykle bardzo zagmatwany. Dlatego też na bazie C powstały kompatybilne z nim języki dodające wygodne w użyciu wsparcie dla kodu zorientowanego obiektowo. Pierwszy z nich to niezwykle popularny C++, w którym większość tych rozszerzeń to różnego rodzaju dodatkowe operacje wykonywane podczas kompilacji. Drugi to niszowy Objective-C, który (oprócz składni) od C++ różni się tym, że dodatkowe elementy jakie zostały do niego wprowadzone są odpowiednimi operacjami wykonywanymi podczas działania programu. Dzięki temu udaje się uzyskać w języku kompilowanym do kodu natywnego część udogodnień znanych z technologii takich jak .NET czy Java. Klasy W języku Objective-C każda klasa jest także obiektem zawierające podstawowe informacje wymagane przez pozostałe funkcje wsparcia runtime. Najważniejsze z danych przechowywanych przez obiekty opisujące klasy to: nazwa klasy rozmiar instancji klasy (z uwzględnieniem klas bazowych) lista zmiennych składowych klasy lista funkcji składowych klasy wskaźnik na klasę bazową lista klas pochodnych realizowane protokoły Traktowanie klasy jako obiektu (inspirowane Smalltalkiem) pozwala znacząco poszerzyć możliwości języka szczególnie jeżeli chodzi o refleksyjność. Struktury opisujące klasy najczęściej są przechowywane w wewnętrznych danych runtime. Odpowiednie informacje są wydobywane przy okazji tworzenia instancji danej klasy, a następnie wiązane nowym obiektem. Dlatego też poniższy kod: {geshi lang="objc"}array = [NSArray new]{/geshi}zostanie w większości implementacji, już przez kompilator zamieniony na konstrukcję podobną do tej: {geshi lang="objc"}array = [(objc_get_class("NSArray")) new]{/geshi}Funkcja objc_get_class przegląda listę wszystkich klas w poszukiwaniu żądanej i w przypadku jej odnalezienia zwraca wskaźnik do niej. Cała operacja ma miejsce już podczas działania programu, dlatego też istotna jest szybkość działania takich podstawowych operacji. Jednym ze sposobów na przyśpieszenie kodu jest cachowanie wskaźników na obiekty opisujące klasy. W rezultacie funkcja objc_get_class jest wykonywana jeden raz dla każdej klasy, a w każdym kolejnym przypadku używany jest zwrócony przez nią wskaźnik. Obiekty Wszystkie klasy w Objective-C dziedziczą po NSObject. Jest to klasa która realizuje większość operacji pozwalających na korzystanie przez programistę z informacji jakie są przechowywane o każdej klasie. Oferowana funkcjonalność to między innymi: sprawdzenie czy klasa odpowiada na selektor sprawdzenie czy klasa realizuje protokół podanie funkcji odpowiadającej na selektor wykonanie podanego selektora podanie nazwy klasy Selektory Selektory identyfikują wysyłaną do obiektu wiadomość, czyli innymi słowy, nazywają funkcję składową która powinna zostać wywołana. W większości jest to po prostu ciąg znaków odpowiadających nazwie funkcji, chociaż w niektórych implementacjach zawiera także unikalny numer identyfikacyjny. W celu usprawnienia operacji tłumaczenia ciągu znaków na selektor i odwrotnie istnieją odpowiednie tablice przechowujące listy wszystkich zarejestrowanych danych. Jako że mimo tego, może to być kosztowna operacja, umożliwiane jest (wręcz zalecane) tłumaczenie nazw do selektorów podczas kompilacji. Wywołanie funkcji składowych Wywołanie funkcji składowych, a właściwie zgodnie z nomenklaturą Objective C: wysyłanie wiadomości obiektom jest przeprowadzany w całkowicie dynamiczny sposób. Warto także zaznaczyć, że ponieważ klasy także są traktowane jako obiekty, statyczne funkcje składowe wywoływane są w taki sam sposób. Oto przykładowy kod wysyłania komunikatu do obiektu: {geshi lang="objc"}[obiekt metoda]{/geshi}zostaje zamieniony na: {geshi lang="objc"}objc_msgSend(obiekt, @selector(metoda)){/geshi}Funkcja objc_msgSend, na podstawie informacji zawartych w opisie klasy której instancją jest object, wywołuje odpowiednią metodę. Każda klasa zawiera listę selektorów oraz przypisanych im adresów funkcji. Procedura przekazująca wiadomość przeszukuje tę listę (z uwzględnieniem klas bazowych) w poszukiwaniu adresu odpowiedniej metody, która następnie zostaje wywołana. Często, w celu przyśpieszenia tej bardzo częstej operacji, wykorzystywane są tak zwane dispatch tables. Właściwie pod każdym względem przypominają one tablice funkcji wirtualnych wykorzystywane np. w C++. Każda taka tablica zawiera jedynie adresy kolejnych funkcji składowych klasy. W tej implementacji unikalny numer identyfikacyjny selektora służy także jako indeks wskazujący na odpowiedni adres w tej tablicy. Najważniejszą różnicą między dispatch table a tablicami funkcji wirtualnych jest fakt, że dispatch tables najczęściej są tworzone już podczas działania programu na podstawie listy funkcji składowych zawartej w obiekcie opisującym klasę. Pozostałe dane dotyczące klasy Często zdarza się, że wpisy z adresami funkcji składowych i odpowiadającymi im selektorami zawierają także informację o przyjmowanych przez metodę argumentach. Jest to przydatne przy debuggingu. Podobnie rzecz się ma z wpisami dotyczącymi zmiennych składowych. Obiekt opisujący klasę przechowuję listę struktur zawierających nazwę każdej takiej zmiennej, jej typ (dla ułatwienie debuggingu) i przesunięcie w stosunku do bazowego adresu instancji. Podsumowanie Objective-C prezentuje inne podejście co do sposobu implementacji rozszerzeń związanych z OOP w C niż C++. Opiera się bardziej na wykonywaniu operacji podczas działania programu, co zmniejsza jego wydajność, ale z drugiej strony oferuje szereg dodatkowych możliwości. Niech za przykład posłużą tutaj choćby systemy rozproszone. W Objective-C przy odrobinie wysiłku ze strony osoby implementującej taki system, można tworzyć obiekty rozproszone w banalnie prosty sposób. Możliwe jest to właśnie dzięki dużej ilości informacji które zostają w kodzie po kompilacji, oraz wielu możliwościach wstawienia dodatkowego kodu podczas działania programu. Oczywiście takie rozwiązania są też możliwe w C++ czy innych językach, ale nie zawsze jest to aż takie proste. Główną wadą Objective-C jest jego niewielka popularność. Przed śmiercią chroni go właściwie jedynie OpenStep. Warto jednak zwrócić uwagę na jego możliwości, ponieważ jest on gdzieś pomiędzy innymi językami kompilowanymi do kodu natywnego a kompilowanymi do kodu pośredniego. Z jednej strony wsparcie runtime jest bardzo rozbudowane, ale wciąż istnieje możliwość uzyskania maksymalnej możliwej wydajności w krytycznych miejscach, przez ograniczenie używania niektórych z jego funkcji. Tue, 24 Feb 2009 22:18:12 +0100http://pdziepak.quarnos.org/2009/02/24/obiekty-klasy-i-metody-w-objective-c/Objective-CProgramowanieTechblogobjective-cdispatch tablevirtualvtabledtableselectorselektorSELklasaobiektinstancjaruntimecocoaopenstep