Degree in Computer Science

Operating Systems (2011/2012)

Course code 4S00019   Credits 12   Coordinator Graziano Pravadelli Disciplinary sector ING-INF/05 - Information Processing Systems Teaching language Italian

Links Course news Seminars related to the course

Teaching is organised as follows:

Lecture timetable

Educational objectives

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.

Syllabus

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

Laboratory:
------------
* 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, ...).
* Thread programming.

Exam methods

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

Laboratory:
-----------
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 second half of June.
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.

Teaching aids
Activity	Title	Format (Language, Size, Publication date)
Teoria	10- Gestione della memoria virtuale	pdf (it, 1,043.956 KB, 12/7/11)
Teoria	11- Gestione della memoria secondaria	pdf (it, 2,426.028 KB, 12/19/11)
Teoria	12- Il file system	pdf (it, 1,794.825 KB, 1/10/12)
Teoria	13- Strutture RAID	pdf (it, 750.654 KB, 1/17/12)
Teoria	14- Sottosistema di I/O	pdf (it, 841.194 KB, 1/17/12)
Teoria	15- Caso di studio	pdf (it, 1,345.854 KB, 1/20/12)
Teoria	1- Presentazione del corso	pdf (it, 272.192 KB, 10/3/11)
Teoria	2- Definizione e storia dei sistemi operativi	pdf (it, 799.022 KB, 10/3/11)
Teoria	3- Componenti di un sistema operativo	pdf (it, 360.596 KB, 10/3/11)
Teoria	4- Architettura di un sistema operativo	pdf (it, 396.527 KB, 10/5/11)
Teoria	5- Processi e thread	pdf (it, 1,032.123 KB, 10/10/11)
Teoria	6- Scheduling della CPU	pdf (it, 1,444.221 KB, 10/26/11)
Teoria	7- Sincronizzazione tra processi	pdf (it, 1,639.778 KB, 10/28/11)
Teoria	8- Deadlock	pdf (it, 600.064 KB, 11/13/11)
Teoria	9- Gestione della memoria	pdf (it, 1,339.317 KB, 11/21/11)
Teoria	Calendario appelli	pdf (it, 34.393 KB, 11/21/11)
Teoria	Calendario delle lezioni del I semestre	pdf (it, 52.897 KB, 1/18/12)
Laboratorio	Calendario laboratorio	pdf (it, 49.926 KB, 3/19/12)
Laboratorio	Consegne elaborati	pdf (it, 27.488 KB, 3/1/12)
Laboratorio	Divisione studenti per laboratorio	pdf (it, 42.717 KB, 3/19/12)
Laboratorio	Materiale didattico di laboratorio	html (it, 39.31 KB, 5/17/12)

Statistics on students' past performance (Art. 2 del D.M. 31/10/2007, n. 544)

Data from AA 2011/2012 are not available yet