Slides

Notes

List

Wiki

Main

Home

Operační systémy

Rozvrh

V zimním semestru 2011/2012 se přednášky konají každý týden v pondělí od 9:00 do 10:30 v učebně S3 a ve čtvrtek od 9:00 do 10:30 v učebně S3. Cvičení se konají podle níže uvedeného harmonogramu v úterý od 9:00 do 10:30 v učebně S6 a ve čtvrtek od 12:20 do 13:50 v učebně S8.

Harmonogram cvičení	Úterní běh	Čtvrteční běh
1.1 Úvod, náplň, požadavky [slajdy]	4. října 2011	6. října 2011
1.2 Zveřejnění zadání semestrálních prací [mailing list]	9. října 2011	9. října 2011
2.1 Seznámení s prostředím pro vypracování semestrálních prací [slajdy]	11. října 2011	13. října 2011
2.2 Nahlášení skupin, výběr rozšířeného zadání	16. října 2011	16. října 2011
3. Seznámení s výukovým systémem Kalisto [slajdy]	20. října 2011	20. října 2011
3. až 6. týden: samostatná práce, konzultace
6. Odevzdání základního zadání Kostra kernelu	13. listopadu 2011	13. listopadu 2011
7. až 10. týden: samostatná práce, konzultace
10. Odevzdání základního zadání Správa paměti	11. prosince 2011	11. prosince 2011
11. až 15. týden: samostatná práce, konzultace
15.1 Prezentace semestrálních prací a výběrových zadání	10. ledna 2012	12. ledna 2010
15.2 Odevzdání základního zadání Uživatelské procesy	15. ledna 2012	15. ledna 2012
20. Osobní odevzdání rozšířeného zadání, milestone výběrových zadání	17. února 2012	17. února 2012

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 d3s.mff.cuni.cz
• Martin Děcký, martin.decky at d3s.mff.cuni.cz
• Petr Tůma, petr.tuma at d3s.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 může podle situace měnit.

Harmonogram přednášek	Datum
Overview Lecture Administrative introduction. Rehearsal of common hardware concepts. Computer architecture. Addressing, buses, transfers.	3. října 2011
Detailed Lecture Rehearsal of common hardware concepts. Interrupts. Direct memory access. Pipelined and superscalar execution. Memory content caching. Bus timing diagrams.	6. října 2011
Overview Lecture History, operating system roles, operating system architecture. How has history influenced the development of operating systems. Roles of extended machine and resource manager. Monolithic kernels, microkernels. Virtualization basics.	10. října 2011
Detailed Lecture Processes, process context. Executing program. Context, processes, threads. Parallel execution, context switching. Process bootstrapping. Starting a process, system bootstrapping.	13. října 2011
Overview Lecture Process scheduling. Exercise building proces state diagram. Scheduling basics, cooperative, preemptive. Scheduling requirements, application classes. Basic schedulers, round robin, priorities, deadlines. Processes. Process and thread lifecycle API.	17. října 2011
Detailed Lecture Process loading and linking. Principles of relocation and linking. Program image, EXE, ELF. System architecture. System call basics. System call API, Linux, Windows, Kalisto.	24. října 2011
Detailed Lecture Process scheduling, scheduling algorithms. Scheduling in Linux, Windows, Solaris. Some advanced scheduling algorithms. Scheduling on multiprocessors. Scheduling API.	27. října 2011
Overview Lecture Process synchronization, race conditions, synchronization problems. Definition of race conditions. Typical synchronization problems. Process synchronization, basic tools. Synchronization means. Active waiting, Dekker, Peterson. Passive waiting, algorithm sketch.	31. října 2011
Mixed Lecture Basic synchronization tools. Interfaces for atomic operations and barriers. Interface for locks of various kinds. Introduction to memory models.	3. listopadu 2011
Mixed Lecture More memory models. Operation ordering and data races. Examples of common memory models. More synchronization tools. Semaphores, condition variables, usage. Exotic tools, events, monitors, guards. Advanced synchronization tools. Non blocking synchronization, definition, principles. Scheduling anomalies, convoys, inversion, deadlock.	7. listopadu 2011
Overview Lecture Process memory management. Typical process memory layout. Stack organization, frames, addressing. Heap organization, block selection algorithms, overhead, fragmentation. Garbage collection principles, reference counting, reference tracing.	10. listopadu 2011
Overview Lecture Process memory management. Heap organization, block selection algorithms, overhead, fragmentation. Garbage collection principles, reference counting, reference tracing. Memory management overhead summary.	14. listopadu 2011
Overview Lecture System memory management, virtualization through paging. Basic issues of memory management among processes. Paging, principles, what is in hardware and in software. Mapping information structure, paging tables, translation caches. Page replacement algorithms, locality of reference, input information.	21. listopadu 2011
Detailed Lecture Hardware memory virtualization support on various architectures. Intel IA32. Intel IA64. MIPS. Some others.	24. listopadu 2011
Detailed Lecture Hardware memory virtualization support on various architectures. Intel IA32. Intel IA64. MIPS. Some others. System memory management, virtualization through segmentation.	28. listopadu 2011
Overview Lecture Introduction to process communication. Shared memory, messages, principles and classification. Process communication, messages, signals, RPC. Posix signals. System V messages. Mach kernel messages. RPC principles, interface description, stub generation, marshalling. Sun RPC implementation, very briefly, just as an example of how things work.	1. prosince 2011
Overview Lecture Device driver architecture, synchronous and asynchronous service, basic device examples. Top and bottom halves, interrupt service, deferred service. Existence of driver classes, driver framework.
Detailed Lecture Device driver architecture, basic device examples. Bus as a device, PCI, USB, SCSI. Device identification. Driver interface.
Detailed Lecture Device classes and device examples. Mouse. Console. Audio devices. Network cards. Some others.
Detailed Lecture Device classes and device examples. Graphics. Disks. Disks as devices. Disk interface, ATA, ATAPI, SATA. Memory technology devices as special disks. Disk request scheduling, algorithms, queueing. Disk partitioning, volume management.
Mixed Lecture Disk error diagnostics. File system interfaces.
Introductory Lecture File system interfaces. File system disk layout, principles, examples. FAT, FAT32, exFAT HPFS ext2, ext3, ext4 NTFS

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 implementační práci 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 (kdy je potřeba demonstrovat milestone, tedy jakousi pokročilou alfa-verzi řešení), na vypracování výběrového zadání je zpravidla lhůta do konce zkouškového období letního semestru (přesné lhůty jsou součástí dohody se cvičícím). Také v případě výběrových zadání je prezentace semestrální práce nutnou podmínkou k udělení zápočtu.

