[linuxkernelnewbies] Petr Tůma: Operačn í systémy

Mon, 20 Apr 2009 01:11:04 -0700

http://195.113.20.55/~ceres/sch/osy/main.php

Operační systémy

Rozvrh

V zimním semestru 2008/2009 se přednášky konají v úterý od 15:40 do 17:10 v učebně S5 a ve čtvrtek od 10:40 do 12:10 v učebně S4. Cvičení se konají podle zde uvedeného harmonogramu v úterý od 17:20 do 18:50 v učebně S6 a ve čtvrtek od 12:20 do 13:50 v učebně S1.

Harmonogram cvičení První běh Druhý běh
1. Úvod, náplň, požadavky [slajdy] 2. října 2008 7. října 2008
2.1 Seznámení s prostředím pro vypracování semestrálních prací [slajdy] 9. října 2008 14. října 2008
2.2 Zveřejnění zadání semestrálních prací [mailing list] 12. října 2008
3.1 Seznámení s výukovým systémem Kalisto [slajdy] 16. října 2008 21. října 2008
3.2 Rozdělení do skupin, výběr rozšířeného zadání do 19. října 2008
3. až 6. týden: samostatná práce, konzultace
6. Odevzdání základního zadání Kostra kernelu 9. listopadu 2008
7. až 10. týden: samostatná práce, konzultace
10. Odevzdání základního zadání Správa paměti 14. prosince 2008
11. až 15. týden: samostatná práce, konzultace
15.1 Prezentace semestrálních prací a výběrových zadání 15. ledna 2009 13. ledna 2009
15.2 Odevzdání základního zadání Uživatelské procesy 18. ledna 2009
20. Osobní odevzdání rozšířeného zadání, milestone výběrových zadání do 20. února 2009

Kontakt

K výměně informací mezi studenty a vyučujícími je určen mailing list. Pro dotazy a připomínky týkající se výuky používejte prosím přednostně tento mailing list.

Pokud máte dotaz nebo připomínku, kterou nechcete posílat do mailing listu, můžete použít také mail:

  • Vlastimil Babka, vlastimil.babka at dsrg.mff.cuni.cz
  • Martin Děcký, martin.decky at dsrg.mff.cuni.cz
  • Petr Tůma, petr.tuma at dsrg.mff.cuni.cz

Můžete použít také wiki.

Náplň přednášek

