Computer Systems Principle [3] - Operation System

Operating System

• A computer platform consists of a collection of hardware resources, such as the processor, main memory, I/O modules, timers, disk drives, and so on.
• Computer applications are developed to perform some task. Typically, they accept input from the outside world, perform some processing, and generate output.
• The OS is a layer of software between the applications and the computer hardware that supports applications and utilities.

Operating system is a low-level software which:

• handles the interface to peripheral hardware
• schedules tasks
• allocates storage
• presents a default interface to the user when no application program is running

Multitasking

sharing a single processor between several independent jobs.

• introduces overheads because the processor spends some time in choosing the next job to run and in saving and restoring tasks’ state.
  • Each switches = overheads
• improves the system efficiency as compared with uniprogramming.

Uniprogramming

Applications are executed one by one sequentially.

• Only one application can be in the main memory.
• All resources are provided to the application.
• Problem: Processor must wait for I/O instruction to complete before preceding.

Multiprogramming

Multiple applications can be executed in an interleaving manner with 1 CPU.

• More than 1 applications can be resident in the main memory at the same time.
• All resources are dynamically allocated to the applications.
• Advantage: When one job needs to wait for I/O, the processor can switch to the other job when necessary.

Process

The OS turns applications into processes and executes them in interleaving manner and/or in parallel to achieve the goals.

Any job that can be assigned to and executed on a processor must be in a form called process (a.k.a. task).

A process (a.k.a. task) is an entity that consists of 3 essential elements.

• program code
• a set of data associated with that code
• A Process control block (PCB) that contains all of the information about a process that is needed by the OS.

What is a PCB

To uniquely characterize a process:

• Identifier: A unique identifier associated with this process, to distinguish it from all other processes.
• State: If the process is currently executing, it is in the running state.
• Priority: Priority level relative to other processes.
• Program counter: The address of the next instruction in the program to be executed.
• Memory pointers: Includes pointers to the program code and data associated with this process, plus any memory blocks shared with other processes.
• Context data: The data present in registers in the processor while the process is executing.
• I/O status information: Includes outstanding I/O requests, I/O devices (e.g., disk drives) assigned to this process, a list of files in use by the process, and so on.
• Accounting information: May include the amount of processor time and clock time used, time limits, account numbers, and so on.

^those info are stored in a data structure, called a process control block (PCB).

PCB is created and managed by the OS.

PCB contains sufficient information so that it is possible to interrupt a running process and later resume execution as if the interruption had not occurred.

Process States

Trace

The sequence of instructions that execute for a process is referred to as a trace of the process.

Dispatcher

used to switch the processor from one process to another.

A 2-state Model

When the OS creates a process at the explicit request of another process, the action is referred to as process spawning.

When one process spawns another, the former is referred to as the parent process, and the spawned process is referred to as the child process.

A 5-state Model

State Explaination:

• New - A process that has just been created but has not yet been admitted to the pool of executable processes by the OS.
• Ready - A process that is prepared to execute when given the opportunity.
• Running - The process that is currently being executed. For a computer with a single processor, at most one process at a time can be in this state.
• Blocked/Waiting - A process that cannot execute until some event occurs, such as the completion of an I/O operation.
• Exit - A process that has been released from the pool of executable processes by the OS, either because it halted or because it aborted for some reason.

Events that lead to state transition:

• Null -> New
  • A new process is created to execute a program.
• New -> Ready
  • The OS will move a process from the New state to the Ready state when it is prepared to take on an additional process. A system should assure that there are not so many active processes as to degrade performance.
• Ready -> Running
  • When it is time to select a process to run, the OS chooses one of the processes in the Ready state. This is the job of the scheduler or dispatcher.
• Running -> Exit
  • The currently running process is terminated by the OS if the process indicates that it has completed, or if it aborts.
• Running -> Ready
  • The running process has reached the maximum allowable time for uninterrupted execution, or a process of lower priority level gives way to a process of higher priority level.
• Running -> Blocked
  • A process is put in the Blocked state if it requests something for which it must wait.
• Blocked -> Ready
  • A process in the Blocked state is moved to the Ready state when the event for which it has been waiting occurs.
