Lab Zadanie 3

Motto: Operating system programming is so much fun that it will eventually be outlawed (cytat z sieci)
Pod-motto: I wish it were already outlawed… (anonimowy student MIMUW)

Znormalizowana postać patch'a

(APT) Czy ktoś wie jakie opcje należy użyć do diff'a?
Czy chodzi o opcje -ru? Czy jest jakaś opcja, aby pomijał nie istniejące pliki w katalogach? Chodzi o to by nie trzeba było robić make clean'a?
(KM) Ja chyba wyślę tak: diff —normal -rN linux-2.6.17.13 linux-2.6.17.13-km > linux-2.6.17.13-km.patch
(APT) Trzeba najpierw zrobić make mrproper inaczej wygeneruje gigantycznego diff'a

(EE…) diff -uprN -X linuxDir/Documentation/dontdiff ble ble2 >patch winno zadziałać ok.

Ograniczenia na wątki

(KM) Myślałem, że moje rozwiązanie działa dobrze, ale właśnie odkryłem, że gdy proces tworzy wątki, to są one bez żadnych ograniczeń (powinny _dzielić_ ograniczenia z procesem macierzystym). Przy tworzeniu procesów ograniczenia się poprawnie dziedziczą.

Ktoś miał podobny problem? Może trzeba coś więcej poczarować przy pliku "fork.c". Ktoś się orientuje jak to jest naprawdę z tworzeniem nowego wątku? Używa się do tego "do_fork"? task_struct jest chyba wspólny dla wszystkich wątków (i procesu macierzystego), nie?
Jeszcze może to być kwestia makra "current" - dla każdego wątku zwraca tę samą strukturę task_struct?

(BG) W task_struct jest wskaźnik na główny proces danej grupy wątków

(MK) I co on robi? Tj. jeśli trzymam limity w task_struct, to co z tego wynika?

(KM) Przy forku zmieniłem zachowanie w zależności od flag i działa.

Waiting for root file system

(MK) Problem niezwiązany bezpośrednio z treścią zadania - czy ktoś z Was wie, co można poradzić na błąd "Waiting for root file system…" (tj. przy bootowaniu nowego jądra system się zawiesza z takim komunikatem)? Nie wiem, o co chodzi z tym błędem - jak się trochę poczeka, to wyświetla błąd typu "dev/sda1 does not exist", mimo że w menu.lst w GRUBie mam ustawiony root na sda1.

(AK) Miałem podobną systuację, chyba coś innego ale może komuś się przyda. Poza powyższym komunikatem pojawiały sie informacje typu: "disagrees about version of symbol …" i inne "invalid module format…". Przyczyną było zrobienie tylko make bzImage, cp i reboot. Przy większym make (np. po zmianie czegoś w sched.h) trzeba (poza make bzImage i cp arch/i386/boot/bzImage /boot/vmlinuz-2.6.17.13; cp System.map /boot/System.map-2.6.17.13) zrobić pełny make: make modules, make modules_install, mkinitramfs -o /boot/initrd.img-2.6.17.13 2.6.17.13. Bez nowych modułów i initramfs bedzie powyższy "Waiting… ". Nie czekałem co się dalej stanie tak więc może to coś innego.

(KM) Musiałbym trochę pogooglować, ale może nie masz wszystkich potrzebnych sterowników wkompilowanych (nie jako moduły!) w jadro (mi się już kiedyś tak zdarzyło, że musiałem kilka sterowników włączyć i dopiero wtedy zaczęło działać). Które sterowniki należy wybrać zależy od sprzętu. Może być też tak, że masz teraz inne sterowniki niż wcześniej i Twój dysk może być teraz np. hda a nie sda.
Jeśli chodzi o kompilacje to ja robie zawsze make; make module_install i kopiuje bzImage w odpowiednie miejsce - zawsze mi tak działa.

Narzucanie ograniczeń - gdzie?

