FANDOM


SummaryEdit

1. Number of study hours: 17

2. Short description of the course: The course “Operating Systems” is organized in five units. The first unit is an introduction that presents the organization of the operating systems and the mechanisms that enable the interactions with the user, with the applications, and with the hardware. The next units present the aspects related to the management of the processor, memory, and security. In particular the second unit introduces the concept of concurrency and it explains how this concept is implemented in terms of processes and threads. The third unit defines the concept of virtual memory, presents the memory management techniques based on swapping and paging, and discusses the functions of a file system. The fourth unit introduces the security issues, defines the concept of identification and authentication, presents the main protection mechanisms, and discusses the threats to the systems and the defences to these threats. The last unit describes the main functionalities of the Linux and Windows operating systems.

3. Target groups: The employers of IT core level professionals are the target sector. The project objectives directly address the promotion of high knowledge and skills standards in IT area and in particular provide an innovative approach to training. The first target group consists of IT students (vocational school IT basic level training and the first courses of colleges and universities) in technology area and IT practitioners not having vocational certificates yet.

4. Prerequisites The prerequisites for this course are basic knowledge on the computer architectures (see course C.1 Computing Components and Architectures) and on computer programming (see course B.3 Programming).



5. Aim of the course - learning outcomes The main objective of the course is to give a good knowledge of the main issues related to the design of the operating systems and of the features of some of the most widely used systems, and to give a better understanding of the limits and potentialities of real operating systems. To this purpose the course adopts a standard structure, introduces the principles and the fundamental concepts that are the base of the operating systems, and it discusses how these concepts are implemented in real systems. In particular it analyses the techniques that can be used to coordinate the processes, to manage the system resources, and to abstract the hardware. Finally the module presents the main features of the operating systems Linux and Windows.


ContentsEdit

C2.1 PrinciplesEdit

1.1.1. C2.1.1 Functions of a typical operating system for a general purpose computer A computer comprises three main elements: the hardware , the operating system, and the applications (the last two elements are the software layers of the computer). The operating system is a program that behaves as an intermediary between the applications and the hardware. Its main purpose is to provide the user with an environment for the execution of the applications. The operating system also offers to the applications a standard interface for the use of the devices . Thus the applications do not need to know the specific interface of each device, but they use the standard interface and leave to the operating system the task of interacting with the device. The operating system can also be seen as a resources manager. Let us imagine what may happen if several programs use the same device (say a printer) at the same time. The result could be chaotic as the prints of the programs may overlap. From this point of view the operating system acts as a referee. In particular it decides when and how long an application can use a given resource. Since different resources should be managed with different policies, the operating system includes a component for the management of each resource class. The most important resource managers are the processor, memory, and devices managers, and the file system . All the operating system components are encapsulated into a unique program called kernel that offers all of the operating system services. However some parts of the operating system (such as compilers or interfaces) may not be included into the kernel. For security reasons (see “Security and protection”), the code not included in the kernel (that includes all the applications) is executed in user mode. In user mode an application can use only its own data, and it cannot interfere with other application or with the kernel. However the kernel is always executed in supervisor mode where it has access to all the system resources.


The main elements of a computer: hardware, operating system and applications.

The figure shows the three main elements of a computer: hardware, operating system and applications. The applications and the operating system are the software layers.


The operating system resource managers The figure shows the three elements of a computer: Hardware, Operating System and Applications. The operating system comprises four resource managers: the processor manager, the memory manager, the devices manager and the file system. Each component communicates with the applications and with the hardware. C2.1.2 The different types of operating systems: batch, time-sharing, and real-time The first operating systems (batch systems) were not interactive at all. The programmer had to write the program with its data (job) on paper, to punch it on cards, and to send the cards to the computer centre for the execution. The first batch systems were mono-programmed and they could execute only one job per time. As the computer became more powerful the batch systems became multi-programmed (that is they could execute more than one job at the same time). The lack of interactivity is the main limit of batch systems. With the technological advance in computer system design and with the availability of user-friendly interfaces the operating systems became interactive. To enforce interactivity, however, short response times to the user commands are mandatory, and it is necessary to guarantee a uniform progress to all the programs in the system. To this purpose the processor time is split into time intervals called quantums, and the processor is cyclically assigned to each program for a quantum. The operating systems that use this strategy are called time-sharing. Several users using a time-sharing system at the same time are unaware of each other, and each of them believes he has the entire system for himself Batch and time-sharing systems are however unfit to support applications where there are temporal deadlines to be met (for instance the control of industrial plants). In some of these applications the deadlines are so critical that, if they were not met, the controlled system would become dangerous for human life, for the environment, or for the economy. For instance, missing a deadline in an industrial plant control application may compromise the integrity of the plant itself. The operating systems that enforce the respect of critical deadlines are called hard real-time. In other applications the deadlines are important but not critical (for instance in the reproduction of a movie). The systems supporting this kind of applications are called soft real-time.


C2.1.3 The Application Program Interface (API ) The kernel defines an interface, which associates a procedure (called system call) to each service offered by the operating system. For instance a write operation on a device is a service, which is offered by the operating system in terms of a specific system call in the kernel. For security reasons the applications cannot invoke directly the system calls, but they need to use an indirect mechanism implemented by a special instruction of the processor. This instruction generates a software interrupt to the processor that causes the execution of the interrupt manager in the kernel of the operating system. The interrupt manager recognizes the interrupt as the request (by an application) of execution of an operating system service, thus it finds the corresponding procedure (system call) in the kernel and executes it. The operating systems often offer an interface that enables the programmer to use the operating system services without the need for low-level invocation of the system calls through special processor instructions. This interface is normally available in several programming languages in form of a software library called API. The API is a library of procedures that offer to the applications all the services of the operating system. Generally to each operating system service (and then to each system call) corresponds one procedure of the API. In this case the procedure simply invokes the corresponding system call. However some API procedure can offer more complex services that are implemented by a composition of several system calls. Clearly the API is specific for an operating system and for a programming language, and each operating system may provide different API. Win32 and PThreads are examples of APIs of Windows and Linux, respectively.


API, system calls interface and kernel of the operating system 