• Ready -> Exit
  • A parent may terminate a child process at any time. Besides, if a parent terminates, all child processes associated with that parent may be terminated.
• Blocked -> Exit

Improving the efficiency with more queues

• It would be more efficient to have a number of queues, one for each event.
  • when the event occurs, the entire list of processes in the appropriate queue can be moved to the Ready state.
• If the dispatching of processes is dictated by a priority scheme, then it would be convenient to have a number of Ready queues, one for each priority level.

Suspended Processes

• When none of the processes in main memory is in the Ready state
  • the OS swaps one of the blocked processes out on to disk into a suspend queue.
• The OS can then
  • admit a newly created process or
  • bring in a previously suspended process.
  • The latter option is preferred as it does not increase the system load.

A 6-State Model

A 7-State Model

Process Description

The OS constructs and maintains tables of information about each entity that it is managing.

These tables must be linked or cross- referenced in some fashion.

• Memory Tables - keep track of allocation both main and secondary memory to processes
• I/O Tables - manage I/O devices and channels of the computer system
• File Tables - provide information about the existence of files
• Process Tables - to manage processes

Typical elements of a process image

• User Data - modifiale part of the user space
• User Program - The program to be executed
• Stack - used to store parameters and calling addresses for procedure and system calls
• Process Control Block (PCB) - Data needed by the OS to control the process

PCB

• Process identification - unique numeric identifier
  • Identifier of this process
  • Identifier of parent process
  • User identifier
• Processor state information - consists of the contents of processor register
  • When a process is interrupted, all of this register information must be saved
  • it can be restored when the process resumes execution.
• Process control information - to control and coordinate the various active processes.
  • Process state - (e.g. running, ready, etc.)
  • Priority - the scheduling priority of the process.
• Structuring Information - Data Structuring

Data Structuring

A process may be linked to other process in a queue or some other structure. The PCB may contain pointers to other processes to support these structures.

Process Control

Modes of processor execution

• User Mode - less-privileged mode
  • executes user programs
• Kernel Mode (aka system mode, control mode) - more-privileged mode
  • can execute certain instructions
  • can access certain regions of memory
  • executes the OS kernel

a bit in the program status word (PSW) indicates the mode of execution

Typical Functions of an OS Kernel

• Process Management - Process creation, scheduling and dispatching, switching
• Memory Management
• I/O Management
• Support Functions - Interrupt handling, Accounting, Monitoring

Process creation

1. Assign a unique process identifier to the new process.
2. Allocate space for the process. (includes all elements of the process image)
3. Initialize the PCB.
4. Set the appropriate linkages. (e.g. put it in a queue as a linked list)
5. Create or expand other data structures. (e.g. for billing purpose)

Process Switching

A process switch can only occur when there is a mode switch.

• OS gains control
  • System interrupt (Not initiated by the running process)
    • interrupt
      • Reaction to an asynchronous external event
    • trap
      • Handling of an error or an exception condition
  • Supervisor call (Initiated by the running process)
    • Explicit request
      • Call to an operating system function

Mode Switching

occurs when a computer system passes the control of the CPU between the OS and an application.

mode switch =/= process switch

Interrupt/trap/supervisor call results in a mode switch,

but it may not change the state of the current process.

Mode switch requires less overhead.

1. sets the program counter to the starting address of an interrupt handler program.
2. switches from user mode to kernel mode
   • so that the interrupt processing code may include privileged instructions.

Change of Process state

interrupt does not necessarily result in a process switch

1. Save the context of the processor, including program counter and other registers.
2. Update the PCB of the process that is currently in the Running state. (includes changing the state of the process to one of the other states).
3. Move the PCB of this process to the appropriate queue.
4. Select another process for execution.
5. Update the PCB of the process selected (includes changing the state of this process to Running).
6. Update memory management data structures if necessary.
7. Restore the context of the processor to that which existed at the time the selected process was last switched out of the Running state, by loading in the previous values of the program counter and other registers.

Thread

To construct a process, the OS reserves memory to hold a process image.

We can build a process image for a process, split the associated program of the process into independent program segments, execute them as if they were different processes.

The execution of each segment is considered as a thread.