(MK) Gdzie należy egzekwować ograniczenia przepustowości? Mam na myśli to, że jeśli np. moja przepustowość wynosi 10 kB na 10 s (na razie olewając podział na deskryptory, tylko patrząc się na samo urządzenie), to nigdy nie mogę pozwolić nikomu wczytać naraz (w jednej operacji odczytu) więcej niż 10kB, bo wtedy przekroczę dozwoloną średnią na 10s. Tymczasem przy wywołaniach funkcji sys_read i potem vfs_read podawany argument count (ile chcę wczytać) może być dowolnie duży, w szczególności jak ktoś zechce naraz wczytać 500 GB, to nie mogę sam "podziabać" jego żądania na mniejsze kawałki. Jeśli chcę (zgodnie z semantyką zadania) zapobiec np. sytuacji, w której ktoś czyta naraz bardzo dużo, a chwilę potem się zamyka, to musiałbym taki odczyt uznać za nielegalny i np. zwrócić jakiś błąd czy coś.

Czy ktoś z was rozwiązał już tę kwestię?

(AK) Ja widzę trzy rozwiązania:

  • Usypiam proces na odpowiednią ilość czasu tak aby średnia się zgodziła. Np jesli ograniczenie 1KB/s czyli srednio 10KB na 10 s i jeśli mamy read 100KB to powinienem uśpić proces na 90 s i wtedy zrobić cały read. Średnia sie zgodzi lecz w innym przedziale (100s a nie 10s)
  • Zwrócić błąd - niemożliwość wykonania operacji przy takich ograniczeniach
  • Pociąć read na mniejsze kawałki - wg mnie spowoduje to tysiąc innych problemów i odrzucam to rozwiązanie

(MK) Aha, chyba nie ma z tym problemu, bo wystarczy w sys_read ustawić przekazywany dalej count na MIN(tyle ile chcę przeczytać, tyle ile mogę) i odpowiedni ustawić offset. Wtedy proces fizycznie przeczyta tylko tyle, ile mu pozwolimy, a jak będzie chciał czytać więcej, to musi jeszcze raz wywołać read() (wtedy będzie czytał od offsetu, na którym skończył).

(AK) Zastanawiam się czy zawsze powinniśmy postepować w taki sposób: jeśli można odczytać chociaż jeden bajt to nigdy nie usypiamy procesu tylko zwracamy MIN(ile chcę, ile mogę). Proces usypiamy tylko wtedy gdy nie można zwrócić ani jednego bajtu (return 0 w read oznacza koniec pliku)

(MK) Wydaje się to sensowne, bo read() nie ma obowiązku zwrócić tyle przeczytanych bajtów, ile mu kazaliśmy - jeśli program chce dokonać b. dużego odczytać, to sam musi sprawdzać, ile zwrócił read() i ew. go ponawiać (wteyd faktycznie czeka tylko wtedy, kiedy zostało mu 0 B limitu).

(MK) I drugie pytanie - czy implementując (jakoś tam, np. pamiętając w task_struct listę trójek "deskryptor, limit, urządzenie") podział ograniczeń pomiędzy deskryptory należy to zrobić w sys_read (i wtedy w read_vfs nic w zasadzie nie trzeba zmieniać), czy sensowniej jest zrobić to gdzieś indziej?

(AK) ja wybrałem sys_read[v], sys_write[v]

Numery urządzeń

(AK) Udało się komuś wyciągnąć numery urządzeń dla read/write na pliku? Próbowałem już w wielu miejscach i dla urzadzeń znakowych i_rdev w inode jest poprawna natomiast dla blokowych mam zawsze niezainicjowaną, tzn major=0 minor=0.
(BG) Informacje o systemie plików powinny być w superbloku (i_sb)

TGID i TID