The figure shows 4 layers. From the top to the bottom the layers are: applications, API, kernel (which includes the system calls interface), and hardware.

C2.1.4 How the resources are managed by software The operating system programs the devices using a mechanism called memory-mapped input/output. This mechanism consists in assigning a set of memory locations to each device. These memory locations correspond to the internal registers of the device, thus the processor can communicate with the device by appropriate read/write operations on these locations. Let us consider a simple example of a device that reads/writes magnetic badge, which is associated to two memory locations: x for the commands and y for the data. Two examples of device programming are the following: • The operating system writes the value 1 in location x to command the device a copy of the badge content in location y. Once the operation is concluded the operating system can read the badge content from location y. • The operating system writes a data D in location y and value 2 in location x to command the device to copy the data D on the badge. Let us consider an application which requests to the operating system the execution of one of these operations (let’s say the read operation) to the device. Clearly this application cannot proceed with its execution until the operation is completed. However, since the read operation may take a lot of time, the operating system may temporally block the application to execute other applications. When the device has completed the read operation it sends an interrupt to the processor. The processor then interrupts the execution of the current application to execute the interrupt manager. The interrupt manager identifies the device that raised the interrupt and runs the corresponding device driver . The device driver is a procedure in the kernel of the operating system that communicates with the device, and, in this case, completes the requested operation by giving the data read by the device to the application that requested it.


Memory mapped Input/output: the access of location x produces the access to register A of the device. The figure shows an example of memory-mapped input/output. On the right hand side it is shown a device containing only register A. In the centre of the figure it is shown the memory as a sequence of locations. Register A is mapped on the location x. When the operating system reads or writes location x it accesses the register A.


C2.2 Concurrent and Parallel ProcessesEdit

C2.1 Explain the reasons for concurrency inside an OS The concept of concurrency exists is several daily activities. For example it is possible at the same time to cook and to write a letter: if the water boils while writing the letter, it is possible to stop writing, put the pasta in the water and then start writing again. The two activities (cooking and writing) evolve concurrently, and the concurrency is obtained by sharing the time between the two activities. Similarly, the operating system let several activities (called processes) evolve concurrently. For example it can, at the same time, control the mouse movements and the e-mails. The operating system let all of the processes evolve in a uniform way, giving to the users the impression that the processes evolve simultaneously. The concurrent execution of different processes is managed by the operating system scheduler . The scheduler selects the next process that will be executed by the processor. If the scheduling policy is without pre-emption , the process in execution can keep the processor as long as it wants. If the scheduling policy is with pre-emption, when the scheduler let the processor execute each process for a period and then takes again the control of the system to select the next process to be executed. The scheduling policy depends on the kind of operating system. In batch systems the most used scheduling policy is the SJF , which gives priority to the shortest activities, and does not use pre-emption. This scheduling policy maximizes the system throughput (i.e. the number of processes completed per unit of time). Round-robin is a pre-emptive scheduling algorithm used in interactive systems. It executes the processes cyclically, assigning the processor to each process for a quantum of time. In this way several processes can use the processor at the same time and to each of them is given the same level of service.


Scheduling with pre-emption: the concurrent processes P1, P2, and P3 are executed cyclically. The figure shows the sequence of execution with pre-emption of the processes P1, P2, and P3. In the figure it is shown the sequence P1, P2, P3, P1, etc. Each process is executed for a quantum.


Round-robin scheduling: (a) list of processes ready for the execution while the processor is executing P1 and (b) list of processes ready for the execution after the execution of P1. Round-robin scheduling: the right hand side shows the list of processes ready for the execution during the execution of P1. The list contains P2, P3, and P4. On the left hand side it is shown the list of processes ready for the execution after the execution of P1. The list contains P3, P4, and P1, and process P2 is in execution.


Scheduling SJF: (a) list of processes to be executed and their respective execution times, and (b) list of processes as sorted by the SJF algorithm. SJF scheduling: on the right hand side it is shown list of processes to be executed and their respective execution times. The list contains the processes P1, P2, P3, and P4, and their execution times are 10, 7, 8, and 5, respectively. On the left hand side it is shown the list of processes as sorted according to the execution time by the SJF algorithm. The list is: P4, P2, P3, and P1. The next process that will be executed is P4.

C2.2 Describe the mutual exclusion problemEdit

Complex programs are often organized as a set of cooperating processes. Cooperating processes interact in order to exchange data (inter-process communication) and execute actions in the right sequence (synchronization). The cooperation can be achieved in two different models: shared memory and messages exchange. In the shared memory model two (or more) processes share the same memory area; hence the values written by one process are immediately visible to the other. In the message exchange model the processes communicate using system calls that allow the exchange of messages. In the shared memory model, if two processes access a shared resource without properly synchronizing, they may interfere with each other and the resource state may result inconsistent. The piece of code of a concurrent process that accesses a shared resource is called a critical section . To avoid interferences the critical sections that access the same resource should never be executed concurrently (mutual exclusion ). The main mechanism offered by the operating systems to implement the mutual exclusion is the semaphore. It consists of a state and two atomic operations : up and down. A process uses down to test the state of the semaphore: if it is unlocked then it locks the semaphore and accesses to the critical section; otherwise the process waits until the semaphore is unlocked by another process that executes the up operation. The incorrect use of critical sections and semaphores may lead to a pathologic situation called deadlock in which a set of the processes are all blocked because they are waiting for an event that only one of these processes can produce. There are several techniques dealing with deadlock, but they are all quite complex. An example of such techniques is the Banker’s algorithm that is able to check whether granting the access to a critical section is deadlock-free.



Mutual exclusion of critical sections. The figure shows the mutual exclusion on the same critical section. The concurrent process A enters the critical section at time T1. At time T2 the process B attempts to execute the critical section but it is blocked and waits. At time T3 the process A releases the critical section, thus B enters the critical section. The process B releases the critical section at time T4.


