Podstawy informatyki
dr hab. Krzysztof Komęza
prof. PA

Systemy operacyjne
" Unix, Linux
" Windows XP,Vista, 7
" AIX, System 7 (Power PC, Power Stack - Motorola)
" systemy czasu rzeczywistego QNX ( Quantum
" systemy czasu rzeczywistego QNX ( Quantum
Software Systems)
" systemy rozproszone - ANSA ( Architecture
Management Ltd.)
System operacyjny - zadania
" ułatwianie komunikacji użytkownika z
komputerem
" zarządzanie pozostałymi elementami
oprogramowania
oprogramowania
" obsługiwanie zbiorów w pamięci zewnętrznej
" sterowanie urządzeniami zewnętrznymi
" kontrolowanie poprawności sprzętu
" organizowanie pracy wieloprogramowej
( wielozadaniowej ) i wielodostępnej
UNIX"! - historia
" 1969 - Ritchie i Thompson, pierwszy system
UNIX (Laboratoria BELL).
" 1971 - wersja na PDP-11/20; pierwsza
publikacja  Unix Programmer s Manual .
publikacja  Unix Programmer s Manual .
" 1972 - drugie wydanie tej książki, wprowadzenie
definicji potoku Å‚Ä…czÄ…cego procesy, trzecia
wersja systemu.
" 1973 - rezygnacja z asemblera, stworzenie
języka C.
UNIX"! - historia c.d.
" 1974 - artykuł w Communications of the
Association for Computing Machinery uważany
za pierwszÄ… oficjalnÄ… definicjÄ™ systemu.
" 1975 - bezpłatne rozpowszechnienie systemu
" 1975 - bezpłatne rozpowszechnienie systemu
 UNIX Szóstego Wydania w szkołach
wyższych.
" 1979 - bezpłatne rozpowszechnienie systemu
 UNIX Siódmego Wydania w szkołach
wyższych.
" 79/80 - powstaje Berkeley UNIX.
UNIX"! - historia c.d.
" 1978-1983 - powstajÄ… wersje UNIXa dla VAX,
M68000, Z80.
IBM System/34 zostaje wyposażony w AT&T
UNIX"!.
UNIX"!.
" 1984 - pojawia sie IBM UNIX dla komputerów
PC (PC/IX) i dużych maszyn (VM/IX).
" 1983 - Hewlett-Packard przyjmuje HP-UX"!
jako swój główny system operacyjny.
" 1983 - Digital Equipment Co. wprowadza Ultrix
dla VAX-11.
UNIX"! - wersje i pochodne
Wersja 6
Wersja 7
Wersja 7
4.2 BSD System III Linux
SunOS Solaris HP-UX System V
( SUN ) (Hewlett-Packard)
IBM-AIX Digital Unix
SCO UNIX System V Xenix
(IBM) ( DEC )
UnixWare
LINUX
" Linus Torvald  1991 ( Minix)
" Red Hat
" Slackware
" Slackware
" Debian
" SuSE
" Caldera
" Knoppix
" FreeBSD
UNIX"! - wielozadaniowość
i wielodostępność
" wielozadaniowość z wywłaszczaniem
" wielozadaniowość bez wywłaszczania
(  yielding - regularne zwalnianie dostępu
do procesora )
do procesora )
" wielodostępność
UNIX"! - pliki
" każdy zbiór informacji jest plikiem
" nazwa - rozróżnia duże i małe litery (prawie
wszystkie drukowalne z wyjÄ…tkiem spacji)
dane.nowe.txt
dane.nowe.txt
" znaki uogólniające *, ?,[]
[1AaBb], [1-3], [a-f]
" pliki zwykłe, pliki specjalne - reprezentujące
urzÄ…dzenia, katalogi
UNIX"! - struktura katalogów
/
(root)
dev bin lib etc tmp usr
bin tmp lib man spool user 1 .... user n
UNIX"! - struktura katalogów
/
(root)
katalog nadrzędny ..
usr
bieżący katalog roboczy .
bieżący katalog roboczy .
( ~ katalog macierzysty
user1 .... usern
użytkownika user1 )
$ pwd /usr/user1
listy listy
$cd .. $pwd /usr
$cd user1/listy nowe stare
$cd /usr/usern
cd ../user1/listy/nowe ; cd ~/listy/stare ; cd
UNIX"! - informacje o pliku
Nazwa właściciela Rozmiar pliku w bajtach Nazwa pliku
$ ls -al
total 24
drwxrwxr-x 6 krzysztof klan 678 Feb 28 17:32 .
drwxrwxr-x 6 krzysztof klan 678 Feb 28 17:32 .
drwxrwxr-x 9 krzysztof klan 212 Jan 12 10:02 ..
drwxrwxr-x 1 krzysztof klan 143 Mar 11 15:52 książka
-rwxr-x--- 2 krzysztof klan 8822 Feb 14 12:09 tekst
drwx------ 1 krzysztof klan 657 Feb 22 19:33 prog
___________________________
Typ pliku Liczba łączników Nazwa grupy Data i czas ostatniej modyfikacji
( d - kartoteka , spacja - plik zwykły, b lub c - plik specjalny )
UNIX"! - prawa do plików
" prawo do czytania, pisania i wykonywania
$ ls -al
total 24
drwxrwxr-x 6 krzysztof klan 678 Feb 28 17:32 .
drwxrwxr-x 9 krzysztof klan 212 Jan 12 10:02 ..
drwxrwxr-x 1 krzysztof klan 143 Mar 11 15:52 książka
drwxrwxr-x 1 krzysztof klan 143 Mar 11 15:52 książka
-rwxr-x--- 2 krzysztof klan 8822 Feb 14 12:09 tekst
drwx------ 1 krzysztof klan 657 Feb 22 19:33 prog
___________________________
-rwxrwxr-x
UNIX"! - nadawanie praw dostępu do plików
" Metoda symboliczna:
" chmod
" + - dodanie prawa dostępu
- - zabranie prawa dostępu
- - zabranie prawa dostępu
- u  właściciel, g  grupa, o  inni, a  dla wszystkich
- Przykłady:
" chmod +x-w mojedane
" chmod g+rw mojedane
" chmod o+r mojedane
UNIX"! - nadawanie praw dostępu do plików
" Prawa bezwzględne:
" Zamiana systemu ósemkowego na binarny: 0  000, 1-
001, 2- 010, 3  011,4  100, 5  101, 6  110, 7  111
" chmod 554 mojedane
" chmod 554 mojedane
" odpowiednia liczba ósemkowa przez zsumowanie 4 
odczyt, 2  zapis, 1  wykonanie
" chmod 544 mojedane
" ls -l mojedane
" 101 100 100
" r-x r r
UNIX"! - Å‚Ä…czniki (dowiÄ…zania)
/usr/user1/nowe /usr/user1/nowe /usr/user1/nowe
pogoda pogoda1 pogoda1
Plik
utworzony
pod
pod
oryginalnÄ…
Pogoda Pogoda
nazwÄ…
dzisiaj... dzisiaj...
pogoda
ln pogoda pogoda1 rm pogoda rm pogoda1
ln -s internet /bin/www/netscape ( Å‚Ä…cznik symboliczny )
UNIX"! - identyfikatory plików
" pliki identyfikuje się w katalogach za pomocą indeksów
" indeks dla danego wolumenu to indeks do tablicy
zapisanej na tym urzÄ…dzeniu (i-lista)
numer identyfikacyjny użytkownika, który utworzył plik
kod ochronny pliku
trzynaście numerów bloków zajętych przez plik
rozmiar pliku
czas ostatniej modyfikacji pliku
liczbę dowiązań do pliku
bity rodzaju pliku
UNIX"! - fizyczna struktura plików
0 1 2 3 4 5 6 7 8 9 10 11 12
rzeczywiste numery bloków pliku
5120 bajtów (blok 512)
adres bloku przechowujÄ…cego
adresy dalszych 128 bloków pliku
(138 bloków = 70656 bajtów)
adres bloku przechowującego adresy 128 bloków,
z których każdy zawiera adresy dalszych 128 bloków pliku
(16522 bloków = ~8 Mbajtów)
adres bloku przechowującego adresy 128 bloków,
z których każdy przechowuje dalszych 128 bloków,
z których każdy zawiera adresy 128 bloków pliku
(2113674 bloków = ~1 Gbajt)
UNIX"! - podstawowe operacje na plikach
" Kopiowanie
cp plik-z
ródłowy plik-docelowy
cp -i pogoda pogodadzis
cp pogoda /usr/user2/pogoda
cp pogoda /usr/user2/pogoda
cp plik-z
ródłowy nazwa-katalogu
cp pogoda /usr/user2
z użyciem znaków specjalnych
cp *.txt listy cp list?.txt listy cp list[1-3].txt listy
" Przenoszenie
mv oryginalna-nazwa-pliku nowa-nazwa-pliku
" Informacja o składni poleceń - man nazwa polecenia
UNIX"! - podstawowe operacje na plikach
" Wylistowanie katalogu
 ls -opcje
opcje: F - nazwy katalogów poprzedzone ukośnikiem, R - z
podkatalogami
" Przeszukiwanie katalogów w poszukiwaniu plików
 find -name wzorzec
 find -type typ-pliku ( d - katalog, f - zwykły plik)
" Wyświetlanie plików
 cat nazwa pliku
 more nazwa pliku
UNIX"! - wolumeny wymienialne
mount /dev/fd0 /usr/jasio/oferty/dla_ewy
/usr/jasio
oferty listy sprawozdania
(korzeń)
dla_kazika dla_piotra dla_ewy
rozdział1 rozdział2 podsumowanie
rozdział1 rozdział2 podsumowanie
/usr/jasio
oferty listy sprawozdania
dla_kazika dla_piotra dla_ewy
rozdział1 rozdział2 podsumowanie
UNIX"! - maszyna wirtualna
" szereguje, koordynuje i zarzÄ…dza wykonywaniem
procesów
" zapewnia usługi systemowe, takie jak operacje wejścia-
wyjścia i zarządzania plikami
wyjścia i zarządzania plikami
" obsługuje wszystkie inne operacje związane ze
sprzętem
UNIX"! - jÄ…dro systemu
" duża liczba procedur usługowych wykonujących funkcje
ściśle związane z obsługą sprzętu
" centralny koordynator współpracy procedur z
działającymi procesami
działającymi procesami
powłoka
jÄ…dro
(shell)
UNIX"! - powłoka
" powłoki Bourne a, Korna i C
ekran
standardowe wyjście
Powłoka $ wiersz poleceń
standardowe wejście
klawiatura
UNIX"! - przekierowanie
" przekierowanie standardowego wyjścia do pliku >, >>
ekran
Plik kopia
adresat
nadawca
standardowe wyjście
Powłoka $ cat list > kopia
standardowe wejście
Plik list
klawiatura
adresat
nadawca
UNIX"! - potoki
$ sort mojalista | cat -n | lpr
potok potok
sort mojalista cat -n lpr
sort mojalista cat -n lpr
ekran komputer modem 1 ekran 2 komputer 3 modem
ekran komputer modem 1 ekran 2 komputer 3 modem
mojalista
modem
1 ekran
ekran
2 komputer
komputer
3 modem
UNIX"! - procesy
" Uruchomienie programu czy polecenia powłoki
zwiÄ…zane jest z uruchomieniem procesu.
" Procesy są narzędziem przydziału zasobów
komputera takich jak: procesor, pamięć oraz
komputera takich jak: procesor, pamięć oraz
urządzenia wejścia - wyjścia dla aplikacji.
" Proces inicjowany przez użytkownika ma
uprawnienia tego użytkownika dzięki mechanizmom
rozwidlania i wypełniania.
UNIX"! - rozwidlanie procesów
proces 1
fork 1 proces 1
fork 2 proces 2
proces 3
UNIX"! - rozwidlanie procesów c.d.
"  fork - powołuje do istnienia parę procesów,
wyposażonych w ten sam program i prawie takie samo
środowisko
" zmiany wykonywanego programu dokonuje inna funkcja
" zmiany wykonywanego programu dokonuje inna funkcja
(execl - w C++), a mimo tej zmiany proces pozostaje ten
sam.
" od momentu rozwidlenia procesy są całkowicie
niezależne.
UNIX"! - identyfikator skuteczny użytkownika
" parametry procesów powstałych w wyniku działania
tandemu fork-execl są na ogół identyczne
" dzięki takiemu rozwiązaniu czasami występują problemy
dotyczące praw dostępu
dotyczące praw dostępu
program passwd
właściciel root
prawa rwx--x--x
S
plik haseł
/usr/kazio
/usr/kazio
właściciel root
root
prawa rw-------
UNIX"! - hierarchia procesów
Wynik działania komendy ps
S UID PID PPID PRI SZ TTY TIME CMD
S 0 0 0 0 2 ? 0:02 swapper
S 0 1 0 30 15 ? 0:02 init
S 201 31 1 30 23 co 0:26 csh
S 201 31 1 28 20 02 0:13 sh
S 201 31 1 28 20 02 0:13 sh
S 0 18 1 40 12 ? 0:24 update
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
S 202 221 219 26 35 02 0:13 sed
R 202 223 220 54 66 02 0:10 sort
S 202 224 220 26 18 02 0:01 spelipro
S 202 225 220 26 65 02 0:02 spellpro
S 202 226 220 26 6 02 0:01 comm
R 0 227 33 54 26 03 0:14 ps
UNIX"! - zarzÄ…dzanie procesami
" uruchamianie zadań w tle
 ls  R > lista 2> wykbl &