(MK) Mam taką wątpliwość - wiele plików w procu jest dodawane dwa razy, jako PROC_TID_XXX i PROC_TGID_XXX (w base.c) - ma to, jak się zdaje, jakiś związek z obsługą wątków (tid = identyfikator wątku, tgid = identyfikator grupy wątków (czyli proces)). Czy ktoś z was wie, jak powinny być dodane pliki readlimit, writelimit (tak, żeby był jeden taki plik dla całego procesu, czyli wspólny dla wątków)?
(BG) w /proc/<pid>/ znajdziesz pozycje z PROC_TGID, w /proc/<pid>/task/<tid> znajdziesz PROC_TID. Przejrzyj numery inode przez ls -i.
Dodałem pozycje w pid_directory_inos, tgid_base_stuff i proc_pident_lookup.

Wątki

Wątki współdzielą ograniczenie w ramach tego samego procesu.

Pozdrawiam,
Kuba Łącki

On 01/15/2010 03:57 PM, Kornel Maczyński wrote:

Dzień dobry,
mam pytanie w związku z zadaniem III z SO. Czy wątki należy traktować tak jak zwykłe procesy, tzn. Jeśli proces ma włączone ograniczenie na danym urządzeniu i stworzy wątek, to musi się z nim podzielić pasmem czy wątek dostaje swoje prywatne pasmo (jak przy stworzeniu nowego procesu)?

Testy

(AK) Czy są jakieś założenia odnośnie technologii, języka, formy i implementacji testów? Czy można np. zaimplementować test w całości w pythonowych unittestach? Zapisy, odczyty, zliczanie statystyk i generowanie raportu implementowane w pythonie. Bądź też wykorzystać jakieś wysokopoziomowe narzędzia typu cp, time. Czy być może pożądane jest jakieś rozwiązanie bazujące na prostych programach w C wykonujących niskopoziomowe operacje read/readv i write/writev? W treści zadania nie ma na ten temat komentarza tak więc rozumiem, że jest tu pełna dowolność. Ważne jest jedynie aby testy pokazywały w miarę wiarygodne wyniki.

(Jakub Łącki) Tak, choć trzeba uważać, żeby wysokopoziomowy język nie wykonywał operacji wejścia/wyjścia przez wywołanie systemowe mmap.

Dziedziczenie

(AK) Wg. treści zadania możliwe jest obejście ograniczeń poprzez zlecanie operacji zapisu/odczytu potomkom procesu. Ponieważ proces potomny nie dziedziczy tymczasowych wartości związanych z ograniczeniami więc każdy proces (który zużył już swoje ograniczenia i musiałby czekać ok 10 aż dostanie kolejna porcję) może stworzyć potomka i zlecić mu daną operacje odczytu/zapisu. Takie zlecanie zadań można robić dowolną ilość razy. Wg. treści zadania taka sytuacja jest dopuszczalna i akceptujemy takie niebezpieczeństwo.

(JŁ) Wprawdzie nie ma tu pytania, ale odpowiedź brzmi tak:)

Przydział ograniczeń

(AK) Kilka kwestii jest dla mnie niejasnych. W treści zadania mamy: "(…) gdy wiele deskryptorów procesu dotyczy tego samego urządzenia, ograniczenie musi być podzielone po równo między wszystkie deskryptory". Co to znaczy, że deskryptory procesu (task_struct) dotyczą urządzenia? Rozumiem, że chodzi o deskryptory plików procesu, a nie task_struct?
Jeśli zatem chodzi o sytuację, w której mamy proces, ma on nałożone pewne ograniczenia na dane urządzenie, kilka jego deskryptorów plików odnosi się do jednego urządzenia to dlaczego mielibyśmy w obrębie jednego procesu rozdzielać "po równo" ograniczenia dla różnych deskryptorów plików? Proces może mieć otwartych wiele deskryptorów plików ale nie musi korzystać z nich równomiernie. Nie rozumiem jak warunek przydziału "po równo" wynika z warunków nałożonych na ograniczenia.
Jeśli natomiast w powyższym cytacie przez "deskryptorów procesu" rozumiemy task_struct, to pojawia się pytanie dlaczego algorytm miałby dla różnych procesów, które mają zupełnie inne ograniczenia, miałby przydzielać dostęp do urządzeń "po równo".

