1 Kategorie systemów czasu rzeczywistego

2 Podstawowe definicje

3 Podstawowe definicje

4 Standard IEEE / ANSI

5 System Czasu RzeczywistegoSensory Sterowniki Otoczenie KOMPUTER

6 Kategorie SCR

7 Kategorie SCR

8 Kategorie SCR

9 Cechy SCR

10 Problematyka SCR

11 JEDNOSTKA PLANUJĄCO - STERUJĄCAStrategia PUSH JEDNOSTKA PLANUJĄCO - STERUJĄCA M M M M Materiały Sterowanie Informacje

12 Strategia PUSH

13 JEDNOSTKA PLANUJĄCO - STERUJĄCAStrategia SQUEEZE JEDNOSTKA PLANUJĄCO - STERUJĄCA M B Materiały Sterowanie Informacje

14 Strategia SQUEEZE

15 JEDNOSTKA PLANUJĄCO - STERUJĄCAStrategia PULL JEDNOSTKA PLANUJĄCO - STERUJĄCA M Materiały Sterowanie Ssanie

16 Systemy JIT

17 Notacja (trójpolowa) 

18  = 1 2

19  = 1, 2, 3, 4, 5

20 Dodatkowe zasoby (discretely-additional resources)

21

22 Wymagania kolejnościowe zadań.in–tree out–tree

23 Parametry zadania

24 Parametry zadania

25 Kryteria optymalizacji

26 Kryteria optymalizacji

27 Zależności między kryteriami wi Ti Lmax  wi Ci  Ti  Ci Cmax Kryteria 1, 2 są w relacji 1  2 jeśli rozwiązanie problemu z kryterium 2 dostarcza rozwiązania problemu z kryterium 1.

28 System permutacyjny (PF, Permutation Fow-shop)1 2 m Przepływ zadań Stanowisko obsługi Maszyna

29 System (F, Flow-shop) Przepływ zadań Stanowisko obsługi Maszyna 1 2 m

30 System gniazdowy (J, Job-shop)Przepływ zadań Stanowisko obsługi Maszyna 1 2 m

31 System równoległy (P, Parallel-shop)Przepływ zadań Stanowisko obsługi Maszyny

32 System gniazdowy równoległyPrzepływ zadań Stanowisko obsługi Maszyny

33 Typy zagadnień szeregowania

34 Algorytm Johnsona O(nlogn)Cmax(*) = m i n Cmax() * 

35 Problem PF3|P2, no-bottl.|Cmax

36 Algorytm Johnson O(nlogn)

37 Zadania podzielne. Procesory równoległe

38 Zadania podzielne. Procesory równoległe2 6 4 P1 P2 Z4 Z3 P3 Z2 Z1 Z5

39 Zadania podzielne. Procesory równoległe2 6 4 P1 P2 Z5 Z3 Z2 Z1 Z4 Z6 8 10

40 Zadania zależne. Procesory równoległe

41 Algorytm Hu, Przykład 1 2 3 4 Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8 Z10 Z11 Z9 2 6 4P1 P2 Z2 Z1 Z4 Z3 Z6 Z8 Z5 Z7 Z9 Z10 Z11

42 Zadania niezależne, procesory równoległeLPT P1 P2 P3 RPT

43 Reguła EDD (Earliest Due Date)Z2 Z1 d1 d2 Z1 Z2 d1

44 Zadania niezależne, przerywalne.

45 Zadania zależne, przerywalne.

46 Zadania zależne, procesory równoległe.

47 Przykład P| pj=1, in–tree | Lmax0*, 4 0*, 2 0*, 2 Z1 Z2 Z3 -1*, 2 -1*, 3 Z4 Z5 Z6 -1*, 4 -2*, 3 Z7 Z8 -4*, 5 2 4 P2 P3 Z3 Z2 Z6 Z5 Z7 Z9 Z1 P1 Z4 Z8 L*max= 0 Z10 Z9 -5*, 6 dj*, dj -6*, 7 Z10