" jobs  pokazuje zadania użytkownika wykonywane w tle oraz
zatrzymane CTRL+z
" Do ponownego uruchomienia zatrzymanego zadania na
" Do ponownego uruchomienia zatrzymanego zadania na
pierwszym planie używamy polecenia fg a w tle bg.
" Sposób podania :
" przez podanie PID fg  x pid ( jobs  l )
" przez podanie numeru zadania ( z nawiasu
kwadratowego )
" wydanie polecenia bez opcji spowoduje uruchomienie
ostatnio zatrzymanego zadania
UNIX"! - zarzÄ…dzanie procesami
" Wysyłanie sygnałów do procesów  kill
" sygnał 2 sigint przerwanie wykonania procesu nakazane z
klawiatury = CTRL+c
" sygnał 3 sigquit  zakończenie procesu wraz z utworzeniem pliku
core zawierającym pamięć procesu=CTRL+\
core zawierającym pamięć procesu=CTRL+\
" sygnał 9  sigkill unicestwienie procesu ( root lub właściciel )
" sygnał 15 sigterm domyślny  programowe (miękkie zakończenie
procesu)
" sygnał 19  sigstop  zatrzymanie wykonywania procesu =
CTRL+z
" kill  nr sygnału %nr zadania z jobs w [ ] lub PID procesu
UNIX"! - zarzÄ…dzanie procesami
" Wykonywanie z opóz
nieniem:
" Zamiast umieszczać zadanie w tle, można określić czas, kiedy ma zostać
wykonane. Można następnie wylogować się.
" at czas data
" godz:minuty am pm
" miesiąc ( Jan Feb ) dzień ( monday , tuesday ) słowa kluczowe am pm now
noon midnight today tomorrow
" data +liczba odcinek czasu (hours minutes days weeks months years
" next odcinek czasu względem aktualnej daty lub czasu
" at  l pokazywanie aktualnych zadań
" at  r numer zadania  anulowanie zadania
" at  m powiadamianie o wykonaniu zadania
UNIX"! - demon zegarowy
"  cron - synchronizuje z
zegarem systemowym
procesy, których wykonanie
procesy, których wykonanie
jest zależne od czasu
" wszystkie procesy
synchronizowane czasowo
zawarte sÄ… w tablicy
 crontab