(JŁ) W treści zadania "deskryptor" oznacza deskryptor pliku.
Deskryptor pliku "dotyczy urządzenia X" jeśli plik ten jest zapisany w systemie plików na urządzeniu X.
Jeśli proces ma otwartych n deskryptorów dotyczących urządzenia Y i ograniczenie odczytu (dla zapisu będzie analogicznie) wynosi L, to każdy deskryptor ma (w podstawowej wersji zadania) przypisane ograniczenie równe L/n. Tak, to jest nieefektywne: jeśli pewne deskryptory nie są używane, można to zrobić lepiej i dostać za to dodatkowe punkty. Ważne, by suma przepustowości deskryptorów nie przekroczyła całej przepustowości dla procesu.

(AK) Mój pomysł na rozwiązanie to przechowywanie dla każdego procesu historii odczytanych/zapisanych bajtów z ostatnich 10 sec dla każdego urządzenia. Bez rozróżnienia na deskryptory plików. Dla danego urządzenia historia jest odświeżana przy każdej operacji sys_read[v]/sys_write[v]. Nie widzę potrzeby "interesowania" się jaki to był deskryptor pliku tylko do jakiego urządzenia odnosi się dane wywołanie. Takie podejście jest bardziej sprawiedliwe niż jakiekolwiek, które stara się rozdzielać ograniczenia pomiędzy deskryptory. Odpada zatem cała kwestia związana z algorytmami przydziału i martwi mnie to o tyle, czy przypadkiem nie interpretuję treści błędnie. Czy takie rozwiązanie zatem kwalifikuje się jako "implementujące bardziej wyrafinowany algorytm podziału pomiędzy deskryptory" i będzie nagradzane dodatkowymi punktami?

(JŁ) Niestety, treść zadania mówi jasno: ograniczenie powinno być podzielone pomiędzy deskryptory. W szczególności trzeba uniknąć sytuacji, w której proces czyta na zmianę z dwóch deskryptorów, ale szybkość transmisji jednego deskryptora jest istotnie mniejsza od szybkości drugiego.

Ponadto na konsulacjach udało mi się uzyskać odpowiedź na pytanie "po co scheduler?". Scenariusz jest taki: proces ma otwarte dwa deskryptory plików: fd1, fd2. Z fd1 czyta dużo i często, fd2 mało i rzadko. Przy czym odczyt z fd1 jest z flagą O_NONBLOCK, czyli nie możemy uśpić procesu (to chyba powinno dotyczyć tylko FIFO - do doczytania). Dając pewną gwarantowaną ilość bajtów do czytania dla każdego deskryptora nigdy nie bedziemy oczekiwali na read, jeśli nie rozróżnimy ograniczeń na desryptory to przy odczytach z fd2 bedziemy oczekiwać czasem 10 sec. Wg. mnie to bardzo rzadki scenariusz i trochę to naciągane ale takie info uzyskałem od Jakuba.

(MK) Mógłbyś opisać dokładniej ten przykład i jego uzasadnienie? Bo nie do końca zrozumiałem, o co chodzi. Jakie ma tu znaczenie, że używamy O_NONBLOCK?

(AK) Nie jest to dla mnie całkiem jasne i najlepiej byłoby spisać dokładnie taki scenariusz i zapytać Jakuba jak dokładnie program powinien się zachować. Wg. mnie istotne jest przemyślenie takiej sytuacji: mamy wywołanie sys_read z ustawioną flagą O_NONBLOCK, mamy dane do odczytania, ale przekroczyłoby to limit. Czy w takiej sytuacji mamy uśpić proces, czy return -1 and set errno to [EAGAIN]? Wydaje mi się, że wg. Jakuba mamy wyjść z błędem, ale tutaj jeszcze wolałbym się upewnić.

