Operating Systems (2007/2008)

Course Not running, not visible

Teaching is organised as follows:
Unit Credits Academic sector Period Academic staff
Teoria 6 ING-INF/05-INFORMATION PROCESSING SYSTEMS 2° Q, 3° Q Graziano Pravadelli
Laboratorio 4 ING-INF/05-INFORMATION PROCESSING SYSTEMS 3° Q Graziano Pravadelli

Learning outcomes

Module: Teoria
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.

Module: Laboratorio
The course consists of 48 hours of lectures and practical applications. It provides the students with an introduction to the operating system programming focusing on the Unix System V and Linux environments. At the end of the course the student will be able to implement shell scripts and C programs covering all the aspectes reported in the following program.


Module: Teoria
* 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.

Module: Laboratorio
* Introduction to C programming: compiler, linker, libraries and the make program.

* Structure of a C program: variables, statements, functions and parameter passing, pointers and dynamic memory allocation, I/O and string management.

* System programming
- Shell scripts (bash)
o script structure
o selection and iteration
o input and output
o variables
o system commands
- System programming in C
o files and directories
o processes (fork / exec)
o pipe and named pipe
o semaphores
o shared memory
o message queues
- Threads:
o thread creation and termination
o thread synchronization

Assessment methods and criteria

Module: Teoria
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).

Module: Laboratorio
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 observance of deadlines is mandatory. Students that miss the deadline cannot take the exam in the oral mode. Besides, the oral mode can be taken only by students that pass a test on C programming.

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

For the exam method related to the theory course, please see the corresponding course.

The total 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).

Reference books
Author Title Publisher Year ISBN Note
A. Silberschatz, P.B. Galvin, G. Gagne Sistemi Operativi (Edizione 6) Addison Wesley 2002 8871921402
A. Silbertschatz, P.B. Galvin, G. Gagne Sistemi operativi (con esempi in Java) (Edizione 6) Apogeo 2005 8850321007