Processes and Threads

Advantage using Thread than Process

• All these threads come from the same process
  • share the same process image/files/resources
• Scheduling can be thread-oriented instead of process-oriented
  • a higher level of parallelism can be achieved
• Involved overhead is less
  • Thread switching under the same process is faster than process switching
• Inter-thread communication mechanism is less complicated than inter-process communication

Multithreading

• 1 Core can only have 1 Process
• 1 Process can have many Threads

In a multithreaded environment:

Synchronize the activities of the various threads so that they do not interfere with each other or corrupt data structures.

For Each Process:

• 1 PCB in 1 process
• 1 User address space in 1 process

For Each Thread:

• separate thread control block (TCB)
  • containing register values, priority, and other thread-related state information.
• separate stacks

All threads of a process share the state and resources of that process

(But a thread state =/= process state!)

Thread functionality

Key states for a thread

• Running
• Ready
• Blocked

4 basic thread operations

• Spawn - When a new process is spawned, a thread for that process is also spawned.
  • the new thread is placed on the ready queue
  • provided with its own register context and stack space
• Finish - a thread completes
  • register context and stacks are deallocated
• Block - block when a thread needs to wait for an event
  • user registers, program counter, and stack pointers are saved
• Unblock - when the event for which a thread is blocked occurs
  • the thread is moved to the Ready queue

Note: blocking a thread does not result in blocking a process when a process has multiple threads.

User-Level and Kernel-Level Threads

• user-level threads (ULTs)
• kernel-level threads (KLTs)
  • Aka kernel-supported threads or lightweight processes

User-level threads

all of the work of thread management is done by the application.

the kernel is not aware of the existence of threads

Any application can be programmed to be multithreaded by using a threads library.

Threads library - a package of routines for ULT management

It contains:

• for creating and destroying threads
• for passing messages and data between threads
• for scheduling thread execution, and
• for saving and restoring thread contexts.

1. Processes are first scheduled by the kernel.
2. Threads of a process are then scheduled by the threads library. They share the CPU time dispatched to the process.
3. The state of a thread reflects its real physical state only when the process is in running state.
4. The state of a thread is frozen when the process is in ready/blocked state.

Key Note:

• Process are handled by kernel
• Threads are handled by threads library
• Threads are invisibble to the kernel
• when a process is not running, the state of thread is frozen

Kernel-level threads

all of the work of thread management is done by the kernel.

A thread is handled as if it were a process

Combined approaches

Some OSs provide a combined ULT/ KLT facility.

Multicore and Multithreading

Amdahl’s law

$$Speedup =\frac{\text { time to execute program on a single processor }}{\text { time to execute program on } N \text { parallel processors }}=\frac{1}{(1-f)+\frac{f}{N}}$$

Uniprocessor scheduling

Scheduling Policies

Non-preemptive

• A process in the Running state continues to execute until :
  • it terminates
  • or it blocks itself to wait for I/O or to request some OS service.

Preemptive

• The decision to preempt may be performed when :
  • a new process arrives
  • or an interrupt occurs that places a blocked process in the Ready state
  • or periodically, based on a clock interrupt.

Preemptive policies incur greater overhead than nonpreemptive ones

Scheduling Algorithms

User oriented & performance related scheduling criteria

Turnaround Time (TAT)

• The time interval between the submission of a process and its completion (= execution time + waiting time)
• Turnaround Time = finish - arrival
  • or = waiting time + service time

Normalized turnaround time (NTT)

• NTT = TurnaroundTime/Service Time
• Higher TurnaroundTime or NTT = Lower Performance / lower level of service

Response time

• Response ratio = (Waiting Time + Service Time)/Service Time

Scheduling policy

First Coming First Serve (FCFS)

• often combined with a priority scheme to provide an effective scheduler

Round robin

• A clock interrupt is generated at periodic intervals

Shortest Process Next (SPN)

• Possible starvation for longer processes

Shortest Remaining Time (SRT)

• Possible starvation for longer processes
• A preemptive version of SPN

Highest Response ratio Next (HRRN)

Response ratio $R=(w+s) / s \quad<1$

Where $w$ is time spent waiting for the processor, $s$ is expected service time

