Lecture
1. Types of scheduling
|
Type of scheduling |
Functions performed |
|
Long-term |
The decision to add a job (process) to the pool of those being executed in the system |
|
Medium-term |
The decision to add a process to the set of processes fully or partially residing in main memory |
|
Short-term |
The decision as to which of the available processes (threads) will be executed by the processor |
|
I/O scheduling |
The decision as to which of the processes' (threads') I/O requests will be handled by a free I/O device |
Scheduling diagram taking into account job (process) queues
A typical thread state graph
2. Preemptive
The simplest scheduling algorithm, implementing the thread states as in slide 27
A scheduling algorithm that gives preference to threads with intensive I/O
Priority switching with time slicing
Changing the base priority of a thread
Priority increase
priority 15 for 2 processor quanta, if a thread that is ready to run has been idle for longer than a certain threshold time.
Priority decrease
|
Degree of awareness |
Relationship |
Influence of one process on another |
Potential problems |
|
Processes are unaware of each other |
Competition |
Ø The result of one process does not depend on the actions of the others.
Ø One process may affect the running time of another.
|
ØMutual exclusion
ØDeadlocks
ØStarvation
|
|
Processes are indirectly aware of each other's existence |
Cooperation by sharing |
ØThe result of one process may depend on information obtained from the others.
ØOne process may affect the running time of another.
|
ØMutual exclusion
ØDeadlocks
ØStarvation
ØSynchronization
|
|
Processes are directly aware of each other's existence
|
Cooperation by communication
|
ØThe result of one process depends on information obtained from other processes.
ØOne process may affect the running time of another.
|
ØDeadlocks (consumable resources)
ØStarvation
|
Competition is a situation in which two or more processes require access to the same resource (a printer, a file, etc.), called a critical resource. The part of a program that uses a critical resource is called a critical section.
The need for mutual exclusion:
A group of processes is in a deadlock if each process in the group is waiting for an event that only another process in the same group can cause
The "starvation" problem
Starvation. The halting of one or more threads of a multithreaded application for an indefinite time (or permanently). Threads that are not dispatched for execution, even though they are not blocked and are not waiting for anything, are said to be starving. The cause of starvation usually lies in the dispatching rules and policies. For example, if a continuously running non-blocking high-priority thread is dispatched on a single-core processor, another thread with a lower priority will never start running.
Processes that interact with other processes without explicit information about each other access shared variables, shared files or databases.
Problems: mutual exclusion, deadlock, starvation. In addition: process synchronization to ensure data consistency
Example: suppose the condition a = b must hold, with the initial values a = b = 1
Option 1: the processes execute sequentially
P1: a = a + 1; b = b + 1; P2: b = 2 * b; a = 2 * a;
Option 2: the processes interrupt each other
P1: a = a + 1; interrupt; P2: b = 2 * b; interrupt;
P1: b = b + 1; interrupt; P2: a = 2 * a;
Consistency is violated: a = 4, b = 3
Situations in which two or more processes handle shared data (files) and the final result depends on the relative speeds of the processes (threads) are called race conditions
2. Lock variables (software approach)
3. Using system functions for entering a critical section
4. Dijkstra Semaphores
Semaphore: a variable S, primitives P (proberen – test; down) and V (verhogen – increment, up)
V(S) – the variable S is increased by 1 in a single action. Fetching, incrementing and storing cannot be interrupted. The variable S cannot be accessed while this operation is being executed.
P(S) – the variable S is decreased by 1 if this is possible, staying within the range of non-negative values. If S cannot be decreased, the thread executing the P operation waits until the decrease becomes possible. The P operation is indivisible.
In the special case, the semaphore S can take binary values 0 and 1, turning into a locking variable (a binary semaphore).
The P operation contains the potential for the process that executes it to move into a waiting state (if S = 0).
Under some circumstances, the V operation can activate a process that was suspended by the P operation.
A queue operating on the FIFO principle is used to hold the processes waiting on semaphores.
Conditions for a deadlock situation to arise:
Strategies for dealing with deadlocks:
1. Ignoring the problem altogether.
2. Detection and elimination of deadlocks (recovery).
3. Avoiding deadlock situations through careful resource allocation.
4. Prevention by structurally negating one of the four conditions necessary for a deadlock.
Deadlock detection methods
For example, suppose a system of seven processes (A, B, C, D, E, F, G) and six resources
(R, S, T, V, W, U) at some moment corresponds to the following list:
QUESTION: Is this system deadlocked, and if so, which processes are involved?
THE ANSWER CAN BE OBTAINED BY BUILDING A RESOURCE-PROCESS GRAPH.
2. Several resources of each type in the system.
Deadlock detection algorithm
It is based on comparing resource vectors. In the initial state, all processes are unmarked. As the algorithm proceeds, processes are marked to indicate that they can finish their work, i.e. they are not in a deadlock. After the algorithm terminates, any unmarked process is in a deadlock situation.
Algorithm
A, i.e. Ri <= Aj or ri j <= Aj , j = 1, m.
row of the matrix C is added to the vector A, i.e. Aj := Aj + ci j , j = 1, m.
Return to step 1.
3. If no such processes exist, the algorithm terminates. If there are unmarked processes, they are in a deadlock.
Deadlock recovery methods
Deadlock avoidance through safe resource allocation. Such algorithms are based on the concept of safe states. For example, Dijkstra developed a scheduling algorithm that makes it possible to avoid deadlocks (the banker's algorithm).
To synchronize threads belonging to different processes, the OS must provide threads with system synchronization objects.
Such objects include events, mutexes (mutex – mutual exclusion), system semaphores, and others.
An event object is used to notify threads that certain actions have been completed.
A mutex (the simplest binary semaphore) is used to control access to data.
Semaphores are used to signal that a sequence of events has occurred.
"Ordinary" OS objects are also used for synchronization: files, processes, threads
All synchronization objects can be in a signaled or a non-signaled (free) state. Using the system call WAIT(X), a thread can synchronize its execution with a synchronization object X. Using the system call SET(X), a thread can put the object X into the signaled state. In addition, the OS defines a set of signals for logical communication between processes, as well as between processes and users (terminals).
Classes of interrupts: external, internal, software
1. External interrupts – the result of user actions and of signals from the computer's peripheral devices and controlled objects.
2. Internal interrupts – the result of emergency situations arising during the execution of a program instruction.
3. Software interrupts – the result of executing special instructions planned in the program (a system call).
Principles of building interrupt systems:
Sequence of actions when handling interrupts
1. Primary hardware recognition of the interrupt type. If interrupts are disabled, the current program continues. Otherwise, the interrupt dispatcher is called and, depending on the information received by the processor (interrupt vector, priority, etc.), the interrupt handling routine is invoked.
2. Some part of the context of the interrupted thread is saved, which will allow its execution to be resumed after the interrupt is handled (usually the processor status word – the EFLAGS register in the Pentium – and the general-purpose registers). The full context may also be saved if the OS services the interrupt with a process switch.
3. The address of the interrupt handling routine is loaded into the program counter, and a new PSW is set, which defines the privileged mode of processor operation during interrupt handling.
4. Interrupts are temporarily disabled by masking so that a queue of nested threads of the same routine does not form.
5. After the interrupt has been handled by the operating system kernel, the interrupted context is restored (partly by hardware – the PSW and the contents of the program counter, partly by software – retrieving data from the stack), the handling of interrupts of this type is re-enabled, and the thread resumes from the point of interruption.
7.2. System calls
A system call allows an application to ask the OS to perform some action, implemented as a procedure of the OS code segment.
The implementation of system calls must satisfy the following requirements:
Possible schemes for servicing system calls:
1. Decentralized – each system call has its own interrupt vector assigned to it. Advantage – high speed of processing system calls; disadvantage – growth of the interrupt vector table.
2. Centralized – by means of a system call dispatcher.
Fig. Centralized scheme of system call handling
[[b6777]]
Comments