Introduction to computer architecture and operating systems (2019/2020)

Course code
Tiziano Villa
Other available courses
Other available courses
    Academic sector
    Language of instruction
    Teaching is organised as follows:
    Activity Credits Period Academic staff Timetable
    Teoria mod. 1 6 I semestre Tiziano Villa

    Go to lesson schedule

    Teoria mod. 2 3 II semestre, I semestre Tiziano Villa

    Go to lesson schedule

    Laboratorio 3 II semestre, I semestre Nicola Drago

    Go to lesson schedule

    Learning outcomes

    The aim of the course is to provide the theory and practice to implement an algorithm in hardware, exploring a spectrum of options ranging from dedicated specialized devices to programs on a general-purpose processor. The students will understand how a processor works and how an high-level program is translated into machine language and then executed; they will understand the organization of a computer system and of the operating systems running on it, with the related issues of cor-rectness and efficiency.

    At the end of the course, the students will be able to design specialized hardware for simple algo-rithms; translate simple programs from an high-level specification to machine language; write shell scripts using system calls in C in the UNIX environment; manage an information system, especially for what the installation and maintenance of applications and resources is concerned.


    Computer Architecture.

    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.

    Operating systems.

    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.

    Practical exercises: system-level and shell programming with C.

    Assessment methods and criteria

    Written test for the theoretical part with questions and exercises (3/4 of the final grade).
    Programming projects and written test for the laboratory (1/4 of final grade).

    Reference books
    Activity Author Title Publisher Year ISBN Note
    Teoria mod. 1 R.Katz, G.Borriello Contemporary logic design (Edizione 2) Pearson Education International 2005 0-13-127830-4
    Teoria mod. 1 Y.N. Patt, S.J. Patel Introduction to Computing Systems (Edizione 2) McGrawHill 2004 978-0-07-246750-5
    Teoria mod. 1 Franco Fummi, Mariagiovanna Sami, Cristina Silvano Progettazione Digitale (Edizione 2) McGraw-Hill 2007 8838663521
    Teoria mod. 2 Randal E. Bryant, David R. O'Hallaron Computer Systems: A Programmer's Perspective (Edizione 3) Pearson; 3 edition (March 12, 2015) 2015 978-0134092669
    Teoria mod. 2 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, 18/11/19)
    Architettura - Lezioni LC3  x-gzipx-gzip (it, 6577 KB, 02/02/20)
    XX-TV Temi d'esame  x-gzipx-gzip (it, 4241 KB, 19/12/19)
    EASO-M0 Storia dei sistemi di calcolo  pdfpdf (en, 3172 KB, 15/12/19)
    EASO-M1 Processi  pdfpdf (en, 1048 KB, 08/12/19)
    EASO-M2 Sincronizzazione dei processi  pdfpdf (en, 1109 KB, 19/12/19)
    EASO-M3 Gestione dei processi  pdfpdf (en, 1858 KB, 15/01/20)
    EASO-M4 Memoria  pdfpdf (en, 2296 KB, 18/02/20)
    2020-03-20 EserciziBaseScript.pdf  pdfpdf (it, 170 KB, 20/03/20)
    2020-Elaborato BASH.pdf  pdfpdf (it, 259 KB, 15/04/20)
    2020-Elaborato SystemCall.pdf  pdfpdf (it, 108 KB, 15/05/20)
    Corso shell UNIX (BASH)  pdfpdf (it, 4992 KB, 11/03/20)
    Elenco comandi di SHELL.pdf  pdfpdf (it, 236 KB, 20/03/20)
    Esercizi utilizzo comandi di shell  pdfpdf (it, 83 KB, 11/03/20)
    IstructionSet.pdf  pdfpdf (it, 43 KB, 17/01/20)
    LC3 - Esercizi.pdf  pdfpdf (it, 292 KB, 30/01/20)
    LC3 - Lezione1.pdf  pdfpdf (it, 475 KB, 16/01/20)
    LC3 - Lezione2.pdf  pdfpdf (it, 540 KB, 16/01/20)
    LC3 - Lezione3.pdf  pdfpdf (it, 409 KB, 16/01/20)
    ModalitàDiEsame2020.pdf  pdfpdf (it, 327 KB, 30/01/20)
    Shell_EserciziScript.pdf  pdfpdf (it, 20 KB, 27/03/20)
    SystemCallLucidi.pdf  pdfpdf (it, 1538 KB, 15/04/20)