Operating Systems - Teoria (2006/2007)

Learning outcomes

The course covers the basic concepts related to operating systems for coordinating tasks and resources in a computer. In particular, the focus will be on process and resource management (e.g., memory, file system, etc.). Theoretical concepts will be further investigated with practical applications on the Linux operating system during the laboratory course.

The theoretical course consists of 48 hours of front lectures. Further 48 hours will be provided for the laboratory course.

* Introduction: Evolution and role of the operating system. Architectural concepts. Organization and functionality of an operating system.

* Process Management: Processes. Process status. Context switch. Process creation and termination. Thread. User-level thread and kernel-level thread. Process cooperation and communication: shared memory, messagges. Direct and indirect communication.

* Scheduling: CPU and I/O burst model. Long term, short term and medium term scheduling. Preemption. Scheduling criteria. Scheduling algorithm: FCFS, SJF, priority, RR, multiple queues with and without feedback. Algorithm evaluation: deterministic and probabilistic models, simulation.

* Process synchronization: data coherency, atomic operations. Critical sections. SW approaches for mutual exclusion: Peterson and Dekker's algorithms, baker's algorithm. HW for mutual exclusion: test and set, swap. Synchronization constructs: semaphores, mutex, monitor. Deadlock, starvation. Examples: producer/consumer, readers/writers, dining philosophers.

* Deadlock: Deadlock conditions. Resource allocation graph. Deadlock prevention. Deadlock avoidance. Banker's algorithm. Deadlock detection e recovery.

* Memory management: Main memory. Logical and physical addressing. Relocation, address binding. Swapping. Memory allocation. Internal and external fragmentation. Paging. HW for paging: TLB. Page table. Multi-level paging. Segmentation. Segment table. Segmentation with paging.

* Virtual memory: Paging on demand. Page fault management. Page substitution algorithms: FIFO, optimal, LRU, LRU approximations. Page buffering. Frame allocation: local and global allocation. Thrashing. Working set model. Page fault frequency.

* Secondary memory. Logical and physical structure of disks. Latency time. Disk scheduling algorithms: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK. I/O subsystem: I/O Hardware. I/O techniques: programmed I/O, interrupt, DMA. Device driver and application interface. I/O kernel services: scheduling, buffering, caching, spooling.

*File System: file, attributes and related operation. File types. Sequential and direct access. Directory structure. Access permissions and modes. Consistency semantics. File system structure. File system mounting. Allocation techniques: adjacent, linked, indexed. Free space management: bit vector, lists. Directory implementation: linear list, hash table.

* Case study: UNIX. Kernel structure and implementation of main functionalities.

The final exam consists of a written test containing questions and exercises. Alternatively students can pass the exam by solving two intermediate tests during the course. For the laboratory exam, please see the related course.
The final grade will be obtained according to the following formula:
finale_grade = theory_grade*0.6 + laboratory_grade*0.4

The theory grade for students that pass the exam with intermediate tests is computed according to the following formula:
theory_grade = 2/3*grade_test1 + 1/3*grade_test2

The exam (theory+laboratory) must be completed within 4 sessions starting from the session when the student passes the theory exam or the laboratory exam (according to the one that is passed first).