Operating Systems - Teoria (2005/2006)

Learning outcomes

The course presents an introduction to the main concepts related to operating systems, which are essential tools for the coordination of computer’s tasks and resources. In particular, the course focuses on topics related to SW architectures, and process and resource (memory, file system, …) management. Finally, the laboratory concerns about the use of a Unix-like operating system.
The course is composed of 48 class hours (6 credits) of theory, and 48 class hours (4 credits) of laboratory.

* Introduction: The role of the operating system and its evolution. Architectural elements. Structure and functionality of an operating system.

* Process management: Processes. State of processes. Context switch. Process creation and termination. Threads. User threads and kernel threads. Process cooperation and communication: shared memory, messages. Direct and indirect communication.

* Scheduling: CPU-I/O burst model. Long-time, middle-time and short-time scheduling. Preemptive and non-preemptive scheduling. Scheduling criteria. Scheduling algorithm: FCFS, SJF, priority-based, RR, multiple queue, feedback. Evaluation of the algorithms based on deterministic models, probabilistic models, and simulation.

* Process synchronization. Data coherency, atomic operation. Critical section. SW solutions to mutual exclusion: algorithms of Peterson and Dekker, bakery’s algorithm. HW solutions to mutual exclusion, test and set, swap. Synchronization: semaphores, monitor. Deadlock and starvation management. Example of synchronization: producer/consumer, writer/reader, dining philosophers, sleeping barber.

* Deadlock. Necessary conditions for deadlocks. Allocation graph. Deadlock prevention. Deadlock avoidance. Banker’s algorithm. Deadlock detection and recovery.

* Memory management. Main memory. Physical and logic addressing. Re-location, address binding. Swapping. Contiguous memory allocation. Internal and external fragmentation. Paging. HW for paging: TLB. Page table. Multi-level paging. Segmentation. Segment table. Paging and Segmentation.

* Virtual memory. Paging on demand. Page fault management. Algorithms for page replacement: FIFO, optimal, LRU and approximations. Buffering. Frame allocation: local and global. Thrashing. Working set. Analysis of page fault frequency.

* Secondary memory. Physical and logical structure of disk. Access time. Disk scheduling: FCFC SSTF, SCAN, C-SCAN, LOOK, C-LOOK.

* I/O subsystem. I/O hardware. Programming I/O, interrupt, DMA. Device driver and application interface. Kernel /O services: scheduling, buffering, caching, spooling.

* File system. File, attributes and operations. Sequential and direct access. Directory structure. File protection. Consistency semantics. Structure of a file system. Mounting. Block allocation: contiguous, linked, indexed. Free space management.

* Case study. Unix: kernel structure and main functionalities.

The exam is written and consists of practical exercises and questions. Oral exam is facultative.
Two intermediate exams are scheduled during the course.
For the laboratory exam see the corresponding course.
The final score is provided by the following formula:
Score = theory_score*0.6+ laboratory_score*0.4
The theory_score for students that succeeds on intermediate exams is provided by the following formula:
Theory_score =2/3*score_exam_1+1/3*score_exam_2