Access to a critical section using a semaphore. The figure shows the access to a critical section using a semaphore. On the top it is shown the process P1 that executes the down primitive. The state of the semaphore is unlocked; hence P1 accesses the critical section. In the middle it is shown P1 during the execution of the critical section. The semaphore is locked. Another process P2 executes the down primitive to access the critical section but it gets blocked. At the bottom is shown the process P1 that executes the up primitive to release the critical section and to unlock the semaphore. As a consequence P2 accesses the critical section.

C2.3 Describe the concept of a processEdit

A process is an activity executed on the processor and controlled by a program. To implement concurrency each process is assigned with a state, which can be ready, in execution, or blocked. A process is blocked if, to continue its execution, it needs a resource that is not available at the moment (for instance it waits a data to be read from the disk). When the resource becomes available the operating system awakes the process by switching it from blocked to ready state. The ready processes are those processes that can be executed at any time. The instant of time in which they are executed is decided by the scheduler. In a given instant of time (in uniprocessor systems) only one process can be in execution. From the execution state only two transitions are possible: • In the blocked state: when the process requests a resource that is not available; • In the ready state: this transition is decided by the operating system (for instance when the process has completed its quantum). To implement the process model, the operating system keeps a data structure in the kernel called process table , and each process in the system is associated to an entry (called process descriptor ) in this table. The process descriptor maintains all the information necessary to the operating system for the management of the process. In particular it contains the process state, a copy of all the values of the processor registers as they were the last time the process was in execution, information about the memory allocated and the files opened by the process, and other information. These data are updated when the execution of the process is interrupted (and hence the process state transitions from execution to blocked or ready), such that the process execution can later be started again as if the process had never been interrupted.

Process management Memory management File management Process identifier; Processor registers; Process state; Total execution time; Quantum. Memory area assigned to the process. For example; initial address and length. List of opened files with the respective descriptors.

Some data included in a process descriptor


Process state transition diagram. The graph in the diagram represents the state transition of the processes. The graph has three nodes (ready, execution, and blocked), and the oriented edges represent any possible state transition. In particular the graph has the following edges: from execution to ready, from execution to blocked, from ready to execution, and from blocked to ready.


C2.4 Describe the concept of a threadEdit

In the process model presented in the previous unit each process defines a space of resources and executes a unique sequential activity. However, in modern operating systems, the processes can organize their activities into concurrent sub-activities called threads . In this case the processes are called multi-threaded. In this model the process defines only a space of resources and threads. All the resources belonging to the process are shared by all the process threads, and the threads can use only resources belonging to the process. The simplest way to implement the threads is in user mode. In this case the threads are implemented by user-mode libraries, thus this implementation does not need any change to the kernel of the operating system. A more efficient implementation of the threads is in the kernel. In this case the operating system schedules only the threads but not the processes, and, in addition to the process table, it also keeps a thread table . Each thread in the system is associated with an entry (called thread descriptor ) in this table. Differently than the case in which the processes are single-threaded, in this case a process descriptor contains only information about the resources belonging to the process (such as memory allocated or files opened by the process), while the information about process execution is now spread in the thread descriptors. A thread descriptor maintains all the information necessary to the operating system for the management of a thread. In particular it contains the thread state and a copy of the values of the thread register, as they were the last time the thread was in execution. The thread descriptor is updated whenever the thread execution is interrupted (and hence the thread state transitions from execution to blocked or ready), so that the thread execution can later be started again as if the thread had never been interrupted.



Multithreaded process with three threads. The figure shows a multithreaded process that includes the program, the data, and three threads.

C.2.2.5 Describe a context switch operation The context switch is a mechanism used by the pre-emptive scheduling algorithms when they switch a process from the execution state to the blocked or to the ready state. In a typical scheduling algorithm pre-emption, for example the round robin, when the scheduler switches a process from ready to execution it performs two operations: • Initializes the system timer to raise an interrupt at the end of the quantum; • Invokes the context switch. The initialization of the timer is necessary to implement pre-emption, because at the end of the quantum the timer raises an interruption, and the interrupt manager thus invokes again the scheduler. The purpose of the context switch is to remove from the processor the process in execution (say process A) and to restore in the processor the state of another process (say process B). However, during its execution, process A has changed its context, that is, the values of the program counter , the processor state register, and all the general registers. Hence the removal of A from the processor should be performed carefully. In particular this operation involves making a copy of the process context in the process descriptor of A, in order to be able to restore later the context in the processor, when the scheduler will decide to execute again the process. After the removal of process A from the processor, the context switch restores the context of B in the processor. To this purpose it reads the context of B from its process descriptor, and it copies one by one all the register values in the appropriate processor registers. The last value to be copied is the program counter. Once this register has been restored process B is again in the same state it was when it was interrupted, and it can continue its execution as if it had never been interrupted.


C2.3 Memory and Storage Management C.2.3.1 Describe the concept of virtual memory and its purpose In the first operating systems it was mandatory to load the entire code and data of a process to execute it. This was a great limitation since the maximum size of a program was limited by the maximum amount of physical memory of the system on which it was executed. For this reason it was introduced the concept of virtual memory. Virtual memory is a memory management technique that extends the capacity of the main memory. With this technique each process has a virtual address space equal to the maximum space addressable by the processor, and independent of the size of the main memory. For instance, in a system with addresses of 32 bits the addressable space is of 4 GB . Paging is the most used technique of virtual memory. With paging both the physical and the virtual memory are split into partitions of fixed size called blocks (or frames) and pages, respectively. When a process should be executed, only the pages in use by the process are actually loaded in the physical memory (one page per block), while the other pages are kept on the disk. Note that contiguous pages do not need to be loaded in contiguous blocks. The memory manager swaps the pages from the disk to the memory and vice versa, based on the process references to the pages. However the processes are unaware of this fact, and they refer the virtual memory locations as if they were all loaded in the main memory. As compared to memory management techniques that do not define virtual memory, the paging technique has the following advantages: • A process does not need to be entirely loaded in the memory to be executed, but it is sufficient to load only the pages it is actually using. This means that loading a process is faster and that the pages never used are never loaded. • The maximum size of a process is not limited by the physical memory, but it is limited by the maximum amount of addressable memory.