UNIX"! - podział czasu
" czas współzawodniczącym procesom przydziela jądro
na podstawie priorytetu
" im niższa liczba wyrażająca priorytet tym wyższy
priorytet
" wartości priorytetów są aktualizowane cyklicznie, na
" wartości priorytetów są aktualizowane cyklicznie, na
ogół w odstępach kilkusekundowych
" użytkownik może obniżyć priorytet wybranego procesu
poleceniem  nice
" zwiększenie priorytetu procesu jest zarezerwowane dla
administratora
UNIX"! - przydzielanie pamięci
Chronione obszary pamięci
poszczególnych programów
Programy o strukturze wielowchodliwej
(re-entrant)
segment kodu segment danych Programy o strukturze zwykłej
segment stosu
UNIX"! - filtry
" Filtry sÄ… poleceniami odczytujÄ…cymi dane, wykonujÄ…cymi na
nich określone działania i wysyłające wynik do
standardowego strumienia wyjściowego. Filtr zwykle nie
modyfikuje danych wejściowych.
" Wyprowadzanie początku i końca pliku: head i tail:
" Wyprowadzanie początku i końca pliku: head i tail:
- head  liczbawierszy nazwapliku
- tail  liczbawierszy nazwapliku
" Filtry wyjściowe: wc i sort:
- zliczanie słów wc :
" opcje - -l  zlicza liczbę wierszy, -w  zlicza słowa, -c  zlicza
znaki
" sort  sortowanie plików :
UNIX"! - przeszukiwanie plików
" Przeszukiwanie plików: grep i fgrep
" grep wzorzec lista-plików
" Wzorce  wyrażenia regularne  pozwalają na dopasowanie różnych
odmian wzorca:
- dopasowanie początku i końca wiersza: wzorzec na początku wiersza ^wzorzec lub
na końcu wiersza wzorzec$. Kombinacji ^$ można użyć do poszukiwania pustego
wiersza.
wiersza.
- dopasowywanie dowolnego znaku  kropka jest znakiem specjalnym pasujÄ…cym do
dowolnego znaku , Można używać tyle kropek ile znaków chcemy zastąpić.
Żeby znak kropki działał trzeba go umieścić w środku
- dopasowywanie powtarzających się znaków - * ( np. c* oznacza zero lub więcej
wystąpień znaku c, tak więc aby poszukiwać c, cc, ccc itd. należy podać cc*,
można wykorzystać również . (kropkę) .* oznacza dowolny łańcuch znaków
" Pozdrowienia dla Ciebie i Rodziny .*Ciebie
 Pozdrowienia dla Ciebie i Rodziny Ciebie.*
 Pozdrowienia dla Ciebie i Rodziny a.*R
" Klasy znaków: [], klasy wykluczające ^ [^listaznakówwyłączonych]
UNIX"! - operacje wejścia-wyjścia
" dla programu shell wszystkie operacje we-wy
wyglÄ…dajÄ… tak jak operacje na plikach (nic nie wiadomo o
istnieniu jakichkolwiek urządzeń)
" zadanie ukrycia prawdziwych urządzeń pod postacią
" zadanie ukrycia prawdziwych urządzeń pod postacią
pozornych plików przypisano do jądra systemu
" niezależność od urządzeń
UNIX"! - pliki blokowe i znakowe
" pliki specjalne znakowe reprezentujÄ… urzÄ…dzenia
 terminalopodobne
 bufory danych
 bufory danych
 brak ustalonych właścicieli buforów
 zapisywanie buforów na dysk sporadyczne i tylko na żądanie
" pliki specjalne blokowe reprezentujÄ… urzÄ…dzenia
 dyskopodobne
UNIX"! - dostęp swobodny
" wszystkie urządzenia i nośniki są traktowane tak samo -
jako magazyny plików składających się z ciągu znaków
" jednak urządzenia różnią się sposobem dostępu do
plików
" dostęp swobodny - np. dysk twardy
" dostęp swobodny - np. dysk twardy
 czas dostępu do dowolnego miejsca jest prawie identyczny
(wszystkie pliki jednakowo dostępne)
 czytanie i pisanie może odbywać się w różnej kolejności
 do nadzorowania miejsca wykonania operacji służy wskaz
nik
pozycji
UNIX"! - dostęp sekwencyjny
" urządzenia typu klawiatura czy drukarka są ściśle
sekwencyjne
 nie można odczytać znaków raz wysłanych do drukarki
 czytanie z innych urządzeń odbywa się tylko w ściśle określonej
kolejności (wymuszonej przez urządzenie)
kolejności (wymuszonej przez urządzenie)
" także te urządzenia UNIX traktuje jednakowo !!!
" jednokierunkowość takich urządzeń jak klawiatura czy
drukarka jest maskowana przez odpowiednie prawa
dostępu do pliku
UNIX"! - X Windows
" Jednolity graficzny interfejs użytkownika ( GUI )
projekt Athena realizowany przez MIT
1987 - utworzenie X Consortium przez 12 czołowych
producentów stacji roboczych - powstaje Wersja 11 X Windows
HP, IBM i DEC tworzÄ… FundacjÄ™ Oprogramowania Otwartego
HP, IBM i DEC tworzÄ… FundacjÄ™ Oprogramowania Otwartego
oraz standard Motif wypierajÄ…cy standard OpenLook
1993 - Unix System Laboratories i Novell dajÄ… poczÄ…tek
Inicjatywie COSE ( Common Open Software Environment) której
celem jest stworzenie graficznego środowiska pracy ( CDE )
UNIX"! - X Windows - architektura
" architektura klient - serwer
Komputer o dużej mocy
Graficzna stacja robocza
obliczeniowej
Program
X
użytkowy
ekran
I-O
X Serwer
X protokół
X Klient
klawiatura
UNIX"! - X Windows - architektura
" architektura klient - serwer
Stacja robocza
X
X
Program
ekran
użytkowy
I-O
X Serwer
X protokół
X Klient
klawiatura
UNIX"! - X Windows - struktura
System
operacyjny
(widget y)
UNIX"! - podstawowe usługi sieciowe
" mail 1965
" write 1970
" talk 1970
" talk 1970
" telnet 1971
" ftp 1970
" www 1989 T. Berners-Lee i R. Cailliau
UNIX"! - mail
" mail- za pomocą programu mail można w prosty sposób
wysyłać i odbierać wiadomości od innych użytkowników.
wysyłanie
mail nazwa użytkownika
temat
treść listu
treść listu
[CTRL+d]
mail temat < plik z treścią listu
odbieranie
mail
wyświetlana jest lista nagłówków otrzymanych listów
nr listu [ spacja lub Enter ]
zakończenie pracy
q
Przeczytane listy zachowywane sÄ… w pliku mbox.
UNIX"! - write i talk
" Programy write i talk slużą wyłącznie do komunikacji z innymi
zalogowanymi użytkownikami ( listę takich użytkowników
można uzyskać poleceniem who )
" write - pozwala na wysyłanie w czasie rzeczywistym
wiadomości do innego użytkownika. Polecenie mesg -n
pozwala uniknąć odbierania wiadomości.
pozwala uniknąć odbierania wiadomości.
" talk - służy do utworzenia dwukierunkowego połączenia z
innym użytkownikiem
UNIX"! - telnet
" telnet - polecenie służące do zdalnego logowania
do odległego systemu
open adres
login:
nazwa użytkownika i hasło
( w szeregu systemach istnieje użytkownik guest z bardzo
małymi uprawnieniami umożliwiający zalogowanie bez
znajomości hasła )
quit
UNIX"! - ftp
" ftp - program służący do bezpośredniego przesyłania dużych plików
z jednego serwera na drugi
open adres
Name: nazwa użytkownika
Name: nazwa użytkownika
Password: hasło
( w szeregu systemach istnieje użytkownik anonymous)
binary - zmian trybu na binarny, ascii - tekstowy (domyślny)
get nazwa pliku - kopiuje pliki z systemu odległego do
lokalnego ( mget dla kilku plików naraz )
put nazwa pliku - odwrotnie (mput)
close
quit
IP - unikalny adres logiczny komputera
" IP - 32 bitowa liczba całkowita przedstawiana w tzw.
poczwórnej notacji dziesiętnej:
8 bitów 8 bitów 8 bitów 8 bitów
liczba dziesiętna.liczba dziesiętna.liczba dziesiętna.liczba dzie.
Np. 194.92.216.161
" nadawany przez RIPE NCC w Europie wg. RFC 2050
" w przyszłości - IPv6 - 128 bitów - 3.4 10 38 adresów
(16000 adresów na 1 metr kwadratowy powierzchni
Ziemi) zamiast około 4 miliardów obecnie.
Klasy sieci
Klasa Pierwsze Adres Adres Liczba Liczba
sieci 3 bity sieci komp. sieci komp.
A 1 - 0 od 2 do 8 24 bity 127 ~16 mln
A 1 - 0 od 2 do 8 24 bity 127 ~16 mln
B 1 - 1,2 - 0 14 bitów 16 bitów 16384 ~65 tys.
C 1- 1,2 - 1 21 bitów 8 bitów ~2.1 mln. 254
3 - 0
System nazw domenowych DNS
" nazwa domenowa składa się z kilku części oddzielonych
kropkami
mail.p.lodz.pl
" nazwa domenowa przekładana jest na adres IP przez
" nazwa domenowa przekładana jest na adres IP przez
system działający w oparciu o tzw. serwery nazw
" domeny krajowe: PL - Polska, DE - Niemcy, FR - Francja
" domeny rodzajowe: COM - organizacje komercyjne,
EDU - edukacyjne, GOV - rzÄ…dowe,
INT - międzynarodowe, NET - zajmujące się siecią,
ORG - niekomercyjne
Adresy prywatne
Adresy w sieci
" adres sieci - ostatni człon ustawiony na 0 ( 199.35.208.0 )
" maska sieci jest używana do uzyskania adresu sieci na podstawie
adresu komputera
adres komputera 199.35.209.26
maska sieci 255.255.255.0
maska sieci 255.255.255.0
1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
" adres rozgłoszeniowy (broadcast) - ostatni człon ustawiony na 255 -
pozwala na wysłanie wiadomości do wszystkich komputerów w sieci
" adres bramy (gateway)
" adres serwera nazw
" urządzenie pętli zwrotnej ( IP 127.0.0.1 )
Maska sieci: 255.255.255.128
Numer podsieci: 128.96.34.0
128.96.34.15
128.96.34.1
H1
R1
Maska sieci : 255.255.255.128
128.96.34.130
Numer podsieci : 128.96.34.128
128.96.34.139
128.96.34.139
128.96.34.129
H2
R2
H3
128.96.33.1
128.96.33.14
Maska sieci : 255.255.255.0
Numer podsieci : 128.96.33.0
Chapter 4, Figure 25
Protokół TCP/IP
" Twórcą protokołu TCP/IP jest Vinton Cerf.
" Protokół TCP świadczy usługi warstwy transportowej:
tworzy wirtualne połączenia
realizuje wymianę informacji w postaci pakietów (datagramów)
kontrolując poprawność (poprzez sekwencyjne numerowanie
bajtów i obliczanie sumy kontrolnej oraz sprawdzanie kolejności
danych)
wymusza ponownÄ… retransmisjÄ™ danych w przypadku braku
potwierdzenia ich poprawności
" Protokół IP działa w warstwie sieciowej i jest odpowiedzialny za
przesyłanie pakietów danych w sieci.
Transport mediów
" Rozróżniamy dwa typy mediów  takie które tolerują oraz takie które
nie tolerują utraty pakietów. Do pierwszych należą dz
więk i obraz do
drugich strony www i wiadomości błyskawiczne (instant message).
" Niezawodny transport mediów: TCP i SCTP (Stream Control
Transmission Protocol RFC 2960).
" TCP działa najlepiej, kiedy odbiorca nie musi czekać na odebranie
całej wiadomości, żeby zacząć ją obrabiać. Typowym przykładem jest
przeglÄ…darka internetowa.
" Z drugiej strony, jeżeli aplikacja jest zainteresowana odebraniem
" Z drugiej strony, jeżeli aplikacja jest zainteresowana odebraniem
wszystkich danych od razu lepszym wyborem jest SCTP. SCTP
dostarcza raczej wiadomości niż strumień bitów. Wiadomość może na
przykład zawierać całą wiadomość błyskawiczną lub plik
transferowany pomiędzy dwoma użytkownikami. SCTP ma własności
niedostępne dla TCP jak: lepsze zabezpieczenie przeciw atakom DoS,
multi-homing (używanie kilku adresów dla jednego strumienia
danych), wiele strumieni dla jednej asocjacji (połączenia) SCTP.
" Mimo zalet SCTP jest jak na razie rzadko używany.
Transport mediów
" Transport zawodny  najczęściej używanym jest
protokół UDP. W tym przypadku nie ma żadnej
kontroli przepływu ani sprzężenia zwrotnego. W
związku z możliwością utraty pakietów niektóre
kodeki rozpraszają informację pomiędzy wiele
pakietów. Mimo tego, że UDP jest powszechnie
używany ma on jedną dodatkową wadę jaką jest
brak odporności na powstawanie zatorów. Wzrost
brak odporności na powstawanie zatorów. Wzrost
liczby aplikacji używających UDP do transmisji
mediów spowodowało rozpoczęcie prac nad
nowym protokołem zawodnym odpornym na
zatory. JednÄ… z propozycji jest utworzenie
zawodnego protokołu SCTP. Odpowiedzią jest też
DCCP (Datagram Congestion Control Protocol),
będący w fazie draft.
Transport mediów
" DCCP jest zawodnym protokołem transportowym, który zapewnia
ustanawianie połączeń jak również negocjowanie algorytmów
kontroli zatorów. Połączenie jest ustanawiane na drodze trzy
krotnej wymiany komunikatów, podczas której następuje
negocjowanie parametrów połączenia. W szczególności strony
negocjują algorytm zwalczania zatorów. Algorytmy zwalczania
zatorów są identyfikowane poprzez CCID (Congestion Control
Identifiers). W chwili obecnej sÄ… trzy metody do wyboru: kontrola
zatorów bazująca na nadawcy, TCP-podobna kontrola zatorów i
zatorów bazująca na nadawcy, TCP-podobna kontrola zatorów i
TFRC (TCP-Friendly Rate Control).
" RTP (Real Time Transport Protocol RFC 3550) umożliwia transport
mediów czasu rzeczywistego, takich jak dz
więk i obraz, poprzez
protokoły zawodne takie jak UDP lub DCCP. Jest zawsze używany
w połączeniu z RTCP (RTP Control Protocol), który dostarcza
statystykę jakości usług i informacje potrzebne do
przeprowadzania synchronizacji pomiędzy mediami.
Transport mediów
" Główną intencją RTP jest umożliwienie odbiorcom odtwarzanie
mediów w odpowiednim tempie. W sieciach IP nie mamy żadnej
zależności kształtowania czasu dotarcia pakietów w związku z
tym pakiety docierają z różnym opóz
nieniem tworzÄ…c zjawisko
tzw. jitter u.
" Z tego względu odbiorca do porządkowania pakietów używa
znacznika czasu protokołu RTP. Odbiorca umieszcza
przychodzÄ…ce pakiety w buforze zgodnie z ich znacznikiem
czasowym i zaczyna je odgrywać. Jeżeli pakiet z określonym
czasowym i zaczyna je odgrywać. Jeżeli pakiet z określonym
znacznikiem powinien być uruchomiony ale w dalszym ciągu
nie nadszedł odbiornik używa techniki interpolacji aby zapełnić
szczelinÄ™ ( w przypadku dz
więku odtwarza ostatni pakiet
dłużej). Jeżeli pakiet nadejdzie póz
niej jest on odrzucany.
Odbiornik musi podjąć ważną decyzję  w którym momencie
rozpocząć odtwarzanie. Różne implementacje używają różnych
parametrów do decydowania o długości bufora.
A
Ä…cze danych
" Metody dostępu do sieci pracującej w oparciu o
transmisję w paśmie podstawowym:
oparte na dostępie rywalizacyjnym - największe
znaczenie mają metody oparte na nasłuchu stanu łącza
i wykrywaniu kolizji (CSMA/CD):
i wykrywaniu kolizji (CSMA/CD):
Ethernet ( IEEE 802.3 ISO 8802.3 )
oparte na przekazywaniu uprawnienia (token passing)
Token-Ring (IEEE 802.5) - IBM
ARCnet - Datapoint Corporation
Fiber Distributed Data Interface (ANSI X3T9.5 IEEE
802.5)
A
Ä…cze fizyczne
" przewody koncentryczne  do 1000 MHz
" kabel typu skrętka  do 600 MHz
" sieci bezprzewodowe radiowe  od 400 MHz,
" sieci bezprzewodowe radiowe  od 400 MHz,
ISM (Industrial Scientific-Medical) 2,5-5 GHz
do 11 GHz
" mikrofale i łączność satelitarna  do 300 GHz
" podczerwień  103  105 GHz
" światłowód - 1013  1015 GHz
Sieci bezprzewodowe
IEEE 802.11
Parametry standardów Wi-Fi
Standard 802.11b 802.11g 802.11n
Pasmo 2,4 GHz 2,4 GHz 2,4 GHz
Szybkość transmisji 11 Mb/s 54 Mb/s 150, 300 Mb/s
Szybkość transmisji 11 Mb/s 54 Mb/s 150, 300 Mb/s
Zasięg w budynku 46 m 46 m 90 m
Zasięg na terenie otwartym 96 m 96 m 250 m
HomeRF
IEEE 802.16a (WiMAX) 2-11 GHz 75 Mb/s zasięg do 50 km
(w Polsce 3,5 GHz i 3,7 GHz UrzÄ…d Komunikacji
Elektronicznej UKE )
UMTS/HSDPA  telefonia komórkowa
Historia
" W połowie lat osiemdziesiątych firmy Microsoft i
IBM współpracowały przy opracowaniu systemu
operacyjnego OS/2, który napisano w języku
asemblera dla jednoprocesorowych systemów
Intel 80286.
" W 1988 roku Microsoft postanowił zacząć od
nowa i opracować system operacyjny w nowej
technologii (NT), który zawierałby interfejsy
programów użytkowych zarówno OS/2 jak i
POSIX.
" W paz
dzierniku 1988 do zbudowania takiego
systemu wynajęto Dave a Cutlera, konstruktora
systemu operacyjnego VMS dla komputerów VAX
firmy DEC.
Windows NT , 2000, XP
Podsystem klient-serwer
Konsola
Tryb użytkownika (User Mode)
Tryb chroniony (Kernel Mode)
Tryb chroniony (Kernel Mode)
Menedżer okien,
Program wykonawczy (Executive)
grafiki i druku
(realizuje funkcje
WIN32 USER oraz GDI)
Sterowniki urządzeń Jądro
(device drivers) (mikrokernel)
Sterownik portu System buforowania
wizyjnego (spooler)
Abstrakcyjna warstwa sprzętowa
(HAL)
Sterownik miniportu Sterownik portu
wizyjnego równoległego
Windows NT
Aplikacje
Aplikacje Aplikacje Aplikacje OS/2
Proces
Aplikacje
16 bit. i
POSIX Win32 (tryb znakowy)
zgłoszenia
DOS
Podsystem
Podsystem
Podsystem
Podsystem Podsystem Pod.
Podsystem Podsystem Pod.
Podsystemy
Podsystemy
POSIX
POSIX
bezpieczeństwa
Win32 OS/2 CSR
(nowy Interix)
(Server)
DLL - biblioteka dołączana dynamicznie
User Mode
Kernel Mode
Windows NT
User Mode
Kernel Mode
Executive
Menedżer Zarządzanie Monitor Menedżer
Win 32
ZarzÄ…dzanie
procesów pamięcią bezpie- procesu
Execu-
Execu-
operacjami
operacjami
wirtualną czeństwa buforowania
wirtualną czeństwa buforowania
tive
wejścia/
Wywoływanie
Menedżer
wyjścia
lokalnych
obiektów
procedur
Mikrokernel
Abstrakcyjna warstwa sprzętowa (HAL)
Hardware
Warstwa abstrakcji sprzętu
" Warstwa HAL (hardware abstraction layer) jest
oprogramowaniem, które ukrywa różnice
sprzętowe przed górnymi warstwami systemu
operacyjnego, aby ułatwić uczynienie systemu NT
przenośnym.
" Warstwa HAL tworzy interfejs maszyny
wirtualnej, z którego korzystają elementy
systemu operacyjnego umieszczone wyżej.
" System Windows XP działa na procesorach
zgodnych z architekturą IA32 i IA64 ( W2000 był
testowany na platformie DEC Alpha )
Windows NT - program wykonawczy
Executive
" Menedżer procesów i wątków -
pomocnicze prace zwiÄ…zane z
zarzÄ…dzaniem procesami i wÄ…tkami -
zasadnicze prace wykonuje jÄ…dro
zasadnicze prace wykonuje jÄ…dro
" Zarządzanie pamięcią wirtualną
" Monitor bezpieczeństwa
" Zarządzanie operacjami wejścia-
wyjścia
" Menedżer procesu buforowania
Windows NT - program wykonawczy
Executive
" Funkcje używane przez moduły Executive:
- menedżer obiektów - tworzy, zarządza i usuwa obiekty,
używane do reprezentowania zasobów systemu: procesów,
wątków i innych.
- LPC - wywoływanie lokalnych procedur - wymiana
informacji pomiędzy procesami klienta i procesem serwera
w ramach systemu ( jest to wersja remote procedure call
w ramach systemu ( jest to wersja remote procedure call
(RPC) przemysłowego standardu wymiany informacji
pomiędzy klientem i serwerem poprzez sieć)
- funkcje wykorzystywane podczas przebiegu programu
(run-time function) - operacje arytmetyczne, zmiana typów,
operacje na łańcuchach)
-pomocnicze procedury programu zarzÄ…dzajÄ…cego (
executive support routines) - alokacja pamięci,
synchronizacja
Podstawowe pojęcia
" Proces :
- wykonywalny program definiujÄ…cy statycznÄ… sekwencjÄ™
instrukcji oraz dane
- obszar pamięci używanej przez proces
- zasoby systemowe : zmienne synchronizujÄ…ce (semaphores),
porty (wejścia) komunikacyjne, zbiory
- unikalny identyfikator (process ID)
- unikalny identyfikator (process ID)
- co najmniej jeden wÄ…tek
" WÄ…tek :
- ulotna zawartość zbioru rejestrów reprezentujących stan
procesora
- dwa stosy (wydzielone obszary pamięci) jeden do pracy w trybie
użytkownika i drugi do pracy w trybie uprzywilejowanym
- wydzielony obszar pamięci używany przez procedury ładowane
(dołączone do programu w trakcie wykonywania)
- unikalny identyfikator (thread ID)
" Wewnętrznie system używa jednego typu identyfikatora dla
procesów i wątków (client ID)
WÄ…tek
" Wątek może się znajdować w jednym z sześciu stanów:
 gotowości
 pogotowia
 wykonywania
 oczekiwania
 przejściowym
 zakończenia.