Přednášky jsou uspořádány zhruba do párů tak, aby vždy první přednáška v daném týdnu uváděla témata obecnějšího charakteru a druhá přednáška v daném týdnu tato témata doplňovala a zpřesňovala. Toto uspořádání se bude podle situace měnit.

  • Introduction, assignments and evaluation, bits of history, operating system roles, operating system architecture.
    • Assignments, evaluation criteria, presentation and coding and functionality.
    • How has history influenced the development of operating systems.
    • Extended machine and resource manager.
    • Structure and architecture.
  • Rehearsal of common hardware and software concepts for those who did not know :-).
    • Computer architecture.
    • Busses, interrupts, transfers.
    • Pipelining, parallelism.
    • Memory, caches.
  • Processes, process context, process scheduling, basic scheduling algorithms.
    • Executing program.
    • Context, processes, threads.
    • Parallel execution, context switching.
    • Scheduling, cooperative, preemptive.
    • Basic schedulers, round robin, priorities, deadlines.
  • Process bootstrapping, loading and linking, system calls.
    • Starting a process, bootstrapping.
    • Exercise building proces state diagram.
    • Relocation, linking.
    • Program image, EXE, ELF.
    • System call API, Linux, Windows.
  • Process synchronization, race conditions, synchronization problems, basic tools.
    • Definition of race conditions.
    • Typical synchronization problems.
    • Synchronization means, active waiting, Dekker, Peterson, passive waiting.
    • Interface for locks and semaphores.
    • Interface for condition variables.
  • Advanced scheduling algorithms. API for processes.
    • Scheduling in Linux, Windows, Solaris, elsewhere.
    • Scheduling anomalies, convoys, inversion, deadlock.
    • Interface for forking and joining, pthreads.
  • Process communication, messages, signals, RPC.
    • Shared memory, only that it exists.
    • Messages, principal classification.
    • Posix signals.
    • System V messages.
    • Mach kernel messages.
    • RPC principles, interface description, generation of stubs, marshalling.
    • Sun RPC implementation, Microsoft DCOM implementation, very briefly.
  • Extended synchronization tools, implementation of synchronization, pitfalls to avoid.
    • Implementation of a lock, spin lock, recursive lock.
    • Barrier, futex, events, monitors, guards.
    • Non blocking synchronization, definition, principles.
  • System memory management, virtualization through paging, replacement algorithms.
    • Basic issues of memory management among processes.
    • Paging, principles, what is in hardware and in software.
    • Mapping information structure.
    • Page replacement algorithms.
  • Hardware memory virtualization support on various architectures.
    • Intel IA32.
    • Intel IA64.
    • MIPS.
    • Some others.
  • Process memory allocation, allocators, garbage collection.
    • Typical address space map, code, data, heap, stack.
    • Relative addressing on stack.
    • Allocation on heap, basic algorithms, pools, slabs.
    • Garbage collection, goals, tracing, counting, copying.
  • Advanced memory management on parallel and distributed systems.
    • Memory manager architecture, portability, pagers.
    • Memory manager API.
    • Exercise building a virtual memory architecture.
  • Device driver architecture, synchronous and asynchronous service, basic device examples.
    • Top and bottom halves, interrupt service, deferred service.
    • Existence of driver classes, driver framework.
    • Bus as a device, PCI, USB, SCSI.
    • Clock as a device.
    • Keyboard as a device.
  • Device classes and device examples except disks.
    • Mouse.
    • Console.
    • Audio devices.
    • Network cards.
    • Some others.
  • Disks, disk scheduling, interface to file systems, basics of internals.
    • Disks, interface, ATA, ATAPI, SATA.
    • Disk request scheduling, algorithms, queueing.
    • Basic interface, streams, mapping, directories, locking, backup, extras.
  • Example of device servicing in detail, interrupt handling.
    • Disk error diagnostics.
    • Disk partitioning, volume management.
    • Memory technology devices as special disks.
    • Example of interrupt handling probably on keyboard or disk.
  • Simple file systems, FAT, HPFS, NTFS.
    • Generic disk layout issues.
    • FAT.
    • HPFS.
    • NTFS.
  • Advanced file systems, EXT, XFS, RAISER, SPIRALOG.
    • EXT.
    • XFS.
    • RAISER.
    • SPIRALOG.
  • Specialized file systems, ISO9660, UDF, JFFS2, integration.
    • ISO9660, UDF, JFFS2.
    • Virtual nodes, file system integration.
  • Design of a file system that meets specific criteria.
    • Exercise with designing file system structures.
  • Networking, API, sockets, queues, filters.
    • Berkeley sockets.
    • Protocol stack architecture, copying and dispatching issues.
    • Filtering, principles.
    • Queueing, principles.
  • Network scheduling algorithms.
    • TB, SFQ, CBQ, RED.
  • Network file systems.
    • Issues with caching and consistency.
    • NFS, AFS, CODA, GFS.
  • Specialized applications of networking, load balancing clusters.
    • Memory sharing.
    • Mosix clustering.
    • Single image clusters, Amoeba, Plan 9.
  • Security, principles.
    • Imposing security, authentication and authorization.
    • Security models, access lists, capabilities, levels.
    • PAM, Kerberos, SELinux.
  • Strange operating system projects.
    • Specialized kernels, trusted systems, based on SIGOPS.

Semestrální práce

Součástí náplně předmětu je vypracování semestrální práce, jejímž cílem je vytvoření jednoduchého operačního systému v prostředí simulátoru procesoru MIPS R4000. Semestrální práce jsou určeny pro skupiny studentů, přičemž každá ze skupin má za úkol implementovat všechny tři části práce tak, aby splnily základní zadání, a jednu z těchto částí tak, aby splnila rozšířené zadání.

Na vypracování každé části semestrální práce podle základního zadání jsou čtyři výukové týdny. Dokončení vypracování rozšířeného zadání je možné v případě potřeby ještě během zkouskového období zimního semestru. Všechny skupiny mají za úkol na cvičení prezentovat svou práci ostatním studentům. Prezentace semestrální práce je nutnou podmínkou k udělení zápočtu.

Zadání jednotlivých částí

Přesná zadání jednotlivých částí semestrální práce budou zaslána cvičícími do mailing listu předmětu. Následující přehled má pouze informativní charakter.

  • Kostra kernelu
    • základní zadání
      • Bootstrap
      • Debugging support
      • Interrupt and exception handling
      • Kernel threads
      • Locks
      • All on single processor
    • rozšířené zadání
      • Semaphores
      • Condition variables
      • Blocking free lists
      • All on multiprocessor
      • Evaluation of blocking free lists
  • Správa paměti
    • základní zadání
      • Page allocator
      • Translation fault handler
      • Address space with fixed number of contiguous blocks
      • Use of statically allocated structures permitted
    • rozšířené zadání
      • Heap allocator
      • Multiple heap allocation strategies
      • Address space with unlimited number of contiguous blocks
      • Use of statically allocated structures discouraged
      • Evaluation of heap allocation strategies
  • Uživatelské procesy
    • základní zadání
      • System call interface
      • User processes with address spaces
      • Demo user process with synchronization of output on console
    • rozšířené zadání
      • Disk block device driver
      • Loading raw process image from disk blocks