Feedback

• The policy penalizes jobs that have been running longer

The table gives a full view.

Concurrency

Basically:

• Communication among processes
• Sharing of and competing for resources
  • e.g. Memory, files, I/O access
• Synchronization of the activities of multiple processes
• Allocation of processor time to processes

Atomic operation

A function or action implemented as a sequence of one or more instructions that appears to be indivisible.

Atomicity guarantees isolation from concurrent processes.

Critical Section

A section of code within a process that requires access to shared resources and that must not be executed while another process is in a corresponding section of code.

• Writing/modifying shared data must be done in a critical section.

即係好似試衣服房咁，你用果陣其他人唔用得同一間房，但係可以用其他房

Mutual Exclusion

The basic requirement for support of concurrent processes is the ability to enforce mutual exclusion.

when one process is in a critical section that accesses shared resources

no other process may be in a critical section that accesses any of those shared resources.

Race Condition

Final result depends on who run faster.

• Synchronization among multiple processes is needed to avoid race conditions.

Semaphores

It is a non-negative integer vaiable used to support concurrency.

Also called counting semaphore or general semaphore.

3 Operations of Semaphore

• Initialize
  • int s;
• Decrement
  • s = s--; if $s\geq0$, go ahead, else blocked.
• Increment
  • s = s++: if $s\leq0$, let go 1 process.

Binary Semaphore

The Semaphore that only takes on the values 0 and 1.

Strong Semaphore

FCFS queue for semaphore lock -> Strong semaphore

Deadlock

Deadlock can be defined as the permanent blocking of a set of processes.

Characteristics of Deadlock

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

All the above 4 case must achieved to result in a deadlock.

Approaches to get rid of Deadlock

• Prevention
• Avoidance
  • Ensure that the system is always in a safe state
• Detection
  • periodically detects the circular wait condition exists or not

Recovery

Options

1. Abort all deadlocked processes.
2. Back up each deadlocked process to some previously defined checkpoint, and restart all processes.
3. Successively abort deadlocked processes until deadlock no longer exists.
4. Sucessively preempt resources until deadlock no longer exists.

Avoid Deadlock - Approaches

Terms Explain

• Allocation matix A - Denote the Resource you already allocated to each process
• Claim matrix C - Denote the Resource still need for each process
• Request Matrix Q = Matrix C-A
• Available vector V - The resource you have after serving all those process at once
  • equal to $R - \sum A_{row}$
• Resource vector R - Denote the Resource you have
  • equal to $V + \sum A_{row}$ or Points on $R_s$ from the graph

Process initiation denial

Do not start a process if its demands might lead to deadlock.

This strategy is hardly optimal as it assumes the worst situation.

• Added as much as Possible Processes that the total Matrix C are $\leq$ Resources vector R.

Resource allocation denial

Do not grant an incremental resource request to a process if this allocation might lead to deadlock.

Basically take care the process one by one.

• Find a process that Matrix C-A $\leq$ Available vector V.

• Complete that process and delete that row (release resource)

• Repeat ^ until all process are in ready state. (that means all the process can be completed)

• Safe state - all of the processes can be run to completion

• Unsafe state - not safe. MAY lead to deadlock.

Resource Allocation Graph

a tool for characterizing the allocation of resources to processes

Used to see if there is circular wait chain.

• Draw the Rs
• Draw the Ps
• Connect the Ps and Rs

A deadlock situation

Real-Time Scheduling

It is usually possible to associate a deadline with a particular task.

• A hard real-time task is one that must meet its deadline.
• A soft real-time task has an associated deadline that is desirable but not mandatory.
• An aperiodic task has a deadline by which it must finish or start, or it may have a constraint on both start and finish time.
• A periodic task has a deadline once per time period.

4 Real-Time Scheduling Approaches

• Static table-driven scheduling
  • Applicable to periodic tasks
  • Not flexible because any change to any task requirements requires that the schedule be redone.
  • offline prior to the start of execution (statically)
• Static priority-driven preemptive scheduling
  • assign priorities to tasks
  • priority-driven preemptive scheduler is used
  • offline prior to the start of execution (statically)