48 Zadania niepodzielne, dodatkowe zasoby

49 Przykład Ppodz, res11CmaxZj Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8 R(Zj) 1 rj 4 2 3 5 7 2 4 P2 Z4 Z5 Z1 P1 Z7 6 8 10 Z6 Z8 Z3 Z2 P3

50 Cykliczny algorytm FIFO

51 Struktura kolejki w algorytmie cyklicznym1 2 3 4 6 5 7 Kierunek obsługi

52 Cykliczny algorytm LIFO (Last in First Out)Kolejka Stanowisko obsługi Zadania przerwane Zadania zakończone

53 Cykliczny algorytm SS (Selfish Scheduling)

54 System obsługi wg. algorytmu SSKolejka System kolejek Stanowisko obsługi Zadania wykonane Podstawowy algorytm szeregowania Nowe zadania Zadania oczekujące Zadania wykonywane

55 Szeregowanie zadań cyklicznych:

56

57 Binaryzacja okresów zadań

58 Binaryzacja niezdominowanaT1 T2 T3 T4 T5 1 7 8 14 15 21 22 28 Uszeregowanie dopuszczalne dla binaryzacji B1: [7: 1, 4]

59 Binaryzacje niezdominowane

60

61 Komunikacja między zadaniami

62 Kolejki komunikatów Kolejka zadań odbierających wysyłającychBlok kontrolny kolejki Długość kolejki Rozmiar wiadomości Element

63 Jednokierunkowa komunikacjaKolejki komunikatów Kopia I Kopia II Bufor zadania wysyłającego Bufor zadania odbierającego Jednokierunkowa komunikacja

64 Semafor

65 Rejestry zdarzeń. Flagi zdarzeń.OR /AND 1 ZAD1 ZAD2 Ustawienie flag zdarzeń ZAD3 Użycie rejestru i flag zdarzeń

66 Potoki ZAD. CZYTAJĄCE PISZĄCE DANE POTOK Deskryptor

67 Zakleszczenie (deadlock)KOLEJKA (pusta) ZADANIE 2 (czeka na semafor) SEMAFOR ZADANIE 1 (czeka na dane, posiada semafor)

68 Przeterminowanie (starvation)KOLEJKA ZADANIE 2 SEMAFOR ZADANIE 1 ZADANIE 3

69 Inwersja priorytetów (priority inversion)ZAD1 ZAD2 NISKI WYSOKI Priorytet t1 t2 t3 t4 t5 Inwersja priorytetów

70 Inwersja priorytetów Inwersja priorytetów Priorytet Nieznany czasWYSOKI NISKI t3 t4 t5 t6 t1 t2 t7

71 Usługi jądra systemu czasu rzeczywistego

72 Jądro z wywłaszczaniemZADANIE A 1 7 3 5 2 IRS 4 ZADANIE B 6 Czas wykonanie

73 Stany zadania

74 ZADANIE 1 Stos STATUS Wskaźnik stosu Priorytet TCB . . . Kontekst Pamięć CPU Rejestry CPU ZADANIE n

75 Przełączanie kontekstu

76 Cechy systemu VxWorks

77 Stany zadania VxWorks WYKONYWANE GOTOWE OCZEKUJĄCE WSTRZYMANEZAWIESZONE

78 Mechanizmy Komunikacji między zadaniami

79 Współdzielona pamięć, wzajemne wykluczanieZADANIE 1 ZADANIE 2 ZADANIE 3 Wsp_Dane PAMIĘĆ

80 Semafory VxWorks

81 Inwersja priorytetów Priorytet Zadanie A Zadanie B Zadanie Cw posiadaniu semafora czas wywłaszczenie blokada oddanie semafora pobranie semafora

82 Dziedziczenie priorytetówZadanie A Zadanie B czas w posiadaniu semafora wywłaszczenie blokada pobranie semafora C A B oddanie semafora dziedziczenie priorytetu Zadanie C

