Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 2: Memory and Process Management Part 2 - Coggle Diagram
Chapter 2: Memory and Process Management
Part 2
The Major System Resource Types Within A Computer System
A resource, or system resource, is any physical or virtual component of limited availability within a computer system.
Every device connected to a computer system is a resource.
Every internal system component is a resource.
Virtual system resources include files, network connections and memory areas.
Network Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel
This data may be delivered over a physical or logical link, or pass through a certain network node.
The throughput is usually measured in bits per second (bit/s or bps), and sometimes in data packets per second or data packets per time slot.
Electrical Power
Electric power is the rate at which electric energy is transferred by an electric circuit.
The SI unit of power is the watt, one joule per second.
Hard Disk Space
The term "disk space" is an amount of computer storage space on random-access memory devices, such as on a hard drive, floppy or USB flash drive.
Disk space units are commonly measured in large numbers of bytes, such as Kilobytes, Megabytes, and Gigabytes, with each unit 1024x times larger than the previous unit.
The term originated in the 1950s, for the storage area on a hard disk drive, which internally had disk-shaped platters to rotate quickly
As storage devices have been created in other shapes, the term "disk space" has still been used to refer to areas of permanent storage on various storage devices.
The total disk space can span multiple devices, such as areas on an array of disk drives.
External Devices
An external device is a component that can be connected to your computer. These external components of the computer are called : peripheral input or output. It exists two types of peripheral, input devices and output devices.
The input devices is used to provide information (or data) to the computer system: Keyboard (typing text), mouse (pointing), scanning (scanning of paper documents), microphone, etc..
The output devices are used to bring out information from the computer system: monitor, printer, speaker, etc..
You can also add peripheral input / output operating in both directions : a CD-ROM, a USB key or an external hard drive for example, can store data (output) or provide data (input).
Memory
Random access memory
Random access memory (RAM) is a form of computer data storage.
A random access device allows stored data to be accessed in any order in very nearly the same amount of time for any storage location or size of memory device.
A device such as a magnetic tape requires increasing time to access data stored on parts of the tape that are far from the ends.
Memory devices (such as floppy discs, CDs and DVDs) can access the storage data only in a predetermined order, because of mechanical design limitations; the time to access a given part of the device varies significantly due to its physical location.
Virtual Memory
In computing, virtual memory is a memory management technique developed for multitasking kernels.
This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM).
Input / Output Operations
IOPS ( Input/Output Operations Per Second, pronounced eye-ops) is a common performance measurement used to benchmark computer storage devices like hard disk drives (HDD), solid state drives (SSD), and storage area networks (SAN).
As with any benchmark, IOPS numbers published by storage device manufacturers do not guarantee real-world application performance.
IOPS can be measured with applications, such as Iometer (originally developed by Intel), as well as IOzone and FIO and is primarily used with servers to find the best storage configuration.
CPU Time
CPU time (or CPU usage, process time) is the amount of time for which a central processing unit(CPU) was used for processing instructions of a computer program, as opposed to, for example, waiting for input/output (I/O) operations.
The CPU time is often measured in clock ticks or seconds.
CPU time is also mentioned as percentage of the CPU's capacity at any given time on multi-tasking environment
That helps in figuring out how a CPU’s computational power is being shared among multiple computer programs.
In contrast, elapsed real time (or simply real time, or wall clock time) is the time taken from the start of a computer program until the end as measured by an ordinary clock.
Elapsed real time includes I/O time and all other types of waits incurred by the program.
Process Concept
An operating system executes a variety of programs
Batch system – jobs
Time-shared systems – user programs or tasks
Textbook uses the terms “job” and “process” almost interchangeably
Process – a program in execution; process execution must progress in sequential fashion
A process includes:
program counter
stack
data section
As a process executes, it changes state
New/created: The process is being created
running: Instructions are being executed
Waiting/blocked: The process is waiting for some event to occur
ready: The process is waiting to be assigned to a processor
terminated: The process has finished execution
Life cycle of a process:
The state diagram for a process captures its life-cycle. The states represent the execution status of the process; the transitions represent changes of execution state.
Each active process has its own execution status, so there is a state diagram for each process. There are relationships between the states of various processes that are maintained by the operating system.
Running
A process in the running state has all of the resources that it needs for further execution, including a processor.
Blocked
A process that needs some resource other than a processor for further execution is in a blocked state. It is usually placed in a queue waiting for the needed resource.
Ready
A process in the ready state has all of the resources that it needs for further execution except for a processor. It is normally held in a ready queue until a processor becomes available.
Interrupts
Interrupts are special signals sent by hardware or software to the CPU.
It's as if some part of the computer suddenly raised its hand to ask for the CPU's attention in a lively meeting.
Sometimes the operating system will schedule the priority of processes so that interrupts are masked -- that is, the operating system will ignore the interrupts from some sources so that a particular job can be finished as quickly as possible.
There are some interrupts (such as those from error conditions or problems with memory) that are so important that they can't be ignored. These non-maskable interrupts (NMIs) must be dealt with immediately, regardless of the other tasks at hand.
An event that change the sequence in which a processor execute instructions
Prevents a process from monopolizing the system
OS sets interrupting clock/interval timer to allow user to run in a specific time interval.
If process does not free CPU in interval time, interrupting clock generates an interrupt that cause OS to regain control
OS turn the previously running process to ready, and makes the first process on the ready list running
Scheduling Process
A process is executed until it must wait, typically for the completion of some I/O request. In a simple computer system, the CPU then just sits idle. All this waiting time is wasted; no useful work is accomplished. With multiprogramming, we try to use this time productively. Several processes are kept in memory at one time. When one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. This pattern continues. Every time one process has to wait, another process can take over use of the CPU
Scheduling of this kind is a fundamental operating-system function. Almost all computer resources are scheduled before use. The CPU is, of course, one of the primary computer resources. Thus, its scheduling is central to operating-system design.
The success of CPU scheduling depends on an observed property of processes:
Process execution consists of a cycle of CPU execution and I/O wait.
Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution
The durations of CPU bursts may vary greatly from process to process and from computer to computer, they tend to have a frequency curve similar to that shown in next figure. (exponential or hyper-exponential) with a large number of short CPU bursts and a small number of long CPU bursts.
An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a few long CPU bursts. This distribution can be important in the selection of an appropriate CPU-scheduling algorithm.
Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler (or CPU scheduler). The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.
Note that the ready queue is not necessarily a first-in, first-out (FIFO) queue
As we shall see when we consider the various scheduling algorithms, a ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list. Conceptually, however, all the processes in the ready queue are lined up waiting for a chance to run on the CPU. The records in the queues are generally process control blocks (PCBs) of the processes.
CPU Scheduler
As mentioned in previous lecture;
Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler (or CPU scheduler).
The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.
Medium-Term Scheduler
The mid-term scheduler may decide to swap out a process which :
Has not been active for some time, or a process which has a low priority, or
A process which is page faulting (kesalahan muka surat) frequently, or
A process which is taking up a large amount (julat) of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or
When the process has been unblocked and is no longer waiting for a resource.
Short-Term Scheduler
Also known as the dispatcher.
Decides which of the ready, in-memory processes are to be executed (allocated a CPU) next following a clock interrupt, an IO interrupt, an operating system call or another form of signal.
Makes scheduling decisions much more frequently than the long-term or mid-term schedulers
Short-term scheduler
Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU
Short-term scheduler is invoked very frequently (milliseconds) (must be fast)
Processes can be described as either:
I/O-bound process – spends more time doing I/O than computations, many short CPU bursts
CPU-bound process – spends more time doing computations; few very long CPU bursts
Long-Term Scheduler
The long-term, or admission, scheduler decides which jobs or processes are to be admitted to the ready queue.
When an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler.
Thus, this scheduler dictates what processes are to run on a system, and the degree of concurrency to be supported at any one time
Long-term scheduler
Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue
Long-term scheduler is invoked very infrequently (seconds, minutes) (may be slow)
The long-term scheduler controls the degree of multiprogramming
Differentiate between preemptive and non-preemptive technique in scheduling.
In computing, preemption (more correctly ”pre-emption”) is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time
Such a change is known as a context switch.
It is normally carried out by a privileged task or part of the system known as a preemptive scheduler, which has the power to preempt, or interrupt, and later resume, other tasks in the system.
CPU scheduling decisions may take place when a process:
Switches from running to waiting state
Terminates
Switches from waiting to ready
Switches from running to ready state
When scheduling takes place only under circumstances 1 and 2, we say that the scheduling scheme is non-preemptive; otherwise, its called preemptive
Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keep the CPU until it release the CPU either by terminating or by switching to waiting state. (Windows 95 and earlier)
Preemptive scheduling incurs a cost associated with access to share data.
Consider the case of two processes that share a data. It is preemptive so that while one process is updating the data, the second process then tries to read the data, which are in an inconsistent state
Scheduling Algorithms
Shortest Job First
When the CPU is available, it is assigned to the process that has the smallest next CPU burst.
If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie.
Priority, Multilevel Queue
A priority is associated with each process, and the CPU is allocated to the process with the highest priority (high priority and low priority).
We assume that low numbers represent lower priority. (1, 2, 3, 4, 5 : 5 is highest priority
Non-preemptive.
Round Robin Scheduling
The round-robin (RR) scheduling algorithm is designed especially for timesharing systems.
It is similar to FCFS scheduling, but preemption is added to switch between processes.
A small unit of time, called a time quantum or time slice, is defined. (A time quantum is generally from 10 to 100 milliseconds.)
The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
To implement RR scheduling, we keep the ready queue as a FIFO queue of processes.
New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
Multilevel Feedback Queue
Has a number of queues, each assigned a different priority level.
A job that is ready to run can only be on a single queue.
It allows a process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts.
If a process uses too much CPU time, it will be moved to a lower-priority queue.
For example, consider a multilevel feedback-queue scheduler with three queues, numbered from 0 to 2 (0,1 and 2)
The scheduler first executes all processes in queue 0. Only when queue 0 is empty will it execute processes in queue 1. Similarly, processes in queue 2 will only be executed if queues 0 and 1 are empty.
A process that arrives for queue 1 will preempt a process in queue 2. A process in queue 1 will in turn be preempted by a process arriving for queue 0.
First In First Out (FIFO)
The process that requests the CPU first is allocated to the CPU first
Whichever process that first placed their request will get the CPU first.
How many processes?
What are the sequence of the processes?
Calculate “Waiting Time”
Label Waiting Time into the Gantt Chart.
Multilevel Queue
Processes are easily classified into different groups.
It partitions the ready queue into several separate queues.
Each queue has its own scheduling algorithm
Ready queue is partitioned into separate queues:
foreground (interactive)
background (batch)
Scheduling must be done between the queues.
Partitions the ready queue into several separate queues.
Each queue has its own scheduling algorithm
There must be scheduling between the queues
The processes are permanently assigned to one queue based on some property of the process. For example :
Interactive process
Batch process
Appropriate Scheduling Criteria
Waiting Time
Response Time
*Response Time/Ratio = Turnaround Time / Burst Time
Turnaround Time
*Turnaround Time = Burst Time + Waiting Time
Thread
A thread is the smallest unit of processing that can be performed in an OS. In most modern operating systems, a thread exists within a process - that is, a single process may contain multiple threads.
Benefits of Multithreading
Operate faster on computer systems that have multiple CPUs, CPUs with multiple cores, or across a cluster of machines
because the threads of the program naturally lend themselves to truly concurrent execution
Eg: Downloading a video while playing it at the same time
Ability for an application to remain responsive to input
In a single-threaded program, if the main execution thread blocks on a long-running task, the entire application can appear to freeze. By moving such long-running tasks to a worker thread that runs concurrently with the main execution thread, it is possible for the application to remain responsive to user input while executing tasks in the background
Shared Resources
When you use multiple threads instead of separate processes multiple threads share a single address space, all open files, and other resources
Potential Simplicity
Multiple threads may reduce the complexity of some applications that are inherently suited for threads.
Threads Relationship to Processes
At least one kernel thread exists within each process. If multiple kernel threads can exist within a process, then they share the same memory and file resources.
A thread represents a line of execution within a process. Processes can be multithreaded, that is, they can have several different lines of execution occurring simultaneously.
Define Deadlock
In a multiprogramming environment, several processes may compete for a finite number of resources.
A process requests resources; and if the resources are not available at that time, the process enters a waiting state.
Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes.
This situation is called a deadlock
Deadlock
In computer science, Coffman deadlock refers to a specific condition when two or more processes are each waiting for each other to release a resource, or more than two processes are waiting for resources in a circular chain.
Deadlock is a common problem in multiprocessing where many processes share a specific type of mutually exclusive resource known as a software lock or soft lock.
Deadlocks are particularly troubling because there is no general solution to avoid (soft) deadlocks.
A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
Deadlock Example
This situation may be likened to two people who are drawing diagrams, with only one pencil and one ruler between them.
If one person takes the pencil and the other takes the ruler, a deadlock occurs when the person with the pencil needs the ruler and the person with the ruler needs the pencil to finish his work with the ruler.
Both requests can't be satisfied, so a deadlock occurs.
Bridge Crossing Example
Traffic only in one direction
Each section of a bridge can be viewed as a resource.
If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).
Several cars may have to be backed up if a deadlock occurs.
Starvation is possible
Printers Scenario
A system may have two printers. These two printers may be defined to be in the same resource class if no one cares which printer prints which output.
However, if one printer is on the ninth floor and the other is in the basement, then people on the ninth floor may not see both printers as equivalent, and separate resource classes may need to be defined for each printer.
Conditions For A Deadlock To Occur
1.Mutual exclusion condition: a resource that cannot be used by more than one process at a time.
2.Hold-and-wait condition: each thread holds one resource while waiting for another.
3.No preemption condition: thread can only release resources voluntarily. No other thread (or OS) can force the thread to release.
4.Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds
All four conditions must occur before the deadlock happens.
There will be no deadlock if at least one of the conditions unhold.
3 ways to deal with deadlock
We can deal with the deadlock problem in one of three ways:
Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state. OR
Allow the system to enter a deadlock state, detect it, and recover. OR
Ignore the problem altogether and pretend that deadlocks never occur in the system.
Deadlock Prevention
Mutual Exclusion: The mutual-exclusion condition must hold for non-sharable resources. (Weaknesses: resource utilization may be low, and starvation)
Hold and Wait: whenever a process requests a resource, it does not hold any other resources
No Preemption: no preemption of resources that have already been allocated. (often applied to resources whose state can be easily saved and restored later, such as CPU registers and memory space)
Circular Wait: to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.
Deadlock Avoidance
Prevent deadlocks by restraining how requests can be made
The restraints ensure that at least one of the necessary conditions for deadlock cannot occur and, hence, that deadlocks cannot hold.
Deadlock Solution
1.Non-blocking synchronization algorithm
a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress.
2.Serializing tokens
serializing tokens are a concept in concurrency control arising from the ongoing development of DragonFly BSD. According to Matthew Dillon, they are most akin to SPLs, except a token works across multiple CPUs while SPLs only work within a single CPU's domain.
3.Lock-free and wait-free algorithm
Lock-free data structures guarantee the progress of at least one thread when executing multithreaded procedures, thereby helping you avoid deadlock
4.Resource hierarchy solution
The resource hierarchy solution avoids deadlocks, it is not always practical, especially when the list of required resources is not completely known in advance.
For example, if a unit of work holds resources 3 and 5 and then determines it needs resource 2, it must release 5, then 3 before acquiring 2, and then it must re-acquire 3 and 5 in that order.
Computer programs that access large numbers of database records would not run efficiently if they were required to release all higher-numbered records before accessing a new record, making the method impractical for that purpose.