" System przy określaniu kolejności wątków korzysta z 32
priorytetów. Są one podzielone na dwie klasy: czasu
rzeczywistego oraz zmienną. Wątek, którego kwant czasu
się wyczerpie, zostaje przerwany i jeśli należał do klasy
zmiennej jego priorytet ulega zmniejszeniu. Wątek, który
oczekiwał na jakąś operację np. dane z klawiatury ma
priorytet podwyższany w zależności od operacji na którą
oczekiwał (przyrost dla urządzeń typu myszka będzie
większy niż dla dysku).
WÄ…tek
" Podobnie jak procesy, wątki użytkują wspólnie
jednostkÄ™ centralnÄ… i w danej chwili tylko jeden
wÄ…tek jest aktywny.
" Wykonanie wÄ…tku w procesie przebiega
sekwencyjnie, a każdy wątek ma własny stos i
licznik rozkazów.
licznik rozkazów.
" W odróżnieniu od procesów wątki nie są
niezależne od siebie. Dany wątek może zapisywać
i czytać stosy dowolnych innych wątków.
" Zaletą wątków jest możliwość działania innych
wątków gdy jeden z nich jest zablokowany i
czeka. Daje to powiększenie przepustowości i
wydajności.
WÄ…tek
" Planowanie przydziału procesora następuje
wówczas, gdy wątek przechodzi do stanu
gotowości lub oczekiwania, gdy kończy działanie
lub wtedy, kiedy aplikacja zmienia priorytet wÄ…tku
lub przypisanie procesora. Jeżeli wysoko
priorytetowy wÄ…tek czasu rzeczywistego staje siÄ™
priorytetowy wÄ…tek czasu rzeczywistego staje siÄ™
gotowy do działania w czasie, w którym działa
wÄ…tek nisko priorytetowy, to nisko priorytetowy
wątek jest wywłaszczany. Wywłaszczanie takie daje
wątkowi czasu rzeczywistego preferencyjny dostęp
do procesora, jeśli wątek dostępu takiego
potrzebuje. Jednak Windows nie jest
rygorystycznym systemem czasu rzeczywistego,
gdyż nie zapewnia, że wątek czasu rzeczywistego
rozpocznie działanie w konkretnym limicie czasu.
Proces i jego podstawowe zasoby
Znacznik dostępu
( virtual address space descriptors)
Proces
VAD VAD VAD
Opis pamięci wirtualnej
Tablica obsługi (handle table)
Tablica obsługi (handle table)
(zbiór)
Obiekt
(wspólny obszar
Obiekt
pamięci)
(zmienna
Obiekt
synchronizujÄ…ca)
WÄ…tek WÄ…tek WÄ…tek
Podstawowe pojęcia
" Obiekt w systemie operacyjnym - dane, czynności i atrybuty.
Zasadnicza różnica pomiędzy obiektem a zwykłymi danymi
polega na tym, że wewnętrzna struktura obiektu jest ukryta i
użytkownik musi użyć specjalnych usług aby ją odczytać lub
zmienić.
zmienić.
Obiekty sÄ… wprowadzane aby:
- nadawać zasobom systemu nazwy do których może
odwoływać się użytkownik
- dzielić zasoby pomiędzy procesami
- chronić zasoby przed niepowołanym dostępem
" API - aplication program interface - zestaw procedur z których
programista aplikacji korzysta, aby zażądać i użyć usług
niższego poziomu wykonywanych przez system operacyjny.
Obiekt programu zarzÄ…dzajÄ…cego
Executiv
Proces 1
Nagłówek
Nazwa obiektu
obiektu
Katalog obiektu
Proces 2
Opis praw dostępu
Proces 3
Lista poboru
Typ obiektu
Typ obiektu
Licznik otwarć
Licznik otwarć
Lista otwierajÄ…cych
Nazwa typu
Typ obiektu
Rodzaje dostępu
Licznik odwołań
Czy podlega synchronizacji?
Czy podlega stronicowaniu?
Ciało
Metody postępowania:
obiektu
otwieranie,zamykanie,
Dane specyficzne obiektu
poszukiwanie obiektu,
zmiana atrybutów
bezpieczeństwa,
zapytanie o imiÄ™.
Windows NT - Executiv
" Obiektowy system NT stosuje obiekty we wszystkich swoich
usługach i fragmentach.
" Zadaniem zarządcy obiektów jest nadzorowanie użytkowania
wszystkich obiektów. Jeśli wątek chce skorzystać z obiektu, to
wywołuje metodę open zarządcy obiektów w celu otrzymania
uchwytu (handle) do obiektu.
uchwytu (handle) do obiektu.
" Uchwyty są standaryzowanymi interfejsami do obiektów
wszystkich rodzajów. Podobnie jak uchwyt do pliku, uchwyt do
obiektu jest niepowtarzalną w procesie liczbą całkowitą,
umożliwiającą dostęp do zasobu systemowego i wykonywanie na
nim działań.
" Zarządca obiektów pilnuje, które procesy używają których
obiektów.
" Każdy nagłówek obiektu zawiera licznik procesów dysponujących
uchwytami do danego obiektu. Kiedy licznik ten siÄ™ wyzeruje,
następuje usunięcie obiektu z przestrzeni nazw, jeżeli jego nazwa
była tymczasowa.
" Obiekty trwałe reprezentują elementy fizyczne, takie jak napędy
Windows NT - Executiv
" Działania na obiektach odbywają się za pomocą
standardowego zbioru metod: create, open,
close, query name, parse i security.
" Query name  jest używana, gdy wątek ma
uchwyt do obiektu, ale chce poznać jego nazwę
uchwyt do obiektu, ale chce poznać jego nazwę
" Zarządca obiektu posługuje się operacją parse w
celu odnalezienia obiektu na podstawie jego
nazwy
" Operację security wywołuje się wtedy, kiedy
proces otwiera obiekt lub zmienia tryb jego
ochrony
Windows NT  Executiv  obiekty
nazewnicze
" Executiv umożliwia nazwanie dowolnego obiektu.
" Przestrzeń nazw jest globalna, zatem jeden proces może utworzyć
obiekt z nazwą, a inny proces może utworzyć uchwyt do takiego
obiektu i dzielić obiekt z pierwszym procesem.
" Chociaż przestrzeń nazw nie jest bezpośrednio widoczna w sieci,
zarządca obiektów pomaga sobie w dotarciu do obiektu w innym
zarządca obiektów pomaga sobie w dotarciu do obiektu w innym
systemie za pomocÄ… operacji parse.
" Nazwy obiektów są strukturalne. Katalogi są reprezentowane za
pomocą obiektów katalogowych. Przestrzeń nazw obiektów może
się rozrastać przez dodanie domen obiektów, które są
zamkniętymi w sobie zbiorami obiektów. Przykładem domen
obiektów są dyskietki i dyski.
" Podobnie jak dowiÄ…zania symboliczne w Unix realizowane sÄ…
obiekty dowiązań symbolicznych
Windows NT - Kernel
" ZarzÄ…dzanie harmonogramem pracy
wątków
" Obsługa wyjątków
" Obsługa przerwań
" Obsługa przerwań
" Synchronizacja pracy wieloprocesorowej
" ZarzÄ…dzanie obiektami jÄ…dra
Windows NT - Kernel - podstawowe pojęcia
" Przerwanie - jest wydarzeniem asynchronicznym, które jest
niezależne od tego co procesor w danej chwili wykonuje. Są
generowanie głównie przez urządzenia wejścia/wyjścia lub zegar
systemowy i mogą być przyjmowane lub blokowane.
" Wyjątek - wydarzenie związane z wykonywaniem określonej
instrukcji.
instrukcji.
Typowo wyjątki są generowane przez błędy programowe takie jak:
próba dostępu do zabronionego obszaru pamięci lub dzielenie
przez zero, a także mogą być wynikiem działania specjalnego
programu wspomagającego usuwanie błędów zwanego
debuggerem.
" Przerwania i wyjątki mogą być generowane zarówno przez sprzęt
jak i oprogramowanie (wyjątek błędu magistrali, przerwanie
programowe).
" Przerwania są obsługiwane w zależności od poziomu
pierwszeństwa IRQL (interrupt request level)
Windows NT - wykorzystanie przerwań
" Wykonywanie operacji wejścia/wyjścia w tle.
Procesor rozpoczyna operacjÄ™ we/wy i wykonuje inne wÄ…tki kiedy
urzÄ…dzenie wykonuje odpowiednie operacje. Kiedy urzÄ…dzenie
kończy operację wysyła do procesora przerwanie. Urządzenia
określające pozycję (mysz), drukarki, klawiatura, dyski i karty
sieciowe są sterowane przy pomocy przerwań.
sieciowe są sterowane przy pomocy przerwań.
" Sterowanie wielozadaniowością.
Jądro generuje przerwania programowe w celu wywłaszczenia
aktualnie pracujÄ…cego wÄ…tku i zastÄ…pienia go innym.
" Przejęcie sterowania od wątku który zakończył lub zawiesił pracę -
przerwanie DPC (deffered procedure call)
" Asynchroniczne wykonywanie procedur (APC) - pozwala
użytkownikowi lub systemowi na wykonanie fragmentu kodu
programu w dowolnym momencie.
Windows NT  działanie jądra
" Przykłady wyjątków obsługiwanych przez jądro:
 niedozwolona próba odwołania do pamięci
 nadmiar stałopozycyjny
 nadmiar lub niedomiar zmiennopozycyjny
 dzielenie całkowite przez zero
 dzielenie zmiennopozycyjne przez zero
 dzielenie zmiennopozycyjne przez zero
 niedozwolony rozkaz
 błąd czytania strony
 próba naruszenia ochrony strony
 przekroczenie rozmiaru zbioru stronicowania
 osiągnięcie punktu kontrolnego przez program uruchomieniowy
" Proste wyjątki mogą być obsługiwane przez procedurę obsługi
pułapki obsługa innych należy do obowiązków ekspedytora
wyjątków ( exception dispatcher).
" WyjÄ…tek w trybie jÄ…dra w przypadku nieodnalezienia procedury
obsługi powoduje awarię systemu.
Windows NT  działanie jądra
" Przerwania systemu NT i ich poziomy:
 błąd procesora lub szyny  31
 awaria zasilania  30
 powiadomienie międzyprocesorowe  29
 zegar  28
 typowe przerwania sprzętowe 12-27
 typowe przerwania sprzętowe 12-27
 wywołanie procedury 4-11
 program diagnostyczny 3
 przerwania programowe 0-2