Výběrové semestrální práce

Po dohodě se cvičícím se skupiny mohou rozhodnout místo výše uvedeného jednotného zadání pro zadání výběrové, které typicky představuje implementaci v nějakém reálně používaném operačním systému. Postup práce na výběrovém zadání se kontroluje na konci zkouškového období zimního semestru, na vypracování výběrového zadání je zpravidla lhůta do zkouškového období letního semestru (přesné lhůty jsou součástí dohody se cvičícím). Výběrová zadání jsou k dispozici z několika okruhů, na jejichž základě se mohou studenti také inspirovat pro své originální zadání obdobné obtížnosti.

  • OpenSolaris
    • RCU (Read-Copy-Update) synchronizace
    • Video4Solaris
    • WebDAV filesystem driver
    • HFS+ filesystem driver
    • JFFS2 filesystem driver
    • FTDI převodník mezi USB a sériovým rozhraním
  • HelenOS
    • Rozšíření implementace bezpečnostních kontextů
    • Port na novou zajímavou architekturu (např. MIPS64, Cell)
    • Rozchození nějakého portu nativně
    • Podpora real-time plánování
    • Podpora pro NUMA hardware
  • zlomekFS
    • Podpora pro weakly connected režim
  • Linux či Windows či jiný OS
    • Ovladač zařízení rozumného rozsahu
    • Jiné rozšíření rozumného rozsahu

Rozdělení do skupin

Semestrální práce jsou určeny pro tříčlenné skupiny studentů. Rozdělení do skupin spolu s preferencemi rozšířeného zadání je nutné nahlásit emailem cvičícímu.

Hodnocení semestrální práce

Při hodnocení semestrální práce je kladen důraz na celkovou kvalitu zpracování. Vedle samotné implementace je hodnocena také kvalita zápisu kódu a kvalita dokumentace:

  • kvalita implementace
    • programovací techniky
    • datové struktury
    • efektivita
    • funkčnost
  • kvalita zápisu kódu
    • struktura (členění a modularita)
    • přehlednost (oddělení logických celků, symbolické zápisy)
    • konzistence (jazyková konzistence, pojmenovávání objektů)
    • komentáře (komentáře k souborům, funkcím a logickým celkům kódu)
  • kvalita dokumentace
    • angličtina
    • popis vlastností řešení
    • úroveň ústní prezentace práce

Standardní splnění každé skupiny kritérií je hodnoceno nejvýše 7 body, 3 body jsou k dispozici pro hodnocení nad rámec standardního splnění kritérií. Celkem je tedy možné za semestrální práci získat nejvýše 30 bodů.

Odevzdání libovolné základní části semestrální práce do jednoho týdne po termínu je penalizováno ztrátou 3 bodů, do dvou týdnů po termínu je penalizováno ztrátou 5 bodů. Bodová ztráta se uplatní pouze jednou, tedy pokud například propásnete termíny dvou základních částí o jeden týden, stále budete penalizováni pouze ztrátou 3 bodů.

S výjimkou odůvodněných případů znamená odevzdání libovolné základní části semestrální práce více než dva týdny po termínu nemožnost získání zápočtu. O oprávněnosti udělení výjimky rozhoduje cvičící.

S výjimkou odůvodněných případů není možné odevzdání rozšířeného zadání semestrální práce po termínu. O oprávněnosti udělení výjimky rozhoduje cvičící.

Materiály ke stažení

K vypracování semestrální práce jsou k dispozici následující materiály:

Celkové hodnocení

Celkové hodnocení předmětu má dvě složky. První složku tvoří semestrální práce, druhou písemná zkouška. Na obě složky je kladen stejný důraz s tím, že výrazné nedostatky v jedné z obou složek hodnocení lze jen obtížně suplovat vyšším výkonem ve složce druhé.

Obě složky jsou hodnoceny číslem z intervalu [0,1], které vyjadřuje procentuální splnění požadavků v dané složce. Výsledná známka je určena součinem obou hodnocení a následujícími koeficienty:

  • S × P >= 0.63 ~ 1
  • S × P >= 0.43 ~ 2
  • S × P >= 0.23 ~ 3
  • jinak 4

Reply via email to