Operating Systems (2016/2017)

Course code
Graziano Pravadelli
Academic sector
Language of instruction
Teaching is organised as follows:
Activity Credits Period Academic staff Timetable
Teoria 8 I sem. Graziano Pravadelli
Esercitazioni 2 II sem. Nicola Drago
Laboratorio [Laboratorio 1] 2 II sem. Nicola Drago
Laboratorio [Laboratorio 2] 2 II sem. Michele Lora

Lesson timetable

Learning outcomes

The course introduces to operating system design, with particular regards to concepts related to the architecture of an operating system, and to the management and synchronization of processes and resources.
At the end of the course, the students will be able to understand how an operating system works and they will know how to:
- develop or update components of an operating system;
- develop applications that use the functionality offered by the operating system.


* 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 threads and kernel-level threads. 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-based, RR, HRRN, 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: 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. RAID.

*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.

* 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.

* Shell programming in Unix/Linux.
* Introduction to the system programming in Unix/Linux.
* System calls for I/O.
* System calls for process management.
* System calls and techniques for inter-process communication and synchronization (pipe, fifo, message queue, share memory, semaphores, ...).

Assessment methods and criteria

The exam is composed of two parts: theory and laboratory.
To pass the exam, the student must show
- they have understood the principles related to how an operating system works
- they are able to describe the concepts in a clear and exhaustive way without digressions
- they are able to apply the acquired knowledge to solve application scenarios described by means of exercises, questions and projects.

The final exam consists of a written test containing questions and exercises.

The exam can be taken in two modes: oral or written.

Oral mode:
During the course, students must solve 4 homeworks and provide the corresponding solutions within deadlines defined by the theacher. Then, at the end of the course, on the second half of June, each student must present orally the provided solutions to the theacher.
The exam can be taken in oral mode only on the first week of July.
The observance of deadlines is mandatory. Students that miss the deadline cannot take the exam in the oral mode.

Written mode:
The exam consists of solving some exercises related to system programming by means of shell scripts and/or C programs.

Total grade
The total grade (thery+laboratory) is given by:
theory_grade*0.5 + laboratory_grade*0.5.

Reference books
Activity Author Title Publisher Year ISBN Note
Teoria Andrew S. Tanenbaum I moderni sistemi operativi (Edizione 3) Addison Wesley 2009 8871925408 Un classico, da consultare per vedere spiegati gli argomenti in una forma diversa da quella del libro di testo consigliato.
Teoria Dhananjay M. Dhamdhere Sistemi Operativi (Edizione 1) McGraw-Hill 2010 9788838664878 Libro con taglio più americano. Da consultare per approfondimenti.
Teoria Abraham Silberschatz, Peter Baer Galvin, Greg Gagne Sistemi operativi. Concetti ed esempi. (Edizione 9) Pearson 2014 9788865183717 Questo è il testo consigliato. Segue lo stesso flusso adottato dalle slide.
Teaching aids
Title Format (Language, Size, Publication date)
Calendario lezioni I semestre  pdfpdf (it, 42 KB, 03/01/17)
Dove trovare il materiale didattico plain plain (it, 0 KB, 23/09/16)