" Poziom przerwań IRQL decyduje czy przerwanie będzie
obsługiwane czy też blokowane (maskowane).
Windows NT - programy obsługi urządzeń
" Programy obsługi urządzeń hardwerowych -
czytajÄ… i zapisujÄ… dane wykorzystujÄ…c HAL z
urządzeń fizycznych oraz sieci
" Programy obsługi systemu plikowego - które
akceptują żądania zapisu czy odczytu zbiorów
akceptują żądania zapisu czy odczytu zbiorów
" Programy obsługi filtrów - np. realizujących
odbicie lustrzane dysków
" Programy obsługi usług sieciowych - obsługują
żądania kierowane do innych komputerów w sieci
Lista zainstalowanych programów obsługi
urządzeń - Control Panel - Devices
Windows NT  sprzęt wejścia-wyjścia
" Urządzenia I/O : pamięci, przesyłania danych i
urządzenia interfejsu z człowiekiem.
" Port  punkt Å‚Ä…czÄ…cy urzÄ…dzenie z maszynÄ…
" Szyna  wiązka przewodów wraz z ściśle
określonym protokołem, precyzującym zbiór
określonym protokołem, precyzującym zbiór
komunikatów, które można tymi przewodami
przesłać
" Sterownik (controller) jest zespołem układów
elektronicznych, które mogą kierować pracą
portu, szyny lub urzÄ…dzenia.
Windows NT  sprzęt wejścia-wyjścia
Procesor
Pamięć
Szyna SCSI
podręczna
Monitor
Dysk
Most lub
Sterownik
sterownik
Pamięć
Pamięć
Sterownik
Sterownik
graficzny
graficzny
pamięci
operacyjna
SCSI
Szyna PCI
Sterownik Klawiatura
dysku IDE
Interfejs szyny
rozszerzajÄ…cej
Szyna rozszerzajÄ…ca
Dysk
Port równoległy Port szeregowy
Windows NT  sprzęt wejścia-wyjścia
" Komunikacja pomiędzy procesorem a sterownikiem odbywa się
poprzez rejestry sterownika służące do pamiętania danych i
sygnałów sterujących.
" Rozkazy I/O powodujące przesłanie bajtu lub słowa na adres portu
I/O.
" Sterownik urządzenia może też umożliwiać operacje I/O
" Sterownik urządzenia może też umożliwiać operacje I/O
odwzorowane w pamięci operacyjnej. W tym przypadku rejestry
urzÄ…dzenia sÄ… odwzorowane w przestrzeni adresowej procesora.
" Port I/O składa się na ogół z czterech rejestrów:
 stan (status)  zakończenie bieżącego polecenia, dostępność danych
wyjściowych, wykrycie błędu
 sterowanie (control)  zmiana trybu pracy urzÄ…dzenia
 dane wejściowe (data-in)
 dane wyjściowe (data-out)
" Niektóre sterowniki mają układy FIFO, w których przechowuje się
po kilka bajtów danych, aby rozszerzyć pojemność sterownika.
Windows NT  odpytywanie
" Uzgadnianie (handshaking)  prosty przykład :
 do koordynowania zależności między sterownikiem a procesorem są używane 2
bity
 sterownik zaznacza swój stan za pomocą bitu zajętości (busy) w rejestrze stanu
 procesor sygnalizuje swoje życzenia za pośrednictwem bitu gotowości polecenia
w rejestrze poleceń
" Ciąg uzgodnień:
" Ciąg uzgodnień:
 procesor powtarza czytanie bitu zajętości, dopóki nie przyjmie on wartość 0
 procesor ustawia bit pisania i wpisuje bajt do rejestru danych wejściowych
 procesor ustawia bit gotowości polecenia
 sterownik po stwierdzeniu ustawienia bitu gotowości ustawia bit zajętości
 sterownik czyta rejestr poleceń i wykonuje operację I/O
 sterownik czyści bit gotowości polecenia oraz bit błędu w rejestrze stanu, aby
powiadomić, że operacja zakończyła się pomyślnie, po czym czyści bit zajętości,
sygnalizując, że zakończył działanie
Windows NT  bezpośredni dostęp do
pamięci (DMA  direct memory access)
" Obsługą DMA zajmuje się najczęściej oddzielny sterownik
" W trybie DMA procesor zapisuje w pamięci blok sterujący
DMA: wskaz
nik do z
ródła przesyłania, wskaz
nik miejsca
docelowego przesyłania oraz liczbę bajtów do przesłania.
" Sterownik DMA przejmuje bezpośredni nadzór nad szyną
" Sterownik DMA przejmuje bezpośredni nadzór nad szyną
pamięci, umieszczając w niej adresy w celu wykonania
przesłania bez pomocy jednostki centralnej.
" Zakończenie działania sterownik DMA sygnalizuje
przerwaniem.
" W czasie pracy DMA pamięć operacyjna jest niedostępna
dla procesora. Może on korzystać wyłącznie z pamięci
podręcznej.
" Mimo tego stosowanie trybu DMA zwiększa wydajność.
Windows NT  zarządca wejścia-wyjścia
" Zarządca IO odpowiada za systemy plików, administrowanie
pamięcią podręczną oraz za programy sterujące urządzeń i sieci.
" Zamienia otrzymane zamówienia na standardową postać,
nazywaną pakietem zamówienia wejścia-wyjścia (I/O request
packet  IRP), po czym kieruje pakiety IRP do przetwarzania do
właściwych programów sterujących.
właściwych programów sterujących.
" Zarządca IO współpracuje z menedżerem procesu buforowania
zwanym także zarządcą pamięci podręcznej. Wielkość pamięci
podręcznej zmienia się dynamicznie w zależności od ilości wolnej
pamięci w systemie.
Windows NT  plikowe wejście-wyjście
Proces
I/O z pam. podr. ZarzÄ…dca I/O
ZarzÄ…dca System
pamięci plików
pamięci plików
podręcznej
I/O z pominięciem
Brak strony
pamięci podręcznej
Kopiowanie danych
Program
ZarzÄ…dca
obsługi dysku
pamięci
wirtualnej
Operacje I/O przebiegają zasadniczo z wykorzystaniem pamięci podręcznej.
Windows NT - menedżer okien i grafiki
" Menedżer okien - zarządza zawartością okien, gromadzi sygnały
wejściowe z klawiatury, myszy i innych urządzeń wejściowych i
przekazuje komunikaty użytkownika do aplikacji.
" GDI (Graphical Device Interface) - graficzny interfejs użytkownika
jest biblioteką funkcji używanych dla graficznych urządzeń
wyjściowych
wyjściowych
Zawiera funkcje kreślenia tekstu, linii i figur oraz operowania
grafikÄ….
" Program użytkowy wywołuje standardowe funkcje (USER) do
tworzenia okien i przycisków na ekranie. Menedżer okien przesyła
to żądanie do GDI, który przekazuje go do sterownika portu
wizyjnego, gdzie jest ono formatowane do postaci przyjmowanej
przez urządzenie graficzne. Postać specyficzna dla danego typu
urzÄ…dzenia (karty graficznej) jest uzyskiwana po zastosowaniu
sterownika miniportu wizyjnego.
Windows NT - przenośność
" Struktura warstwowa - funkcje zależne od architektury są zawarte w
jądrze natomiast funkcje zależne od sprzętu są umieszczone w HAL.
" Większość systemu jest napisana w C, a część interfejsu użytkownika
i podsystemu graficznego w C++.
" Jedynie niewielka część systemu wykorzystuje Asembler
" Jedynie niewielka część systemu wykorzystuje Asembler
Praca równoległa
" SMP - symmetric multiprocessing - charakteryzuje siÄ™
równouprawnioną pracą procesorów
Pamięć procesu
00000000
Zarezerwowana
2-GB
dla
przestrzeń
procesu
- dostępna do zapisu i odczytu
adresowa
w trybie użytkownika
w trybie użytkownika
procesu
7FFFFFFF
( za wyjÄ…tkiem stron tylko do odczytu
zawierajÄ…cych kod programu)
80000000
Używana
2-GB
przez
przestrzeń
system
- dostępna jedynie w trybie
adresowa
uprzywilejowanym
systemu
FFFFFFFF
Pamięć wirtualna i fizyczna
Pamięć wirtualna
Pamięć fizyczna
strona nieaktywna
4 kB strona
strona aktywna
Pamięć niestronicowana  zawsze mająca odpowiednik w pamięci fizycznej.
Zarządca pamięci wirtualnej
" Przydział pamięci przebiega
dwustopniowo:
 zarezerwowanie części przestrzeni adresowej procesu
 zatwierdzenie przydziału poprzez wygospodarowanie
miejsca w pliku stronicowania
miejsca w pliku stronicowania
" Do reprezentowania bloku pamięci
wspólnej dla dwóch procesów system
wprowadza rozwiÄ…zanie pod nazwÄ…
obiektu sekcji (section object). Po
otrzymaniu uchwytu do obiektu sekcji
procesowi wolno odwzorować tylko
potrzebny fragment pamięci. Fragment ten
jest nazywany widokiem.
Zarządzanie pamięcią
" Oprócz pamięci wirtualnej Win32 Api
pozwala na korzystanie z:
 plików odwzorowanych w pamięci  umożliwia
dostęp do obszaru pamięci przez różne procesy
które używają tego samego pliku
które używają tego samego pliku
 stosu (sterty, heap)  jest obszarem
zarezerwowanej przestrzeni adresowej na
poczÄ…tku jest to obszar 1MB dla procesu
 lokalnej pamięci wątków