Physical memory of m blocks, virtual memory of n>m pages, and pages kept on the disk. The figure shows a physical memory of m blocks (numbered from 0 to m-1), a virtual memory of n>m pages (numbered from 0 to n-1), and the pages kept on the disk. The pages have the same size of the blocks. Pages 0 and n-2 are loaded on blocks 1 and 2, respectively, while all the other pages are stored on the disk.

C.2.3.2 Describe how an OS manages a virtual memory through storage and memory hardware With paging the processor generates addresses referred to the virtual memory rather than to the physical memory (hence the addresses are called virtual addresses). Hence each virtual address must be translated into a physical address (that is, is an address to the main memory). To this purpose a virtual address is split into two fields: the address of the page and the offset within the page. This means that the virtual address belongs to a page, and to access the page it is necessary to find the block hosting the page. The correspondence between pages and blocks is kept in the page table . Each process has its own page table, which is kept in the main memory and which contains one entry for each page, called page descriptor . If a page is loaded in the main memory the page descriptor contains the address of the corresponding block. Hence the address translation of a virtual address x extracts the address of the page p from x, and it uses p to address the page descriptor in the page table. From the descriptor it extracts the block address, which, in turn, is combined with the offset to obtain the physical address. The paging implementation should solve two main problems: 1. The address translation should be fast; 2. The page table can be very large. To solve the first problem the addresses translation is executed by a hardware component called MMU . The MMU maintains a cache of the most recently used page descriptors, so that it can translate immediately the virtual addresses corresponding to the descriptors in its cache. To solve the second problem the operating systems use alternative implementations of the page table; one of these solutions is known as the inverse page table. The inverse page table is a unique table for all the processes. This table contains a descriptor for each block (thus it occupies a space proportional to the main memory), and each block descriptor contains a page address and a process identifier.



A page table and correspondence between pages and blocks. The figure shows a main memory of four blocks and the page table of a process with a virtual memory of 8 pages. In particular, pages 1,2,4,5, and 7 are not loaded in the main memory, pages 0, 3, and 6 are loaded in the blocks 1, 3, and 2, and block 0 is free. Hence the page descriptors 0, 1, 2, 3, 4, 5, 6, and 7 are 1, not loaded, not loaded, 3, not loaded, not loaded, 2, not loaded, respectively.


Address translation. The figure shows the translation of a virtual address of 14 bits. The first 8 bits (00101011) are the page address and the last 6 bits (001110) are the offset. With the page address it is extracted the block address from the page table. The block address is of 6 bits (001001) and it is combined with the offset to obtain the 12 bits physical address 001001001110.


C.2.3.3 Explain what “thrashing” is and how it is overcome A page fault occurs when a process generates a virtual address corresponding to a page that is not loaded in the main memory. When a page fault happens the operating system invokes a page fault management procedure that blocks the process that generated the virtual address, finds on the disk the requested page, and uploads the page in a free block in the main memory. Then the page fault manager updates the page descriptor with the block address, and awakes the blocked process so that the process can continue its execution as if the page was already in the main memory. If there are not free blocks in the main memory to upload the new page, the operating system uses a page replacement algorithm that selects a page that can be swapped from the memory to the disk in order to free a block. The selection of the page to be removed is quite critical. In fact, if the removed page will be referenced again in the near future, the operating system will soon have to manage another page fault to upload again the removed page. For this reason the page replacement algorithm selects a page that is out of the working set of the process, i.e. a page that is not in use by the process anymore. However there are cases in which the blocks are not sufficient to keep in the main memory the working sets of all the processes. When this situation occurs, the processes often reference pages that are not loaded in memory, and the system faces a large number of page faults. The management of the page faults is very expensive in terms of time due to the disk accesses for page loads and removals, thus the system becomes busy to manage continuous page faults and the processes do not make any meaningful progress in their work. This pathological situation is known as trashing . To tackle with trashing the system should reduce the number of processes in the system. This can be achieved by blocking a process and temporarily swapping it out to the disk to free some blocks.


C.2.3.4 Describe how the concept of memory hierarchy affects programming (e.g. in separating “working memory” from “files”) The processor uses the RAM memory (main memory) to store both the program and the data of the processes in execution. However in some cases the main memory may be too small to contain all the processes active in the system. For this reason it is possible to use larger (but slower) memories to temporarily store programs and data. This idea was first implemented by involving directly the programmer in the management of the memories. This technique is called overlay. With overlay a programmer can specify what sections of the code can be moved to the disk to free space for other code sections. More recently this technique was abandoned in favour of the virtual memory that extends the memory capacity but does not involve the programmer. The system memories (cache , RAM, hard disks, and optical disks) have different features in terms of cost, storage space and speed, and generally the faster memories are also the smaller and the most expensive. For this reason, with virtual memory, the operating system identifies the most frequently used pieces of code and data and moves them in the faster memories. The search of data and code in the slower memories and their copy to the faster memories is transparent to the users and to the applications. In this way the operating system gives to the user the impression of a system with a large, fast, and cheap memory. This organization of the system memories is called a memory hierarchy. It should be observed however, that the applications could always explicitly use the some of the system memories to extend their storage capacity (see C.2.3.5 “Describe the functions of a file system”). Hence some memories (in particular the disks) are splits in two partitions: one partition implements the storage used by the virtual memory (called backing store), and the other is directly accessible using the file system.


A memory hierarchy. The figure shows a memory hierarchy. From the top to the bottom the hierarchy comprises: cache, RAM, hard disks, and optical disks.

C.2.3.5 Describe the functions of a file system The file system is an operating system component that is responsible for the storage of data on permanent storage devices (hard disks, optical disks, USB pens, etc.). It abstracts all the low-level details of the disks and enables the user to efficiently manage and organize information on the disks. To this purpose the file system defines the concepts of files and directories . The files are defined as persistent information units associated to a file name. The directories are folder containing files and sub-directories, and their purpose is to enable the operating system and the users to efficiently organize the files in a hierarchical structure. A directory is a table that contains one entry for each file or sub-directory belonging to the directory. The structure of a directory entry depends on the file system. In general it contains a file name (or a directory name) and some information associated to the file such as its attributes or the information necessary to retrieve the file content in the disk. The directories are generally organized in a tree structure. The tree has a root directory (that in Unix is denoted with symbol “/”) and the other directories are sons of the root (if they are directly contained in the root) or root descendants. Thus, with the only exception of the root directory, every file or directory has a father, that is, the directory in which it is contained. The file system manages the correspondence between the abstract model of files and directories and their actual implementation on the disk by maintaining appropriate data structures on the disk. These structures contain the information needed to retrieve the files and the directories in the disk. Occasionally, due to faults or errors, these data structure may become inconsistent (for instance if the computer is turned off while the file system is performing some work). For this reason the operating system offers tools able to check the file system integrity and to fix it.