• Dynamic planning-based scheduling
  • feasibility analysis is carried out at run time (dynamically)
  • After a task arrives, but before its execution begins, an attempt is made to create a schedule that contains the previously scheduled tasks as well as the new arrival.
• Dynamic best effort scheduling
  • feasibility analysis is carried out at run time (dynamically)
  • tasks are aperiodic
  • system tries to meet all deadlines and aborts any started process whose deadline is missed
  • system assigns a priority when a task arrives
  • easy to implement and little overhead
  • Until the result comes out, we do not know whether a timing constraint will be met.

Earliest Deadline

A straightforward scheme is to always schedule the ready task with the earliest deadline and let that task run to completion. (Non-preemptive)

Earliest Deadline with unforced idle times

Earliest deadline with unforced idle times - Always schedule the eligible task with the earliest deadline and let that task run to completion. (Non-preemptive)

Keyterms

• Arrival Time / Ready Time
  • Time at which task becomes ready for execution.
• Starting Deadline
  • Time by which a task must begin.
• Execution Time / Processing Time
  • Time required to execute the task to completion.
• Ending Deadline / Completion Deadline
  • Time by which a task must be completed.
• Priority
  • The relative importance of the task.

Ideal (Perfect) Scheduling

$$\frac{C_{1}}{T_{1}}+\frac{C_{2}}{T_{2}}+\cdots+\frac{C_{n}}{T_{n}} \leq 1$$

Where $C$ is execution time, $T$ is the period. $n$ is the number of processes.

Rate Monotonic Scheduling (RMS)

Though it is possible to achieve greater overall processor utilization and accommodate more periodic tasks with earliest deadline scheduling (EDS), RMS has been widely adopted in industrial applications.

$$\frac{C_{1}}{T_{1}}+\frac{C_{2}}{T_{2}}+\cdots+\frac{C_{n}}{T_{n}} \leq n\left(2^{1 / n}-1\right)$$

Where $C$ is execution time, $T$ is the period. $n$ is the number of processes.

Stability is easier to achieve with RMS.

File Management

• Field - basic element of data
• Reacord - a collection of related fields
• File - a collection of similar records
• Database - a collection of related data

Five Fundamental file organizations

Pile

• Data are collected in the order in which they arrive. (Chronological order)
• Variable-length records
• variabble set of fields

Unsuitable for most applications

Only for temporary storage

Sequential File

• All records same length, consist fixed-length fields (a table)
• Key field uniquely identifies the record and determines the sequential order

Most common form of file structure

Optimum for batch apllications

Indexed Sequential File

• An index to the file is added to support random access.
• different levels of indexing can be implemented to provide greater efficiency

Indexed File

• Multiple indexes are used.

used why flexibility of efficiently searching by various attributes is desirable

Direct or Hashed File

• Records are randomly distributed in the file
• A Hash function is used to calculate the address of a record (key value pairs)

often used where very rapid access is required

B-Tree (Balanced Tree)

With all branches of equal length, would give the best average performance.

A B-Tree is characterized by its minimum degree d and satisfies the following properties:

• Every node has at most 2d-1 keys and 2d children (i.e. 2d pointers)
• Every node(except root) has at least d-1 keys and d pointers
• Root has at least 1 key and 2 children
• All leaves appear on the same level and contain no pointers
• A nonleaf node with k pointers contains k-1 keys

Search a key

Start at the root node. Search down the tree level by level.

• If desirable key < smallest key in the node
  • take the leftmost pointer
• If desirable key > largest key in the node
  • take the rightmost pointer
• if desirable key between the values of two adjacent keys in the node
  • take the pointer between these keys

Insert a key

Search the tree for the key. If the key is not in the tree, then reach a leaf node.

• If node has < 2d-1 keys then insert the key
• If node is full, then promote the median key to next higher level, split the nodes.

Average No. of access

$$d^{n+1} = N$$

where N = records, n = levels, d = entries per index table

To find Average No. of access for a table of d entries:

$$\sum_1^{d-1}fP(f) = \frac{d}{2}$$

Therefore

Average No. of access = Number of levels(index and record) $\times \frac{d}{2}$

$= (n+1)\times \frac{d}{2}$