Laboratorium
Zasady zaliczenia laboratorium
- Ocena z laboratorium bierze pod uwagę umiejętności nabyte w trakcie kursu oraz terminowość oddawania zadań
- Rozwiązania zadań należy wysyłać w terminie na przydzielone konto SVN, poza pierwszą listą którą należy oddać w terminie
- Rozwiązania zadań wysłane po danym terminie, ale do 1 tygodnia liczone są maks. za połowę punktów, po terminie 1 tygodnia liczone są za ZERO punktów
- Zadania z gwiazdką można wysyłać bez straty punktów do tygodnia po terminie oraz liczą się jako zadania DODATKOWE
- Wysłane rozwiązania, należy oddać na laboratorium, bez straty punktów na pierwszych lub drugich zajęciach po terminie SVN, na trzecich zajęciach (bez usprawiedliwień) zadania liczone są maks. za połowę punktów na czwartych zajęciach zadania liczone są za ZERO punktów (nawet zadania wysłane w terminie na SVN)
Lista 1 (Lab) Termin oddania do 17.10.2023 31.10.2023
Uwaga: Zadania z tej listy proszę nie wysyłać na SVN!
- (2pt)
Zainstaluj program do wirtualizacji VirtualBox lub QEMU
lub libvirt (można wykorzystać też dowolny inny program do wirtualizacji). Zapoznaj się z programem.
- (5pt)
Zainstaluj w środowisku wirtualnym dystrybucję Linuksa np. Ubuntu.
Pobierz obraz systemu tutaj.
Naucz się podstawowych komend obsługi systemu z konsoli
np.
cd, ls, cat, less, apt-get
itp.
- (8pt)
Zainstaluj w środowisku wirtualnym dystrybucję Linuksa Arch Linux.
Pobierz obraz systemu tutaj.
Naucz się podstawowych informacji o systemie oraz umiej wytłumaczyć w kilku zdaniach co najmniej
- Co to jest BIOS oraz UEFI?
- Co to jest GPT,
MBR?
- Co to jest i jak obsługiwać program do robienia partycji dysku np. fdisk?
Wykonaj podstawowe polecenia programu samodzielnie w maszynie wirtualnej
- Co to jest system plików i jakie systemy plików wykorzystuje Linux?
- Ogólne pytania z procesu instalacji
Przykładowe instalacje Arch Linuksa i
instrukcja oraz
instalacja w VirtualBox
- (10pt)*
Zainstaluj w środowisku wirtualnym system operacyjny z rodziny BSD
FreeBSD. Jako podstawowy system plików wybierz ZFS oraz wytłumaczyć co to są
jails oraz pokaż przykład zastosowania. Umiej zastosować wirtualizację z
wykorzystaniem bhyve.
Lista 2 (Lab) Termin wysłania na SVN do 31.10.2023
Na SVN proszę wysłać tylko zadania 3, 4. Resztę zadań należy oddać na pierwszych (lub drugich) zajęciach po terminie wysłania.
- (5pt)
Uruchom poniższy program w symulatorze MARIE (przełącz 'Output mode' na 'UNICODE'). Wytłumacz przy
oddawaniu jak on działa.
LOAD str_ptr
STORE tolower_ptr
JNS tolower
HALT
tolower_itr, DEC 0
tolower_ptr, HEX 0
tolower_idx, HEX 0
tolower_offset, HEX 20
tolower, HEX 0
tolower_while, LOAD tolower_ptr
ADD tolower_itr
STORE tolower_idx
CLEAR
ADDI tolower_idx
SKIPCOND 400
JUMP tolower_do
JUMPI tolower
tolower_do, ADD tolower_offset
OUTPUT
LOAD tolower_itr
ADD ONE
STORE tolower_itr
JUMP tolower_while
str_ptr, HEX 18 / memory location of str
str, HEX 48 / H
HEX 45 / E
HEX 4C / L
HEX 4C / L
HEX 4F / O
HEX D / carriage return
HEX 57 / W
HEX 4F / O
HEX 52 / R
HEX 4C / L
HEX 44 / D
HEX 0 / NULL char
/ constants
ONE, DEC 1
- (5pt)
Uruchom poniższy program w symulatorze MARIE (przełącz 'Output mode' na 'DEC'). Wytłumacz przy
oddawaniu jak on działa (źródła tego i innych przykładowych programów można znaleźć na stronie https://github.com/mathewmariani/MARIE-Examples).
Cond, LOAD COUNT / Load count into AC
SUBT TEN / Remove 10 from count
SKIPCOND 000 / Skipcond 000 if AC < 0
JUMP End / End Loop
Loop, LOAD COUNT / Load count into AC
ADD ONE / Increment Count by 1
STORE COUNT / Store AC in count
JNS Fibb
JUMP Cond / Check loop conditions
Fibb, HEX 000 / Store value for JNS
CLEAR / AC = 0
/ Fi = F1 + F2
ADD F1 / AC + F1
ADD F2 / AC + F2
STORE Fi / Fi = AC
/ F1 = F2
LOAD F2 / AC = F2
STORE F1 / F1 = AC
/ F2 = Fi
LOAD Fi / AC = Fi
STORE F2 / F2 = AC
/ Quick Output
LOAD Fi / AC = FI
OUTPUT / Output AC
JUMPI Fibb
End, HALT / Halt process
/ variables
COUNT, DEC 0 / count for loop
Fi, DEC 0
F1, DEC 0
F2, DEC 1
/ constant values
ZERO, DEC 0
ONE, DEC 1
TWO, DEC 2
THREE, DEC 3
FOUR, DEC 4
FIVE, DEC 5
SIX, DEC 6(
SEVEN, DEC 7
EIGHT, DEC 8
NINE, DEC 9
TEN, DEC 10
- (10pt)
Wytłumacz jak wykonane jest mnożenie dla MARIE (patrz przykład z symulatora).
Korzystając z tego przykładu napisz dzielenie z resztą. Wystarczy dzielenie bez znaku.
- (15pt)*
Napisz program dla MARIE, który wypisuje sinus i cosinus w arytmetyce stałoprzecinkowej
(Fixed-point arithmetic)
podobnie jak np.
1000*sin(x/1000) i 1000*cos(x/1000)
(dla dokładności do 3 miejsc) dla x=0,...,1000. Do obliczania możesz wykorzystać prosty
algorytm Marvin'a Minsky'ego patrz HAKMEM - ITEM 149
lub Reversing Sinclair's amazing 1974 calculator hack - half the ROM of the HP-35.
Lista 3 (Lab) Termin wysłania na SVN do 12.11.2023
Na SVN proszę wysłać tylko zadania 6, 7 i 8. Resztę zadań należy oddać najpóźniej na pierwszych (lub drugich) zajęciach po terminie 12.11.2023.
- (5pt)
Wytłumacz jakie pliki zawierają katalogi /dev, /proc oraz sys.
Wykorzystując polecenie dd odczytaj pierwszy sektor z
dysku głównego (uwaga na prawa dostępu) lub podpiętego pendrive'a i wyświetl przez hexdump -C.
Z katalogu proc wyświetl informacje o pamięci, procesorze i partycjach.
- (5pt)
Zapoznaj się z programem ps (man ps). Naucz się posługiwać tym programem, aby umieć sprawdzać co najmniej
istnienie i parametry wybranych procesów (PID procesu i rodzica, stan procesu,
priorytet, nice, ilość pamięci, zużycie czasu procesora). Uruchom też kilka
terminali pokaż jakie urządzenie tty wykorzystują. Wykonując komendę ps axjf
pokaż wszystkie procesy które podpięte są do tych terminali (kolumna TTY).
- (5pt)
Zapoznaj się z kompilatorem języka C (polecenie gcc) oraz języka C++ (polecenie
g++). Uruchom poniższy program w języku C.
$ cat > test.c
#include <stdio.h>
int main(int argc, char *argv[])
{
printf("Hello, World!\n");
return 0;
}
^D
$ gcc -Wall -pedantic test.c
$ ./a.out
Wytłumacz każdy z powyższych kroków. Co oznaczają opcje -Wall oraz -pedantic?
Zobacz man gcc.
- (5pt)
Pokaż na przykładzie (np. sleep 1000, sleep 1001, ...) zarządzanie zadaniami wykorzystując
<polecenie> & - uruchamianie w tle (background) oraz jobs, fg, bg, kill oraz ^Z.
Uruchom kilka zadań w tle i pokaż jak można nimi zarządzać, czyli zatrzymywać,
wznawiać oraz kończyć ich działanie. Pokaż jak uruchomione zadanie (nie w tle), można
w czasie działania uruchomić w tle np. wykonując komendę sleep 100 (bez &)
w czasie działanie przełącz je do działania w tle.
- (5pt)
Poleceniem mkfifo (man mkfifo) utwórz potok nazwany (ang.
named FIFO). Wywołując polecenie cat w różnych terminalach
spowoduj wpisywanie danych do potoku przez jeden(ne) proces(y), i odczytywanie
i wyświetlanie ich przez inne. Zaobserwuj, kiedy polecenie cat czytające
z potoku czeka na więcej danych, a kiedy kończy pracę. Analogicznie, kiedy
czeka na więcej danych (z klawiatury) polecenie cat piszące do potoku?
- (8pt)
Napisz program w języku C, który wykorzystując sekwencje Esc
(ang. escape sequences) standardu ANSI wyświetli na ekranie napis "Hello, World!", po kolei we wszystkich dostępnych
przez terminal kolorach. Czy terminal może wyświetlić 256 lub więcej kolorów?
- (10pt)
Napisz potok poleceń (może być w skrypcie), który zamienia wszystkie nazwy plików w danym katalogu
(bez podkatalogów) na małe litery, czyli wszystkie duże litery występujące w
nazwach plików zostaną zamienione na małe, a małe litery pozostają oczywiście
dalej małe. Skrypt powinien działać poprawnie na takich nazwach plików jak " ABC DEF",
"-AbC aBc" i "--ABC DEF". Przy oddawaniu, proszę podane nazwy plików zakładać w konsoli korzystając z polecenia touch.
- (15pt)*
W shellu można przekierować standardowe wejście, wyjście i wyjście błędu przez wykorzystanie
przekierowań <, > oraz 2>. Załóżmy jednak że już wykonaliśmy komendę i dopiero w czasie działającego już
procesu chcemy zmienić wejście, wyjście lub wyjście błędu. Na przykład
$ sleep 1000 &
[1] 4096
$ ls -l /proc/4096/fd
lrwx------ 1 user users 64 10-30 12:32 0 -> /dev/pts/4
lrwx------ 1 user users 64 10-30 12:32 1 -> /dev/pts/4
lrwx------ 1 user users 64 10-30 12:32 2 -> /dev/pts/4
$ # tutaj zmieniamy wyjście działającego procesu 4096 na plik /tmp/foo
$ # oczywiście nie kończymy działa procesu np. przez kill 4096 w trakcie
$ # zmiany wyjścia ...
$ ...
$
$ ls -l /proc/4096/fd
lrwx------ 1 user users 64 10-30 12:32 0 -> /dev/pts/4
lrwx------ 1 user users 64 10-30 12:32 1 -> /tmp/foo
lrwx------ 1 user users 64 10-30 12:32 2 -> /dev/pts/4
Napisz program który dokonuje takiej zmiany. Tutaj nie korzystamy z takich
narzędzi jak gdb lub inny debugger! Wykorzystaj do tego ptrace.
Dobre wprowadzenie do ptrace można znaleźć w tych dwóch artykułach:
Playing with ptrace, Part I,
Playing with ptrace, Part II.
Przykład konwersji stron podręcznika
man do formatu PDF:
$ man -t ps | ps2pdf - ps.pdf
$ man -t gcc | ps2pdf - gcc.pdf
$ # Dla czcionek 'Courier'
$ zcat $(man -w gcc) | groff -Tps -fC -mandoc | ps2pdf - "gcc.pdf"
W przypadku braku programu
ps2pdf, należy zainstalować pakiet
ghostscript np. pod archlinuksem:
# pacman -S ghostscript
Lista 4 (Lab) Termin wysłania na SVN do 26.11.2023 3.12.2023
-
(10pt)
Napisz skrypt w Bashu, który pokazuje informacje o wszystkich procesach (podobne jak program ps aux).
W zadaniu wykorzystaj system plików proc (standardowo w systemie Linux montowanym w katalogu /proc, man 5 proc)
do pobrania informacji o procesach np. cat /proc/PID/status (i/lub /proc/PID/stat) wyświetla informacje o procesie PID.
Wyświetl ppid, pid, comm, state, tty, rss, pgid, sid i poznaj dokładnie wszystkie wymienione oznaczenia!
Dodatkowo wyświetl informację ile proces ma otwartych plików. Wszystkie te informacje o jednym procesie mają być "ładnie" (patrz np. man column)
wyświetlone w jednym wierszu podobnie jak w programie ps.
-
(15pt)
Napisz skrypt w Bashu, który co sekundę prezentuje informacje o systemie operacyjnym. Dane pobierz
wykorzystując pseudo system plików proc w Linuksie domyślnie zamontowanym w katalogu /proc (patrz man 5 proc) oraz sysfs (patrz man 5 sysfs).
Skrypt powinien prezentować następujące informacje:
- Aktualną oraz średnią prędkość wysyłania i odbierania danych z sieci (odczytaj i zinterpretuj /proc/net/dev oraz wyświetl w B, KB lub MB w zależność od aktualnej prędkości) i
- Aktualne wykorzystanie rdzeni procesora dla każdego rdzenia osobno w procentach (patrz /proc/stat - man 5 proc) wraz z aktualną częstotliwością (patrz np. /sys/devices/system/cpu/cpu0/cpufreq/scaling_cur_freq dla cpu0) pracy rdzenia procesora (podobnie jak htop) i
- Jak długo system jest uruchomiony w dniach, godzinach, minutach i sekundach (/proc/uptime) i/lub
- Aktualny stan baterii w procentach (/sys/class/power_supply/BAT0/uevent) i
- Obciążenie systemu /proc/loadavg oraz
- Aktualne wykorzystanie pamięci /proc/meminfo (przeanalizuj co oznaczają 3 początkowe wiersze).
W przypadku prędkości przesyłania danych skrypt powinien prezentować "graficznie" historię poprzednich pomiarów np. prosty wykres słupkowy.
Przykładowe programy z wykresami na których można się wzorować to: s-tui lub
bmon lub bpytop. Można wykorzystać inne znaki w UTF-8.
Zobacz też informacje o komendzie tput np.
link i/lub
link.
Układ oraz kolejność wyświetlanych informacji jest dowolna.
-
(10pt)
Napisz skrypt w Bashu wykorzystujący REST API do pobierania danych z dwóch przykładowych źródeł np.
Chuck Norris API i The Cat API lub dowolne inne które pobiera
tekst i obrazki. Do zapytań RESTowych wykorzystaj curl lub wget do parsowania
JSONa wystarczy program jq (pacman -S jq), dla osób korzystających z formatu XML dostępny jest program xmllint (pacman -S libxml2).
Po uruchomieniu skryptu na ekranie pokaż obraz z bazy 'The Cat API' wykorzystując np.
program img2txt (pacman -S libcaca) lub catimg oraz poniżej wyświetl losowy cytat z bazy Chucka Norrisa.
-
(15pt)
Napisz skrypt w Bashu, który znajduje takie same pliki w podanym katalogu oraz
podkatalogach i wyświetla je w terminalu posortowane w kolejności malejącej po
wielkościach plików (z pełną ścieżką), czyli na początku zostaną wyświetlone
duplikaty plików które zajmują najwięcej miejsca na dysku. Pliki są takie
same jeśli mają taką samą zawartość nie jeśli mają takie same nazwy
i/lub wielkość. Przykładowe wywołanie programu
$ ./searchduplicate /bin
gdzie pierwszym parametrem jest katalog w którym, mają zostać znalezione
duplikaty plików.
Wskazówka: Na początku najlepiej jest obliczyć
hash
wszystkich plików np.
sha256sum (man sha256sum),
później można efektywnie ( O(nlogn) ) znaleźć pliki które są takie same.
- (15pt)*
Celem tego zadania jest dokładniejsze poznanie ANSI escape sequences i obsługi terminali. Bazując np. na grze
arkanoid
napisz w Bashu prostą wersję gry która pozwala na ucieczkę z labiryntu. Do generowania labiryntu wykorzystaj dowolne
algorytmy. Zrób tak aby
gra (labirynt) dostosowywała się do wielkości terminala.
Przetestuj program na różnych emulatorach terminali np.
xterm,
urxvt,
st,
gnome-terminal,
linux console
itp.,
czy są jakieś różnice?
Lista 5 (Lab) Termin wysłania na SVN do 10.12.2023
- (5pt)
Napisz program w języku C, który uruchomi powłokę (Bash) z prawami roota. Po kompilacji programu
można ustawić (z poziomu roota) dowolne atrybuty (np. patrz SUID).
Następnie już z poziomu
dowolnego użytkownika uruchamiając program uruchamia się konsola administratora, podobnie jak sudo /bin/bash
(bez wprowadzania hasła). Oczywiście proszę nie wykorzystywać programu 'sudo' we własnym programie!
- (5pt)
Napisz w języku C programy testujące, które odpowiedzą na następujące pytania:
- Czy można napisać program do obsługi wszystkich sygnałów (patrz kill -l)? Napisz program prezentujący odpowiedź.
- Czy jest możliwe wysłać sygnał SIGKILL, lub inny do procesu init (PID 1) czyli np. kill -9 1 (nawet będąc rootem)?
- Czy sygnały są kolejkowane? Np. napisz program testowy wysyłający wiele razy do danego procesu sygnał (np. SIGUSR1) i zobacz czy wszystkie dotarły.
- (10pt)
Zaimplementuj w języku C prostą wersję powłoki o nazwie lsh. Jak prawdziwa powłoka,
lsh odczytuje linię ze standardowego wejścia i przeszukuje ścieżki ze zmiennej
PATH (inaczej mówiąc zamiast execve wykonuje execvp)
i wykonuje podany program. Proszę pamiętać o ustawieniu argumentów wykonywanej komendy.
Jeśli linia kończy się znakiem (&), wtedy lsh powinien nie czekać
aż komenda zostanie skończona i od razu wrócić.
W innym przypadku lsh powinien zaczekać, aż program wykona się. lsh powinien
skończyć swoje działanie naciskając klawisze Control+D lub pisząc exit.
Zmieniamy katalogi przez wpisanie komendy cd. Komendy cd oraz exit to komendy wbudowane.
Uwaga: Procesy uruchomione w tle, które się zakończyły mogą stać się procesami 'zombi',
rozwiąż ten problem w lsh. Znajdziesz w sieci wiele rozwiązań np.
Build your own shell
lub sh z xv6,
ale to ma być wersja minimalna wystarczy napisać prosty parser dla linii komend oraz zastosować
kilka wywołań systemowych!
- (10pt)
Zaimplementuj w programie lsh z poprzedniego zadania potoki | (ang. pipe) oraz
przekierowanie standardowego wejścia (<), wyjścia (>) oraz wyjścia błędu (2>).
Wskazówka: Zobacz program lssort.c. Ponadto Ctrl-C przerywa wykonywanie programu
w powłoce (nie samej powłoki oraz zadań wykonywanych w tle).
- (15pt)*
Zaimplementuj w programie lsh zarządzanie zadaniami (job-control), czyli
co najmniej komendy wbudowane fg, bg, jobs oraz ^Z.
Patrz książka Michael Kerrisk, "Linux Programming Interface".
- (15pt)*
Dopisz do xv6 nowe wywołania systemowe. Jako pierwsze napisz wywołanie systemowe o nazwie
hello wyświetla tylko napis "Hello World!" oraz wywołanie systemowe getppid które wraca pid rodzica. Napisz program w języku C, który testuje
nowe wywołania systemowe. Uwaga: Pamiętaj, że dodanie nowego wywołania, aby rozszerzyć funkcjonalność jądra nie powinno być
stosowane jako pierwszy wybór! Potraktuj to zadanie tylko jako ćwiczenie.
Lista 6 (Lab) Termin wysłania na SVN do 22.12.2023 7.01.2024
Uwaga: Wszystkie zadanie wykonujemy na symulatorze (aktualizacja: 2023.12.18) wersja OFFLINE
- bugfix: problem z autorepeat (Miłosz Kozłowski)
- dodane zostało sterowanie z klawiatury:
- klawisze kursora przewijanie schematu (z shiftem wolniej)
- '[', ']' to zmniejszenie i powiększenie (zoom out, zoom in)
- 'e' to edycja (edit)
- 'r' to uruchomienie (run)
- 'l' to wczytywanie (load)
- 's' to zapisywanie (save)
- 'shift' to minimap
- 'c','v' - w trybie uruchomienia (run) pojedynczy lub ciągły zegar
- bugfix: poprawiony błąd znikających połączeń i elementów w symulatorze (Miłosz Kozłowski)
Na SVN proszę wysłać tylko zadania 2, 3, 4 i 5 w postaci plików json zapisanych w tej wersji symulatora.
-
(10pt)
Przeanalizuj dokładnie działanie procesora 4-Bit CPU (plik examples/cpu.json).
Przy oddawaniu zadania odpowiedzieć należy na jedno z pytań:
- która instrukcja potrzebuje więcej niż 1 cykl zegara na wykonanie (execute). Zobacz sygnały 'Exec Clock' i 'Exec Done'
- wskaż układ w którym realizowane jest dodawanie i odejmowanie oraz wytłumacz jak on działa (zobacz sygnały ADD i SUB, które wchodzą na wejście bramki OR)
- wytłumacz jak przebiega cykl fetch instr, fetch param, execute, write back (control unit)
- wytłumacz jak działa zwiększanie instruction pointera oraz skąd wiadomo w których momentach należy go zwiększyć tzn. jedne instrukcje posiadają parametry inne nie, skąd wiadomo kiedy można przejść do następnej komórki pamięci (które bramki tym sterują?)
- wytłumacz na przykładzie jak działa instrukcja JMP, prześledź sygnały i wytłumacz jak działają bramki (Set Address) w instruction pointer
- wytłumacz jak działa mechanizm flagi zero, jakie instrukcje mogą zmienić flage?
- wytłumacz działanie instrukcji SWP i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji MOV i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji OUT i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji JZ i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji ADD i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji SUB i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji AND i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji OR i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji XOR i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz działanie instrukcji IN i prześledź cały cykl (fetch, ...) jego działania
- wytłumacz co się dzieje jak wprowadzimy "nielegalną" instrukcję np. do pamięci wpiszemy 0x0e. Czego brakuje? Co należało by zrobić aby procesor po prostu ominął instrukcję
Prowadzący wybiera numer pytania na które należy odpowiedzieć, więc należy znać odpowiedzi na wszystkie, czyli
po prostu rozumieć jak działa przedstawiony procesor. Prowadzący wybierając pytanie może dopytywać się
różnych innych szczegółów procesora.
- (15pt)
Do 4-Bit CPU (plik examples/cpu.json) dodaj nową instrukcje nazwijmy ją ASL xx
(accumulator shift left) o kodzie 0x0C, która mnoży rejestr A przez 2^n (A<<n) gdzie n to parametr instrukcji.
- (15pt)
W 4-Bit CPU (plik examples/cpu.json) pamięć jest realizowana za pomocą 'diode matrix' (plik examples/diode.json).
Wymyśl dowolny inny sposób na przechowywanie programu (niż 'diode matrix'). Podsumowując, można wykorzystać
dowolne komponenty dostępne w symulatorze, oczywiście oprócz 'diode'. Dołącz pamięć do symulacji 4-bit CPU i pokaż,
że całość działa.
- (10pt*)
W 4-Bit CPU (plik examples/cpu.json) pamięć jest realizowana za pomocą 16x4
'diode matrix' (plik examples/diode.json) + dekoder (16 komórek pamięci 4 bitowych), czyli szyna
adresowa jest 4-bitowa (maks 2^4 komórek pamięci). Zmodyfikuj ten CPU tak aby szyna adresowa była 5-bitowa, przy czym instrukcje
skoków JZ, JMP mogą być 4-bitowe i tylko na adresy parzyste, czyli pierwszy bit w skoku ustawiamy na zero, więc możemy
skakać tylko na adresy 0, 2, 4, 6, ... lub można to rozwiązać w inny sposób np. skoki tylko do pierwszych 16 komórek (lub drugich 16-32) itp.
- (10pt)* Zrób zadanie poprzednie tak, aby możliwe były jednak skoki w dowolne 5-bitowe adresy pamięci z wykorzystaniem dalej 4-bitowych
komórek pamięci ROM (bez zmian mamy też rejestry 'instruction register' i 'parameter register').
Lista 7 (Lab) Termin wysłania na SVN 14.01.2024
Przydatne linki:
- (10pt)
Napisz program w asemblerze dla procesora x86, który pobiera liczbę
całkowitą w systemie dziesiętnym ze standardowego wejścia i wyświetla na standardowym
wyjściu liczbę 32-bitową w kodzie szesnastkowym, czyli np. dla podanej liczby $123$ (ze standardowego wejścia)
należy ten łańcuch znaków zamienić na liczbę zapisaną w rejestrze, tak aby można
było wykonywać operacje arytmetyczne do zamiany na postać szesnastkową.
Zatem program oblicza w assemblerze to co robi ten kod
scanf("%d",&a); printf("%x\n",a); w języku C. Do wyświetlania wykorzystaj wywołanie systemowe
write, do odczytu read odpowiednio z deskryptorów 1 i 0.
- (10pt)
Napisz program w asemblerze dla procesora ARM, który wysyła na standardowe wyjście
liczby pierwsze z zakresu od 1 do 100 000. Do uruchomienia możesz wykorzystać
qemu-arm
(patrz Wykład 20.12.2023) z pacman -S qemu-user.
- (10pt)
Napisz program w asemblerze x86 z wykorzystaniem koprocesora matematycznego
x87, który potrafi obliczać funkcje matematyczne dla podanego argumentu. Program
pobiera ze standardowego wejścia łańcuch znaków postaci "liczba" np. 2 lub 3.14 itd. Wykorzystując koprocesor matematyczny
oblicza wynik (na liczbach zmiennoprzecinkowych) $\sin(x)$, $\cos(x)$, $\mbox{sqrt}(x)$ i
$\exp(x)$, gdzie $x$ to wprowadzona liczba. Wszystkie wyniki wysyłaj na standardowe
wyjście. Do konwersji na liczby zmiennoprzecinkowe należy samemu napisać
odpowiednie procedury tzn. bez wykorzystania funkcji bibliotecznych np. scanf,
atof, printf,
ftoa itp.
(ale można wzorować się na kodach z linków!). Nie muszą to być pełne konwersje
tzn. np. 1e12 itp. wystarczy format cyfry kropka cyfry!
- (10pt)
Napisz funkcje w asemblerze x86 z wykorzystaniem
koprocesora matematycznego x87:
- $f_1(\mbox{double } a, \mbox{float } b, \mbox{double } c, \mbox{int } d)=\frac{a}{b} - c\cdot d$
- $f_2(\mbox{double } a, \mbox{int } b) = \log_{b} a$
- $f_3(\mbox{double } a, \mbox{int } b) = b^{a}$
- $f_4(\mbox{float } a, \mbox{int } b) = \sqrt[b]{a}$
- (10pt)
Wykorzystując rozkazy
MMX,
bibliotekę SDL oraz wzorując się na
przykładzie z wykładu fade, napisz program
wykonujący płynne przenikanie jednego obrazu graficznego w drugi. Postaraj się
jak najbardziej zoptymalizować program (czyli uzyskać jak największe
FPS).
- (10pt)
Napisz program w asemblerze x86 z rozkazami SIMD AVX, który
liczy silnię n! na liczbach $512$-bitowych. Do obliczań należy wykorzystać
$256$-bitowe rejestry YMM0, YMM1, ... dostępne w AVX (x86_64). Liczba $n$ pobierana
jest z argumentów argc, argv (lub ze standardowego wejścia) oraz wynik
wysyłany jest na standardowe wyjście.
- (10pt)
Pobierz z github system operacyjny xv6 z łatą xv6.patch. Krótka instrukcja
instalacji jest tutaj. Następnie przy oddawaniu
zadania na laboratorium wykonaj:
- (10pt)
Zaimplementować w systemie xv6 program ps, który
wyświetla listę wszystkich procesów uruchomionych w systemie. Należy dodać
kolejne wywołanie systemowe np. getpinfo(), które zwraca informacje o
procesie. Nowe wywołanie systemowe będzie miało następujący interfejs:
int getpinfo(int pid, struct uproc *up);
gdzie pid jest numerem procesu w tablicy ptable.proc[nproc]
zawierającej wszystkie procesy, a struct uproc jest
strukturą opisującą proces. Struktura zawiera następujące informacje o
procesie: nazwa procesu, id procesu, id procesu nadrzędnego, rozmiar
pamięci procesu, stan procesu, czy proces czeka na kanale i czy został
zabity.
Należy zdefiniować strukturę uproc i zaimplementować narzędzie ps
poprzez wielokrotne odpytywanie systemu o wszystkie możliwe procesy w systemie
(takie proste rozwiązanie, ile maksymalnie może być procesów w xv6?), tj.
wszystkich elementów tablicy ptable.proc[nproc]. Następnie należy
utworzyć program na poziomie użytkownika, który wywołuje nowe wywołanie systemowe getpinfo().
Wpisanie ps w wierszu powłoki xv6 powinno wypisać
wszystkie procesy uruchomione w systemie i informacje o nich.
Lista 8 (Lab) Termin wysłania na SVN i oddania 2.02.2024
- (5pt)
Załóż system plików FAT i VFAT
(podobnie jak na wykładzie). Utwórz na nim kilka plików (co najmniej jeden większy od wielkości
pojedynczego klastra) i pokaż jak są przechowywane w systemie plików (hexdump -C) np. jak zmieniła się
tablica alokacji (FAT), tablica katalogów (root directory entry) oraz gdzie znajduje się zawartość plików.
Usuń wybrany plik i pokaż jak zmienił się system plików. Co należy zrobić aby odzyskać skasowany plik?
Wprowadź długą nazwę pliku i pokaż jak jest reprezentowana w systemie FAT i VFAT.
- (5pt)
Napisz w języku C program, wykorzystujący FUSE, który pozwala "spłaszczyć"
widok plików na dysku tzn. jeśli jako parametr podamy dany katalog to system wróci wszystkie pliki w tym katalogu oraz podkatalogach
jako jeden duży katalog. Dokładnie coś podobnego jak działa polecenia flat
w programie ranger.
- (10pt)
Przeanalizuj techniki wstrzykiwania kodu do programu,
np. można wykorzystać następujące źródła
Napisz program dla (język C + asembler) x86 lub ARM, który wykonuje kod (ukrywa się) w ramach innego processu np. mogę "wstrzyknąć" kod do procesu
bash i wykonując polecenie ps nie widać w ogóle mojego programu.
-
(5pt)
Wykorzystując CUDA (lub OpenCL) napisz kernel obliczający na GPU równolegle fraktal Mandelbrot-a.
Napisz także wyświetlanie wygenerowanego fraktala np. z wykorzystanie OpenGL i zapisywanie do pliku - najprościej do formatu
ppm, ale może być dowolny.
- (5pt)
Wykonaj samodzielnie atak przepełnienia bufora z wykorzystaniem
debuggera gdb oraz z poziomu powłoki. Wytłumacz dlaczego
program uruchamiający powłokę musi być tak napisany (dodatkowe wywołania, wpisanie zera
do napisu "/bin/sh" z poziomu asemblera itp). Wyjaśnij działanie opcji -z execstack
i -fno-stack-protector oraz co to jest randomizacja stosu. Więcej informacji patrz slajdy z wykładu.
- (5pt)
Napisz w języku C własną implementacje funkcji printf i scanf (nazwijmy je myprintf i myscanf).
Funkcje nie mogą wykorzystywać, żadnych funkcji bibliotecznych (atoi, fprintf, fscanf itp.)
oraz makr va_start, va_arg i va_end (np. możesz skorzystać z wyjaśnienia tutaj
oraz patrz X86 calling conventions i dokładniej
cdecl)
oraz można wykorzystać wywołania systemowe read i write z odpowiednim standardowym deskryptorem.
Program należy skompilować na maszynę 32-bitową tzn. gcc -m32 np. dla 64-bitowego systemu ArchLinux trzeba zainstalować
pakiet gcc-multilib z repozytorium multilib.
W funkcjach wystarczy zaimplementować "%s", "%d", "%x" i "%b", gdzie w naszej implementacji "%s" wyświetla
ciąg znaków, "%d" liczbę w systemie dziesiętnym, "%x" liczbę w systemie szesnastkowych oraz
"%b" liczbę w systemie binarnym.
- (5pt)
Napisz w języku C wielowątkową wersję mnożenia macierzy boolowskich. Program powinien pobierać z linii komend
wielkość macierzy (wypełniać ją losowymi wartościami 0 lub 1, patrz man 3 random) oraz liczbę wątków, która
powinna zostać uruchomiona do mnożenia. Zaimplementuj program tak, że każdy wątek pracuje na osobnym
wierszu, jeśli jeden skończy pracę to dalej pracuje na następnym wolnym wierszu oraz pamiętaj, że
pojedynczy iloczyn skalarny (wiersz razy kolumna) może zostać ustalony wcześniej nawet po pierwszej koniunkcji.
Pamiętaj, że przy dostępie do zmiennych współdzielonych mogą wystąpić wyścigi!