A directory hierarchy organized as a tree. The figure shows a directory hierarchy organized as a tree. The root directory has three son directories: Home, Office and Free Time. Directory Home has two files: Money and Family. The directory Free Time contains only the file Tennis. The directory Office contains the files one and three and the directory Old. Finally the directory Old contains the files Three and Four.


C.2.4 Security and Protection C.2.4.1 Recognise the need for protection and security (in terms of confidentiality, integrity and availability) in a computer system Nowadays the use of computers as a support to documents storage is becoming common practice. In some cases the information stored in a computer are critical since unveiling them may result in some sort of damage for the owner. For this reason they should be protected according to their level of privacy. Traditionally the security problem has been solved using physical protection mechanisms. For example documents on paper may be kept in a safe deposit box. Unfortunately with computers the problem is more complex since they are easily accessible even from remote and a physical protection is often not feasible. It is thus necessary to provide computers of adequate protection mechanisms. These mechanisms should give several access levels in order to selectively grant the appropriate privilege to each user, and they should be dynamic, that is, it should be possible to dynamically change the access privileges of a user. The protection mechanisms can be used to implement different security policies. In general, security has three objectives: Confidentiality , Integrity , and Availability . Data confidentiality is the possibility, granted to the legitimate owner of the data, to selectively grant or revoke the access to the data to selected users. Data Integrity means that unauthorized users or system failures cannot surreptitiously alter, damage, or delete data. Data availability means that the system guarantees to the legitimate data owner the access to the data, even in presence of faults or of malicious attacks by external entities. In other words a malicious user or a fault cannot prevent the access to the data. An attack attempting to prevent the access to a data to the legitimate user is called a denial of service.

C.2.4.2 Describe the types of protection mechanisms used in OS The main objective of protection is to provide mechanisms that prevent violations of the system security policies. Initially the protection was conceived as a set of mechanisms preventing a process to interfere with the kernel or with other processes in the main memory, and it was based on hardware supports enforcing the separation between user mode and supervisor mode and on the separation of the virtual memories of the processes. More recently the concept of protection has been extended due to the diffusion of different and more harmful threats. Consequently current protection schemes make extensive use of cryptography and of mechanisms for resources access control. The cryptography is a tool used to implement confidentiality. Its objective is to transform a message using an encryption key into an encrypted message that cannot be read by users that do not have an appropriate decryption key. More formally, given a message X and the encryption key Kc, the encrypted message Y is obtained by applying an encryption algorithm Ac, that is, Y=Ac(X,Kc). Message decryption is achieved by applying a decryption algorithm Ad to the encrypted message and the decryption key, that is, X=Ad(Y,Kd). The cryptography mechanism relies on the secrecy of the keys to ensure the secrecy of the encrypted messages, while the encryption and decryption algorithms are generally public. In a cryptographic system the encryption and decryption keys are bond in a mathematical relation. If making public a key may compromise the secrecy of the other key (a case is if the two keys are the same), thus it is necessary to keep both of them secret, and the cryptographic system is said to be symmetric. The DES is an example of a symmetric cryptographic system where the encryption and decryption keys are sequences of 54 bits. The messages are encrypted in bunches of 64 bits, thus longer messages must be split in bunches of 64 bit to be encrypted.


Encryption and decryption of a message. The figure shows a message X that is encrypted into message Y using the algorithm Ac and the encryption key Kc. The message Y is thus decrypted using the decryption algorithm Ad using the decryption key Kd.

C.2.4.3 Understand the difference between identification and authentication The first operation executed when a user connects to a computer is the user identification. To this purpose the user must give its username (or login) to the system. Then the system should authenticate the user identity. This consists in requesting to the user a proof of its identity. Most methods of authenticating a user are based on three general principles, namely identifying: 1. Something that the user knows 2. Something that the user has 3. Something that the user is The first type of authentication generally consists in requesting a password to the user. The typed password is compared with the stored password, and if they match the user is authenticated In the second case the authentication is achieved, for example, by means of a magnetic badge owned by the user that the user should insert in an appropriate badge reader. In the third case the authentication is achieved by measurements of physical features by the users (biometrics), such as its fingerprints. The authentication by means of password is the most widely used form of authentication due to its simplicity. Its main weakness is that, in some cases, it is difficult to keep a password secret. A good password (for example a random sequence of characters) is reasonably secure, however the users often prefer passwords that are easy to remember (such as names or meaningful dates). These passwords are easy to guess, and there exist data bases of common passwords and programs that use these data bases to illicitly connect to the systems through the internet. A password can get compromised by a visual or electronic monitoring: a colleague may see the password during its digitations on the keyboard, or it can be used a program that simulates the authentication procedure so that the same user gives its password unwittingly. In the most secure systems the passwords are usually combined with other authentication schemes. C.2.4.4 Describe authentication techniques and define a “strong” authentication scheme Symmetric cryptographic systems are computationally efficient. However they are unfit to efficiently provide authentication. Consider for example the purchase of product on the internet using the credit card: if the purchaser and the seller preliminary agree on the symmetric keys, the message containing the card code can be encrypted with symmetric cryptography, and this would guarantee both the authenticity and integrity of the message. However the key exchange between the two peers is critical: it is not possible to just send the keys since another entity may intercept the keys and subsequently intercept and decrypt the credit card code. Clearly this problem has to do with authentication of the two peers and with confidentiality, in fact each peer should make sure that it exchanges the keys with the other peer and that the keys are not sniffed by other entities. An efficient solution is to use other secure channels to exchange the keys; however more efficient mechanisms make use of public key encryption. In public key cryptographic systems (such as RSA ), computing a key using the other key is so complex that it is considered infeasible even with massively parallel computers. Then in these cryptographic systems one of the keys can be made public. If the encryption key Kc of a user A is public, whoever can send an encrypted message to A using Kc, however only A knows the decryption key (that is private), and thus only A can decrypt the message. If the decryption key Kd of a user A is public, it can be implemented a digital signature system that authenticates the identity of the message transmitter. A user A that sends a message with a digital signature computes the signature by encrypting the message with its private encryption key Kc. In this way, using the public decryption key of A, anybody can decrypt the signature and compare it with the message to verify the identity of the sender. Clearly another user B that does not know Kc cannot produce a legitimate signature of A.



