Operating Systems (2006/2007)

Course partially running

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

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.


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

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