CS340
Lecturer: Dr. Simina Fluture
Week #1 – SUMMER SHORT
Topics: Course Introduction
Operating Systems
Generations of Operating Systems
Operating System: A collection of programs that act as intermediaries between the user and the computer hardware. It can also be thought of as a resource manager.
Operating Systems Generations
Prior to the 1st Generation: early computing systems had NO operating system.
1st Generation (50s):
Batch processing systems: Jobs with similar needs were batched together and were run as a group.
The operating system’s major task was to automatically transfer control from one job to the following one. A batch system is characterized by the lack of interaction between the user and the job during execution.
Sequential execution; FCFS scheduling algorithm.
Batch files
2nd Generation (early 60s): Multiprogramming, Multiprocessing systems
Multiprogramming: one CPU, multiple processes ready for execution.
In a multiprogramming environment there is competition among processes for resources (memory, the CPU, etc.). Associated with different resources we have queues; What process will use the resource next will be decided by the operating system (schedulers).
Most use scheduling algorithms: priority scheduling algorithms and round robin scheduling algorithms.
Advantage: much better utilization of resources
Disadvantage: synchronization issues
Multiprocessing: several processors are used on a single computer system to increase the processing power of the system. Processes share the computer bus, the clock and sometimes memory and peripheral devices.
CS340
Lecturer: Dr. Simina Fluture
Uniprocessing Environment:
Main Memory
CPU
BUS
Multiprocessing Environment: more than one CPU, many processes ready for execution. CPUs are sharing the bus and the memory and system clock.
Main Memory
CPU 1
CPU 2
CPU 3
Cache 1
Cache 2
Cache 3
BUS
The Symmetric multiprocessing model (SMP): C P U s a r e p e e r s The Asymmetric multiprocessing model: master – slave relation
3rd Generation (mid 60s to mid 70s)
by the early 60s, most computer manufacturers had two distinct, totally incompatible, product lines: – the word-oriented, large-scale scientific computers
– the character-oriented, commercial computers
IBM attempted to solve this problem by introducing the System/360. The System/360 was designed to handle both scientific and commercial computing by providing the largest assortment of machine simulators and emulators ever assembled.
Timesharing systems (interactive) are multiprogramming systems that support multiple terminals, one for each active user of the system.
Today most systems provide both, batch and timesharing processing. These are known as multimode systems.
A major feature introduced in this generation is spooling. (Simultaneous Peripheral Operation On- Line)
CS340
Lecturer: Dr. Simina Fluture
4th Generation (mid 70’s to Present)
As hardware costs decreased, it became feasible to have a computer system dedicated to a single user. Personal computers appeared in the 70s. In the beginning the CPUs in PCs lacked the features needed to protect an operating system from user programs. The goals of these operating systemshavechangedwith time.Nowthesystemstrytomaximizeuserconvenienceand responsiveness.
The mid 80’s saw the growth of networks with PC’s running network operating systems and distributed operating systems.
Real-Time Systems are used when there are rigid time requirements. A real-time operating system has fixed time constraints. Processing must be done within the given amount of time.
There are 2 flavors of real-time systems:
Hard real-time system: guarantees that critical task is done in time
Applications: Army, robotics, medical field
Strict times constraints over all processes; processes must start and end at specific times;
Soft real-time system: a critical real-time task gets priority over other tasks Applications: Multimedia
Many concepts are implemented in the same way in the previously mentioned environments. It is easy most of the time to switch from one environment to the other.
Real time systems are very different (in their implementation) compared to any of the previous environments.
Less use of virtual memory
Minimal interrupts
Uses heavyweight processes instead of threads
Centralized system vs Distributed system
CS340
Lecturer: Dr. Simina Fluture
Starting a Computer
Interrupts
Dual-mode operations
I/O Structure (only what it is covered in class)
Starting a Computer:In order to start running (whether it is started up or rebooted), a computer needs to have an initial program to run; called a bootstrap program. When the CPU is started, it branches to a fixed memory location. This hardwired address points to the ROM, which contains a small program called the bootstrap loader (program). This program initializes all aspects of the system, which include locating the operating-system kernel and loading it into memory. The OS then starts executing the first process, and waits for some event to occur.
More Detailed (in class) : ROM, POST, MBR
Main Memory
P100
CPU
BUS
Kernel
P50 P300 P100
Ready Queue
A process that is in the Ready queue: all that the process needs in order to execute is the control over the CPU.
Interrupts:
The occurrence of an event is signaled by an interrupt from the hardware (sending a signal to the CPU) or the software (by executing a special operation called the system call).
An interrupt can be synchronous if it is the DIRECT result of the current instruction being executed by the CPU. Otherwise it is known as asynchronous.
Dual-Mode Operation (processor modes):
A mode bit, is added to the hardware of the computer to indicate the current mode. User-mode (1) the operation is done on behalf of the user.
System (monitor) -mode (0) the operation is done on behalf of the OS.
Privileged – instructions are instructions that can be executed only in the monitor mode.
CS340
Lecturer: Dr. Simina Fluture
CS340
Lecturer: Dr. Simina Fluture
Operating System Components Command Interpreter Singletasking system (MS-OS), TSR
Multitasking system (UNIX)
Operating System Components
The Operating system is partitioned into system components with very specific tasks. Process Management
Main-Memory Management File Management
I/O System Management Secondary-Storage Management Networking Protection System Command-Interpreter
Command-Interpreter System/Program
The command interpreter is the interface between the user and the operating
system. can be either:
– included in the kernel
– a special program that runs when a job is initiated.
Commands can come: – from files
– directly from a terminal
Command implementation:
1. The command interpreter contains the code to execute the command. 2. Commands are implemented by special programs.
CI – Single tasking system (MS-DOS)
Kernel
Non-Resident
Resident
Kernel
P100
Non-Resident
Resident
Kernel
MS – DOS at boot time
– the command interpreter is invoked when the computer is started.
– MS-DOS loads the program to be run into main memory, overwriting part of the command
interpreter.
– PC is set to the first instruction of the loaded program.
– the program runs and either an error causes a trap or the program executes a system call to
terminate.
– the command interpreter resumes execution.
– the residual piece of the command interpreter reloads the rest of the command interpreter from the
disk.
CS340
Lecturer: Dr. Simina Fluture
MSDOS can provide a method for limited concurrent execution. Terminate and Stay Resident call
CI – Multitasking system – (Berkeley) UNIX
The Command Interpreter in Unix is a process that runs in user mode.
In UNIX each line of the shell is parsed to obtain strings that contain the name of the command and the parameters.
The shell of the user’s choice (command interpreter) is run when a user logs onto the system.
The shell either waits for the process to finish, or runs the process in the ‘background’.
The user is free to ask the shell to run other programs.
P200
CI SHELL
P100
Kernel
CS340
Lecturer: Dr. Simina Fluture
OPERATING SYSTEM – ARCHITECTURE (DESIGN) – ASYNCHRONOUS
Simple Structure
Monolithic Structure:
simplest structure: place all the functionality of the kernel into a single file that uses a single address space. There is no modular design. Examples of basic monolithic structure: original Unix, Linux.
However, in time the monolithic structure became highly modular allowing the kernel to be modified easily.
The system structure is limited by the hardware. In the beginning MS-DOS and UNIX had a simple structure.
The interfaces and levels of functionality were not well separated.
MS-DOS
|———————————————————–| | application program | |———————————————————-||
|| | || || || |||| |———————–| || || | MS-DOS device drivers | || || |———————–| || || || ||||
|————————————-|
| ROM BIOS device drivers | |————————————-|
Fig. MS-DOS simple structure
|—————————–|
| resident system program |—————————–|
MS-DOS – application programs are able to access the basic I/O routines. This makes MS-DOS vulnerable to errant programs.
Unix
The original UNIX was limited to two separable parts: the kernel and the system programs. The main idea was that the kernel represented a whole indivisible part with a huge responsibility.
CS340
Lecturer: Dr. Simina Fluture
Fig. Unix Simple Structure
Modern Structure
Layered Structure:
If we have the hardware support, the OS can be broken into smaller pieces, creating a modular operating system.
The OS is broken into a number of layers (levels), each built on top of lower layers.
The lowest (0 layer) is the hardware. The highest (Nth layer) is the user interface.
Each layer uses functions and services of lower-level layers only.
-)
+)
The new-layered structure replaces the traditional vertical architecture with a horizontal one introduce with Windows NT.
New terms:
Microkernel
Mach: 80; moving away from a monolithic structure where the kernel has a huge responsibility to a very small kernel.
Microkernel represents the most used and fundamental component of the OS. The microkernel functions as a message exchange: validates messages, passes them between components, grants access to the hardware, and performs a protection function.
-)
+)
When it comes to Windows the microkernel concept is introduced by Windows NT. Windows NT (new technology) revolutionized the Windows architecture.
(the users)
shells and commands compilers and interpreters system libraries
system-call interface to the kernel
signals terminal handling character I/O system terminal drivers
file system swapping block I/O system disk and tape drivers
CPU scheduling page replacement demand paging virtual memory
kernel interface to the hardware
Terminal controllers terminal
device controllers disks and tapes
memory controllers physical memory
CS340
Lecturer: Dr. Simina Fluture
CS340
Lecturer: Dr. Simina Fluture
Windows 10
Kernel – hybrid architecture that provides subsystems to simulate different OS environments, like Linux (WSL )
responsibilities: thread scheduling, low-level processor synchronization, interrupt and exception handling, switching between user and system modes. Mostly written in C.
Executive: provides services used by all the environment subsystems (like: object manager, virtual memory manager, process manager, plug and play and startup manager)
It is highly object oriented.
Environmental subsystems
User-mode processes that enable Windows to run programs developed for other operating systems: Win32, POSIX (earlier edition of Windows) , OS/2.
The most important subsystem is Win32. Win32API represents the native environment for Windows NT, Windows 2000, Windows XP and even Windows 10.
HAL (Hardware Abstraction Layer):
User level application are written in C/C++ and don’t depend on the architecture.
HAL isolates the OS from platform specific hardware differences. Provides the support for Symmetric Multiprocessing (SMP). Most of the upper level modules can access the hardware only through the HAL.
In early days 450 HAL interfaces have been developed. Today AMD64 port for Windows 10 comes with only one HAL. The reason is that in our days different architectures tend to merge into one common architecture.
APPLE
MacOS: desktop and laptop computers – Intel architecture
iOS: mobile OS for iPad and iPhone ARM based architecture
Darwin: example of microkernel for macOS. Hybrid, layered structure. It contains two main components: Mach microkernel component and BSD Unix Kernel.
CS340
Lecturer: Dr. Simina Fluture
UNIX – loadable kernel modules.
System V Release 4 (SVR4)
Features:
Real-time processing support
Process scheduling classes Virtual memory management Virtual file system Preemptive kernel
Unix runs on machines ranging from 32-bit microprocessors up to supercomputers.
A small core of facilities provides functions and services needed by a number of system processes. Each of the outer circles represents functions that can be implemented in many different ways.
Android: designed for Android smartphone and tablet computers. linux kernel;
CS340
Lecturer: Dr. Simina Fluture
Topics: Process Control Block (asynchronous) Process States
Process transitions and State Diagram
Process is a program in execution. A program by itself is not a process. A program can be seen as a passive entity, such the content of a file, a process can be seen as an active entity.
Process Control Block
The PCB of a process provides to the OS all key information about the process. The PCB defines a process to the operating system. The access to the PCB of a process is done using a unique process ID.
Topics: Mode Switch / Full context Switch Process States
Process transitions and State Diagram
Main processor actions (mode switch):
It saves the context of the processor.
It sets the PC to the starting address of an OS program, the interrupt handler routine. The Interrupt Handler checks the cause of the interrupt and it might service the interrupt. One of the main tasks of the Interrupt Handler Routine is to protect the PCB of the process. Usually it is the only process that can modify information inside the PCB. (In more complicated situation, the Interrupt Handler will call a specific Interrupt Service Routine that will service the Interrupt).
Meanwhile the processor switched from the user mode to the system mode.
If the interrupt results in a full Process Switch (full context switch) save the context of the processor.
update the PCB of the process that is currently in the Running state. move the PCB of this process to the appropriate queue.
select another process for execution.
update the PCB of the new process.
update memory management data structures.
restore the context of the processor to that which existed at the time the selected process was last switched out of the Running state.
Process Switch times are pure overhead and are highly dependent on hardware support.
CS340
Lecturer: Dr. Simina Fluture
Process States
New – a process that has just been created but has not yet been admitted to the pool of executable processes.
Ready swapped – the process is in secondary memory, but is available for execution as soon as it is loaded into main memory.
Ready (active) – the process is in main memory and available for execution.
Running – the process is currently being executed.
Blocked – the process is in main memory and awaiting an event. The process doesn’t have all the resources it needs.
Blocked swapped – the process is in secondary memory and it may wait for an event.
Terminated – the process has finished execution.
State Transitions & State Diagram
CS340
Lecturer: Dr. Simina Fluture
Process Operations
Activate: restart the process from the point at which it was suspended. The process is moved from the suspended (swapped-out) in secondary memory to the corresponding active state.
Swapped (suspended in secondary memory): it is often an operation performed by the OS to control the number of processes residing in the main memory, the degree of multiprogramming. Mostofthetimethesuspensionlastsonlybriefperiodsoftime.
A process remains suspended until ANOTHER process activates it. Swapping is a high-priority operation.
Release: is required to move the process from the blocked state to the corresponding ready state.
Process Creation
A process can create new processes called the children of that process.
In terms of execution:
the parent continues to execute concurrently with its children.
the parent waits until some or all of its children have terminated.
In terms of resource utilization:
the child may be able to obtain the resources directly from the OS.
the child may be constrained to a subset of the resources of the parent process. (good for deadlock handling)
In terms of the address space:
the child is a duplicate of the parent. (same address space & variables with same values)
the child is a separate program (different address space)
UNIX
There are three important system calls used in the creation of a process:
fork( ), exec( ), wait( )
Process 1 is created as a part of the system boot-up. Every other process is created by P1 as a result ofa forksystemcall.Theinitprocessmanagesalluserloginactivityandcreatetheinitialuser processfor eachuser.
Fork Returned Value: -1 cannot create a process
0 returned value to the child
1 – nnn The PID of the child returned to the parent process
Windows (NT/2000/XP)
in Win32API there is a CreateProcess function which in turn calls the Windows kernel functions CreateProcess and CreateThread. There can be many different options for creating the
process, so the CreateProcess function has many parameters, and some of these parameters can be quite complex. In contrast with the UNIX fork( ) call, where there are no parameters – in windows the child’s behavior is completely defined by the parent’s profile and default behavior.
MS-DOS
a system call exists to load a specified binary file into memory and execute it as a child process. The call suspends the parent until the child has finished execution.
CS340
Lecturer: Dr. Simina Fluture
Process Termination
When a process finishes executing, it asks the OS to delete it by using the exit system call. The process may return data to its parent via the wait (provides the process id) system call.
All the resources of the process are deallocated.
A process can cause the termination of another process using the abort system call. Usually only the parent of the process that is to be terminated can invoke such system call.
On PC a user may quit its application. – Everything results in a system call to the OS to terminate the requesting process.
A parent may terminate the execution of one of its children because:
the child exceeded the usage of some resources.
the task assigned to the child is no longer required.
the parent is exiting and the OS does not allow a child to continue if its parent terminates.
UNIX
A process may terminate by using the exit system call, and its parent process may wait for that event. If the parent terminates, all its children have assigned as their new parent the init process. echo $? Displays the exit code of the last process.
Zombie State:
Zombie process:
Kill – command; “sure” kill
VMS
cascading termination.
CS340
Lecturer: Dr. Simina Fluture
Process Synchronization (Introduction) Principles of Concurrency (asynchronous)
Topics:
Degrees of interaction between processes (threads) & Potential ControlProblems CriticalSection&theCriticalSectionProblem Constraints on acceptable solutions to CS problem
The general structure of a typical process P
Between processes there might be interactions. These interactions can be classified on the basis of the degree to which processes are aware of each other’s existence.
Processes unaware of each other: independent processes that are not intended to work together. The O.S. needs to be concerned about the competition for resources.
The best example is the multiprogramming of multiple independent
processes. Potential Control Problems: Deadlock, Starvation, Delay
Processes indirectly aware of each other: processes those are not necessarily aware of each other by name but share access to some object, such as an I/O buffer. Such processes need cooperation
in sharing the common object.
Multiple processes may have access to shared variables, files or databases.
Potential Control Problems: Mutual Exclusion, Deadlock, Starvation, Data Coherence. (Producer/Consumer, Reader/Writer problem)
Processes directly aware of each other: processes able to communicate with each other by name. The communicationprovidesawaytosynchronizeorcoordinatethevariousactivities.
Potential Control Problems: Deadlock, Starvation.
Critical Section & the Critical Section Problem Let’s
consider the following situation.
The registration period is over, but for the next 2 weeks students can drop or add courses. Students can drop/add classes by calling one of the two operators. One of the operators is responsible for the ‘add’ cases, the other one for the ‘drop’ cases.
A: the number of students currently registered. A is a shared variable.
P0
add ( ) {
while (true) { ………
A++; ………
}} }}
P1
drop ( ) {
while (true) { ………
A–; …….
Suppose that we don’t know the order of students’ requests, but if we consider the case by which one student called to drop a course and another called to add the course, after both students finished their transactions, the number of registered students remains unchanged.
The corresponding lower level instructions are: (given in class)
CS340
Lecturer: Dr. Simina Fluture
Let’s consider the following sequences of instructions (up – down):
P0-0 P0-1 P1-0 P1-1 P1-2 P0-2
Initially: A
R120 R1 21 R2 20
= 20
P0-0 P1-0 P1-0 P1-1 P0-1 P1-2 P1-1 P0-0 P0-2 P0-1 P1-2 P0-2
What will be the value of A, after the execution of each sequence of instructions?
The final result depends on the order in which the processes (threads) access the shared value. A++ and A— represent the Critical Sections (CS).
Critical Section: is a segment of code in which the process may be access common variables, shared data, etc.
In order to solve the previous problem, we must require only one process to be allowed in its CS at a given time (Mutual Exclusion condition).
Data coherence represents a problem not only for the lower-level instructions.
We can have the following situation. Suppose two items of data A and B are to be maintained in the relation A=B. Any process that updates one value, must also update the other one.
Even if we keep mutual exclusion on the execution of each individual instruction, we might still have a data coherence problem.
Race Condition: When several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.
Critical Section Problem: design a protocol that processes can use to cooperate and properly use the data of the critical section.
Constraints on acceptable solutions to CS problem
Mutual Exclusion with respect to CS. At a given time, only one process can be in the CS. Progress Condition: if no process is in the CS and there are processes trying to enter their CS, then only processes competing for the CS should participate in the decision of which will enter the CS next and the decision must be made in finite time.
No Starvation: no process should be postponed for an indefinite period of time.
Assumptions:
Write and Read memory cell are atomic operations (indivisible). Processes do not have priorities.
The relative process speeds are unknown.
Processes are assumed to be sequential and
cyclic.
The general structure of a typical process Pi: while(true) {
entry section
CS
exit section
remainder section }