COE 512 – Computer Systems Architecture
Compiled by: Engr. Guilbert Nicanor A. Atillo
Lesson 10 – Operating System - Important Theory
- Introduction
- Processes
- The Kernel
- Scheduling
- Scheduling Policies, Algorithms
- Memory Management
- Physical and Virtual Store
- Cache Memory
- Paging
Operating Systems - Some Theory
In Chapter 8 we saw how the operation - in the sense of `driving' them - of computers evolved through users operating them, to operators, and finally through various sophistications of operating system software to timesharing operating systems.
First, we give a demonstration of the effect of multiprogramming.
Figures 9.1 and 9.2 shows the execution of three identical jobs, under two different operating system regimes.
Assume that the jobs/processes/programs are in memory to start with, that they do some computation (taking 10 millisec) which results in the requirement to read a particular record from a disk file (taking 10 millisec), finally they do some more computation (again 10 millisec). Viewed as executions of single programs this may not appear too useful - where do the results go to - but, in fact, the jobs are quite typical of what would be encountered by a timesharing during the execution lifetime of three processes
Figure 9.1 shows how the jobs would have to run on a single user system like MS-DOS. The computer is I/O blocked during each disk input - regardless of whether the input is by polled I/O, interrupts, or DMA.
Figure 9.2 shows the effect of multiprogramming; when one process become I/O bound, the CPU can do processing for another. Thus, a 90 millisec of computer usage can be reduced to 60; add more jobs and you get a greater increase in efficiency. NB. in this case, you are concerned with the method of I/O transfer - ideally the CPU asks for the data, and receives an interrupt when they are placed in memory.
Figure 9.1: Illustration of multiprocessing (a) single user |
Figure 9.2: Illustration of multiprocessing (b) multiprogrammed |
The work that a modern timesharing operating system performs is a good deal more complex than that of, for example, a simple resident monitor - or even a single user OS like MS-DOS. Nevertheless, like all complex systems, the analysis of operating systems responds to breaking them into subsystems/components.
The following functions are required:
1. Dispatching or scheduling. Switching the processor from one process to another; allowing jobs to enter queue.
2. Interrupt handling.
3. Resource allocation. Allocation of the computer's resources to processes: memory, I/O devices, CPU time.
4. Resource protection. Ensuring that no process can access any resource which has not been allocated to it.
5. Provision of (virtual) I/O and other services.
6. Provision of a file system - to processes, and to human users.
7. Analysing and decoding user commands - and requests from programs, and converting these into procedure and program names.
The functions that meet these requirements, and the relationships between them are sometimes shown as a so-called onion-skin diagram; this concept of layers of skin is closely related to that of levels of abstraction given in chapter 8.
We shall now briefly look at a selection of topics that pertain to these requirements.
The concept of a process is central - first used by MULTICS. Sometimes referred to as a task. Definition can be difficult: `a program in execution' may be the best.
During its life, a process goes through a series of discrete states:
- Running - if it currently has the CPU resource;
- Ready - if it could use the CPU if the CPU were available;
- Blocked - if it is waiting for some event to happen before it can proceed.
When a job is admitted to the system, a corresponding process is created and placed at the back of the queue and it is marked ready; alternatively, there may be separate queues. It gradually moves to the top of the ready list - see scheduling/dispatching below; when the CPU becomes available the process makes a state transition from ready to running. Strictly speaking this is dispatching.
To prevent any one process, say process A, monopolising the system - i.e. to provide time-sharing it must be possible possible to stop the process after it has consumed its allocated amount of CPU time. This is done via an interrupting clock (hardware) which allows a specified time quantum - a time-slot to pass; if process A is still using the CPU the clock generates an interrupt, causing the system to regain control. Process A now makes the state transition back to ready, i.e. A is put back in the ready queue.
The next process, process B, say, on the ready queue is now put into the running state; and so on ....
If a running process initiates an I/O operation before its time-slot expires then the process is forced to release the CPU; it enters the blocked state and releases the CPU.
If a process is in the blocked state and the event for which it is waiting completes, then the process makes the transition from blocked to ready. The four state transitions are shown in Figure 9.3
Figure 9.3: Process State Transitions: a Process can be running, blocked, or ready |
Because of this `switching on and off' of processes is is necessary to have housekeeping information associated with each process. A process control block PCB which is a record containing important current information about the process, for example: current state of the process, unique identification of the process, the process's priority, open files & I/O devices, use of main memory and backing store, other resources held, a register save area (see chapter 7).
All of the operations involving processes are controlled by a portion of the OS called its nucleus, core or kernel. The kernel represents only a small portion of the code of the entire OS but it is intensively used and so remains in primary storage while other portions may be transferred in and out of secondary storage as required.
One very important function of the kernel is interrupt processing. In large multi-user systems, the kernel is subjected to a constant barrage of interrupts. Clearly, rapid response is essential: to keep resources well utilised, and to provide acceptable response times for interactive users.
In addition, while dealing with an interrupt, the kernel disables other interrupts. Thus, to prevent interrupts being disabled for long periods of time, the kernel is designed to do the minimum amount of processing possible on each interrupt and to pass the remaining processing to an appropriate system process.
The kernel of a sophisticated OS may contain code to perform:
- interrupt handling;
- process creation & destruction;
- process state switching and dispatching;
- inter process communication;
- manipulation of PCB;
- support of I/O activities;
- support of memory allocation & deallocation;
- support of the file system;
- support of system accounting functions.
Supporting hardware and microcode is often provided - even for portable operating systems like UNIX.
The kernel has privileges that allow it to do things that normal processes cannot do, e.g. access I/O devices. Privilege is usually conferred by the processor state, i.e. privilege level is stored in hardware, so a process has a different processor state from the kernel. In the original Intel 8086/88 and 80286, there was limited support for processor states; however, in the 80386 and after, full time-sharing was supported.
The goal of scheduling (the method by which processor time is managed) is to provide good service to all the processes that are currently competing for resources, including the CPU.
Three type of scheduling may be identified: long term scheduling, medium term scheduling, and short term scheduling.
We will be concerned only with short-term scheduling - also called dispatching, which decides how to share the computer among all the processes that currently want to compute. Such decisions may be made frequently - tens of times per second.
There are several competing goals that scheduling policies aim to fulfill - one is good throughput. For short term scheduling, this minimizes the number of process switches. Another goal is good (quick) service.
Some of the - often conflicting - objectives of a good scheduling algorithm/policy are:
1. Be fair - all processes should be treated equitably;
2. Maximize throughput and service, i.e. as many processes as possible per unit time;
3. Maximize the number of interactive users receiving acceptable response times;
4. Be predictable - a given job should run in about the same amount of time regardless of the load on the system;
5. Balance resource use - processes using underutilized resources should be favoured;
6. Achieve a balance between response and utilization;
7. Avoid indefinite postponement - as a process waits for a resource its priority should grow (aging);
8. Enforce priorities;
9. Give preference to processes holding key resources;
10. Give better service to processes exhibiting desirable behaviour e.g. low paging rates - see below;
11. Degrade gracefully under heavy loads.
Thus, scheduling may appear to be a complex problem.
Scheduling Policies, Algorithms
First Come, First Served (FCFS)
Under FCFS, the short term scheduler runs each process until it either terminates or leaves because of I/O or resource requests. Processes arriving wait in the order that they arrive.
FCFS is non-preemptive, so a process is never blocked once it has started to run until it leaves the domain of the short term scheduler.
FCFS is usually unsatisfactory because of the way that it favours long (greedy) processes - like the person in the bank queue in front of you with the weeks takings from a shop!
The intention is to provide good response ratios for short as well as long processes. This policy services (allocates CPU to) a process for a single time slot (length = q), where q = between 1/60 and 1 second; if the process is not finished it is interrupted at the end of the slot and placed at the rear of the ready queue & will wait for its turn again. New arrivals enter the ready queue at the rear.
RR can be tuned by adjusting q. If q is so high that it exceeds the service requirements for all processes, RR becomes the same as FCFS. As q tends to 0, process switching happens more frequently and eventually occupies all available time. Thus q should be set small enough so that RR is fair but high enough so that the amount of time spent switching processes is reasonable.
RR is preemptive, i.e. it will stop a process, if the process has not completed before the end of its time-slot.
SPN (like FCFS) is non-preemptive. It tries to improve response for short processes over FCFS. But, it requires explicit information about the service time requirements for each process. The process with the shortest time requirement is chosen.
Unfortunately, long processes wait a long time or suffer starvation. Short processes are treated very favourably.
- Preemption is worth the extra switching cost. Since context must switch at every interrupt from the running process back to the kernel, it does not usually cost much extra for the kernel to make a decision and allow a different process to run.
- The time-slot should be large enough so that preemption cost does not become excessive, e.g.. if a process switch costs 100 microseconds, the quantum should be about 100 times as long.
- Some policies are more expensive than others to implement. FCFS only requires a queue for the ready list.
- Many OSs use a hybrid policy, with RR for short processes and some other method for long.
- Space management affects scheduling. Processes that need a substantial amount of memory are often given larger time-slots so that they can get more work done while they are occupying main store.
Figure 9.4 shows a five level storage organisation.
Figure 9.4: Five Levels of Memory/Storage. |
Data that is currently accessed most frequently should be in the highest level of storage hierarchy. Each offers about an order of magnitude faster access than its lower neighbour.
The relationship between each layer and the one below it can be considered as similar to that between cache and main memory - cache explained during tutorial or see a textbook. If we need to cache an item from a higher level then access is significantly slower. We call such a situation a cache miss. In contrast a cache hit is when we find the data we need in a cache and need not turn to the associated slower memory.
The OS must arrange main memory so that processes remain ignorant of each other and still share main memory. A guiding principle is that the more frequently data are accessed, the faster the access should be. If swapping in and out of main storage becomes the dominant activity, then we refer to this situation as thrashing.
Physical store is the hardware memory on the machine, usually starting at physical address 0. Certain locations may be reserved for special purposes; the kernel may reside in in the low addresses. The rest of physical store may be partitioned into pieces for the processes in the ready list.
Each process has its own virtual memory - the memory perceived by the process. As far as the process is concerned all address references refer to virtual space. Each process' virtual memory is limited only by the machine address size.
Note: Virtual memory can also be very useful even in a single user system - if the computer has a larger address space than physical memory, and if programs need a large amount of memory; compare overlaying - in which the programmer takes responsibility for segmenting the program into memory sized chunks.
The following, from [Tanenbaum, 1999], pages 65-67, gives a nice explanation of cache memory; cache memory is a small amount of fast memory near the CPU which in many cases mitigates the difficulties caused by the slow(ish) speed of main memory and by the bottleneck of MAR, MBR (see chapter 5). The basic principles employed in paging, see section 9.9, apply to caching.
Insert p. 65 here.
!Insert pp. 66, 67 here
!
!
The most common virtual storage technique is paging. Paging is designed to be transparent to the process - like all virtual memory.
The program and data of each process are regarded - by the OS as being partitioned into a number of pages of equal size. The computer's physical memory is similarly divided into a number of page frames. Page frames are allocated among processes by the OS At any time, each process will have a few pages in memory, while the remainder is in secondary memory.
The real point behind paging is that, whenever a process needs to access a location that is within a page that is in secondary memory, the page is fetched, invisibly to the process, and the access takes place, almost as if the datum had already been in memory. Thus, the process thinks that it has ALL of its virtual memory in main memory.
The remainder of this discussion can now proceed as if we are only concerned with a single process, which happens to be using a bigger virtual memory than can fit in main, physical, memory; ie. what is said is applicable to single user systems as well as multi-user. In addition, we shall simplify the arithmetic by assuming a page size size of 1000 - simpler for decimal oriented humans.
The process's virtual memory is divided into pages. Page 0 refers to locations 0 to 999, page 1: 1000 to 1999, and so on, ...
The CPU must transform from virtual address to physical address:
1. Calculate:
(a)
Virtual page number, i.e. address/1000;
(b)
Offset within that page, i.e. remainder after address/1000.
2. Calculate which page frame - physical page -, if any, that the virtual page occupies; this involves the use of a lookup table, the page table which links virtual pages with page frames e.g. Figure 9.5.
Figure 9.5: Page Table |
The third column - Secondary Store address - indicates where the OS must read/write if a page is to be transferred in/out of memory.
If the process needs a page which is not in memory - marked by a -1, for example-- a page fault is generated, and the OS sets about reading the required page into main memory. Obviously, some other page will have to be removed, to make space for the new page.
The whole paging process is illustrated by the pseudo-code in Figure 9.6. Think of PagedVirtualMemory being used in the situation where you have a PC with 32-bit addressing - 2 Gigabytes of virtual memory) but only 2K of physical memory available for data - forget about instructions for this example. Imagine that you want to use a 60K array of bytes. You use PagedVirtualMemory to access the array; the function hides all the hassle of address translation and paging.
Figure 9.6: Paging |
The choice of page size determined at the design stage is a trade- off between various considerations:
- Overhead space - least with large pages, since page tables have fewer entries.
- Internal waste - smallest with small pages.
- Cold start faults - lower with large pages. These are the faults needed to bring the program into main store the first time. With larger pages there are fewer total pages, hence fewer cold start faults.
- Page fault rate - generally lower with small pages, assuming that a fixed amount of main store is available.
- Efficiency of transfer between main memory and disk store - best with large pages, since they take about the same amount of time to transfer as small pages.
Larger pages are usually better, unless they become so large that too few processes in the ready list can have pages in main store at the same time. Common page sizes are from 512 bytes to 4K bytes but can be as large as 8K.
The storage manager must decide to keep some pages in main store and other pages in secondary store - unless virtual space requirements are less than the available physical space.
These decisions may be made at any time but when a page fault occurs a decision must be made; the process that suffered the page fault cannot continue until the appropriate page is swapped in.
A page replacement policy (PRP)/algorithm is used to decide which page frame to vacate ie. swap out its page.
Some commonly quoted strategies are:
Note: pages being heavily used should be preserved. One goal is to minimize the number of page faults. Swapping can reach a level at which all processes present need to swap so no progress can be made. If this persists, the OS is spending all its time transferring pages in and out of main store - known as thrashing.
Also called longest resident.
When a page frame is needed, the page that has been in main store for the longest time is chosen. This policy tends to save recently used pages which have a higher probability of being used again soon. However a frequently used page still gets swapped out when it gets to be old enough, even though it will have to be brought in immediately.
This method is based on the assumption that the page reference pattern in the recent past is a mirror of the pattern in the near future. Pages that have been accessed recently are likely to continue to be accessed and ought to be kept in main store. It is expensive to implement exactly since in order to find the page least recently used, either a list of pages must be maintained in use order or each page must be marked with the time it was last accessed.
Review Questions:
- Explain interrupts and traps, and provide a detailed account of the procedure that an operating system handles an interrupt.
- What is the supervisor or kernel mode? What is the user mode? What are the differences? Why are they needed?
- Define the meaning of mechanism and policy in the separation of mechanism and policy principle.
- Most modern operating systems provide support for both processes and threads. Define process and thread. List two key differences and similarities between process and thread.
- For each of the following pairs of terms, define each term, making sure to clarify the key difference(s) between the two terms.
(a) “application software” and “system software”
(b) “user mode” and “kernel mode”
(c) “single-core” and “multi-core”
(d) “text segment” and “data segment”
(e) “short-term scheduler” and “long-term scheduler”
(f) “waiting time” and “service time”
RESEARCH Problem:
Compare at least 20 commands for the following: DOS, WINDOWS, LINUX, UBUNTU,and
UNIX. A sample output is shown below. Please pass your hardcopy output on September 14, 2009.
Example:
DOS | WINDOWS | UNIX | LINUX | UBUNTU |
Copy - this command can be used both to copy files from disk to disk or to create a second copy of a file on a single disk.
Ex. C> copy a:brazil1.dat b:\south\brazil2.dat |
copy source [destination] copy d:\i386\atapi.sy_ c:\windows\atapi.sys |
cp firstfile secondfile
|
$ cp stuff stuff.bak |
cp file_name/folder_name |