83 System RTLinuks

84 Systemy KURT, MERT

85 Cechy systemu RTLinuks

86 Architektura systemu RTLinuxZwykłe procesy Linuksa Funkce systemowe, POSIX Drivery Linux Zadanie czasu rzecz. Zadanie czasu rzecz. RT-Linux Scheduler we/wy Przerwania Sprzęt

87 Zadania RTLinuksa

88 Szeregowanie i komunukacja w RTLinuksie

89 Architektura systemu QNXMIKROJĄDRO Zadania (procesy ) systemowe Zadania (procesy) aplikacyjne Poziom zadań Poziom jądra systemu

90 Zadania (procesy) systemowe QNX

91 Funkcje mikrojądra QNX

92 Struktura mikrojądra QNXZAD ZAD Mechanizmy komunikacji (IC) SCHEDULER Przekierowania przerwania (IR) Interfejs sieciowy (NI) Przerwania Zarządca sieci (NM)

93 Zadania (procesy) systemoweSend Receive Reply G W M Z ZReceive ZSend Diagram przejść między zadaniami

94 Szeregowanie, komunikacja i synchronizacja

95 Implementacja spotkaniaWiadomości Mr M Zadanie T1 Zadanie T2 Send( T2, M, Mr ) Receive(M ) Reply(Mr) Implementacja spotkania

96 Depozyty (Proxy) DEPOZYT Proces Widomość

97 Sygnały

98 Automatyczne przekazanie wiadomości przez połączenieKomunikacja w sieci P VQ Send ( ) ZAD VP Q Receive ( ) Zadania wirtualne Węzeł sieci Automatyczne przekazanie wiadomości przez połączenie

99 QNX Neutrino Ochrona pamięci System plików Obsługa we-wy AplikacjaPodsystem graficzny Mikrojądro NEUTRINO Ochrona pamięci Procedury obsługi urządzeń Procedury obsługi sieci Procedury obsługi grafiki SPRZĘT

100 Zastosowanie

101 Standard POSIX

102 Standard POSIX

103 Sieci Petriego

104 Konwencje graficzne  p1 p2 p3 t2 t1

105

106 Znakowanie sieci.

107 Realizacja przejścia t1   p1 p2 p4 p3 p5 3 2 

108 Własności dynamiczne sieci

109 Czasowe sieci Petriego

110 Interpretacja miejsc i przejść

111 Model automatu obsługującego sprzedaż wait 5 10 15 20

112 Model procesów współbieżnych ParBegin t1 p2 ParEnd p1 p3 p4 t2 t0 t3 p0

113 Model protokołu z potwierdzeniemReceived Receive Sender  Receiver Mess_Buff Ack_Buff Ready Wait for ack Send ack mess

114 Komunikacja za pomocą ograniczonego buforaproducer  consumer p k p’

115 Synchronizowany dostęp do obszaru krytycznego  p0 t1 t3  p2 p4 t2 t4

116 Sieciowy model procesu cyklicznegoCzasowy znakowany graf TMG (Timed Marked Graph): pP  p=1 and  p=1 pkc proces k tk i pkb tk i + 1 Operacja oki(h)  tranzycja tki T Czas wykonania operacji oki(h)   czas palenia tranzycji t = T(t)

117 Sieciowy model procesu cyklicznegoprocess k .. p c s

118 Cykliczne procesy współbieżneprocess 1 process k process n

119 Czas cyklu Niech  będzie sekwencją wzbudzeń={: tiT} gdzie: si(v) - jest chwilą w której tranzycja ti inicjuje v-te palenie. Liczba C() jest czasem cyklu sieci, jeżeli istnieje sekwencja wzbudzeń   ( jest zbiorem możliwych sekwencji wzbudzeń), dla której znakowanie sieci M jest równe znakowaniu początkowemu M0 w chwilach kC(), k=1, 2, ... . C*=C(*)=min  {C()}.