Windows NT File System (NTFS)
" FAT16 - 16 bitów - 65536 sektorów
logicznych (cluster) - < 2 GB
" HPFS - 232 sektorów fizycznych - < 4
" HPFS - 232 sektorów fizycznych - < 4
GB
" FAT32 (Windows 95 OEM Service
Realase 2 , Windows 98) - > 4 GB
" NTFS - 264 sektorów logicznych ( 16
1018 )
zbiór < 264 bajtów
Windows NT File System (NTFS)
" nazwa zbioru 255 znaków w systemie Unicode ( 16
bitowy zapis znaków ) - spacje i kropki
" możliwość zapisu dodatkowych własności zbioru
" indeksowanie własności zbioru w celu łatwego
" indeksowanie własności zbioru w celu łatwego
odnalezienia zbioru spełniającego dane kryteria
" ochrona poprawności oparta na systemie
transakcyjnym
" obsługa zapisu nadmiarowego (RAID 1 do 5)
" dynamiczne usuwanie błędnych sektorów
Windows NT File System (NTFS)
" PodstawowÄ… jednostkÄ… systemu NTFS jest
tom (volume). Tom jest tworzony przez
program administrowania dyskiem.
" Tom może obejmować część dysku lub
cały dysk, może też rozciągać się na kilka
cały dysk, może też rozciągać się na kilka
dysków. Wszystkie metadane są
pamiętane w zwykłym pliku.
" Każdy plik w systemie NTFS jest
opisywany przez jeden lub więcej
rekordów tablicy przechowywanej w
specjalnym pliku o nazwie: główna tablica
plików (master file table MFT)
Współpraca NTFS z systemem
LFS
Zapis transakcji
Menedżer wejścia/wyjścia
plik zmian
Program obsługi
(log file service)
Zapis i odczyt
NTFS
Program obsługi
systemu
systemu
odpornego na
Menedżer
błędy
pamięci
podręcznej
Program obsługi
dysku
Menedżer pamięci
wirtualnej
Zapis zbioru na dysku
Sektory wirtualne (VC) Sektory logiczne (LC)
1
541
2
542
3
544
543
Sektory na dysku mają postać tzw. cluster o wielkości od 512 bajtów
do 4 KB (standardowo dla dużych dysków)
Główna tablica plików(Master File
Table)
" MFT jest tablicą rekordów ( 1kB ) zawierających informacje o:
MFT
częściowa kopia informacji o MFT
pliku zmian
wolumenie
wolumenie
tablicy definicji atrybutów
kartotece głównej
mapie bitowej dysku
zbiorze uruchomieniowym systemu (boot)
zbiorze uszkodzonych sektorów
zbiorach użytkowników i kartotekach
...
Zapisy plików (File Records)
Postać dla małych zbiorów
MFT
Małe atrybuty plików są przechowywane w
samym rekordzie MFT. W przypadku dużych
plików lub mocno pofragmentowanych konieczne
plików lub mocno pofragmentowanych konieczne
jest użycie rekordów nadmiarowych.
Informacje podstawowe Nazwa zbioru Deskryptor bezpieczeństwa Dane
dla dużych zbiorów
Dane Dane
Windows NT - bezpieczeństwo
" Identyfikator użytkownika oraz hasło w procesie logowania.
" Prawa dostępu do zasobów systemu.
" System kontroli bezpieczeństwa pozwalający na rejestrację
działań niedozwolonych.
" Ochrona pamięci - zabezpiecza przed dostępem do obszarów
pamięci wirtualnej oraz zapewnia, że w przekazywanych innym
procesom obszarach pamięci fizycznej nie pozostaną ślady po
procesom obszarach pamięci fizycznej nie pozostaną ślady po
bieżącym procesie (dirty data).
Windows NT - lista kontroli dostępu
(acces control list)
Obiekt - plik
Nagłówek
.
obiektu
Identyfikator
Lista kontroli dostępu
bezpieczeństwa
.
Zezwolenie
Zezwolenie Zezwolenie
dla grupy
dla grupy
dla USER1 dla wszystkich
dla USER1 dla wszystkich
TEAM1
na czytanie na wykonanie
Na zapis
Element
kontroli
dostępu (ACE)
Windows NT - bezpieczeństwo
" Podczas sprawdzania tożsamości użytkownika przez proces
rejestracyjny (log in process) procesowi użytkownika przypisuje
się obiekt żetonu dostępu. Żeton dostępu zawiera: identyfikatory
bezpieczeństwa, identyfikatory grup, przywileje, określenie grupy
podstawowej i zastępczą listę kontroli dostępu.
" Każdy obiekt jest chroniony przez listę kontroli dostępu (access-
control list). Lista ta zawiera identyfikatory bezpieczeństwa .
control list). Lista ta zawiera identyfikatory bezpieczeństwa .
Sprawdzanie odbywa siÄ™ jedynie podczas otwierania obiektu.
Wewnętrzne usługi systemu NT, które zamiast ubiegania się o
uchwyty do obiektów stosują wskaz
niki, omijajÄ… sprawdzanie
poprawności dostępu.
" Jedno z pól w żetonie nadzoruje sposób doglądania obiektu.
Operacje doglÄ…dane sÄ… odnotowywane w systemowym dzienniku
działań nadzorowanych.
Definicja
" Sztuczna inteligencja (artificial
intelligence) jest to dział informatyki
zajmujÄ…cy siÄ™ badaniami nad
systemami inteligentnymi, ich
systemami inteligentnymi, ich
modelowaniem, konstrukcjÄ… oraz
wykorzystaniem do wspomagania i
substytucji pracy umysłowej
człowieka oraz do głębszego
zrozumienia ludzkiego sposobu
rozumowania.
Definicja
" Def: Sztuczna Inteligencja (Artificial Intelligence,
AI) to dziedzina nauki zajmujÄ…ca siÄ™
rozwiązywaniem zagadnień efektywnie
niealgorytmizowalnych w oparciu o modelowanie
wiedzy.
Inne definicje:
Inne definicje:
" AI to nauka mająca za zadanie nauczyć maszyny
zachowań podobnych do ludzkich.
" AI to nauka o tym, jak nauczyć maszyny robić
rzeczy które obecnie ludzie robią lepiej.
" AI to nauka o komputerowych modelach wiedzy
umożliwiających rozumienie, wnioskowanie i
działanie.
Definicja
" Inteligencja Obliczeniowa (Computational
Intelligence) ma na celu rozwiÄ…zywanie
zagadnień efektywnie
niealgorytmizowalnych przy pomocy
obliczeń. AI jest jej częścią korzystającą z
obliczeń. AI jest jej częścią korzystającą z
modelowania wiedzy, inne obszary CI nie
korzystajÄ… z metod symbolicznych.
Definicja
" CI zajmuje się modelowaniem procesów
percepcji, pamięci, sterowania, reakcji, zachowań
sensomotorycznych; zaÅ›
" AI modelowaniem wyższych czynności
poznawczych: myślenia, rozumowania,
poznawczych: myślenia, rozumowania,
rozwiązywania problemów, logiką, językiem.
" AI to część CI posługująca się symboliczną
reprezentacją wiedzy, inżynierią wiedzy,
tworzeniem systemów ekspertowych.
" CI zmierza do automatyzacji procesów akwizycji
wiedzy z obserwacji, analizy danych, percepcji,
kategoryzacji, aproksymacji.
Soft
Computing
Optymalizacja
badania operacyjne
Wizualizacja
Logika Sieci Algorytmy
rozmyta neuronowe ewolucyjne
Metody
Metody
statystyczne
Data
CI  dane numeryczne
mining
+ wiedza
AI  dane symboliczne
Rachunek
Systemy
prawdopodobieństwa
ekspertowe
Rozpoznawanie
Uczenie
wzorców
maszynowe
Realizacja
" Cyc (czyt. sajk)  projekt majÄ…cy na celu
stworzenie kompletnej bazy wiedzy, tak zwanego
zdrowego rozsÄ…dku. CYC zawiera w podstawowej
wersji ponad milion reguł. Ma to stanowić
podstawę, która umożliwi programom AI,
przeprowadzanie rozumowania podobnego do
ludzkiego.
ludzkiego.
" Projekt został zapoczątkowany w 1984 roku,
przez dr Douglasa Lenata.
" Struktura bazy wiedzy pozwala na automatyczne
przeprowadzenie rozumowania i wyciÄ…ganie
wniosków. Jednym z pierwszych praktycznych
zastosowań systemu jest CycSecure, który bada
bezpieczeństwo rzeczywistej sieci komputerowej
przeprowadzając symulacje ataków na tę sieć.
" Zwiększa się zainteresowanie bazą wiedzy CYC
Realizacja
" Projekty AI finansowane przez
DARPA (Department of Defense
Advanced Research Projects
Agency) - automatyczne samoloty i
Agency) - automatyczne samoloty i
czołgi; w 2005 roku 5
autonomicznych pojazdów
przejechało 200 km przez pustynię w
stanie Nevada.
" DARPA Urban Challenge
Realizacja
" Nagroda Loebnera - coroczny
konkurs polegajÄ…cy na napisaniu
chatbota z którym rozmowa zostanie
przez sędziów uznana za najbardziej
przez sędziów uznana za najbardziej
podobną do rozmowy z człowiekiem.
Realizacja
" Komputerowe wspomaganie
projektowania (CAD) z
wykorzystywaniem wnioskowania
logicznego na masowo równoległych
logicznego na masowo równoległych
komputerach.
Realizacja
" Inżynierowie IBM rzucili nietypowe wyzwanie mistrzom
amerykańskiego teleturnieju Jeopardy!. Wystawili swojego
"zawodnika" - projekt "Watson", czyli superkomputer
pracujÄ…cy pod kontrolÄ… przygotowywanego od kilku lat
oprogramowania. Pierwsze, próbne starcie należało do
maszyny.
" "Watson" to tworzony przez IBM program potrafiÄ…cy
interpretować ludzki język, "rozumieć" sens zdań i
samodzielnie formułować odpowiedzi. Generalnym
sprawdzianem działania systemu ma być wzięcie udziału w
sprawdzianem działania systemu ma być wzięcie udziału w
teleturnieju Jeopardy! (na którego licencji emitowany był w
teleturnieju Jeopardy! (na którego licencji emitowany był w
TVP program Va Banque).
" Przeprowadzony krótki pojedynek pokazał, że twór IBM ma
szansę wygrać konkurs. W pierwszej rundzie próbnej,
Watson zdobył 4400 dolarów, podczas gdy pozostali dwaj
zawodnicy 3400 i 1200 dolarów. Komputer odpowiedział na
wszystkie pytania bezbłędnie, podobnie zresztą jak ludzie.
" Oprogramowanie "Watson" jest uruchomiane jest na
jednym z superkomputerów IBM, stworzonym z procesorów
POWER7 i mającym do dyspozycji 15 TB pamięci
operacyjnej. System bierze pod uwagę różne możliwe
odpowiedzi i wybiera tÄ™ najbardziej prawdopodobnÄ….
Realizacja
" Algorytm Dijksry
" Algorytm najkrótszej drogi w grafie,
buduje drzewo najkrótszych dróg metodą
zachłanną (jedna z metod heurystycznych) .
Używana przez algorytm OSPF routingu w
Używana przez algorytm OSPF routingu w
sieciach komputerowych.
Zadania AI
" Dowodzenie twierdzeń i
wnioskowanie
" Gra w szachy, warcaby i inne gry o
wysokim stopniu złożoności np. go
" Robotyka
" Robotyka
" Widzenie komputerowe
" Rozpoznawanie obrazów
" Systemy ekspertowe i systemy z
bazÄ… wiedzy, akwizycja wiedzy
często nieuświadomionej (intuicja)
" Systemy uczÄ…ce siÄ™
Zadania AI
" Język naturalny: rozumienie,
tłumaczenie maszynowe, rozumienie
mowy mówionej
" Programowanie automatyczne lub
autoprogramowanie. Opis
autoprogramowanie. Opis
algorytmów przy pomocy języka
naturalnego, automatyczne pisanie
programów, modyfikacja swojego
własnego programu, programowanie
dostępu do baz danych dla
menedżerów.
Dlaczego AI
" Przestrzeń szukania może być
nieskończona lub ogromnie wielka.
" Dla warcabów jest około 1040
różnych gier, 5·1020 pozycji figur!
" Liczba gier w szachach jest rzędu
10120 - tyle jest liści drzewa gry!
Średnio b=35, więc 20 ruchów daje
3520 ~7.6 x 1030 możliwości.
" Kostka Rubika b=13.3, dla 15 ruchów
daje ok. 1017 możliwości.
Metody poszukiwania rozwiÄ…zania
Åšlepe Heurystyczne
Programowanie
dynamiczne
dynamiczne
Szukania
Szukania
Gradientowe
W głąb W szerz wiązką
Rozgałęziaj
Niedeterministyczne
i ograniczaj
Monte Stopniowe Algorytmy
Carlo studzenie genetyczne
130
ALGORYTMY NIEDERMINISTYCZNE
Jedną z pierwszych metod niedeterministycznych była
metoda Monte Carlo wprowadzona w trakcie prac nad
bronią jądrową w Los Alamos przez Stanisława Marcina
Ulama oraz Enrico Fermiego, Johna von Neumann a i
Nicholasa Metropolisa.
Stanisław Marcin Ulam (ur. 13
kwietnia 1909 we Lwowie, zm. 13
kwietnia 1909 we Lwowie, zm. 13
maja 1984 w Santa Fe)  polski i
amerykański matematyk (w 1943
przyjÄ…Å‚ obywatelstwo
amerykańskie), przedstawiciel
lwowskiej szkoły matematycznej.
Współtwórca amerykańskiej bomby termojądrowej Projekt
Teller-Ulam.(anegdota mówi, że nazwa powstała dzięki
wujowi Ulama przegrywajÄ…cemu majÄ…tek w kasynie Monte
Carlo w Monako)
131
ALGORYTMY NIEDERMINISTYCZNE
Metoda Monte Carlo  dokonuje siÄ™ szeregu
losowań punktu w przestrzeni rozwiązań z
rozkładem jednostajnym lub innym
określonym z góry. Wyboru dokonuje się
poprzez proste porównywanie wartości
poprzez proste porównywanie wartości
funkcji celu dla otrzymywanych punktów.
132
ALGORYTMY NIEDERMINISTYCZNE
Inna metodÄ… wprowadzajÄ…cÄ… element niedeterministyczny
jest metoda symulowanego wyżarzania. W metodzie
symulowanego wyżarzania, która może być łączona z
innymi metodami deterministycznymi i
niedeterministycznymi nowo wygenerowany punkt nie
zawsze staje siÄ™ rozwiÄ…zaniem roboczym. Dzieje siÄ™ tak
wówczas, gdy poprawia on wartość funkcji celu,
wówczas, gdy poprawia on wartość funkcji celu,
natomiast w przeciwnym przypadku, akceptacja
następuje z prawdopodobieństwem równym
ëÅ‚ öÅ‚
"f
pa = expìÅ‚ -
÷Å‚
T
íÅ‚ Å‚Å‚
133
ALGORYTMY NIEDERMINISTYCZNE
gdzie |" jest modułem różnicy funkcji celu w starym i
"f|
"
"
nowo wygenerowanym punkcie, T >0 jest parametrem
zwanym temperaturÄ…. Niezmiernie istotne jest dobranie
szybkości malenia temperatury w kolejnych iteracjach.
Następną metodą, której głównym zadaniem jest
uniknięcie bardzo częstej cechy jaką jest utykanie w
zamkniętej trajektorii po której porusza się rozwiązanie
zamkniętej trajektorii po której porusza się rozwiązanie
metody, jest metoda tabu. Idea poszukiwania z tabu
polega na wyposażeniu algorytmu w pamięć
dotychczasowych punktów. Punkty zapamiętane są
tabu i ich ponowne osiągnięcie jest zakazane. W celu
uniknięcia problemów z rozmiarem pamięci, tabu jest
zorganizowane na zasadzie buforu cyklicznego (FIFO) o
ograniczonej pojemności.
134
ALGORYTMY GENETYCZNE
Idea algorytmów genetycznych wywodzi się z teorii
ewolucji Darwina zgodnie z którą w przyrodzie
następuje ciągły proces doskonalenia i specjalizacji
żywych organizmów w celu jak najlepszego
przystosowania do środowiska w którym się znajdują.
Ponieważ w przyrodzie mechanizm ten wykorzystuje
zjawiska dziedziczenia zwiÄ…zane z informacjÄ… zapisanÄ…
w ciągu genów (czyli pojedynczych elementów
w ciągu genów (czyli pojedynczych elementów
niosących informację o żywym organizmie) tworzących
chromosomy czyli stałe składniki jądra komórkowego
roślin i zwierząt, , zbudowane głównie z kwasów
deoksyrybonukleinowego (DNA) i rybonukleinowego
(RNA) oraz z białek zasadowych, samoodwarzające się
przy każdym podziale komórki i rozdzielane między
jądra komórek pochodnych metody te zostały nazwane
metodami genetycznymi.
135
ALGORYTMY GENETYCZNE
Obecnie metody genetyczne sÄ… traktowane jako
zastosowanie algorytmów ewolucyjnych.
Wszystkie operacje wykonywane przez algorytmy
genetyczne operują w odróżnieniu od większości metod
deterministycznych na zbiorach rozwiązań. Każde
rozwiÄ…zanie jest analogicznie do metod
deterministycznych zbiorem wartości zmiennych
deterministycznych zbiorem wartości zmiennych
decyzyjnych. RozwiÄ…zanie charakteryzowane przez
wektor wartości zmiennych decyzyjnych jest nazywane
często przez analogie ze środowiskiem ożywionym 
osobnikiem, a zbiór rozwiązań czyli zbiór osobników 
populacjÄ….
136
ALGORYTMY GENETYCZNE
Przetwarzanie populacji
137
ALGORYTMY GENETYCZNE
W poczÄ…tkowym etapie zwanym inicjacjÄ… populacja
bazowa jest wypełniana losowo wygenerowanymi
osobnikami. Oczywiście proces ten jest zwykle bardziej
skomplikowany i może być powiązany z wyborem
rozkładu według którego następuje losowanie jak
również z bardzo istotnym problemem wyboru zakresu
poszczególnych zmiennych decyzyjnych.
poszczególnych zmiennych decyzyjnych.
Pozostawienie tutaj pełnej losowości nie daje zwykle
dużych szans na uzyskanie sensownego rozwiązania.
Umiejętność określenia zakresu zmiennych
decyzyjnych w których będzie poruszać się rozwiązanie
jest problemem kluczowym dla rzeczywistych
rozwiązań technicznych. Z tego względu wstępem do
stosowania metod genetycznych musi być
wykorzystanie odpowiedniej wiedzy inżynierskiej o
poszukiwanym rozwiÄ…zaniu.
138
ALGORYTMY GENETYCZNE
W następnym kroku dla każdego z osobników obliczana
jest wartość funkcji przystosowania. Funkcją
przystosowania w najprostszym przypadku może być
wartość funkcji celu dla zagadnień jednokryterialnych.
Może być ona jednak określona w sposób bardziej
skomplikowany dla zagadnień wielokryterialnych. Na
tym etapie powstaje problem stosowania ograniczeń.
Większość problemów technicznych to oczywiście
Większość problemów technicznych to oczywiście
problemy z ograniczeniami. Ograniczenia nie majÄ… przy
tym zwykle postaci jawnej czyli pozwalajÄ…cej siÄ™
przedstawić w postaci zależności zawierających
zmienne decyzyjne, ale postać skomplikowanych
algorytmów numerycznych modelujących
skomplikowane zjawiska fizyczne jak np. zjawisko
nagrzewania pod wpływem strat mocy związanym z
optymalizowanym procesem.
139
ALGORYTMY GENETYCZNE
Ponieważ sprawdzenie ograniczeń jest zwykle kosztowne
numerycznie powstaje problem w którym miejscu
procesu będziemy je wprowadzać  na początku czy na
jakimś etapie pośrednim czy na końcu.
Po określeniu wartości funkcji przystosowania następuje
dalszy proces zwany reprodukcjÄ… polegajÄ…cy na
kopiowaniu do populacji tymczasowej losowo
kopiowaniu do populacji tymczasowej losowo
wybranych osobników z populacji bazowej.
Prawdopodobieństwo wylosowania jest tu już zależne
od wartości funkcji przystosowawczej. Stosuje się
również losowanie ze zwracaniem czyli w populacji
pośredniej może się znalez
ć wielu takich samych
osobników o wysokiej wartości funkcji
przystosowawczej.
140
ALGORYTMY GENETYCZNE
Mechanizm krzyżowania i mutacji
141
ALGORYTMY GENETYCZNE
Następnie osobniki z populacji tymczasowej
poddawane sÄ… operacjom genetycznym 
krzyżowaniu i mutacji. Prawdopodobieństwo
krzyżowania i mutacji są parametrami
algorytmu. Dla osobników o n własnościach
zwanych genami losowany jest z rozkładem
zwanych genami losowany jest z rozkładem
równomiernym punkt przecięcia chromosomów
rodzicielskich a następnie powstałe części są
sklejane tworzÄ…c chromosom lub chromosomy
potomne.
142
ALGORYTMY GENETYCZNE
Operacja krzyżowania może mieć oczywiście
wiele różnych rozwiązań:
" klasyczne  para rodziców jeden potomek jak
na rysunku
" para rodziców  para potomków
" pojedynczy osobnik potomny tworzony w
wyniku tzw. krzyżowania globalnego w którym
występuje jeden osobnik wiodący i n
pomocniczych osobników rodzicielskich np.
oddzielnie dla każdego genu
143
ALGORYTMY GENETYCZNE
Wybór sposobu krzyżowania ma wpływ na rozkład cech w
populacji.
Techniki krzyżowania:
" jednopunktowe jak pokazano na rysunku
" dwupunktowe w którym chromosom (wektor zmiennych
decyzyjnych) dzielony jest na trzy części z których tylko
decyzyjnych) dzielony jest na trzy części z których tylko
część środkowa podlega wymianie
144
ALGORYTMY GENETYCZNE
" krzyżowanie równomierne w którym chromosom
potomny tworzony jest w następujący sposób
1
Å„Å‚
Xi dla ¾U(0,1),i < pe
ôÅ‚
Yi =
òÅ‚
ôÅ‚Xi2 w przeciwnym przypadku
ół
gdzie ¾U(0,1),i oznacza losowanÄ… liczbÄ™ losowÄ… z zakresu
gdzie ¾ ,i oznacza losowanÄ… liczbÄ™ losowÄ… z zakresu
<0,1> , a pe założony poziom przeskoku pomiędzy
chromosomem 1 i 2. Wartość ta może być przyjęta
arbitralnie bÄ…dz
losowana dla danej operacji. Typowo pe
jest przyjmowane równe 0,5.
145
ALGORYTMY GENETYCZNE
" Uśredniające
1 2 1
Y = X + ¾U(0,1) (X - X )
lub
lub
Yi = Xi1 +¾U(0,1),i (Xi2 - Xi1)
146
ALGORYTMY GENETYCZNE
W klasycznej metodzie krzyżowania rolę genów
pełniły wartości binarne, a więc operacja
krzyżowania wymagała tylko prostej operacji
logicznej. Taka technika jest też czasami
stosowana do algorytmów praktycznych jednak
nie jest generalnie zalecana ponieważ zakłóca
znaczenie poszczególnych genów, którymi
znaczenie poszczególnych genów, którymi
powinny być zmienne decyzyjne a nie ich
powinny być zmienne decyzyjne a nie ich
elementy takie jak reprezentacja binarna danej
wielkości. Dlatego zalecana jest technika
krzyżowania uśredniającego najlepiej oddająca
sens poszukiwania nowego rozwiÄ…zania jako
pośredniego pomiędzy dwoma rozwiązaniami
bazowymi.
147
ALGORYTMY GENETYCZNE
Mutacje są techniką uzyskania populacji osobników, które
lepiej pokrywają obszar rozwiązania niezależnie od
rozkładu osobników w populacji bazowej. Polega ona
na perturbacji wartości zmiennej decyzyjnej znajdującej
siÄ™ w genie za pomocÄ… zmiennej losowej o wybranym
rozkładzie.
Yi = Xi + ¾r,i
Yi = Xi + ¾r,i
gdzie ¾r,i jest zmiennÄ… losowÄ… o rozkÅ‚adzie r definiowanÄ…
indywidualnie dla każdego genu.
148
ALGORYTMY GENETYCZNE
Używane rozkłady:
" normalny o funkcji gÄ™stoÅ›ci (standaryzowany m =0 Ã
Ã=1)
Ã
Ã
ëÅ‚
ëÅ‚
1 1 x - m2 öÅ‚öÅ‚
expìÅ‚ -
ìÅ‚ ÷Å‚÷Å‚
ìÅ‚ ÷Å‚÷Å‚
ìÅ‚
2 Ã
à 2Ą
íÅ‚ Å‚Å‚
íÅ‚ Å‚Å‚
" Cauchego o funkcji gęstości
" Cauchego o funkcji gęstości
1 Ã
2
Ä„
à + x - m
( )2
149
ALGORYTMY GENETYCZNE
" prostokÄ…tny
Yi = Xi + (2Ãi¾U (0,1),i -Ãi )
150
ALGORYTMY GENETYCZNE
Z tym etapem działania algorytmu genetycznego
są związane różnego rodzaju strategie
ewolucyjne:
" strategia (1+1)  przetwarzany jest jeden
osobnik bazowy. W każdym kroku generowany
jest nowy osobnik poprzez modyfikowanie
każdego genu rozkładem normalnym. Do
każdego genu rozkładem normalnym. Do
dalszego procesowania przyjmowany jest
osobnik lepszy
" strategia 1/5 sukcesów  zmiana à w zależnoÅ›ci
Ã
Ã
Ã
od ilości sukcesów mutacji (uzyskania
osobników o lepszej funkcji przystosowawczej)
 jeżeli liczba sukcesów jest większa od 1/5
