Introduction to computer architecture and operating systems (2015/2016)



Course code
4S02717
Credits
12
Coordinator
Tiziano Villa
Academic sector
ING-INF/05 - INFORMATION PROCESSING SYSTEMS
Language of instruction
Italian
Teaching is organised as follows:
Activity Credits Period Academic staff Timetable
Teoria 9 I semestre Tiziano Villa
Laboratorio 3 II semestre Nicola Drago

Lesson timetable

I semestre
Activity Day Time Type Place Note
Teoria Monday 2:30 PM - 4:30 PM lesson Lecture Hall D  
Teoria Wednesday 2:30 PM - 4:30 PM lesson Lecture Hall A  
Teoria Thursday 8:30 AM - 10:30 AM lesson Lecture Hall B  
II semestre
Activity Day Time Type Place Note
Laboratorio Tuesday 2:30 PM - 6:30 PM laboratorio Laboratory Alfa  

Learning outcomes

Module:
-------

The first part of the class describes how to implement an algorithm into a digital architecture. Some design alternatives are presented ranging from a pure software, running on a general purpose computer, to an ad-hoc hardware implementation. The goal is to understand the compilation steps transforming an high-level programming language into machine-level code.

The second part of the class describes the architecture of an operating system, with the objective to understand the management and synchronization of processes and resources of a general-purpose computing system.

Syllabus

Module:
-------

Fundamentals: information coding, Boolean functions, arithmetic.

Digital design: combinational circuits, sequential circuits, special purpose architectures (control unit + data path), programmable units.

Computer architecture: basic principles, instruction set, processor, memory hierarchy, I/O organization.

Practical exercises: assembly programming of LC-3 architecture.


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, messages. 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.

Assessment methods and criteria

Module:
-------

Written text for the theoretical part (3/4 of final grade).

Programming projects and written text for the laboratory (1/4 of final grade).

Reference books
Activity Author Title Publisher Year ISBN Note
Teoria R.Katz, G.Borriello Contemporary logic design (Edizione 2) Pearson Education International 2005 0-13-127830-4
Teoria Y.N. Patt, S.J. Patel Introduction to Computing Systems (Edizione 2) McGrawHill 2004 978-0-07-246750-5
Teoria Franco Fummi, Mariagiovanna Sami, Cristina Silvano Progettazione Digitale (Edizione 2) McGraw-Hill 2007 8838663521
Teoria Abraham Silberschatz, Peter Baer Galvin, Greg Gagne Sistemi operativi. Concetti ed esempi. (Edizione 9) Pearson 2014 9788865183717
Teaching aids
Title Format (Language, Size, Publication date)
Architettura - Cap. 1-10 CLD Borriello-Katz  x-gzipx-gzip (en, 745 KB, 30/09/15)
Architettura - Lezioni LC-3, Cap. 5, 7-10, ISA  x-gzipx-gzip (it, 6358 KB, 17/12/15)
Architettura - Lezioni Vahid  x-gzipx-gzip (en, 291 KB, 14/12/15)
Lezioni UCB Sistemi Operativi (fino a Lez. 15)  pdfpdf (en, 9620 KB, 11/01/16)
XX-TV Temi d'esame  x-gzipx-gzip (it, 1905 KB, 09/11/15)
2016 Elaborato2 - System CALL C.pdf  pdfpdf (it, 431 KB, 17/05/16)
2016 Esercitazione SHELL - 29 Aprile.pdf  pdfpdf (it, 133 KB, 29/04/16)
2016 Esercizi LC3 con Soluzioni.pdf  pdfpdf (it, 155 KB, 07/06/16)
2016 Esercizi LC3.pdf  pdfpdf (it, 138 KB, 01/04/16)
2016 Esercizi LC3 - Soluzioni.pdf  pdfpdf (it, 155 KB, 12/04/16)
Esercizi C.pdf  pdfpdf (it, 126 KB, 12/04/16)
Esercizi_Pipe_Fifo.tgz  x-gzipx-gzip (it, 23 KB, 26/04/16)
Esercizi SHELL.pdf  pdfpdf (it, 83 KB, 22/03/16)
Ex1SystemCall.txt plain plain (it, 3 KB, 19/04/16)
IstructionSet.pdf  pdfpdf (it, 43 KB, 01/04/16)
System Call C - Linux  pdfpdf (it, 259 KB, 26/04/16)
Testo Elaborato1 - SHELL.pdf  pdfpdf (it, 421 KB, 13/04/16)
Unix Shell.pdf  pdfpdf (it, 4992 KB, 01/04/16)

STUDENT MODULE EVALUATION - 2015/2016