Řešitelé si mohou vymyslet vlastní téma semestrální práce, pokud bude mít přiměřenou obtížnost a pochopitelně netriviální vztah k předmětu. Obvyklé bývá programování ovladače či nějakého rozšíření pro systém Linux, Windows, Mac OS X, Solaris, HelenOS a podobně. Další typickou možností bývá rozšíření nějakého souborového systému (např. zlomekFS), z didaktických důvodů už ovšem neakceptujeme implementaci nových linuxových souborových systémů.

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 nejpozději do termínu, který je uveden v harmonogramu výše. Jen ve výjimečných případech (například v souvislosti s výběrovou semestrální prací) a po předchozí domluvě budou povoleny skupiny s jiným počtem členů.

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í
• provázanost generovaných a ručně psaných částí dokumentace
• ú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ů.

Nutnou podmínkou získání zápočtu je také krátká ústní prezentace na cvičení poslední týden semestru. Hodnocení kvality této prezentace je zahrnuto do kategorie kvalita dokumentace.

Odevzdání libovolné čá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é čá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í.

Materiály ke stažení

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

• Překladač jazyka C pro MIPS
  • toolchain.mips.sh, skript pro stažení a přeložení binutils 2.21.1 a GCC 4.6.1 pro MIPS
  • Linux
    • gcc-4.6.1.bin.linux.x86.tar.bz2, binární verze pro x86 přeložená s prefixem /usr/local/cross/mips32
    • gcc-4.6.1.bin.linux.x86_64.tar.bz2, binární verze pro x86-64 přeložená s prefixem /usr/local/cross/mips32
    • gcc-4.5.1.bin.linux.ppc.tar.bz2, binární verze pro PowerPC přeložená s prefixem /usr/local/cross/mips32
    • gcc-4.5.1.bin.linux.sparc.tar.bz2, binární verze pro UltraSPARC přeložená s prefixem /usr/local/cross/mips32
  • Solaris
    • gcc-4.4.1.bin.solaris.sparc.tar.bz2, binární verze pro UltraSPARC přeložená s prefixem /usr/local/cross/mips32
  • Mac OS X
    • gcc-4.5.1.bin.macosx.x86_64.tar.bz2, binární verze pro x86-64 přeložená s prefixem /usr/local/cross/mips32
    • gcc-4.5.1.bin.macosx.ppc.tar.bz2, binární verze pro PowerPC přeložená s prefixem /usr/local/cross/mips32
  • Windows
    • gcc-4.6.1.bin.win32.x86.zip, binární verze pro x86
    • MSYS-1.0.11.exe, makedepend.zip, shellové prostředí pro x86 (Bash, GNU Make a další utility)
• Simulátor MIPS R4000
  • msim-1.3.8.1.tar.bz2, zdrojový kód simulátoru
  • Linux
    • msim-1.3.8-1.fc13.src.rpm, zdrojový RPM balíček
    • msim-1.3.8-1.fc13.i386.rpm, RPM balíček pro Fedoru 13 na x86
    • msim-1.3.8-1.fc13.x86_64.rpm, RPM balíček pro Fedoru 13 na x86-64
    • msim-1.3.8-1.fc12.ppc.rpm, RPM balíček pro Fedoru 12 na PowerPC
    • msim-1.3.8.bin.linux.x86.tar.bz2, binární verze pro x86 přeložená s prefixem /usr/local
    • msim-1.3.8.bin.linux.x86_64.tar.bz2, binární verze pro x86-64 přeložená s prefixem /usr/local
    • msim-1.3.8.bin.linux.ppc.tar.bz2, binární verze pro PowerPC přeložená s prefixem /usr/local
    • msim-1.3.8.bin.linux.sparc.tar.bz2, binární verze pro UltraSPARC přeložená s prefixem /usr/local
  • Mac OS X
    • msim-1.3.8.bin.macosx.x86_64.tar.bz2, binární verze pro x86-64 přeložená s prefixem /usr/local
    • msim-1.3.8.bin.macosx.ppc.tar.bz2, binární verze pro PowerPC přeložená s prefixem /usr/local
  • Windows
    • msim-1.3.8.1.bin.win32.zip, binární verze pro x86
• Jádro výukového systému
  • kalisto-0.8.9.tar.bz2
• Dokumentace
  • Manuály pro procesor MIPS
    • MIPS R4000 Microprocessor User's Manual, 2. vydání příručky k procesoru MIPS R4000 z roku 1994
    • MIPSpro Assembly Language Programmer's Guide, příručka pro programování v assembleru na procesorech MIPS
    • MIPS32 4K Processor Core Family Software User's Manual, příručka k rodině procesorů MIPS32 4K (vychází z MIPS R3000 a R4000) z roku 2001
  • Dokumentace simulátoru
    • Reference Manual
    • Tutorial (zatím neúplný)

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