Digital signature of a message with a public key cryptographic system. The figure shows a digital signature mechanism of a message X using public key cryptographic system. The sender computes the signature F of X using the private key Kc, and sends both F and X. The receiver authenticates the sender identity by using a verification algorithm that takes as parameters X, F and the public key Kd associated to the private key Kc of the sender. If the authentication check succeeds then the message is accepted by the receiver.

C.2.4.5 Describe the principles of access control The implementation of a protection scheme requires a structure called protection domain that states, for each process (or, in general, for each active entity that may also be a user), a set of protection rights . Each protection right is represented by a pair <resource, set of rights> and contains a resource to which the process has access and the set of allowed operations that the process can perform on the resource. In principle the protection domains can be implemented using the protection matrix . The rows of this matrix represent the protection domains and the columns represent the resources. If not empty, the element of index i,j contains the protection rights of resource j in the domain i. If a process operating in the domain i invokes an operation on resource j, the operating system controls in the matrix whether if the process is allowed to perform that operation. The protection matrix can also include the right for a process to change its protection domain. This can be implemented by considering the protection domains as resources on which it is possible to perform operations such as “switch to domain x”. In a real system the protection matrix is huge, and, in practice, it is never used. Alternative solutions are access control lists or lists of capabilities . An access control list is associated to a resource. It contains the list of processes (or, in general, of active entities) allowed to access the resource and, for each process, the list of operations that the process is allowed to perform. A list of capabilities is associated to a process (or, in general, to an active entity). The list contains the list of resources to which the process is allowed to access, and, for each resource, the list of operations that the process is allowed to perform. Note that the access control lists or list of capabilities are stored in the kernel, thus they are accessible only by the operating system in supervisor mode.



Three protection domains. The figure shows three protection domains. The first domain includes two protection rights: <File A,{read}> and <Semaphore B,{up,down}>. The second domain includes three protection rights: <File B,{read,write}>, <File C,{read,write}>, and <printer 1,{write}> . The third domain includes three protection rights: <File D, {read,write}>, <File E, {read}>, and <printer 1,{write}>. The protection right <printer 1,{write}> is in common between the second and the third protection domain.

Domain File A File B File C Printer D Dom. 1 Dom. 2 Dom. 3 1 Read Read Execution Write Switch to 2 Read Switch to 3 Read Write Write The table is a protection matrix with three protection domains, where the domains are also included as resources. The table has three rows (corresponding to the three domains) and 7 columns corresponding to: file A, file B, file C, Printer D, Domain 1, Domain 2 e Domain 3. In Domain 1 it is possible to: read file A, read and execute file C, write on Printer D, and switch to Domain 2. In Domain 2 it is possible to read file B and switch to Domain 1. In Domain 3 it is possible to read and write file A and to write on Printer A.


Access control lists of three resources (R1, R2, and R3). The figure shows a system with three processes, P1, P2, and P3, and three resources R1,R2, and R3. The access control lists are in the kernel. The list of R1 contains P1:RW (that is, process P1 can read and write R1), and P2:L. The list of R2 contains P1:E (that is, P1 can execute R1), and P3:E. The list of R3 contains P2:RW and P3:R.


Lists of capabilities of three processes P1, p2, and p3. The figure shows a system with three processes, P1, P2, and P3, and three resources R1,R2, and R3. The lists of capabilities are stored in the kernel. The list of P1 contains R1:RW (that is, process P1 can read and write R1), and R2:E (that is, P1 can execute R2). The list of P2 contains R1:E and R3:RW. The list of P3 contains R2:E and R3:R. C.2.4.6 Recognise the need for recovery and back-up Accidental data losses are very common, as they can be caused by hardware faults (for example a failure of a disk), software faults (for example an error in a program damages a document), human errors (such as the erroneous erasure of a file), or, in extreme cases, to larger scale disasters that physically disrupt the computer or its storage. The result of any of these events may result either in data inconsistencies or in their loss. The defence against accidental data losses consists in periodically making backups of the files in the disk on other storage supports such as tapes or DVD . Typically each backup of the data is labelled with the date and time of the backup, such that it can be recovered , that is, retrieved and restored, if needed. To make a backup means to copy all the files on the disk on another storage support, and it is generally a very time consuming operation. Furthermore, to be useful, the backup copies should be made frequently (for example daily), and all these copies should be kept in order to be retrieved later if necessary. Hence the backups may occupy a lot of space. For this reason the backup is often incremental, that is, only the files that are changed from the last backup are stored again, thus saving time and space. Incremental backup is achieved by exploiting some of the file attributes kept by the file system such as the time of last access and indicators of file changes. However, if incremental backup is used, recover a file may mean to analyse several past incremental backups to find the one that contains the file. In the worst case it may be required to look in the last complete backup. Hence, to reduce the recovery costs, a complete backup is scheduled periodically.

C.2.4.7 Understand the threats associated with malware (“backdoors”, Trojan horses, computer viruses...) and describe the main measures against it