wartość ulega zwiększeniu 1/0,82 razy, jeżeli
mamy dokładnie 1/5 pozostaje bez zmian i dla
mniejszej ilości maleje 0,82 razy
151
ALGORYTMY GENETYCZNE
" strategia µ + 
µ :
µ 
µ 
 osobnik ma strukturę składającą się z dwóch chromosomów:
pierwszy zawiera wartości zmiennych niezależnych, drugi
wektor à zawierający wektor standardowych odchyleń
wykorzystywanych podczas mutacji. Mutacji poddawane sÄ…
nie tylko wartości zmiennych niezależnych ale także wartości
standardowych odchyleń.
 bazowa populacja zawiera µ osobników
152
ALGORYTMY GENETYCZNE
" strategia µ + 
µ :
µ 
µ 
 z populacji tej generuje siÄ™ populacjÄ™ potomnÄ… o  osobnikach.
Proces generowania przebiega następująco: wielokrotnie
powtarza się losowanie (ze zwracaniem) osobnika spośród
populacji bazowej do populacji pomocniczej. PopulacjÄ™
pomocniczą poddaje się krzyżowaniu i mutacji. Nową
populacjÄ™ bazowÄ… tworzy µ najlepszych osobników wybranych
µ
z obu populacji.
153
ALGORYTMY GENETYCZNE
Następnym etapem działania algorytmu
genetycznego jest reprodukcja. Jest to proces
przenoszenia osobników z populacji
tymczasowej do potomnej. Proces ten wymaga
wyboru pomiędzy eksploatacja 
przeszukiwaniem obszaru w celu wyznaczenia
przeszukiwaniem obszaru w celu wyznaczenia
ekstremum lokalnego a eksploracja 
osiągnięciem obszaru zawierającego
ekstremum globalne.
154
ALGORYTMY GENETYCZNE
Reprodukcja może przebiegać według szeregu
schematów:
" reprodukcja proporcjonalna  dla każdego
osobnika określa się wartość
prawdopodobieństwa reprodukcji zgodnie z
zależnością
zależnością
Åš(X )
pr (X ) =
Åš(Y )
"
Y"Pt
155
ALGORYTMY GENETYCZNE
gdzie X oznacza osobnika, a Åš
Åš(X) jest jego funkcjÄ…
Åš
Åš
przystosowania. Następnie obliczana jest dystrybuanta
rozkładu reprodukcji
i
i j
Pr (X ) = pr (X )
"
j=1
po czym w celu wyznaczenia osobnika do reprodukcji,
dokonujemy z rozkładem jednostajnym losowania liczby a
z przedziału (0,1). Jeśli spełnia ona warunek a d" Pr(X1) to
d"
d"
d"
reprodukcji podlega osobnik X1 , w przeciwnym
przypadku reprodukowany jest osobnik Xi dla którego
zachodzi
Pr(Xi-1) < a d" Pr(Xi).
d"
d"
d"
156
ALGORYTMY GENETYCZNE
" reprodukcja rangowa  w tej metodzie
reprodukcja osobnika zależy od jego rangi,
wielkości charakteryzującej osobnika w
populacji. Wartość ta może być określona
dwojako: populacja jest sortowana według
wartości funkcji przystosowania i pozycja
wartości funkcji przystosowania i pozycja
określa rangę lub osobniki o jednakowej
wartości lub zakresie funkcji przystosowania
otrzymują jednakowe wartości rang (liczby
całkowite od zera). Po określeniu rangi definiuje
się zmienną losową przypisując każdemu
osobnikowi prawdopodobieństwo reprodukcji
na podstawie jego rangi. Wybór funkcji jest
arbitralnÄ… decyzjÄ….
157
ALGORYTMY GENETYCZNE
Najczęściej używane są:
 funkcja liniowa