Co do proca:

Jeśli ktoś jeszcze nie wie gdzie to patrzymy m.in. na pliki: fs/proc/base.c oraz fs/proc/root.c <-proc_root_init ((MK) - raczej w proc_misc_init w proc_misc.c)

O co chodzi z tym schedulerem?

(MK) Zamieszczam maile do J. Łąckiego i jego odpowiedzi. Niech ktoś mi wyjaśni, gdzie tu jest potrzebna jakakolwiek finezja wykraczająca poza następujące rozwiązanie:

  • pozwalamy procesowi wczytać na raz tyle danych, ile zechce, ale nie więcej, niż (llmit przepustowości)*10 s (żeby nie było tak, że wczytane jednym haustem 1000 GB i nagle się zakończy)
  • jeśli przekroczy ten limit, to usypiamy go na tyle sekund, żeby mu się limit odnowił

IMHO nie ma to nic wspólnego ze schedulingiem, tylko po prostu liczeniem, ile pojedynczemu procesowi przysługuje limitu w jakich odstępach czasu.

(MK)
mam pytanie, czy dobrze rozumiem treść zadania laboratoryjnego, a konkretnie część dotyczącą kolejkowania żądań - czy chodzi o to, by zastąpić systemowego schedulera (tego, który optymalizuje ruch głowicy, ma 4 polityki do wyboru itd.) własnym, która ma działać lepiej przy założeniach o ograniczonej przepustowości? (…)

(odp. J. Łąckiego)
Rozwiązanie zadania nie ma nic wspólnego z algorytmami szeregowania dostępu do dysku (no może cośtam by się znalazło, ale mało).
Chodzi o raczej o to, by ograniczać przepustowość niektórych operacji. Tak, to oznacza, że jeśli jakiś proces czyta bardzo dużo danych, to w celu zmniejszenia przepustowości będzie usypiany.

(MK)
Proszę w takim razie o wyjaśnienie, czym ma się zajmować zasugerowany w treści zadania scheduler, bo zupełnie tego nie rozumiem (skoro limitowanie przepustowości może się odbywać przez proste usypianie procesu na jakiś czas, to gdzie tu potrzeba i miejsce na kolejkowania czegokolwiek?). Nie rozumiem po prostu użytego w treści zadania
stwierdzenia "algorytm zarządzania przydziałem ograniczeń". Można prosić o jakiś prosty przykład, który by pokazywał, po co w ogóle jakikolwiek scheduler, tj. czemu nie wystarczy naiwne rozwiązanie typu "pozwól procesowi czytać aż do wyczerpania przepustowości na daną jednostkę czasu, a potem uśpij go na trochę, żeby odnowił mu się limit"?

(odp. J. Łąckiego)
Treść zadania nie mówi, że należy napisać scheduler, choć umieszczony w treści link może być nieco mylący, bo strona jest luźno związana z tematem.
Idea rozwiązania "pozwól procesowi czytać aż …" jest OK, jednak możliwości jest nieco więcej. Można na przykład pomyśleć o algorytmie, który zachowuje się dobrze jeśli proces raz na dwie jednostki czasu czyta tyle danych ile wynosi dwukrotność limitu na jednostkę albo o innych usprawnieniach.

(KM) FAQ:

On 01/07/2010 06:30 PM, Kornel Maczyński wrote:

Dzień dobry,
mam dwa pytania dotyczące treści zadania 3 z SO.
1. "Uwaga: proszę zwrócić uwagę, że ograniczenie jest przypisane do
urządzenia, a nie do deskryptora pliku. Przy projektowaniu algorytmu należy
uwzględnić, że gdy wiele deskryptorów procesu dotyczy tego samego urządzenia,
ograniczenie musi być podzielone po równo między wszystkie deskryptory.
Rozwiązania implementujące bardziej wyrafinowany algorytm podziału pomiędzy
deskryptory otrzymają dodatkowe punkty."
Czy to, że ograniczenie (np. 3kb/s) ma być podzielone po równo między
wszystkie deskryptory oznacza, że jeśli proces otworzy do jednego pliku 3
deskryptory, a używa tylko jednego, to jego ograniczenie jest trzy razy
mniejsze (1kb/s)?Czy można po prostu zaimplementować ograniczenie tak, że proces wykorzysta je
sobie tak jak będzie chciał (tzn. jeśli będzie używał tylko jeden deskryptor z
powyższego przykładu, to jego ograniczenie wyniesie 3kb/s)?

Muszę skonsultować się z autorem, żeby upewnić się co miał na myśli,
odpowiem wkrótce.

2. Drugie moje pytanie dotyczy plików specjalnych. Jak nasze rozwiązanie
powinno się z nimi obchodzić?

Ograniczenia mają działać jedynie przy operacjach na zwykłych plikach
(wartość ograniczenia należy odczytać z urządzenia, na którym zapisany
jest plik).

Chodzi o to, by nie zdarzyło się tak, że jeśli proces czyta na zmianę z
dwóch deskryptorów, to przepustowość operacji na obydwóch deskryptorach
(w długim okresie) musi być zbliżona.

Pozdrawiam,
Kuba Łącki

On 01/10/2010 04:33 PM, Kornel Maczyński wrote:

Dzień dobry,
jeśli się nie mylę, to pojedynczy proces może czytać tylko z jednego deskryptora na raz — zatem nie występuje tu problem zagłodzenia — w każdej chwili proces czyta/pisze z/do jednego deskryptora i szybkość tej operacji jest ograniczona przez średnią prędkość zapisu na dane urządzenie zadaną przez użytkownika.
Co Pan rozumie przez to, że żaden deskryptor nie może być głodzony/znacząco faworyzowany?

(MK) Chodzi tu chyba o to (p. też dyskusja wyżej), że w danym procesie może działać kilka wątków i każdy może czytać z innego deskryptora. Gdyby ograniczenie było tylko na urządzenie, a nie na deskryptory, to w tej sytuacji jeśli z fd1 czytam często i mało, a innym wątkiem z fd2 - rzadko, to kiedy 1. wątek zużyje dużo limitu na fd1, to może się okazać, że kiedy fd2 będzie chciał przeczytać 1 bajt, to będzie musiał czekać 10 s, mimo że ten deskryptor był praktycznie nie ruszany (raczej nie jest dobrze, kiedy wykonuję np. jeden odczyt w całej historii życia krótkiego wątku i nagle muszę czekać 10 s na przeczytanie 1 bajta). Oczywiście, podział limitu po równo pomiędzy deskryptory prowadzi do sytuacji, kiedy limit na rzadko używanych deskryptorach się marnuje.

Komentarz Samuela Łaszcza:

(21:21:20) Łaszcz: fajne zadanie, wreszcie coś sensownego :P
(21:22:53) Łaszcz: dzięki temu, że można olać mmap/poll/select
(21:23:01) Łaszcz: to trzeba się dostać tylko do najgłębszego read/write
(21:23:13) Łaszcz: i po prostu usypiac proces
(21:23:17) Łaszcz: tak mi się wydaje przynajmniej
(21:23:38) Łaszcz: w ogóle to możesz zacząć od napisania obsługi proca
(21:23:45) Łaszcz: bo to i tak będzie zawsze to samo :)
(21:24:16) Łaszcz: sam algorytm wydaje mi się nietrudny do wymyślenia

Hinty odnośnie kompilacji jądra:

http://www.howtoforge.com/forums/showthread.php?t=21

Uwagi prowadzących do rozwiązań:

Osoby poprawiające zadanie będą wdzięczne za uwagi prowadzących do rozwiązania z pierwszego terminu.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License