Malware denote programs intentionally designed to threat the systems. Most common malware include backdoors, Trojan horses, viruses, and worms. A backdoor is a mechanism that enables the access to a system bypassing the usual authentication controls. Often a backdoor is a hidden user name not associated to a password, so that anybody can connect to the system using that user name. A backdoor can be created by any malicious program executed in the system. A Trojan horse is a piece of code encapsulated in a hosting program. Usually the hosting program is apparently innocuous and charming. If it is executed by the user the Trojan horse can do whatever is allowed to the user: delete or alter data or insert a backdoor. The Trojan horses are widely spread in the internet, hidden within downloadable software, or in the e-mails attachments, masqueraded as documents or images. A virus is a program that can damage or destroy users or system data, and that can reproduce itself by infecting with its code other programs in the system. The infection is transparent to the user thus, when the user executes the infected programs, he also unwittingly executes the virus. The virus infection spreads as users share programs using disks, USB pens, or e-mails. Some viruses infect documents rather than programs. These viruses (known as macro viruses) exploit the fact that some word processors can execute small programs (called macros) included in the documents. Other viruses infect the operating system. For instance there are viruses that infect the disk boot block. The worms are a variant of the viruses. Differently from the viruses the worms are able to find and attack in the internet other vulnerable computers. A system can be protected from malware by using an antivirus , a program that is constantly in execution in the system to look for malware, and that can remove the malware from any file in the file system and from each program that is executed. C.2.5 Widespread Operating Systems C.2.5.1 Describe the main features of an OS belonging to the Unix / Linux family

Linux is a multi-user, Unix-clone, and open-source operating system that were created in the 1991 by the Finnish student Linus Torvalds. Nowdays Linux is a widely used system with a large number of users. Linux comprises three main blocks, according to a monolithic structure: • Kernel: implements the management of the processor, memory, and devices, and the file system. • System libraries: define the standard functions that can be used by the applications to interact with the kernel. • System utilities: include programs such as the user interface (shell) that interprets the user commands, compilers, and other programs for the management of the system. Linux uses a process model similar to that of Unix. In particular the kernel offers two system calls: fork and exec. The fork allows the creation of a (child) process identical to the creator process (the father), with the only difference that the child is assigned a processor identifier (PID ) different than that of the father. Using the exec system call the child can subsequently change its code by executing another program stored in an executable file. Linux offers to the process a number of communication mechanisms, such as pipes, sockets, signals, etc. The Linux file system is crucial for the management of resources such as files and devices, and for the system security. In fact the file system implements as special files both directories and devices, and it defines protection attributes for each file (both normal and special). In particular each Linux user is associated with a user identifier UID and with a group identifier GID, and all the processes, files, and directories are marked with the UID and GID of their owner. The pairs UID and GID define the protection domain of all the processes belonging to a user. For each file or directory it is possible to define what operations are allowed to the owner, to the users in the same group of the owner, and to all the other users, respectively.

File name Owner rights Rights of the owner group Rights of other users File 2 RWE RW– R–– File 3 R–E R–– R–E File 4 –W– ––– ––– The table shows 3 files with the respective rights. In the table the symbol R means that the file can be read, symbol W in means that the file can be written, and symbol E means that the file can be executed.


C.2.5.2 Describe the main features of an OS belonging to the Microsoft Windows family Windows is a multi-user operating system, with the kernel organized in a set of layers. The lowest layer (called HAL ) is the only hardware-dependent part of the system, and it offers to the higher layers a standard interface to the hardware. The layer placed above HAL (called Kernel) contains the mechanisms used by different managers, and the upper layer is the Executive that includes the managers of the processor, memory, and devices, the file system, the manager for the security policies, and the graphical user interface. The part of Windows outside the kernel contains the Win32 API, which offers an (user-friendly) interface of the system calls to the applications. In Windows a process is associated with a unique numerical identifier, a virtual memory, and with protection attributes. Windows provides a unique system call for process creation (called createprocess) that makes the same work as the two Linux system calls fork and exec. Initially a process contains a unique thread, but it can create other threads using the system call createthread. The processes can be grouped into a job, that is, a set of processes that share some properties, for example the available disk quota. Windows offers advanced protection mechanisms that can be used to control the accesses to files, to directories, and to any other object in the kernel such as process or thread descriptors, tables for memory management, data structures used by the file system etc. Each object of the system (included files and directories) is associated with a data structure that contains its protection attributes. The protection attributes of an object are defined according to the access control lists model, thus they contain the set of processes allowed to access to the object, and the set of operations that each process is allowed to perform on the object. The Executive is the kernel component in charge of enforcing the system security, to this purpose it controls any operation performed by any process.



Layers of Windows The figure shows the Windows layers. From the bottom to the top the lower layers, which work in supervisor mode, are: the HAL, the Kernel, and the Executive (that includes the managers of the processor, memory, and devices, the file system, a manager for the Windows security policies, and the graphical user interface). The part of Windows that work in user mode is the Win32 API.


7. Links to additional materials: [SG05] A. Silberschatz, P. B. Galvin, Operating Systems, Seventh edition. Wiley, 2005. [Tan01] A. S. Tanenbaum. Modern Operating Systems: Second edition. Prentice Hall, New Jersey, USA, 2001. [AB04] P. Ancillotti, M. Boari, A. Ciampolini, G. Lipari, Sistemi Operativi, McGraw Hill, Italia, 2004.

8. Test questions Question 1. What is a quantum of time? (C2.1.2) • It is a measure of time in milliseconds. No! A quantum is not necessarily expressed in milliseconds. It is a partition of the time of the processor, and each partition (or quantum) can be assigned to a program for its execution. • It is a partition of the time of the processor. Right: it is a partition of the time of the processor, and each partition (or quantum) can be assigned to a program for its execution. • It is the time necessary to a program to complete its execution. No! In general it is not possible to determine a priori the time necessary to complete a program execution. Furthermore the execution of a program may take several quantum’s. The quantum is a partition of the time of the processor, and each partition (or quantum) can be assigned to a program for its execution. • It is the time necessary to assign the processor to a program. No! The time necessary to assign the processor to a program does not have any relation with the quantum’s. The quantum is a partition of the time of the processor, and each partition (or quantum) can be assigned to a program for its execution.