r(X )
Pr (X ) = a + k(1- )
rmax
gdzie a i k sÄ… dobierane tak, aby
µ
pr (X ) = 1 0 d"pr (X ) d" 1
"
i=1
158
ALGORYTMY GENETYCZNE
 funkcja potęgowa
Pr (X ) = a + k(rmax - r(X ))b
przy czym prawdopodobieństwo może ulec zmianie wraz z
przy czym prawdopodobieństwo może ulec zmianie wraz z
numerem generacji
159
ALGORYTMY GENETYCZNE
" reprodukcja progowa  jest szczególnym przypadkiem
reprodukcji rangowej. Funkcja prawdopodobieństwa
reprodukcji jest określona wzorem
1
Å„Å‚
dla 0 d" r(X)< Áµ
ôÅ‚
pr (X ) = Áµ
pr (X ) = Áµ
òÅ‚
òÅ‚
ôÅ‚
ôÅ‚0 w przeciwnym przypadku
ół
wartość Á jest wskaz
nikiem nacisku selektywnego  im
Á
Á
Á
jest ona mniejsza, tym mniej osobników będzie
reprodukować
160
ALGORYTMY GENETYCZNE
" reprodukcja turniejowa  w każdym kroku dokonuje się
najpierw wyboru podpopulacji zawierajÄ…cej q
osobników. Następnie przeprowadza się turniej
pomiędzy osobnikami. Zwycięzcą zostaje osobnik o
większej wartości funkcji przystosowania. Osobnik ten
jest kopiowany do populacji potomnej. Proces może
przebiegać ze zwracaniem lub nie.
przebiegać ze zwracaniem lub nie.
161
ALGORYTMY GENETYCZNE
Następnym krokiem algorytmu genetycznego jest
sukcesja czyli tworzenie następnej populacji bazowej:
" sukcesja z całkowitym zastępowaniem  nową
populacjÄ… bazowÄ… staje siÄ™ populacja potomna
" sukcesja z częściowym zastępowaniem  nowa
populacja zawiera osobniki zarówno z populacji
populacja zawiera osobniki zarówno z populacji
potomnej, jak i ze starej populacji bazowej. Mechanizm
usuwania może może mieć wiele wariantów:
 usuwanie najgorzej przystosowanych osobników
 usuwanie osobników najbardziej podobnych do potomnych
 usuwanie losowo wybranych osobników
162
ALGORYTMY GENETYCZNE
" elitarna - część osobników ze starej populacji bazowej
przechodzi do nowej populacji w taki sposób, aby
zagwarantować przeżycie co najmniej najlepszego
osobnika. Elitarny schemat sukcesji poprawia
zbieżność algorytmu, ale powoduje tendencję do
 osiadania w obszarach maksimów lokalnych.
INNE ALGORYTMY
163
NIEDETERMINISTYCZNE
" Metoda roju pszczół lub roju cząstek wykorzystuje
grupę rozwiązań do poszukiwania ekstremum zamiast
pojedynczego rozwiÄ…zania. Metoda jest nieco podobna
do metody pełzającego simpleksu, ale wykorzystuje
większą liczbę rozwiązań.
" Algorytmy bakteriologiczne (bakteryjne) wykorzystujÄ…
ideę, że w heterogennym środowisku nie można znalez
ć
ideę, że w heterogennym środowisku nie można znalez
ć
osobnika, który odpowiadałby cechom całego
środowiska. Z tego względu trzeba operować na
wartościach dla zbiorowości. Dają one lepsze wyniki w
problemach pozycjonowania np. anten GSM lub w
zgłębianiu danych (data mining).
INNE ALGORYTMY
164
NIEDETERMINISTYCZNE
" Metoda entropii (cross-entropy)  bardzo podobna do
algorytmów genetycznych
" Algorytm kulturalny  algorytmy genetyczne
uzupełnione o element bazy wiedzy o problemie
" Optymalizacja ekstremalna  istota polega na
eliminowaniu najgorszych rozwiązań zamiast rozwijania
eliminowaniu najgorszych rozwiązań zamiast rozwijania
najlepszych
" Poszukiwanie harmonii  jest algorytmem udajÄ…cym
muzyków w procesie improwizacji
INNE ALGORYTMY
165
NIEDETERMINISTYCZNE
" Algorytmy memetyczne  (neologizm meme pochodzi z
książki Richard a Dawkins a  The Selfish Gene z 1976
roku)  obejmuje wszelkiego rodzaju algorytmy
hybrydowe Å‚Ä…czÄ…ce metody genetyczne z metodami
klasycznymi. Nazwa pochodzi od słowa meme
określającego gen, który może się sam zmieniać
dostosowując się do środowiska. Metody hybrydowe
dostosowując się do środowiska. Metody hybrydowe
możemy podzielić na metody szeregowe  kiedy przy
pomocy metody genetycznej poszukujemy najlepszego
punktu startowego dla metody deterministycznej oraz
na metody równoległe, gdzie metody deterministyczne
mogą być używane tak jak algorytm mutacji do zmiany
cech pojedynczego osobnika.
INNE ALGORYTMY
166
NIEDETERMINISTYCZNE
" Algorytmy memetyczne  (neologizm meme pochodzi z
książki Richard a Dawkins a  The Selfish Gene z 1976
roku)  obejmuje wszelkiego rodzaju algorytmy
hybrydowe Å‚Ä…czÄ…ce metody genetyczne z metodami
klasycznymi. Nazwa pochodzi od słowa meme
określającego gen, który może się sam zmieniać
dostosowując się do środowiska. Metody hybrydowe
dostosowując się do środowiska. Metody hybrydowe
możemy podzielić na metody szeregowe  kiedy przy
pomocy metody genetycznej poszukujemy najlepszego
punktu startowego dla metody deterministycznej oraz
na metody równoległe, gdzie metody deterministyczne
mogą być używane tak jak algorytm mutacji do zmiany
cech pojedynczego osobnika.
167
OPTYMALIZACJA KOOPERACYJNA
Optymalizacja kooperacyjna jest metodÄ… zaproponowanÄ…
przez chińskiego matematyka Xiao-Fei Huang. Metoda
ta używa prostej funkcji jako ograniczenia dolnego dla
funkcji celu w procesie znajdowania jej globalnego
minimum. Metoda sukcesywnie zacieśnia tą funkcję tak,
aż jej minimum globalne dotyka minimum globalnego
funkcji celu. Następnie jest poszukiwane minimum tej
funkcji celu. Następnie jest poszukiwane minimum tej
uproszczonej funkcji co jest oczywiście prostsze.
Metoda ma podobne korzenie jak metoda płaszczyzny
przekroju.
168
OPTYMALIZACJA KOOPERACYJNA
Funkcja używana do rozwiązania może być przedstawiona
w postaci sumy
¨(A)= ¨1(a1)+ ¨2(a2)+L+ ¨n(an)
OczywiÅ›cie funkcja ¨(A) jest tak dobierana, aby jej
OczywiÅ›cie funkcja ¨(A) jest tak dobierana, aby jej
globalne minimum było łatwe do znalezienia.
169
OPTYMALIZACJA KOOPERACYJNA
Załóżmy teraz, że funkcja celu daje się rozłożyć na n
składników postaci
F(A)= F1(A)+ F2(A)+L+ Fn(A)
Postępowanie iteracyjne polega na modyfikowaniu funkcji
Postępowanie iteracyjne polega na modyfikowaniu funkcji
¨(A) zgodnie z zależnoÅ›ciÄ…
n
ëÅ‚
(k-1)
ìÅ‚ ÷Å‚
¨i (k )(ai )= minìÅ‚ Fi(A)+Ä… ( )öÅ‚
a
"¨ j
j
÷Å‚ dla i =1,2,K,n
A\ai
j=1
íÅ‚ Å‚Å‚
170
OPTYMALIZACJA KOOPERACYJNA
gdzie Ä… jest parametrem kontrolujÄ…cym wzajemne
oddziaływanie poszczególnych podzadań minimalizacji,
a opis A\ai oznacza, że minimalizacja odbywa się
względem wszystkich zmiennych za wyjątkiem ai.
Ponieważ funkcje ¨i(A) sÄ… minimalizowane rozwiÄ…zanie
zbliża się do minimum funkcji celu, które może być
wyznaczone jako minimum tych funkcji. Dla każdej
wyznaczone jako minimum tych funkcji. Dla każdej
zmiennej ai otrzymujemy różne wartości tej zmiennej w
każdym z podprocesów minimalizacji. Jeżeli wartości
zmiennej jest jednakowa mówimy o osiągnięciu
konsensusu dla tej zmiennej. Jeżeli konsensus zostaje
osiągnięty dla wszystkich zmiennych oznacza to
osiągnięcie optimum globalnego.
171
OPTYMALIZACJA KOOPERACYJNA
W celu polepszenia zbieżnoÅ›ci funkcje ¨(A) mogÄ… być
modyfikowane poprzez dodanie przesunięcia postaci
¨i (k )(ai )= ¨i (k )(ai )- min(¨i (k )(ai ))
xi
172
OPTYMALIZACJA WIELOKRYTERIALNA
Różne punkty widzenia mogą być wyrażone za pomocą
zadania optymalizacji wielokryterialnej. W tym
przypadku stosuje się więcej niż jedno kryterium
jakości
Qi = Qi(a1,a2...ar ) i =1,2...k
gdzie a1 do ar sÄ… zmiennymi decyzyjnymi naszego
gdzie a1 do ar sÄ… zmiennymi decyzyjnymi naszego
zadania.
Dla problemu optymalizacji wielokryterialnej możemy
zastosować dwa podejścia:
" osiągnięcie maksymalnego efektu przy minimalnych
nakładach
" optymalizacja jednoczesna, tak aby wiele (aż do k)
kryteriów jakości czy też wielkości charakterystycznych
osiągnęło wartości optymalne możliwie jednocześnie
173
OPTYMALIZACJA WIELOKRYTERIALNA
Przy dużej liczbie kryteriów jakości, ale nie tylko,
występują sprzeczności, które prowadzą do tego, że
odpowiednie kryteria jakości nie mogą być
jednocześnie zoptymalizowane przez określony zestaw
zmiennych decyzyjnych.
Generalnie nie istnieje więc zwykle pojedyncze
rozwiÄ…zanie problemu optymalizacji wielokryterialnej.
rozwiÄ…zanie problemu optymalizacji wielokryterialnej.
Zamiast tego możemy proponować zbiór rozwiązań,
które reprezentują najlepszy możliwy kompromis
pomiędzy warunkami. Taki zbiór rozwiązań jest
nazywany zbiorem Pareto-optymalnym.
174
OPTYMALIZACJA WIELOKRYTERIALNA
Dokładniej rozwiązanie może być traktowane jako Pareto-
optymalne wtedy i tylko wtedy jeżeli nie istnieje inne
rozwiązanie które jest dokładnie lepsze w sensie
jednego lub więcej kryterium jakości i nie jest gorsze w
sensie pozostałych kryteriów jakości.