Operating System Structures

*System Components

-Operating System Components
A process in operating system terminology is 'a program in execution'. Unlike a program which is resident on secondary storage, the process is an active entity. The process utilizes the resources of the system. A process is created whenever a program is executed.

Modern computer systems allow multiple processes to be loaded into memory at the same time and, through time-sharing (or multitasking), give an appearance that they are being executed at the same time even if there is just one processor.

The Process

Program in execution

Process state (see text diagram)

Process control block

Machine dependent: context

Machine independent: state, scheduling info, memory mgmt, accounting, open files, I/O

Scheduling

Short-term queues: ready, I/O, sleep

Degree of multi-programming: number of processes

Creation rate vs. exit rate

CPU vs. I/O bound processes

Swapping to maintain a balance

Operations

Creation

Parent/child relationship

Execution: waits for children or continues

Address space: duplicate of parent or new program

Termination

Voluntary: exit()

Involuntary: abort(), kill()

Cooperating vs. independent

Independent: no sharing

Dependent: Sharing, producer/consumer

Interprocess Communication

Message passing vs. shared memory

Blocking vs. non-blocking, send & receive

Direct: point-to-point, simplex or duplex, explicit naming of target

Indirect: send through mailbox, many-to-many, simplex or duplex, name associated with mailbox

Buffering: zero capacity, bounded capacity, unbounded capacity

Exceptional conditions

Process terminates

Lost messages: OS detects and resends, sending process detects and resends, OS detects & process is given option

Detection: timeouts

Scrambled messages: CRC & checksums

CPU Scheduling

Objective: have a process running at all times

CPU-I/O burst cycle (CPU burst times graph)

Next process chosen to run when CPU idles is chosen by short-term scheduler

Scheduling points

1. State change from running to waiting

2. State change from running to ready

3. State change from waiting to ready

4. Process termination

Preemption: process losing the CPU against its will, cases 2 & 3

Dispatcher: performs context switch, switch back to user stack and mode, restart program

Criteria for measuring the performance of a scheduling algorithm

CPU utilization

Throughput: number of processes completed per unit time

Turnaround time: how long it takes a process to complete

Waiting time: in ready queue only

Response time: variance?

Scheduling algorithms

FCFS: average waiting times

Shortest job first: minimum average waiting time

Predicting burst times

Exponential average:

: current burst

: moving average of

past bursts

: relative weights of past and present

SJF is special case of priority scheduling

Priority scheduling implies potential starvation

Round-robin: Time-sharing w/ preemption

Smaller quantum implies more context switching

Real-time scheduling

Response vs. dispatch latency

Priority inversion & inheritance

Algorithm evaluation

Deterministic modeling & analytic evaluation

Queueing models

Simulations

Implementation & empirical observation

Process Synchronization

Background (see text)

Critical section problems >$" align="middle" border="0" width="29" height="28"> solutions must satisfy:

Mutual exclusion

Progress

Bounded waiting

Two-process solutions: Algorithm 1-3 (slides)

-process solutions: Bakery Algorithm

Synchronization hardware: test-and-set (slides)

Semaphores

No busy-waiting

Semaphores have process qu

eues associated with them that waiting processes block in

(slides)

Deadlocks & starvation

Synchronization problems

Do not use the bounded buffer solution in text

Dining Philosophers

Monitors

Programmer-defined operations: internal data is only accessed through the operations

Access to operations is synchronized

Issues: programming language construct, easier to implement in a shared memory environment

Deadlock

Necessary conditions:

1. Mutual exclusion: ability of one process to hold a resource while other processes wait for the same resource

2. Hold and wait: ability of a process while holding one resource to block waiting for another

3. No resource preemption: inability of the system to revoke access to a resource

4. Circular wait: condition where a cycle of processes waiting for resources that are held by other proce

1. sses

Resource Allocation Graphs

Two node types: Resource nodes & Process nodes

Edge from process to resource: request

Edge from resource to process: allocation

Figure 7.1 from text

Prevention: Disallow one of the necessary conditions

1. Mutual exclusion: not possible

2. Hold and wait: grant all at once, request only when not holding (low utilization, starvation)

3. No resource preempti

1. on: allow resources allocated to a process that is waiting to be taken away

2. Circular wait: processes all request resources in the same order

Problems w/ prevention: low utilization, reduced throughput

Avoidance

Safe state: $" align="middle" border="0" width="126" height="29"> sequence of processes is safe if any can obtain resources immediately or from any

Example: text, page 218

Resource graph allocation algorithm:

Single resources only

Additional edge: claim edge, intent to request resource

Requests are granted only if converting edge does not form a cycle

Single resources only

Banker's algorithm

Multiple resource instances

Processes d

eclare the maximum number of instances of each resource

Data structures:

Available: vector of length indicating the number of available resources of each type

Max: matrix defines max demand for each resource type by each process

Allocation: matrix tracks the number of resources of each

type allocated to each process

Need: matrix tracks the remaining resources of each type for each process

-Main Memory Management
Memory management is the act of managing computer memory. In its simpler forms, this

involves providing ways to allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. The management of main memory is critical to the computer system.

Virtual memory systems separate the memory addresses used by a process from actual physical addresses, allowing separation of processes and increasing the effectively available amount of RAM using disk swapping. The quality of the virtual memory manager can have a big impact on overall system performance.

Garbage collection is the automated allocation, and deallocation of computer memory resources for a program. This is generally implemented at the programming language level and is in opposition to manual memory management, the explicit allocation and deallocation of computer memory resources.

-Memory management is a tricky com

promise between performance (access time) and quantity (available space). We always seek the maximum available memory space but we are rarely prepared to compromise on performance.
Memory management must also perform the following functions:

• allow memory sharing (for a multi-threaded system);
• allocate blocks of memory space for different tasks;
• protect the memory spaces used (e.g. prevent a user from changing a task performed by another user);
• optimise the quantity of available memory, specifically via memory expansion systems.

-File Management

Also referred to as simply a file system or filesystem. The system that an operating system or program uses to organize and keep track of files. For example, a hierarchical file system is one that uses directories to organize files into a tree structure.

Although the operating system provides its own file management system, you can buy separate file management systems. These systems interact smoothly with the operating system but provide more features, such as improved backup procedures and stricter file protection.

-I/O System Management

A programmable computer user input/output (I/O) system having a multiple degree-of-freedom magnetic levitation (maglev) device with a matched electrodynamically levitated flotor and stator combination and an electrodynamic forcer means for receiving coil currents for applying controlled magnetic...

-Protection System

Protection System is rather annoyware, i.e commercial software that applies extremely annoying ads to convince users of the need to buy it (buying Protection System means registering this program for at least one year period). We have to stress on that registering Protection System is no escape from its alerts as the hackers’ design is to get endless cashflow from user who once agreed to pay. That is, registered Protection System will ask for updates and extended registration. There is thus ho way to get rid of Protection System’s noisy ads but to remove Protection System entirely.

-Command Interpreter System

The command interpreter (CI) is the program that acts as the interface between you and the operating system. It checks the MPE/iX commands that you enter for spelling and syntax errors. The CI then passes the command along to the appropriate system procedure for execution. Following execution, control returns to the CI, which becomes ready for another command.