Question 2 What is the meaning of memory-mapped input/output? (C2.1.4.) • To assign memory locations to the internal registers of the devices. Right: memory mapped input/output consists in assigning a memory location to each internal register of the devices. The access to a device register is thus achieved by addressing the correspondent memory location. • To assign a memory location to each device. No! To assign a memory location to each device is not necessary since a device may have several registers. It is thus necessary to assign a memory location to each register. • To use the memory as a device. No! The use of the memory is different than the use of the devices. The memory mapped input/output consists in assigning a memory location to each internal register of the devices. • To assign a device register to each memory location. No! To assign a device register to each memory location does not make sense, as there would not be free memory for the execution of the programs. The memory-mapped input/output consists in assigning a memory location to each internal register of the devices.

Question 3 What is the advantage of executing concurrently different activities? (C2.2.1) • To make the activity execution faster. No! Concurrency does not augment the performance of a system, since its implementation implies the additional context switch overhead. Concurrency is useful to let several activities evolve uniformly, giving different users the impression of parallel execution of their activities. • To let several activities evolve uniformly. Right: concurrency is useful to let several activities evolve uniformly, giving different users the impression of parallel execution of their activities. • To augment the system parallelism. No! The parallelism can be augmented only adding more processors. Concurrency simulates the parallelism by letting different activities evolve uniformly. • To exploit the periods in which the processor is waiting for the completion of I/O operations on the devices. No! Concurrency is useful to let several activities evolve uniformly, giving different users the impression of parallel execution of their activities. As a side effect it can also exploit the periods in which the processor is waiting for the completion of I/O operations on the devices.

Question 4 In what circumstance does a process switches from the state execution to the state blocked? (C2.2.3) • At the end of the quantum. No! In this case the process switches to the ready state. It switches in the blocked state if it requests a resource that is not available because it is in use by another process. • When the resource it requested becomes available. No! In this case the process switches from the blocked to the ready state. It switches from the execution to the blocked state if it requests a resource that is not available because it is in use by another process. • It is an arbitrary decision of the operating system. No! The operating system takes decision about the scheduling depending on the behaviour of the processes. In particular a process switches from the execution to the blocked state if it requests a resource that is not available. • When it requests a resource that is in use by another process. Right: when a process requests a resource that is not currently available it cannot continue the execution. For this reason it switches to the blocked state. It will leave the blocked state when the resource will become available.

Question 5 What is the size of the virtual memory of a process? (C2.3.1.) • It is equal to the main memory. No! With virtual memory each process has a memory space unrelated to the physical memory of the system. In particular the virtual memory is equal to the entire address space of the processor. • It is 4 Gigabyte. No! It is 4 Gigabyte only if the address space is of 4 Gigabyte. In general the virtual memory is equal to the entire address space of the processor. • It depends on the number of processes in the main memory. No! Virtual memory is independent of the number of processes in the system, because each process has a virtual space equal to the entire address space of the processor. • It is equal to the address space of the processor. Right: it is equal to the entire address space of the processor, and each process has the same amount of virtual memory.

Question 6 What is the working set of a process? (C2.3.3) • The set of most frequently referenced pages. No! The working set is the set of pages that the process is currently using, thus it is the set of pages referenced in the last memory accesses. A page that is highly referenced but that is no longer used by the process does not belong to the working set. • The set of pages used by the process. No! This set includes all the pages used by the process, even those that are no longer used. The working set is the set of pages that the process is currently using, thus it is the set of pages referenced in the last memory accesses. • The pages referenced in the last memory accesses. Right: the working set is the set of pages that the process is currently using, thus it is the set of pages referenced in the last memory accesses. • The set of least recently referenced pages. No! The working set is the set of pages that the process is currently using, thus it is the set of pages referenced in the last memory accesses. Thus the least recently referenced pages do not belong to the working set.

Question 7 What is the main feature of a symmetric cryptographic system? (C.2.4.2) • The decryption key can be public but the encryption key must be private. No! This is a public key cryptographic system. The main feature is that both the encryption and decryption keys must be kept secret. • A unique key for encryption and decryption. No! The main feature is that both the encryption and decryption keys must be kept secret. Anyway in some cases the keys can be the same. • Both the encryption and decryption keys must be kept secret. Right: the main feature is that both the encryption and decryption keys must be kept secret, as making public one of the keys would expose also the other. • The encryption key can be public but the decryption key must be private. No! This is a public key cryptographic system. The main feature is that both the encryption and decryption keys must be kept secret.

Question 8 When does a public key system can be used to implement a digital signature? (C.2.4.4) • When the encryption key is public and the decryption key is private. No! It is the contrary: the encryption key is private and it is used to produce the signature, while the decryption key is public and it is used to authenticate the signature. • When the encryption key is private and the decryption key is public. Right: the encryption key is private and it is used to produce the signature, while the decryption key is public and it is used to authenticate the signature. • When the encryption and the decryption keys are both private. No! This is a symmetric system. A digital signature can be implemented when the encryption key is private and it is used to produce the signature, while the decryption key is public and it is used to authenticate the signature. • When the encryption and the decryption keys are both public. No! This is not a cryptographic system! A digital signature can be implemented when the encryption key is private and it is used to produce the signature, while the decryption key is public and it is used to authenticate the signature.

Question 9 What is the purpose of the fork system call? (C.2.5.1) • To create a new thread that executes a program stored in an executable file. No! The fork creates processes, not threads! The fork creates a new process identical to the father, which thus executes the same program as the father. • To create a new process that executes the same program as the father. Right: to create a new process identical to the father, thus the new process executes the same program as the father. • To create a new thread that executes the same program as the father. No! The fork creates processes, not threads! The fork creates a new process identical to the father, which thus executes the same program as the father. • To create a new process that executes a program stored in an executable file. No! The fork does not take as parameter any executable file. It creates a new process identical to the father, which thus executes the same program as the father.

Question 10 What is the protection model of Windows? (C.2.5.2) • The use of the supervisor mode. No! Windows uses the supervisor mode to execute the kernel code. However its protection model is based on access control lists. • Protection matrix. No! Windows uses a protection scheme based on access control lists. • Access control lists. Right: each object (resource) is associated to protection attributes stored in an access control list. • Capability lists. No! Windows uses a protection scheme based on access control lists.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.