Operating System 简明教程

Operating System - Quick Guide

Operating System - Overview

操作系统 (OS) 是计算机用户和计算机硬件之间的接口。操作系统是一种执行所有基本任务的软件，例如文件管理、内存管理、进程管理、处理输入和输出以及控制外围设备（例如磁盘驱动器和打印机）。

An Operating System (OS) is an interface between a computer user and computer hardware. An operating system is a software which performs all the basic tasks like file management, memory management, process management, handling input and output, and controlling peripheral devices such as disk drives and printers.

一些流行的操作系统包括 Linux 操作系统、Windows 操作系统、VMS、OS/400、AIX、z/OS 等。

Some popular Operating Systems include Linux Operating System, Windows Operating System, VMS, OS/400, AIX, z/OS, etc.

Definition

操作系统是一个充当用户与计算机硬件之间的接口的程序，并且控制各类程序的执行。

An operating system is a program that acts as an interface between the user and the computer hardware and controls the execution of all kinds of programs.

以下是操作系统的部分重要功能。

Following are some of important functions of an operating System.

Memory Management
Processor Management
Device Management
File Management
Security
Control over system performance
Job accounting
Error detecting aids
Coordination between other software and users

Memory Management

内存管理是指对主内存或主存储器的管理。主内存由一组单词或字节组成，每个单词或字节拥有自己的地址。

Memory management refers to management of Primary Memory or Main Memory. Main memory is a large array of words or bytes where each word or byte has its own address.

主内存提供一种由 CPU 直接访问的快速存储器。程序需要在主内存中才能执行。操作系统针对内存管理执行以下活动：-

Main memory provides a fast storage that can be accessed directly by the CPU. For a program to be executed, it must in the main memory. An Operating System does the following activities for memory management −

Keeps tracks of primary memory, i.e., what part of it are in use by whom, what part are not in use.
In multiprogramming, the OS decides which process will get memory when and how much.
Allocates the memory when a process requests it to do so.
De-allocates the memory when a process no longer needs it or has been terminated.

Processor Management

在多道程序设计环境中，操作系统决定哪个进程在何时获得处理器，以及获得多长时间的处理器。此功能称为 process scheduling 。操作系统针对处理器管理执行以下活动：-

In multiprogramming environment, the OS decides which process gets the processor when and for how much time. This function is called process scheduling. An Operating System does the following activities for processor management −

Keeps tracks of processor and status of process. The program responsible for this task is known as traffic controller.
Allocates the processor (CPU) to a process.
De-allocates processor when a process is no longer required.

Device Management

操作系统通过各个驱动程序管理设备通信。操作系统针对设备管理执行以下活动：-

An Operating System manages device communication via their respective drivers. It does the following activities for device management −

Keeps tracks of all devices. Program responsible for this task is known as the I/O controller.
Decides which process gets the device when and for how much time.
Allocates the device in the efficient way.
De-allocates devices.

File Management

文件系统通常根据目录进行整理，以方便浏览和使用。这些目录可能包含文件以及其他的方向。

A file system is normally organized into directories for easy navigation and usage. These directories may contain files and other directions.

操作系统对文件管理执行以下活动 -

An Operating System does the following activities for file management −

Keeps track of information, location, uses, status etc. The collective facilities are often known as file system.
Decides who gets the resources.
Allocates the resources.
De-allocates the resources.

Other Important Activities

以下是操作系统执行的部分重要活动 -

Following are some of the important activities that an Operating System performs −

Security − By means of password and similar other techniques, it prevents unauthorized access to programs and data.
Control over system performance − Recording delays between request for a service and response from the system.
Job accounting − Keeping track of time and resources used by various jobs and users.
Error detecting aids − Production of dumps, traces, error messages, and other debugging and error detecting aids.
Coordination between other softwares and users − Coordination and assignment of compilers, interpreters, assemblers and other software to the various users of the computer systems.

Types of Operating System

操作系统从第一台计算机开始就存在，并且随着时间的推移不断发展。在本章中，我们将讨论一些最常用的重要操作系统类型。

Operating systems are there from the very first computer generation and they keep evolving with time. In this chapter, we will discuss some of the important types of operating systems which are most commonly used.

Batch operating system

批处理操作系统的用户不会直接与计算机交互。每个用户都会在脱机设备（如穿孔卡）上准备自己的作业，并将其提交给计算机操作员。为了加快处理速度，需求类似的作业会被批处理在一起并作为一组运行。程序员会将自己的程序留给操作员，然后操作员会将具有相似需求的程序分类到批处理中。

The users of a batch operating system do not interact with the computer directly. Each user prepares his job on an off-line device like punch cards and submits it to the computer operator. To speed up processing, jobs with similar needs are batched together and run as a group. The programmers leave their programs with the operator and the operator then sorts the programs with similar requirements into batches.

批处理系统的缺点如下 −

The problems with Batch Systems are as follows −

Lack of interaction between the user and the job.
CPU is often idle, because the speed of the mechanical I/O devices is slower than the CPU.
Difficult to provide the desired priority.

Time-sharing operating systems

分时是一种技术，它使许多位于不同终端的人员能够同时使用一个特定的计算机系统。分时或多任务处理是多道程序设计的逻辑扩展。同时在多个用户之间共享的处理器的時間称为分时。

Time-sharing is a technique which enables many people, located at various terminals, to use a particular computer system at the same time. Time-sharing or multitasking is a logical extension of multiprogramming. Processor’s time which is shared among multiple users simultaneously is termed as time-sharing.

多道程序批处理系统和分时系统之间的主要区别在于，在多道程序批处理系统的情况下，目标是最大化处理器使用率，而在分时系统中，目标是最小化响应时间。

The main difference between Multiprogrammed Batch Systems and Time-Sharing Systems is that in case of Multiprogrammed batch systems, the objective is to maximize processor use, whereas in Time-Sharing Systems, the objective is to minimize response time.

CPU 通过在多个作业之间切换来执行多个作业，但切换发生得很频繁。因此，用户可以收到即时响应。例如，在事务处理中，处理器以短时间段或计算量子执行每个用户程序。也就是说，如果存在 n 个用户，那么每个用户都可以获得一个时间量子。当用户提交命令时，响应时间最多只有几秒钟。

Multiple jobs are executed by the CPU by switching between them, but the switches occur so frequently. Thus, the user can receive an immediate response. For example, in a transaction processing, the processor executes each user program in a short burst or quantum of computation. That is, if n users are present, then each user can get a time quantum. When the user submits the command, the response time is in few seconds at most.

操作系统使用 CPU 调度和多道程序设计为每个用户提供一小部分时间。最初主要设计为批处理系统的计算机系统已经修改为分时系统。

The operating system uses CPU scheduling and multiprogramming to provide each user with a small portion of a time. Computer systems that were designed primarily as batch systems have been modified to time-sharing systems.

分时操作系统具有以下优点：

Advantages of Timesharing operating systems are as follows −

Provides the advantage of quick response.
Avoids duplication of software.
Reduces CPU idle time.

分时操作系统的缺点如下：

Disadvantages of Time-sharing operating systems are as follows −

Problem of reliability.
Question of security and integrity of user programs and data.
Problem of data communication.

Distributed operating System

分布式系统使用多个中央处理器为多个实时应用程序和多个用户提供服务。数据处理作业相应地分布在处理器之间。

Distributed systems use multiple central processors to serve multiple real-time applications and multiple users. Data processing jobs are distributed among the processors accordingly.

处理器通过各种通信线路（例如高速总线或电话线）相互通信。这些被称为 loosely coupled systems 或分布式系统。分布式系统中的处理器在大小和功能上可能有所不同。这些处理器被称为站点、节点、计算机等。

The processors communicate with one another through various communication lines (such as high-speed buses or telephone lines). These are referred as loosely coupled systems or distributed systems. Processors in a distributed system may vary in size and function. These processors are referred as sites, nodes, computers, and so on.

分布式系统的优点如下：

The advantages of distributed systems are as follows −

With resource sharing facility, a user at one site may be able to use the resources available at another.
Speedup the exchange of data with one another via electronic mail.
If one site fails in a distributed system, the remaining sites can potentially continue operating.
Better service to the customers.
Reduction of the load on the host computer.
Reduction of delays in data processing.

Network operating System

网络操作系统在服务器上运行，并为服务器提供管理数据、用户、组、安全、应用程序和其他网络功能的能力。网络操作系统的主要目的是允许网络中多台计算机（通常是局域网 (LAN)、专用网络或其他网络）之间共享文件和打印机访问权限。

A Network Operating System runs on a server and provides the server the capability to manage data, users, groups, security, applications, and other networking functions. The primary purpose of the network operating system is to allow shared file and printer access among multiple computers in a network, typically a local area network (LAN), a private network or to other networks.

网络操作系统示例包括 Microsoft Windows 服务器 2003、Microsoft Windows 服务器 2008、UNIX、Linux、Mac OS X、Novell NetWare 和 BSD。

Examples of network operating systems include Microsoft Windows Server 2003, Microsoft Windows Server 2008, UNIX, Linux, Mac OS X, Novell NetWare, and BSD.

网络操作系统的优点如下 −

The advantages of network operating systems are as follows −

Centralized servers are highly stable.
Security is server managed.
Upgrades to new technologies and hardware can be easily integrated into the system.
Remote access to servers is possible from different locations and types of systems.

网络操作系统的缺点如下 −

The disadvantages of network operating systems are as follows −

High cost of buying and running a server.
Dependency on a central location for most operations.
Regular maintenance and updates are required.

Real Time operating System

实时系统定义为一个数据处理系统，其中处理和响应输入所需的时间间隔非常小，以至于它控制着环境。系统响应输入并显示所需更新信息所花费的时间称为 response time 。因此，在这种方法中，与联机处理相比，响应时间非常少。

A real-time system is defined as a data processing system in which the time interval required to process and respond to inputs is so small that it controls the environment. The time taken by the system to respond to an input and display of required updated information is termed as the response time. So in this method, the response time is very less as compared to online processing.

当对处理器的操作或数据流有严格的时间要求时，可以使用实时系统，并且可以在专用应用程序中将实时系统用作控制设备。实时操作系统必须具有明确定义的、固定的时间约束，否则系统将失败。例如，科学实验、医学影像系统、工业控制系统、武器系统、机器人、空中交通管制系统等。

Real-time systems are used when there are rigid time requirements on the operation of a processor or the flow of data and real-time systems can be used as a control device in a dedicated application. A real-time operating system must have well-defined, fixed time constraints, otherwise the system will fail. For example, Scientific experiments, medical imaging systems, industrial control systems, weapon systems, robots, air traffic control systems, etc.

实时操作系统有两种类型。

There are two types of real-time operating systems.

Hard real-time systems

硬实时系统保证关键任务按时完成。在硬实时系统中，辅助存储器受到限制或缺失，数据存储在 ROM 中。在这些系统中，几乎找不到虚拟内存。

Hard real-time systems guarantee that critical tasks complete on time. In hard real-time systems, secondary storage is limited or missing and the data is stored in ROM. In these systems, virtual memory is almost never found.

Soft real-time systems

软实时系统的限制较少。关键实时任务优先于其他任务，并保留优先级，直到任务完成。软实时系统的实用性不如硬实时系统。例如，多媒体、虚拟现实、海底勘探和行星探测车等先进科学项目。

Soft real-time systems are less restrictive. A critical real-time task gets priority over other tasks and retains the priority until it completes. Soft real-time systems have limited utility than hard real-time systems. For example, multimedia, virtual reality, Advanced Scientific Projects like undersea exploration and planetary rovers, etc.

Operating System - Services

操作系统为用户和程序提供服务。

An Operating System provides services to both the users and to the programs.

It provides programs an environment to execute.
It provides users the services to execute the programs in a convenient manner.

以下是操作系统提供的几种常见服务 −

Following are a few common services provided by an operating system −

Program execution
I/O operations
File System manipulation
Communication
Error Detection
Resource Allocation
Protection

Program execution

操作系统处理从用户程序到系统程序（如打印机后台程序、名称服务器、文件服务器等）的多种活动。这些活动中的每一个都封装为一个进程。

Operating systems handle many kinds of activities from user programs to system programs like printer spooler, name servers, file server, etc. Each of these activities is encapsulated as a process.

进程包括完整的执行上下文（要执行的代码、要处理的数据、寄存器、正在使用的操作系统资源）。以下是操作系统在程序管理方面的主要活动 −

A process includes the complete execution context (code to execute, data to manipulate, registers, OS resources in use). Following are the major activities of an operating system with respect to program management −

Loads a program into memory.
Executes the program.
Handles program’s execution.
Provides a mechanism for process synchronization.
Provides a mechanism for process communication.
Provides a mechanism for deadlock handling.

I/O Operation

I/O 子系统包含 I/O 设备及其相应的驱动程序软件。驱动程序向用户隐藏特定硬件设备的特性。

An I/O subsystem comprises of I/O devices and their corresponding driver software. Drivers hide the peculiarities of specific hardware devices from the users.

操作系统对用户和设备驱动器之间的通信进行管理。

An Operating System manages the communication between user and device drivers.

I/O operation means read or write operation with any file or any specific I/O device.
Operating system provides the access to the required I/O device when required.

File system manipulation

一个文件表示收集起来的相关信息。计算机可以将文件存储在磁盘（二级存储）上，以作长期存储之用。存储介质的示例包括磁带、磁头磁盘和光盘驱动器，如 CD、DVD。这些介质每一种都有其自己的属性，如速度、容量、数据传输速率和数据访问方法。

A file represents a collection of related information. Computers can store files on the disk (secondary storage), for long-term storage purpose. Examples of storage media include magnetic tape, magnetic disk and optical disk drives like CD, DVD. Each of these media has its own properties like speed, capacity, data transfer rate and data access methods.

文件系统通常被组织成目录，以便进行轻松导航和使用。这些目录可能包含文件和其他方向。以下是操作系统在文件管理方面的几个主要活动 −

A file system is normally organized into directories for easy navigation and usage. These directories may contain files and other directions. Following are the major activities of an operating system with respect to file management −

Program needs to read a file or write a file.
The operating system gives the permission to the program for operation on file.
Permission varies from read-only, read-write, denied and so on.
Operating System provides an interface to the user to create/delete files.
Operating System provides an interface to the user to create/delete directories.
Operating System provides an interface to create the backup of file system.

Communication

在分布式系统的情况下，该系统是处理器集合，不共享内存、外围设备或时钟，操作系统管理所有进程之间的通信。多个进程通过网络中的通信线路互相通信。

In case of distributed systems which are a collection of processors that do not share memory, peripheral devices, or a clock, the operating system manages communications between all the processes. Multiple processes communicate with one another through communication lines in the network.

操作系统处理路由和连接策略以及争用和安全问题。以下是操作系统在通信方面的几个主要活动 −

The OS handles routing and connection strategies, and the problems of contention and security. Following are the major activities of an operating system with respect to communication −

Two processes often require data to be transferred between them
Both the processes can be on one computer or on different computers, but are connected through a computer network.
Communication may be implemented by two methods, either by Shared Memory or by Message Passing.

Error handling

错误随时可能发生。错误可能发生在 CPU 中、在 I/O 设备中或在内存硬件中。以下是操作系统在错误处理方面的几个主要活动 −

Errors can occur anytime and anywhere. An error may occur in CPU, in I/O devices or in the memory hardware. Following are the major activities of an operating system with respect to error handling −

The OS constantly checks for possible errors.
The OS takes an appropriate action to ensure correct and consistent computing.

Resource Management

在多用户或多任务环境中，需要为每个用户或作业分配主存储器、CPU 周期和文件存储等资源。以下是操作系统在资源管理方面的主要活动−

In case of multi-user or multi-tasking environment, resources such as main memory, CPU cycles and files storage are to be allocated to each user or job. Following are the major activities of an operating system with respect to resource management −

The OS manages all kinds of resources using schedulers.
CPU scheduling algorithms are used for better utilization of CPU.

Protection

对于具有多个用户且同时执行多个进程的计算机系统，必须保护各个进程免于彼此活动的影响。

Considering a computer system having multiple users and concurrent execution of multiple processes, the various processes must be protected from each other’s activities.

保护是指控制程序、进程或用户访问计算机系统所定义的资源的一种机制或方法。以下是操作系统在保护方面的主要活动−

Protection refers to a mechanism or a way to control the access of programs, processes, or users to the resources defined by a computer system. Following are the major activities of an operating system with respect to protection −

The OS ensures that all access to system resources is controlled.
The OS ensures that external I/O devices are protected from invalid access attempts.
The OS provides authentication features for each user by means of passwords.

Operating System - Properties

Batch processing

批处理是一种技术，在该技术中，操作系统在处理开始前先将程序和数据一起收集到一个批处理中。操作系统执行与批处理相关的以下活动：

Batch processing is a technique in which an Operating System collects the programs and data together in a batch before processing starts. An operating system does the following activities related to batch processing −

The OS defines a job which has predefined sequence of commands, programs and data as a single unit.
The OS keeps a number a jobs in memory and executes them without any manual information.
Jobs are processed in the order of submission, i.e., first come first served fashion.
When a job completes its execution, its memory is released and the output for the job gets copied into an output spool for later printing or processing.

Advantages

Batch processing takes much of the work of the operator to the computer.
Increased performance as a new job get started as soon as the previous job is finished, without any manual intervention.

Disadvantages

Difficult to debug program.
A job could enter an infinite loop.
Due to lack of protection scheme, one batch job can affect pending jobs.

Multitasking

多任务是指 CPU 通过在多个作业之间进行切换来同时执行多个作业。切换发生得非常频繁，以至于用户可以在程序运行时与其交互。操作系统执行与多任务处理相关的以下活动：

Multitasking is when multiple jobs are executed by the CPU simultaneously by switching between them. Switches occur so frequently that the users may interact with each program while it is running. An OS does the following activities related to multitasking −

The user gives instructions to the operating system or to a program directly, and receives an immediate response.
The OS handles multitasking in the way that it can handle multiple operations/executes multiple programs at a time.
Multitasking Operating Systems are also known as Time-sharing systems.
These Operating Systems were developed to provide interactive use of a computer system at a reasonable cost.
A time-shared operating system uses the concept of CPU scheduling and multiprogramming to provide each user with a small portion of a time-shared CPU.
Each user has at least one separate program in memory.

A program that is loaded into memory and is executing is commonly referred to as a process.
When a process executes, it typically executes for only a very short time before it either finishes or needs to perform I/O.
Since interactive I/O typically runs at slower speeds, it may take a long time to complete. During this time, a CPU can be utilized by another process.
The operating system allows the users to share the computer simultaneously. Since each action or command in a time-shared system tends to be short, only a little CPU time is needed for each user.
As the system switches CPU rapidly from one user/program to the next, each user is given the impression that he/she has his/her own CPU, whereas actually one CPU is being shared among many users.

Multiprogramming

*多道程序设计*是指在两个及以上的程序同时驻留在内存中时共享处理器。多道程序设计假定有一个共享处理器。多道程序设计通过组织作业来提高 CPU 利用率，以便 CPU 始终有作业可执行。

Sharing the processor, when two or more programs reside in memory at the same time, is referred as * multiprogramming*. Multiprogramming assumes a single shared processor. Multiprogramming increases CPU utilization by organizing jobs so that the CPU always has one to execute.

下图显示了多道程序设计系统的内存布局。

The following figure shows the memory layout for a multiprogramming system.

操作系统会执行与多道程序设计相关的一些活动。

An OS does the following activities related to multiprogramming.

The operating system keeps several jobs in memory at a time.
This set of jobs is a subset of the jobs kept in the job pool.
The operating system picks and begins to execute one of the jobs in the memory.
Multiprogramming operating systems monitor the state of all active programs and system resources using memory management programs to ensures that the CPU is never idle, unless there are no jobs to process.

Advantages

High and efficient CPU utilization.
User feels that many programs are allotted CPU almost simultaneously.

Disadvantages

CPU scheduling is required.
To accommodate many jobs in memory, memory management is required.

Interactivity

交互性是指用户与计算机系统交互的能力。操作系统会执行与交互性相关的一些活动：

Interactivity refers to the ability of users to interact with a computer system. An Operating system does the following activities related to interactivity −

Provides the user an interface to interact with the system.
Manages input devices to take inputs from the user. For example, keyboard.
Manages output devices to show outputs to the user. For example, Monitor.

操作系统的响应时间需要很短，因为用户会提交并等待结果。

The response time of the OS needs to be short, since the user submits and waits for the result.

Real Time System

实时系统通常是专用嵌入式系统。操作系统会执行与实时系统活动相关的一些活动。

Real-time systems are usually dedicated, embedded systems. An operating system does the following activities related to real-time system activity.

In such systems, Operating Systems typically read from and react to sensor data.
The Operating system must guarantee response to events within fixed periods of time to ensure correct performance.

Distributed Environment

分布式环境是指计算机系统中多个独立的 CPU 或处理器。操作系统对分布式环境执行以下活动：

A distributed environment refers to multiple independent CPUs or processors in a computer system. An operating system does the following activities related to distributed environment −

The OS distributes computation logics among several physical processors.
The processors do not share memory or a clock. Instead, each processor has its own local memory.
The OS manages the communications between the processors. They communicate with each other through various communication lines.

Spooling

Spooling 是在线同时外围操作的首字母缩写词。Spooling 指的是将各种 I/O 作业的数据放入缓冲区。此缓冲区是 I/O 设备可访问的内存或硬盘上的一个特殊区域。

Spooling is an acronym for simultaneous peripheral operations on line. Spooling refers to putting data of various I/O jobs in a buffer. This buffer is a special area in memory or hard disk which is accessible to I/O devices.

操作系统对分布式环境执行以下活动：

An operating system does the following activities related to distributed environment −

Handles I/O device data spooling as devices have different data access rates.
Maintains the spooling buffer which provides a waiting station where data can rest while the slower device catches up.
Maintains parallel computation because of spooling process as a computer can perform I/O in parallel fashion. It becomes possible to have the computer read data from a tape, write data to disk and to write out to a tape printer while it is doing its computing task.

Advantages

The spooling operation uses a disk as a very large buffer.
Spooling is capable of overlapping I/O operation for one job with processor operations for another job.

Operating System - Processes

Process

进程基本上是一个正在执行的程序。进程的执行必须按顺序进行。

A process is basically a program in execution. The execution of a process must progress in a sequential fashion.

简单地说，我们以文本文件形式编写计算机程序，当我们执行该程序时，它将变成一个进程，执行程序中提到的所有任务。

To put it in simple terms, we write our computer programs in a text file and when we execute this program, it becomes a process which performs all the tasks mentioned in the program.

当一个程序被加载到内存中并成为一个进程时，它可以被划分为四个部分 ─ 栈、堆、文本和数据。下图显示了主内存中一个进程的简化布局 −

When a program is loaded into the memory and it becomes a process, it can be divided into four sections ─ stack, heap, text and data. The following image shows a simplified layout of a process inside main memory −

S.N.	Component & Description
1	Stack The process Stack contains the temporary data such as method/function parameters, return address and local variables.
2	Heap This is dynamically allocated memory to a process during its run time.
3	Text This includes the current activity represented by the value of Program Counter and the contents of the processor’s registers.
4	Data This section contains the global and static variables.

Program

程序是一段代码，可以是一行或数百万行代码。计算机程序通常由计算机程序员使用编程语言编写。例如，下面是一个用 C 编程语言编写的简单程序 −

A program is a piece of code which may be a single line or millions of lines. A computer program is usually written by a computer programmer in a programming language. For example, here is a simple program written in C programming language −

#include <stdio.h>

int main() {
   printf("Hello, World! \n");
   return 0;
}

计算机程序是一组指令，执行时执行特定任务。如果将程序与进程进行比较，我们可以得出结论：进程是一个计算机程序的动态实例。

A computer program is a collection of instructions that performs a specific task when executed by a computer. When we compare a program with a process, we can conclude that a process is a dynamic instance of a computer program.

计算机程序中执行明确定义的任务的部分称为 algorithm 。计算机程序、库和相关数据的集合称为 software 。

A part of a computer program that performs a well-defined task is known as an algorithm. A collection of computer programs, libraries and related data are referred to as a software.

Process Life Cycle

在进程执行期间会经历不同的状态。这些状态在不同的操作系统中可能有所不同，且这些状态的名称也没有进行标准化。

When a process executes, it passes through different states. These stages may differ in different operating systems, and the names of these states are also not standardized.

一般来说，一个进程每次可以处于以下五个状态之一。

In general, a process can have one of the following five states at a time.

S.N.	State & Description
1	Start This is the initial state when a process is first started/created.
2	Ready The process is waiting to be assigned to a processor. Ready processes are waiting to have the processor allocated to them by the operating system so that they can run. Process may come into this state after Start state or while running it by but interrupted by the scheduler to assign CPU to some other process.
3	Running Once the process has been assigned to a processor by the OS scheduler, the process state is set to running and the processor executes its instructions.
4	Waiting Process moves into the waiting state if it needs to wait for a resource, such as waiting for user input, or waiting for a file to become available.
5	Terminated or Exit Once the process finishes its execution, or it is terminated by the operating system, it is moved to the terminated state where it waits to be removed from main memory.

Process Control Block (PCB)

进程控制块是由操作系统为每个进程维护的一个数据结构。进程控制块由整型进程 ID (PID) 标识。进程控制块保留所有所需的信息以跟踪一个进程，如下表所列 −

A Process Control Block is a data structure maintained by the Operating System for every process. The PCB is identified by an integer process ID (PID). A PCB keeps all the information needed to keep track of a process as listed below in the table −

S.N.	Information & Description
1	Process State The current state of the process i.e., whether it is ready, running, waiting, or whatever.
2	Process privileges This is required to allow/disallow access to system resources.
3	Process ID Unique identification for each of the process in the operating system.
4	Pointer A pointer to parent process.
5	Program Counter Program Counter is a pointer to the address of the next instruction to be executed for this process.
6	CPU registers Various CPU registers where process need to be stored for execution for running state.
7	CPU Scheduling Information Process priority and other scheduling information which is required to schedule the process.
8	Memory management information This includes the information of page table, memory limits, Segment table depending on memory used by the operating system.
9	Accounting information This includes the amount of CPU used for process execution, time limits, execution ID etc.
10	IO status information This includes a list of I/O devices allocated to the process.

PCB 的架构完全依赖于操作系统，并且在不同的操作系统中可能包含不同的信息。这是一个简化的 PCB 图示 −

The architecture of a PCB is completely dependent on Operating System and may contain different information in different operating systems. Here is a simplified diagram of a PCB −

PCB 在整个生命周期中都维护着一个进程，并在进程终止时删除。

The PCB is maintained for a process throughout its lifetime, and is deleted once the process terminates.

Operating System - Process Scheduling

Definition

进程调度是进程管理器的一种活动，负责从CPU中移除正在运行的进程，并根据特定策略选择另一个进程。

The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy.

进程调度是多道程序操作系统的必然部分。此类操作系统允许一次将多个进程加载到可执行内存中，并且已加载的进程使用时分复用共享CPU。

Process scheduling is an essential part of a Multiprogramming operating systems. Such operating systems allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing.

Process Scheduling Queues

操作系统在进程调度队列中维护所有 PCB。操作系统为每个进程状态维护一个单独的队列，并且相同执行状态的所有进程的 PCB 都放置在同一个队列中。当进程的状态更改时，其 PCB 从其当前队列中取消链接，并移动到其新的状态队列。

The OS maintains all PCBs in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue.

操作系统维护着以下重要的进程调度队列−

The Operating System maintains the following important process scheduling queues −

Job queue − This queue keeps all the processes in the system.
Ready queue − This queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue.
Device queues − The processes which are blocked due to unavailability of an I/O device constitute this queue.

操作系统可以使用不同的策略来管理每个队列（FIFO、循环优先级等）。操作系统调度程序确定如何在就绪队列和运行队列之间移动进程，这在系统上的每个处理器核上只能有一个条目；在上图中，它已与CPU合并。

The OS can use different policies to manage each queue (FIFO, Round Robin, Priority, etc.). The OS scheduler determines how to move processes between the ready and run queues which can only have one entry per processor core on the system; in the above diagram, it has been merged with the CPU.

Two-State Process Model

两态进程模型是指下面描述的运行态和非运行态：

Two-state process model refers to running and non-running states which are described below −

S.N.

State & Description

Running When a new process is created, it enters into the system as in the running state.

Not Running Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute.

Schedulers

调度程序是特殊系统软件，以各种方式处理进程调度。它们的主要任务是选择要提交给系统的作业并决定运行哪个进程。调度程序有三种类型：

Schedulers are special system software which handle process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of three types −

Long-Term Scheduler
Short-Term Scheduler
Medium-Term Scheduler

Long Term Scheduler

它也被称为 job scheduler 。长期调度程序确定哪些程序被允许进入系统进行处理。它从队列中选择进程并将它们加载到内存中以执行。进程加载到内存中以进行 CPU 调度。

It is also called a job scheduler. A long-term scheduler determines which programs are admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling.

作业调度程序的主要目标是提供平衡的作业组合，如 I/O 绑定和处理器绑定。它还控制多道程序设计的程度。如果多道程序设计的程度稳定，那么进程创建的平均速率必须等于离开系统的进程的平均离开率。

The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.

在某些系统上，长期的调度程序可能不可用或是最小的。分时操作系统没有长期调度程序。当进程将状态从新建更改为就绪时，则使用长期调度程序。

On some systems, the long-term scheduler may not be available or minimal. Time-sharing operating systems have no long term scheduler. When a process changes the state from new to ready, then there is use of long-term scheduler.

Short Term Scheduler

它也被称为 CPU scheduler 。其主要目的是根据所选的一组标准来提高系统性能。它是进程从就绪态变为运行态的变化。CPU 调度程序从准备执行的进程中选择一个进程并将 CPU 分配给其中之一。

It is also called as CPU scheduler. Its main objective is to increase system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects a process among the processes that are ready to execute and allocates CPU to one of them.

短期调度程序（也称为分派程序）决定接下来执行哪个进程。短期调度程序比长期调度程序更快。

Short-term schedulers, also known as dispatchers, make the decision of which process to execute next. Short-term schedulers are faster than long-term schedulers.

Medium Term Scheduler

中期调度是 swapping 的一部分。它从内存中删除进程。它降低了多道程序设计的程度。中期调度程序负责处理换出进程。

Medium-term scheduling is a part of swapping. It removes the processes from the memory. It reduces the degree of multiprogramming. The medium-term scheduler is in-charge of handling the swapped out-processes.

如果一个正在运行的进程发出 I/O 请求，则该进程可能会被挂起。被挂起的进程无法继续执行。在这种情况下，为了从内存中删除进程并为其他进程腾出空间，将被挂起的进程移到辅助存储器中。此过程称为 swapping ，并且该进程据说是被换出或注销的。交换可能需要改进进程组合。

A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix.

Comparison among Scheduler

S.N.

Long-Term Scheduler

Short-Term Scheduler

Medium-Term Scheduler

It is a job scheduler

It is a CPU scheduler

It is a process swapping scheduler.

Speed is lesser than short term scheduler

Speed is fastest among other two

Speed is in between both short and long term scheduler.

It controls the degree of multiprogramming

It provides lesser control over degree of multiprogramming

It reduces the degree of multiprogramming.

It is almost absent or minimal in time sharing system

It is also minimal in time sharing system

It is a part of Time sharing systems.

It selects processes from pool and loads them into memory for execution

It selects those processes which are ready to execute

It can re-introduce the process into memory and execution can be continued.

Context Switch

上下文切换是存储和恢复进程控制块中 CPU 的状态或上下文的一种机制，以便以后从同一位置恢复进程执行。使用此技术，上下文切换程序允许多个进程共享单个 CPU。上下文切换是多任务操作系统功能的本质部分。

A context switch is the mechanism to store and restore the state or context of a CPU in Process Control block so that a process execution can be resumed from the same point at a later time. Using this technique, a context switcher enables multiple processes to share a single CPU. Context switching is an essential part of a multitasking operating system features.

当调度程序将 CPU 从执行一个进程切换到执行另一个进程时，从当前正在运行的进程中的状态将被存储到进程控制块中。此后，要执行的下一次进程的状态将从其自身的 PCB 中加载并用于设置 PC、寄存器等。在这一点上，第二个进程可以开始执行。

When the scheduler switches the CPU from executing one process to execute another, the state from the current running process is stored into the process control block. After this, the state for the process to run next is loaded from its own PCB and used to set the PC, registers, etc. At that point, the second process can start executing.

上下文切换在计算上是密集的，因为必须保存和还原寄存器和内存状态。为了避免上下文切换时间，一些硬件系统采用两组或更多组处理器寄存器。当进程切换时，以下信息将被存储以供以后使用。

Context switches are computationally intensive since register and memory state must be saved and restored. To avoid the amount of context switching time, some hardware systems employ two or more sets of processor registers. When the process is switched, the following information is stored for later use.

Program Counter
Scheduling information
Base and limit register value
Currently used register
Changed State
I/O State information
Accounting information

Operating System Scheduling algorithms

进程调度程序根据特定调度算法将不同的进程调度到 CPU。本章将讨论六种流行的进程调度算法 −

A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. There are six popular process scheduling algorithms which we are going to discuss in this chapter −

First-Come, First-Served (FCFS) Scheduling
Shortest-Job-Next (SJN) Scheduling
Priority Scheduling
Shortest Remaining Time
Round Robin(RR) Scheduling
Multiple-Level Queues Scheduling

这些算法要么是 non-preemptive or preemptive 。非抢占式算法设计为，一旦进程进入运行状态，它就无法在完成规定时间之前被抢占，而抢占式调度基于优先级，其中调度程序可以在高优先级进程进入就绪状态的任何时候抢占低优先级正在运行的进程。

These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state.

First Come First Serve (FCFS)

Jobs are executed on first come, first serve basis.
It is a non-preemptive, pre-emptive scheduling algorithm.
Easy to understand and implement.
Its implementation is based on FIFO queue.
Poor in performance as average wait time is high.

每个进程的 Wait time 如下 −

Wait time of each process is as follows −

Process

Wait Time : Service Time - Arrival Time

0 - 0 = 0

5 - 1 = 4

8 - 2 = 6

16 - 3 = 13

平均等待时间：(0+4+6+13) / 4 = 5.75

Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

This is also known as shortest job first, or SJF
This is a non-preemptive, pre-emptive scheduling algorithm.
Best approach to minimize waiting time.
Easy to implement in Batch systems where required CPU time is known in advance.
Impossible to implement in interactive systems where required CPU time is not known.
The processer should know in advance how much time process will take.

给定：进程表及其到达时间、执行时间

Given: Table of processes, and their Arrival time, Execution time

Process	Arrival Time	Execution Time	Service Time
P0	0	5	0
P1	1	3	5
P2	2	8	14
P3	3	6	8

每个进程的 Waiting time 如下：-

Waiting time of each process is as follows −

Process

Waiting Time

0 - 0 = 0

5 - 1 = 4

14 - 2 = 12

8 - 3 = 5

平均等待时间：(0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems.
Each process is assigned a priority. Process with highest priority is to be executed first and so on.
Processes with same priority are executed on first come first served basis.
Priority can be decided based on memory requirements, time requirements or any other resource requirement.

给定：进程表及其到达时间、执行时间和优先级。在这里，我们认为 1 是最低优先级。

Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are considering 1 is the lowest priority.

Process	Arrival Time	Execution Time	Priority	Service Time
P0	0	5	1	0
P1	1	3	2	11
P2	2	8	1	14
P3	3	6	3	5

每个进程的 Waiting time 如下：-

Waiting time of each process is as follows −

Process

Waiting Time

0 - 0 = 0

11 - 1 = 10

14 - 2 = 12

5 - 3 = 2

平均等待时间：(0 + 10 + 12 + 2)/4 = 24/4 = 6

Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion.
Impossible to implement in interactive systems where required CPU time is not known.
It is often used in batch environments where short jobs need to give preference.

Round Robin Scheduling

Round Robin is the preemptive process scheduling algorithm.
Each process is provided a fix time to execute, it is called a quantum.
Once a process is executed for a given time period, it is preempted and other process executes for a given time period.
Context switching is used to save states of preempted processes.

每个进程的 Wait time 如下 −

Wait time of each process is as follows −

Process

Wait Time : Service Time - Arrival Time

(0 - 0) + (12 - 3) = 9

(3 - 1) = 2

(6 - 2) + (14 - 9) + (20 - 17) = 12

(9 - 3) + (17 - 12) = 11

平均等待时间：(9 + 2 + 12 + 11)/4 = 8.5

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multiple-Level Queues Scheduling

多级队列并不是一个独立的调度算法。它们利用其他现有算法对具有共同特征的任务进行分组和调度。

Multiple-level queues are not an independent scheduling algorithm. They make use of other existing algorithms to group and schedule jobs with common characteristics.

Multiple queues are maintained for processes with common characteristics.
Each queue can have its own scheduling algorithms.
Priorities are assigned to each queue.

例如，CPU 绑定任务可以在一个队列中调度，所有 I/O 绑定任务在另一个队列中调度。然后进程调度器交替从每个队列中选择任务，并根据分配给该队列的算法将它们分配给 CPU。

For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another queue. The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU based on the algorithm assigned to the queue.

Operating System - Multi-Threading

What is Thread?

一个线程是一个通过进程代码执行的流，它有自己的程序计数器，用来跟踪下一个要执行的指令，有用来保存当前工作变量的系统寄存器以及包含执行历史的堆栈。

A thread is a flow of execution through the process code, with its own program counter that keeps track of which instruction to execute next, system registers which hold its current working variables, and a stack which contains the execution history.

一个线程与它的对等线程共享一些信息，例如代码段、数据段和打开的文件。当一个线程更改某代码段内存项时，其他所有线程都会看到。

A thread shares with its peer threads few information like code segment, data segment and open files. When one thread alters a code segment memory item, all other threads see that.

一个线程也称为 lightweight process 。线程提供了一种通过并行性来提高应用程序性能的方法。线程代表了一种通过降低开销来提高操作系统性能的软件方法，线程相当于一个传统进程。

A thread is also called a lightweight process. Threads provide a way to improve application performance through parallelism. Threads represent a software approach to improving performance of operating system by reducing the overhead thread is equivalent to a classical process.

每一个线程都精确地属于一个进程，且没有一个线程能够存在于进程之外。每一个线程代表一个独立的控制流。线程已经在网络服务器和 Web 服务器的实现中得到了成功的应用。它们还为共享内存多处理机上应用程序的并行执行提供了一个合适的基石。下图显示了单线程和多线程进程的工作方式。

Each thread belongs to exactly one process and no thread can exist outside a process. Each thread represents a separate flow of control. Threads have been successfully used in implementing network servers and web server. They also provide a suitable foundation for parallel execution of applications on shared memory multiprocessors. The following figure shows the working of a single-threaded and a multithreaded process.

Difference between Process and Thread

S.N.

Process

Thread

Process is heavy weight or resource intensive.

Thread is light weight, taking lesser resources than a process.

Process switching needs interaction with operating system.

Thread switching does not need to interact with operating system.

In multiple processing environments, each process executes the same code but has its own memory and file resources.

All threads can share same set of open files, child processes.

If one process is blocked, then no other process can execute until the first process is unblocked.

While one thread is blocked and waiting, a second thread in the same task can run.

Multiple processes without using threads use more resources.

Multiple threaded processes use fewer resources.

In multiple processes each process operates independently of the others.

One thread can read, write or change another thread’s data.

Advantages of Thread

Threads minimize the context switching time.
Use of threads provides concurrency within a process.
Efficient communication.
It is more economical to create and context switch threads.
Threads allow utilization of multiprocessor architectures to a greater scale and efficiency.

Types of Thread

线程通过以下两种方式实现：

Threads are implemented in following two ways −

User Level Threads − User managed threads.
Kernel Level Threads − Operating System managed threads acting on kernel, an operating system core.

User Level Threads

在这种情况下，线程管理内核不知道线程的存在。线程库包含用于创建和销毁线程、在线程之间传递消息和数据、调度线程执行以及保存和还原线程上下文的代码。该应用程序从单个线程开始。

In this case, the thread management kernel is not aware of the existence of threads. The thread library contains code for creating and destroying threads, for passing message and data between threads, for scheduling thread execution and for saving and restoring thread contexts. The application starts with a single thread.

Advantages

Thread switching does not require Kernel mode privileges.
User level thread can run on any operating system.
Scheduling can be application specific in the user level thread.
User level threads are fast to create and manage.

Disadvantages

In a typical operating system, most system calls are blocking.
Multithreaded application cannot take advantage of multiprocessing.

Kernel Level Threads

在这种情况下，线程管理是由内核完成的。应用程序区域中没有线程管理代码。内核线程直接受操作系统支持。任何应用程序都能被编程为多线程的。应用程序中的所有线程都在一个单一进程中受到支持。

In this case, thread management is done by the Kernel. There is no thread management code in the application area. Kernel threads are supported directly by the operating system. Any application can be programmed to be multithreaded. All of the threads within an application are supported within a single process.

内核对进程整体和进程中的各个线程维护上下文信息。内核根据线程进行调度。内核在内核空间中执行线程创建、调度和管理。与用户线程相比，内核线程通常创建和管理的速度较慢。

The Kernel maintains context information for the process as a whole and for individuals threads within the process. Scheduling by the Kernel is done on a thread basis. The Kernel performs thread creation, scheduling and management in Kernel space. Kernel threads are generally slower to create and manage than the user threads.

Advantages

Kernel can simultaneously schedule multiple threads from the same process on multiple processes.
If one thread in a process is blocked, the Kernel can schedule another thread of the same process.
Kernel routines themselves can be multithreaded.

Disadvantages

Kernel threads are generally slower to create and manage than the user threads.
Transfer of control from one thread to another within the same process requires a mode switch to the Kernel.

Multithreading Models

一些操作系统提供了一种组合的用户级线程和内核级线程工具。Solaris 就是这种方法的一个很好的示例。在组合系统中，同一个应用程序中的多个线程可以在多处理器上并行运行，并且一个阻塞系统调用不必阻塞整个进程。多线程模式有三种类型：

Some operating system provide a combined user level thread and Kernel level thread facility. Solaris is a good example of this combined approach. In a combined system, multiple threads within the same application can run in parallel on multiple processors and a blocking system call need not block the entire process. Multithreading models are three types

Many to many relationship.
Many to one relationship.
One to one relationship.

Many to Many Model

多对多模型将任意数量的用户线程复用到相等或更少数量的内核线程上。

The many-to-many model multiplexes any number of user threads onto an equal or smaller number of kernel threads.

下图显示了多对多线程模型，其中 6 个用户级线程与 6 个内核级线程进行复用。在这个模型中，开发者可以创建任意数量必要的用户线程，而对应的内核线程可以在多处理器机器上并行运行。此模型可以最准确地反映并发性，当一个线程执行阻塞系统调用时，内核可以调度另一个线程执行。

The following diagram shows the many-to-many threading model where 6 user level threads are multiplexing with 6 kernel level threads. In this model, developers can create as many user threads as necessary and the corresponding Kernel threads can run in parallel on a multiprocessor machine. This model provides the best accuracy on concurrency and when a thread performs a blocking system call, the kernel can schedule another thread for execution.

Many to One Model

多对一模型将许多用户级线程映射到一个内核级线程上。线程管理在用户空间中通过线程库完成。当线程执行一个阻塞系统调用时，整个进程将被阻塞。一次只能有一个线程访问内核，因此多线程无法在多处理器上并行运行。

Many-to-one model maps many user level threads to one Kernel-level thread. Thread management is done in user space by the thread library. When thread makes a blocking system call, the entire process will be blocked. Only one thread can access the Kernel at a time, so multiple threads are unable to run in parallel on multiprocessors.

如果以系统不支持的方式在操作系统中实现用户级线程库，那么内核线程将使用多对一关系模式。

If the user-level thread libraries are implemented in the operating system in such a way that the system does not support them, then the Kernel threads use the many-to-one relationship modes.

One to One Model

用户级线程和内核级线程之间是一对一关系。此模型比多对一模型提供了更高的并发性。它也允许在某个线程执行阻塞系统调用时运行另一个线程。它支持多线程在微处理器上并行执行。

There is one-to-one relationship of user-level thread to the kernel-level thread. This model provides more concurrency than the many-to-one model. It also allows another thread to run when a thread makes a blocking system call. It supports multiple threads to execute in parallel on microprocessors.

这个模型的劣势是创建用户线程需要相应的内核线程。OS/2、Windows NT 和 Windows 2000 使用一对一关系模型。

Disadvantage of this model is that creating user thread requires the corresponding Kernel thread. OS/2, windows NT and windows 2000 use one to one relationship model.

Difference between User-Level & Kernel-Level Thread

S.N.

User-Level Threads

Kernel-Level Thread

User-level threads are faster to create and manage.

Kernel-level threads are slower to create and manage.

Implementation is by a thread library at the user level.

Operating system supports creation of Kernel threads.

User-level thread is generic and can run on any operating system.

Kernel-level thread is specific to the operating system.

Multi-threaded applications cannot take advantage of multiprocessing.

Kernel routines themselves can be multithreaded.

Operating System - Memory Management

内存管理是指操作系统的功能，它会处理或管理主内存，并在执行期间在主内存和磁盘之间来回移动进程。内存管理会跟踪每个内存位置，无论它是否已分配给某个进程或它是空闲的。它检查为进程分配多少内存。它决定在什么时间将内存分配给哪个进程。它会跟踪何时释放或取消分配某个内存并相应地更新状态。

Memory management is the functionality of an operating system which handles or manages primary memory and moves processes back and forth between main memory and disk during execution. Memory management keeps track of each and every memory location, regardless of either it is allocated to some process or it is free. It checks how much memory is to be allocated to processes. It decides which process will get memory at what time. It tracks whenever some memory gets freed or unallocated and correspondingly it updates the status.

本教程将向您讲解内存管理相关基础概念。

This tutorial will teach you basic concepts related to Memory Management.

Process Address Space

进程地址空间是由进程在其代码中引用的逻辑地址集。例如，当使用 32 位寻址时，地址范围可以从 0 到 0x7fffffff；换句话说，可能共有 2^31 个编号，理论大小总计为 2GB。

The process address space is the set of logical addresses that a process references in its code. For example, when 32-bit addressing is in use, addresses can range from 0 to 0x7fffffff; that is, 2^31 possible numbers, for a total theoretical size of 2 gigabytes.

操作系统负责在将内存分配给程序时将逻辑地址映射到物理地址。在分配内存之前和之后，程序中会使用三种类型的地址 −

The operating system takes care of mapping the logical addresses to physical addresses at the time of memory allocation to the program. There are three types of addresses used in a program before and after memory is allocated −

S.N.

Memory Addresses & Description

Symbolic addresses The addresses used in a source code. The variable names, constants, and instruction labels are the basic elements of the symbolic address space.

Relative addresses At the time of compilation, a compiler converts symbolic addresses into relative addresses.

Physical addresses The loader generates these addresses at the time when a program is loaded into main memory.

在编译时和加载时地址绑定方案中，虚拟地址和物理地址相同。在执行时地址绑定方案中，虚拟地址和物理地址不同。

Virtual and physical addresses are the same in compile-time and load-time address-binding schemes. Virtual and physical addresses differ in execution-time address-binding scheme.

程序所生成的所有逻辑地址的集合被称为 logical address space 。相应于这些逻辑地址的所有物理地址的集合被称为 physical address space. 。

The set of all logical addresses generated by a program is referred to as a logical address space. The set of all physical addresses corresponding to these logical addresses is referred to as a physical address space.

虚拟地址到物理地址的运行时映射是由内存管理单元 (MMU) 完成的，这是一个硬件设备。MMU 使用以下机制将虚拟地址转换为物理地址。

The runtime mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device. MMU uses following mechanism to convert virtual address to physical address.

The value in the base register is added to every address generated by a user process, which is treated as offset at the time it is sent to memory. For example, if the base register value is 10000, then an attempt by the user to use address location 100 will be dynamically reallocated to location 10100.
The user program deals with virtual addresses; it never sees the real physical addresses.

Static vs Dynamic Loading

在开发计算机程序时必须在静态或动态加载之间进行选择。如果您必须静态加载程序，那么在编译时将编译并链接完整程序，而不会留下任何外部程序或模块依赖项。链接程序将目标程序与其他必需目标模块合并为绝对程序，其中也包括逻辑地址。

The choice between Static or Dynamic Loading is to be made at the time of computer program being developed. If you have to load your program statically, then at the time of compilation, the complete programs will be compiled and linked without leaving any external program or module dependency. The linker combines the object program with other necessary object modules into an absolute program, which also includes logical addresses.

如果您正在编写一个动态加载程序，那么您的编译器将编译程序，并且对于您想要动态包含的所有模块，只会提供引用，其余工作将在执行时完成。

If you are writing a Dynamically loaded program, then your compiler will compile the program and for all the modules which you want to include dynamically, only references will be provided and rest of the work will be done at the time of execution.

在加载时，使用 static loading ，绝对程序（和数据）将加载到内存中以便执行开始。

At the time of loading, with static loading, the absolute program (and data) is loaded into memory in order for execution to start.

如果您使用 dynamic loading ，库的动态例程将以可重定位方式存储在磁盘上，并且仅当程序需要时才加载到内存中。

If you are using dynamic loading, dynamic routines of the library are stored on a disk in relocatable form and are loaded into memory only when they are needed by the program.

Static vs Dynamic Linking

如上所述，当使用静态链接时，链接器将程序所需的所有其他模块组合成一个可执行程序，以避免任何运行时依赖。

As explained above, when static linking is used, the linker combines all other modules needed by a program into a single executable program to avoid any runtime dependency.

当使用动态链接时，不需要将实际的模块或库与程序链接，而是在编译和链接时提供对动态模块的引用。Windows 中的动态链接库 (DLL) 和 Unix 中的共享对象是动态库的良好示例。

When dynamic linking is used, it is not required to link the actual module or library with the program, rather a reference to the dynamic module is provided at the time of compilation and linking. Dynamic Link Libraries (DLL) in Windows and Shared Objects in Unix are good examples of dynamic libraries.

Swapping

交换是一种机制，其中进程可以暂时从主内存（或移动）交换到辅助存储（磁盘），并使该内存可供其他进程使用。在稍后的某个时间，系统将从辅助存储器将进程换回主内存。

Swapping is a mechanism in which a process can be swapped temporarily out of main memory (or move) to secondary storage (disk) and make that memory available to other processes. At some later time, the system swaps back the process from the secondary storage to main memory.

尽管性能通常会受到交换进程的影响，但它有助于并行运行多个大型进程，这就是 Swapping is also known as a technique for memory compaction 的原因。

Though performance is usually affected by swapping process but it helps in running multiple and big processes in parallel and that’s the reason Swapping is also known as a technique for memory compaction.

交换进程所花费的总时间包括将整个进程移动到辅助磁盘以及再将进程复制回内存所需的时间，以及进程重新获取主内存所需的时间。

The total time taken by swapping process includes the time it takes to move the entire process to a secondary disk and then to copy the process back to memory, as well as the time the process takes to regain main memory.

让我们假设用户进程的大小为 2048KB，并且在交换将发生在其上的标准硬盘上，数据传输速率约为每秒 1 MB。从或到内存传输 1000K 进程的实际传输将花费

Let us assume that the user process is of size 2048KB and on a standard hard disk where swapping will take place has a data transfer rate around 1 MB per second. The actual transfer of the 1000K process to or from memory will take

2048KB / 1024KB per second
= 2 seconds
= 2000 milliseconds

现在考虑到输入和输出时间，它将花费完整的 4000 毫秒加上其他开销，其中进程竞争以重新获取主内存。

Now considering in and out time, it will take complete 4000 milliseconds plus other overhead where the process competes to regain main memory.

Memory Allocation

主内存通常有两个分区：

Main memory usually has two partitions −

Low Memory − Operating system resides in this memory.
High Memory − User processes are held in high memory.

操作系统使用以下内存分配机制。

Operating system uses the following memory allocation mechanism.

S.N.

Memory Allocation & Description

Single-partition allocation In this type of allocation, relocation-register scheme is used to protect user processes from each other, and from changing operating-system code and data. Relocation register contains value of smallest physical address whereas limit register contains range of logical addresses. Each logical address must be less than the limit register.

Multiple-partition allocation In this type of allocation, main memory is divided into a number of fixed-sized partitions where each partition should contain only one process. When a partition is free, a process is selected from the input queue and is loaded into the free partition. When the process terminates, the partition becomes available for another process.

Fragmentation

当进程从内存中加载并删除时，空闲内存空间会被分成小块。有时会发生这种情况：进程无法分配给内存块，因为它们的尺寸小，而且内存块仍然未使用。此问题称为碎片。

As processes are loaded and removed from memory, the free memory space is broken into little pieces. It happens after sometimes that processes cannot be allocated to memory blocks considering their small size and memory blocks remains unused. This problem is known as Fragmentation.

碎片有两种类型：

Fragmentation is of two types −

S.N.

Fragmentation & Description

External fragmentation Total memory space is enough to satisfy a request or to reside a process in it, but it is not contiguous, so it cannot be used.

Internal fragmentation Memory block assigned to process is bigger. Some portion of memory is left unused, as it cannot be used by another process.

下图显示了碎片如何导致内存浪费，以及如何使用压缩技术从碎片内存中创建更多可用内存−

The following diagram shows how fragmentation can cause waste of memory and a compaction technique can be used to create more free memory out of fragmented memory −

可以通过压缩或混洗内存内容来减少外部碎片，从而将所有可用内存集中在一个大块中。为了使压缩可行，重定位应该是动态的。

External fragmentation can be reduced by compaction or shuffle memory contents to place all free memory together in one large block. To make compaction feasible, relocation should be dynamic.

可以通过有效分配最小的分区（但足以满足进程需要）来减少内部碎片。

The internal fragmentation can be reduced by effectively assigning the smallest partition but large enough for the process.

Paging

计算机可以寻址超过系统上实际安装的内存量。此额外内存实际上称为虚拟内存，它是将硬盘的一部分设置为模拟计算机 RAM。分页技术在实现虚拟内存中扮演着重要角色。

A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard that’s set up to emulate the computer’s RAM. Paging technique plays an important role in implementing virtual memory.

分页是一种内存管理技术，其中进程地址空间被分成称为 pages 大小相同的块（大小是 2 的幂，介于 512 字节和 8192 字节之间）。进程的大小以页数来衡量。

Paging is a memory management technique in which process address space is broken into blocks of the same size called pages (size is power of 2, between 512 bytes and 8192 bytes). The size of the process is measured in the number of pages.

类似地，主内存被分成称为 frames 的小型固定大小块（物理）内存，并且帧的大小与页的大小保持相同，以便最大程度地利用主内存并避免外部碎片。

Similarly, main memory is divided into small fixed-sized blocks of (physical) memory called frames and the size of a frame is kept the same as that of a page to have optimum utilization of the main memory and to avoid external fragmentation.

Address Translation

页地址称为 logical address ，由 page number 和 offset 表示。

Page address is called logical address and represented by page number and the offset.

Logical Address = Page number + page offset

帧地址称为 physical address ，由 frame number 和 offset 表示。

Frame address is called physical address and represented by a frame number and the offset.

Physical Address = Frame number + page offset

名为 page map table 的数据结构用于跟踪进程页与物理内存中帧之间的关系。

A data structure called page map table is used to keep track of the relation between a page of a process to a frame in physical memory.

当系统将帧分配给任何页面时，它会将此逻辑地址转换为物理地址，并在页表中创建条目，以便在整个程序执行期间使用。

When the system allocates a frame to any page, it translates this logical address into a physical address and create entry into the page table to be used throughout execution of the program.

当进程要执行时，其对应的页面将加载到任何可用的内存帧中。假设您有一个 8Kb 的程序，但您的内存只能在给定时间容纳 5Kb，那么分页概念就会出现。当计算机的 RAM 用完时，操作系统 (OS) 会将空闲或不需要的内存页移动到辅助内存，以释放其他进程的 RAM 并根据程序需要将其取回。

When a process is to be executed, its corresponding pages are loaded into any available memory frames. Suppose you have a program of 8Kb but your memory can accommodate only 5Kb at a given point in time, then the paging concept will come into picture. When a computer runs out of RAM, the operating system (OS) will move idle or unwanted pages of memory to secondary memory to free up RAM for other processes and brings them back when needed by the program.

这个过程在程序的整个执行过程中继续进行，操作系统会不断从主内存中删除空闲页面并将它们写入辅助内存，并在程序需要时将它们取回。

This process continues during the whole execution of the program where the OS keeps removing idle pages from the main memory and write them onto the secondary memory and bring them back when required by the program.

Advantages and Disadvantages of Paging

以下是分页的优点和缺点列表−

Here is a list of advantages and disadvantages of paging −

Paging reduces external fragmentation, but still suffer from internal fragmentation.
Paging is simple to implement and assumed as an efficient memory management technique.
Due to equal size of the pages and frames, swapping becomes very easy.
Page table requires extra memory space, so may not be good for a system having small RAM.

Segmentation

分段是一种内存管理技术，其中每个作业被分成多个不同大小的段，每个段对应一个模块，其中包含执行相关功能的部分。每个段实际上是程序的不同逻辑地址空间。

Segmentation is a memory management technique in which each job is divided into several segments of different sizes, one for each module that contains pieces that perform related functions. Each segment is actually a different logical address space of the program.

当一个进程要被执行时，对于任一代码段，尽管每个代码段被加载到一个可用的连续内存块中，其对应的分段会被加载到不连续的内存中。

When a process is to be executed, its corresponding segmentation are loaded into non-contiguous memory though every segment is loaded into a contiguous block of available memory.

分段内存管理的工作方式与分页非常相似，但是这里的代码段长度可变，而在分页中页面的大小是固定的。

Segmentation memory management works very similar to paging but here segments are of variable-length where as in paging pages are of fixed size.

一个程序代码段包含程序的主函数、实用函数、数据结构等。操作系统对每一个进程维护一个 segment map table 和一个空闲内存块列表以及代码段号、它们的大小和主内存中对应的内存位置。对于每一个代码段，该表储存代码段的起始地址和代码段的长度。对一个内存位置的引用包括一个标识代码段的值和一个偏移量。

A program segment contains the program’s main function, utility functions, data structures, and so on. The operating system maintains a segment map table for every process and a list of free memory blocks along with segment numbers, their size and corresponding memory locations in main memory. For each segment, the table stores the starting address of the segment and the length of the segment. A reference to a memory location includes a value that identifies a segment and an offset.

Operating System - Virtual Memory

计算机可以寻址比系统物理安装量更多的内存。此额外内存实际上称为 virtual memory ，它是设置用于模拟计算机 RAM 的硬盘一部分。

A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that’s set up to emulate the computer’s RAM.

此方案的主要明显优点在于程序可以比物理内存更大。虚拟内存有两个用途。首先，它允许我们通过使用磁盘来扩展物理内存的使用。其次，它允许我们具有内存保护，因为每个虚拟地址都转换为一个物理地址。

The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using disk. Second, it allows us to have memory protection, because each virtual address is translated to a physical address.

以下情况不需要将整个程序完全加载到主内存中。

Following are the situations, when entire program is not required to be loaded fully in main memory.

User written error handling routines are used only when an error occurred in the data or computation.
Certain options and features of a program may be used rarely.
Many tables are assigned a fixed amount of address space even though only a small amount of the table is actually used.
The ability to execute a program that is only partially in memory would counter many benefits.
Less number of I/O would be needed to load or swap each user program into memory.
A program would no longer be constrained by the amount of physical memory that is available.
Each user program could take less physical memory, more programs could be run the same time, with a corresponding increase in CPU utilization and throughput.

面向通用用途的现代微处理器，内存管理单元或 MMU 已内置到硬件中。MMU 的工作是将虚拟地址转换为物理地址。以下是一个基本示例：

Modern microprocessors intended for general-purpose use, a memory management unit, or MMU, is built into the hardware. The MMU’s job is to translate virtual addresses into physical addresses. A basic example is given below −

虚拟内存通常通过按需分页实现。它也可以在分段系统中实现。按需分段也可以用于提供虚拟内存。

Virtual memory is commonly implemented by demand paging. It can also be implemented in a segmentation system. Demand segmentation can also be used to provide virtual memory.

Demand Paging

按需分页系统与交换分页系统非常相似，其中进程驻留在辅助内存中，并且仅在需要时加载页面，而不是预先加载。当发生上下文切换时，操作系统不会将任何旧程序的页面复制到磁盘或将任何新程序的页面复制到主内存。相反，它只在加载第一页后开始执行新程序，并在引用时获取该程序的页面。

A demand paging system is quite similar to a paging system with swapping where processes reside in secondary memory and pages are loaded only on demand, not in advance. When a context switch occurs, the operating system does not copy any of the old program’s pages out to the disk or any of the new program’s pages into the main memory Instead, it just begins executing the new program after loading the first page and fetches that program’s pages as they are referenced.

在执行程序时，如果程序引用了由于不久前交换出去而不在主内存中的页面，则处理器将这种无效内存引用视为 page fault ，并将控制权从程序转移到操作系统以要求将页面调回到内存。

While executing a program, if the program references a page which is not available in the main memory because it was swapped out a little ago, the processor treats this invalid memory reference as a page fault and transfers control from the program to the operating system to demand the page back into the memory.

Advantages

以下是按需分页的优点：

Following are the advantages of Demand Paging −

Large virtual memory.
More efficient use of memory.
There is no limit on degree of multiprogramming.

Disadvantages

Number of tables and the amount of processor overhead for handling page interrupts are greater than in the case of the simple paged management techniques.

Page Replacement Algorithm

页面替换算法是操作系统用来决定将哪些内存页面换出、在需要分配内存页时写入磁盘的技术。分页发生在页面错误发生且不能将空闲页面用于分配目的时，原因是页面不可用或空闲页面的数量低于所需页面。

Page replacement algorithms are the techniques using which an Operating System decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages.

当选择了要替换并换出的页面后，如果再次引用该页面，则必须从磁盘中读入，这需要 I/O 完成。此过程决定了页面替换算法的质量：等待页面输入所需的时间越少，算法就越好。

When the page that was selected for replacement and was paged out, is referenced again, it has to read in from disk, and this requires for I/O completion. This process determines the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.

页面替换算法会查看硬件提供的有关访问页面的有限信息，并尝试选择应替换的页面以最小化页面缺失总数，同时平衡算法本身的存储器和处理器时间成本。存在许多不同的页面替换算法。我们通过在特定的内存引用字符串上运行算法并计算页面错误数来评估算法。

A page replacement algorithm looks at the limited information about accessing the pages provided by hardware, and tries to select which pages should be replaced to minimize the total number of page misses, while balancing it with the costs of primary storage and processor time of the algorithm itself. There are many different page replacement algorithms. We evaluate an algorithm by running it on a particular string of memory reference and computing the number of page faults,

Reference String

内存引用字符串称为引用字符串。引用字符串是人工生成的，或通过跟踪给定系统并记录每个内存引用的地址而生成的。后一种选择会产生大量的数据，我们注意到两件事。

The string of memory references is called reference string. Reference strings are generated artificially or by tracing a given system and recording the address of each memory reference. The latter choice produces a large number of data, where we note two things.

For a given page size, we need to consider only the page number, not the entire address.
If we have a reference to a page p, then any immediately following references to page p will never cause a page fault. Page p will be in memory after the first reference; the immediately following references will not fault.
For example, consider the following sequence of addresses − 123,215,600,1234,76,96
If page size is 100, then the reference string is 1,2,6,12,0,0

First In First Out (FIFO) algorithm

Oldest page in main memory is the one which will be selected for replacement.
Easy to implement, keep a list, replace pages from the tail and add new pages at the head.

Optimal Page algorithm

An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An optimal page-replacement algorithm exists, and has been called OPT or MIN.
Replace the page that will not be used for the longest period of time. Use the time when a page is to be used.

Least Recently Used (LRU) algorithm

Page which has not been used for the longest time in main memory is the one which will be selected for replacement.
Easy to implement, keep a list, replace pages by looking back into time.

Page Buffering algorithm

To get a process start quickly, keep a pool of free frames.
On page fault, select a page to be replaced.
Write the new page in the frame of free pool, mark the page table and restart the process.
Now write the dirty page out of disk and place the frame holding replaced page in free pool.

Least frequently Used(LFU) algorithm

The page with the smallest count is the one which will be selected for replacement.
This algorithm suffers from the situation in which a page is used heavily during the initial phase of a process, but then is never used again.

Most frequently Used(MFU) algorithm

This algorithm is based on the argument that the page with the smallest count was probably just brought in and has yet to be used.

Operating System - I/O Hardware

操作系统的一项重要任务是管理各种 I/O 设备，包括鼠标、键盘、触摸板、磁盘驱动器、显示适配器、USB 设备、位图屏幕、LED、模数转换器、开/关开关、网络连接、音频 I/O、打印机等。

One of the important jobs of an Operating System is to manage various I/O devices including mouse, keyboards, touch pad, disk drives, display adapters, USB devices, Bit-mapped screen, LED, Analog-to-digital converter, On/off switch, network connections, audio I/O, printers etc.

需要一个 I/O 系统来接收应用程序 I/O 请求并将其发送到物理设备，然后接收设备发回的任何响应并将其发送到应用程序。I/O 设备可分为两类−

An I/O system is required to take an application I/O request and send it to the physical device, then take whatever response comes back from the device and send it to the application. I/O devices can be divided into two categories −

Block devices − A block device is one with which the driver communicates by sending entire blocks of data. For example, Hard disks, USB cameras, Disk-On-Key etc.
Character devices − A character device is one with which the driver communicates by sending and receiving single characters (bytes, octets). For example, serial ports, parallel ports, sounds cards etc

Device Controllers

设备驱动程序是可以插入操作系统以处理特定设备的软件模块。操作系统借助设备驱动程序来处理所有 I/O 设备。

Device drivers are software modules that can be plugged into an OS to handle a particular device. Operating System takes help from device drivers to handle all I/O devices.

设备控制器充当设备和设备驱动程序之间的接口。I/O 单元（键盘、鼠标、打印机等）通常由机械组件和电子组件组成，电子组件称为设备控制器。

The Device Controller works like an interface between a device and a device driver. I/O units (Keyboard, mouse, printer, etc.) typically consist of a mechanical component and an electronic component where electronic component is called the device controller.

对于每个设备，始终有一个设备控制器和一个设备驱动程序与操作系统通信。一个设备控制器可能会处理多个设备。作为接口，其主要任务是将串行比特流转换为字节块，根据需要执行纠错。

There is always a device controller and a device driver for each device to communicate with the Operating Systems. A device controller may be able to handle multiple devices. As an interface its main task is to convert serial bit stream to block of bytes, perform error correction as necessary.

连接到计算机的任何设备都是通过插头和插槽连接的，插槽连接到设备控制器。以下是用于连接 CPU、内存、控制器和 I/O 设备的模型，其中 CPU 和设备控制器都使用公共总线进行通信。

Any device connected to the computer is connected by a plug and socket, and the socket is connected to a device controller. Following is a model for connecting the CPU, memory, controllers, and I/O devices where CPU and device controllers all use a common bus for communication.

Synchronous vs asynchronous I/O

Synchronous I/O − In this scheme CPU execution waits while I/O proceeds
Asynchronous I/O − I/O proceeds concurrently with CPU execution

Communication to I/O Devices

CPU 必须有一种方法来与 I/O 设备之间传递信息。有三种方法可用于与 CPU 和设备通信。

The CPU must have a way to pass information to and from an I/O device. There are three approaches available to communicate with the CPU and Device.

Special Instruction I/O
Memory-mapped I/O
Direct memory access (DMA)

Special Instruction I/O

这使用专门用于控制 I/O 设备的 CPU 指令。这些指令通常允许将数据发送到 I/O 设备或从 I/O 设备读取数据。

This uses CPU instructions that are specifically made for controlling I/O devices. These instructions typically allow data to be sent to an I/O device or read from an I/O device.

Memory-mapped I/O

使用存储器映射 I/O 时，同一地址空间由内存和 I/O 设备共享。设备直接连接到某些主内存位置，以便 I/O 设备可以在不经过 CPU 的情况下将数据块传输到/从内存。

When using memory-mapped I/O, the same address space is shared by memory and I/O devices. The device is connected directly to certain main memory locations so that I/O device can transfer block of data to/from memory without going through CPU.

使用存储器映射的 IO 时，操作系统在内存中分配缓冲区并通知 I/O 设备使用该缓冲区将数据发送到 CPU。I/O 设备与 CPU 异步操作，在完成后中断 CPU。

While using memory mapped IO, OS allocates buffer in memory and informs I/O device to use that buffer to send data to the CPU. I/O device operates asynchronously with CPU, interrupts CPU when finished.

这种方法的优点是，可以访问内存的每条指令都可以用于操作 I/O 设备。存储器映射 IO 用于大多数高速 I/O 设备，如磁盘、通信接口。

The advantage to this method is that every instruction which can access memory can be used to manipulate an I/O device. Memory mapped IO is used for most high-speed I/O devices like disks, communication interfaces.

Direct Memory Access (DMA)

像键盘这样的慢速设备将在传输每个字节后向主 CPU 生成一个中断。如果像磁盘这样的快速设备为每个字节生成中断，则操作系统将花费其大部分时间来处理这些中断。因此，一台典型的计算机使用直接内存访问 (DMA) 硬件来减少此开销。

Slow devices like keyboards will generate an interrupt to the main CPU after each byte is transferred. If a fast device such as a disk generated an interrupt for each byte, the operating system would spend most of its time handling these interrupts. So a typical computer uses direct memory access (DMA) hardware to reduce this overhead.

直接内存访问 (DMA) 表示 CPU 授予 I/O 模块在不参与的情况下读写内存的权限。DMA 模块本身控制主内存和 I/O 设备之间的数据交换。CPU 只参与传输的开始和结束，并且仅在整个块传输完成后才中断。

Direct Memory Access (DMA) means CPU grants I/O module authority to read from or write to memory without involvement. DMA module itself controls exchange of data between main memory and the I/O device. CPU is only involved at the beginning and end of the transfer and interrupted only after entire block has been transferred.

直接内存访问需要一种称为 DMA 控制器 (DMAC) 的特殊硬件，它管理数据传输并仲裁对系统总线的访问。这些控制器使用源指针和目标指针（读取/写入数据的目的地）、用于跟踪传输字节数的计数器以及设置（包括 I/O 和内存类型、中断和 CPU 周期的状态）进行编程。

Direct Memory Access needs a special hardware called DMA controller (DMAC) that manages the data transfers and arbitrates access to the system bus. The controllers are programmed with source and destination pointers (where to read/write the data), counters to track the number of transferred bytes, and settings, which includes I/O and memory types, interrupts and states for the CPU cycles.

操作系统使用 DMA 硬件如下所示 −

The operating system uses the DMA hardware as follows −

Step	Description
1	Device driver is instructed to transfer disk data to a buffer address X.
2	Device driver then instruct disk controller to transfer data to buffer.
3	Disk controller starts DMA transfer.
4	Disk controller sends each byte to DMA controller.
5	DMA controller transfers bytes to buffer, increases the memory address, decreases the counter C until C becomes zero.
6	When C becomes zero, DMA interrupts CPU to signal transfer completion.

Polling vs Interrupts I/O

计算机必须有办法检测到任何类型的输入的到达。有两种可能发生的情况，称为 polling 和 interrupts 。这两种技术都可以让处理器处理随时可能发生并且与其当前正在运行的进程无关的事件。

A computer must have a way of detecting the arrival of any type of input. There are two ways that this can happen, known as polling and interrupts. Both of these techniques allow the processor to deal with events that can happen at any time and that are not related to the process it is currently running.

Polling I/O

轮询是I/O设备与处理器通信最简单的方式。定期检查设备的状态的过程，以查看是否需要进行下一次I/O操作，称为轮询。I/O设备只需将信息放入状态寄存器中，处理器就必须来获取该信息。

Polling is the simplest way for an I/O device to communicate with the processor. The process of periodically checking status of the device to see if it is time for the next I/O operation, is called polling. The I/O device simply puts the information in a Status register, and the processor must come and get the information.

大多数情况下，设备不需要关注，当设备需要关注时，它将不得不等到轮询程序下次对其进行询问。这是一种低效的方法，处理器的许多时间都会浪费在不必要的轮询上。

Most of the time, devices will not require attention and when one does it will have to wait until it is next interrogated by the polling program. This is an inefficient method and much of the processors time is wasted on unnecessary polls.

将此方法比作一位老师不断地一个个询问班级里的每位学生，看他们是否需要帮助。显然，更高效的方法是，当学生需要帮助时，由学生告知老师。

Compare this method to a teacher continually asking every student in a class, one after another, if they need help. Obviously the more efficient method would be for a student to inform the teacher whenever they require assistance.

Interrupts I/O

处理I/O的另一种方案是中断驱动的方法。中断是设备发给微处理器的信号，表示需要关注。

An alternative scheme for dealing with I/O is the interrupt-driven method. An interrupt is a signal to the microprocessor from a device that requires attention.

当设备的CPU需要关注时，设备控制器将中断信号放到总线上；CPU接收到中断后，会保存其当前状态，并使用中断向量（处理各种事件的操作系统例程的地址）调用适当的中断处理程序。当处理完中断设备后，CPU将继续其原始任务，就好像从未中断一样。

A device controller puts an interrupt signal on the bus when it needs CPU’s attention when CPU receives an interrupt, It saves its current state and invokes the appropriate interrupt handler using the interrupt vector (addresses of OS routines to handle various events). When the interrupting device has been dealt with, the CPU continues with its original task as if it had never been interrupted.

Operating System - I/O Softwares

I/O 软件通常按以下层组织−

I/O software is often organized in the following layers −

User Level Libraries − This provides simple interface to the user program to perform input and output. For example, stdio is a library provided by C and C++ programming languages.
Kernel Level Modules − This provides device driver to interact with the device controller and device independent I/O modules used by the device drivers.
Hardware − This layer includes actual hardware and hardware controller which interact with the device drivers and makes hardware alive.

I/O 软件设计的一个关键概念是它应该与设备无关，即可能编写可以在访问任何 I/O 设备的情况下无需提前指定设备的程序。例如，一个将文件作为输入读取的程序应该能够在软盘、硬盘或 CD-ROM 上读取文件，而无需对每个不同的设备修改程序。

A key concept in the design of I/O software is that it should be device independent where it should be possible to write programs that can access any I/O device without having to specify the device in advance. For example, a program that reads a file as input should be able to read a file on a floppy disk, on a hard disk, or on a CD-ROM, without having to modify the program for each different device.

Device Drivers

设备驱动程序是软件模块，可以插入操作系统以处理特定设备。操作系统从设备驱动程序获取帮助以处理所有 I/O 设备。设备驱动程序封装了与设备相关的代码，并实现了一个标准界面，这种方式下该代码包含特定于设备的寄存器读/写。设备驱动程序通常由设备制造商编写，并与设备一起在 CD-ROM 上交付。

Device drivers are software modules that can be plugged into an OS to handle a particular device. Operating System takes help from device drivers to handle all I/O devices. Device drivers encapsulate device-dependent code and implement a standard interface in such a way that code contains device-specific register reads/writes. Device driver, is generally written by the device’s manufacturer and delivered along with the device on a CD-ROM.

设备驱动程序执行以下工作 −

A device driver performs the following jobs −

To accept request from the device independent software above to it.
Interact with the device controller to take and give I/O and perform required error handling
Making sure that the request is executed successfully

设备驱动程序处理请求的方式如下：假设有一个请求来读取块 N。如果驱动程序在请求到达时处于空闲状态，它将立即开始执行请求。否则，如果驱动程序已经忙于处理其他请求，它会将新请求放在待定请求队列中。

How a device driver handles a request is as follows: Suppose a request comes to read a block N. If the driver is idle at the time a request arrives, it starts carrying out the request immediately. Otherwise, if the driver is already busy with some other request, it places the new request in the queue of pending requests.

Interrupt handlers

中断处理程序也被称为中断服务例程或 ISR，是一段软件，更确切地说，是操作系统中的回调函数，或更确切地说，是设备驱动程序中的回调函数，其执行是由中断的接收触发的。

An interrupt handler, also known as an interrupt service routine or ISR, is a piece of software or more specifically a callback function in an operating system or more specifically in a device driver, whose execution is triggered by the reception of an interrupt.

发生中断时，中断程序会执行它必须执行的所有操作来处理中断，更新数据结构并唤醒等待中断发生的进程。

When the interrupt happens, the interrupt procedure does whatever it has to in order to handle the interrupt, updates data structures and wakes up process that was waiting for an interrupt to happen.

中断机制接受一个地址 ─ 一个从一小组中选择特定中断处理例程/函数的数字。在大多数体系结构中，此地址是一个存储在称为中断向量表的表中的偏移量。此向量包含专用中断处理程序的内存地址。

The interrupt mechanism accepts an address ─ a number that selects a specific interrupt handling routine/function from a small set. In most architectures, this address is an offset stored in a table called the interrupt vector table. This vector contains the memory addresses of specialized interrupt handlers.

Device-Independent I/O Software

与设备无关的软件的基本功能是执行所有设备通用的 I/O 功能，并向用户级软件提供一个统一的接口。虽然很难编写完全与设备无关的软件，但我们可以编写一些在所有设备中通用的模块。以下是设备无关 I/O 软件功能的列表 −

The basic function of the device-independent software is to perform the I/O functions that are common to all devices and to provide a uniform interface to the user-level software. Though it is difficult to write completely device independent software but we can write some modules which are common among all the devices. Following is a list of functions of device-independent I/O Software −

Uniform interfacing for device drivers
Device naming - Mnemonic names mapped to Major and Minor device numbers
Device protection
Providing a device-independent block size
Buffering because data coming off a device cannot be stored in final destination.
Storage allocation on block devices
Allocation and releasing dedicated devices
Error Reporting

User-Space I/O Software

这些是提供更丰富且简化的接口以访问内核的功能或最终与设备驱动程序交互的库。大多数用户级 I/O 软件都由库过程组成，但有些例外，比如后台处理系统，它是多道程序系统中处理专用 I/O 设备的一种方式。

These are the libraries which provide richer and simplified interface to access the functionality of the kernel or ultimately interactive with the device drivers. Most of the user-level I/O software consists of library procedures with some exception like spooling system which is a way of dealing with dedicated I/O devices in a multiprogramming system.

I/O 库（例如 stdio）位于用户空间中，用于提供与驻留在操作系统中的与设备无关的 I/O SW 的接口。例如，putchar()、getchar()、printf() 和 scanf() 是 C 编程中可用的用户级 I/O 库 stdio 的示例。

I/O Libraries (e.g., stdio) are in user-space to provide an interface to the OS resident device-independent I/O SW. For example putchar(), getchar(), printf() and scanf() are example of user level I/O library stdio available in C programming.

Kernel I/O Subsystem

内核 I/O 子系统负责提供与 I/O 相关的许多服务。以下是一些提供的服务。

Kernel I/O Subsystem is responsible to provide many services related to I/O. Following are some of the services provided.

Scheduling − Kernel schedules a set of I/O requests to determine a good order in which to execute them. When an application issues a blocking I/O system call, the request is placed on the queue for that device. The Kernel I/O scheduler rearranges the order of the queue to improve the overall system efficiency and the average response time experienced by the applications.
Buffering − Kernel I/O Subsystem maintains a memory area known as buffer that stores data while they are transferred between two devices or between a device with an application operation. Buffering is done to cope with a speed mismatch between the producer and consumer of a data stream or to adapt between devices that have different data transfer sizes.
Caching − Kernel maintains cache memory which is region of fast memory that holds copies of data. Access to the cached copy is more efficient than access to the original.
Spooling and Device Reservation − A spool is a buffer that holds output for a device, such as a printer, that cannot accept interleaved data streams. The spooling system copies the queued spool files to the printer one at a time. In some operating systems, spooling is managed by a system daemon process. In other operating systems, it is handled by an in kernel thread.
Error Handling − An operating system that uses protected memory can guard against many kinds of hardware and application errors.

Operating System - File System

File

文件是有名称的、相关信息的时间，记录在磁盘、磁带和光盘之类的二级存储设备上。一般来说，文件是比特、字节、行或记录的序列，其意义由文件的创建者和使用者定义。

A file is a named collection of related information that is recorded on secondary storage such as magnetic disks, magnetic tapes and optical disks. In general, a file is a sequence of bits, bytes, lines or records whose meaning is defined by the files creator and user.

File Structure

文件结构应遵照操作系统能够理解的所需格式。

A File Structure should be according to a required format that the operating system can understand.

A file has a certain defined structure according to its type.
A text file is a sequence of characters organized into lines.
A source file is a sequence of procedures and functions.
An object file is a sequence of bytes organized into blocks that are understandable by the machine.
When operating system defines different file structures, it also contains the code to support these file structure. Unix, MS-DOS support minimum number of file structure.

File Type

文件类型是指操作系统区分不同类型文件的这种能力，例如文本文件、源文件和二进制文件等。许多操作系统支持多种类型文件。像 MS-DOS 和 UNIX 这样的操作系统具有以下类型的文件 -

File type refers to the ability of the operating system to distinguish different types of file such as text files source files and binary files etc. Many operating systems support many types of files. Operating system like MS-DOS and UNIX have the following types of files −

Ordinary files

These are the files that contain user information.
These may have text, databases or executable program.
The user can apply various operations on such files like add, modify, delete or even remove the entire file.

Directory files

These files contain list of file names and other information related to these files.

Special files

These files are also known as device files.
These files represent physical device like disks, terminals, printers, networks, tape drive etc.

这些文件有两种类型——

These files are of two types −

Character special files − data is handled character by character as in case of terminals or printers.
Block special files − data is handled in blocks as in the case of disks and tapes.

File Access Mechanisms

文件访问机制指的是访问文件记录的方式。访问文件有几种方式——

File access mechanism refers to the manner in which the records of a file may be accessed. There are several ways to access files −

Sequential access
Direct/Random access
Indexed sequential access

Sequential access

顺序访问是以某种顺序访问记录，即文件中的信息按顺序处理，逐条记录。这种访问方法是最原始的。示例：编译器通常以这种方式访问文件。

A sequential access is that in which the records are accessed in some sequence, i.e., the information in the file is processed in order, one record after the other. This access method is the most primitive one. Example: Compilers usually access files in this fashion.

Direct/Random access

Random access file organization provides, accessing the records directly.
Each record has its own address on the file with by the help of which it can be directly accessed for reading or writing.
The records need not be in any sequence within the file and they need not be in adjacent locations on the storage medium.

Indexed sequential access

This mechanism is built up on base of sequential access.
An index is created for each file which contains pointers to various blocks.
Index is searched sequentially and its pointer is used to access the file directly.

Space Allocation

文件由操作系统分配磁盘空间。操作系统采用以下三种主要方式将磁盘空间分配给文件。

Files are allocated disk spaces by operating system. Operating systems deploy following three main ways to allocate disk space to files.

Contiguous Allocation
Linked Allocation
Indexed Allocation

Contiguous Allocation

Each file occupies a contiguous address space on disk.
Assigned disk address is in linear order.
Easy to implement.
External fragmentation is a major issue with this type of allocation technique.

Linked Allocation

Each file carries a list of links to disk blocks.
Directory contains link / pointer to first block of a file.
No external fragmentation
Effectively used in sequential access file.
Inefficient in case of direct access file.

Indexed Allocation

Provides solutions to problems of contiguous and linked allocation.
A index block is created having all pointers to files.
Each file has its own index block which stores the addresses of disk space occupied by the file.
Directory contains the addresses of index blocks of files.

Operating System - Security

安全性是指为计算机系统资源（如 CPU、内存、磁盘、软件程序，最重要的是存储在计算机系统中的数据/信息）提供保护系统。如果计算机程序是由未经授权的用户运行的，那么他/她可能会对计算机或存储在其中的数据造成严重损坏。因此，必须保护计算机系统免遭未经授权的访问，对系统内存的恶意访问，病毒，蠕虫等。我们将在本章中讨论以下主题。

Security refers to providing a protection system to computer system resources such as CPU, memory, disk, software programs and most importantly data/information stored in the computer system. If a computer program is run by an unauthorized user, then he/she may cause severe damage to computer or data stored in it. So a computer system must be protected against unauthorized access, malicious access to system memory, viruses, worms etc. We’re going to discuss following topics in this chapter.

Authentication
One Time passwords
Program Threats
System Threats
Computer Security Classifications

Authentication

身份验证是指识别系统的每个用户并将执行中的程序与这些用户相关联。操作系统负责创建一个保护系统，该系统确保运行特定程序的用户是经过身份验证的。操作系统通常使用以下三种方式识别/验证用户 -

Authentication refers to identifying each user of the system and associating the executing programs with those users. It is the responsibility of the Operating System to create a protection system which ensures that a user who is running a particular program is authentic. Operating Systems generally identifies/authenticates users using following three ways −

Username / Password − User need to enter a registered username and password with Operating system to login into the system.
User card/key − User need to punch card in card slot, or enter key generated by key generator in option provided by operating system to login into the system.
User attribute - fingerprint/ eye retina pattern/ signature − User need to pass his/her attribute via designated input device used by operating system to login into the system.

One Time passwords

One-time passwords provide additional security along with normal authentication. In One-Time Password system, a unique password is required every time user tries to login into the system. Once a one-time password is used, then it cannot be used again. One-time password are implemented in various ways.

Random numbers − Users are provided cards having numbers printed along with corresponding alphabets. System asks for numbers corresponding to few alphabets randomly chosen.
Secret key − User are provided a hardware device which can create a secret id mapped with user id. System asks for such secret id which is to be generated every time prior to login.
Network password − Some commercial applications send one-time passwords to user on registered mobile/ email which is required to be entered prior to login.

Program Threats

操作系统进程和内核按照指示执行指定的任务。如果用户程序让这些进程执行恶意任务，则称为 Program Threats 。程序威胁的常见示例之一是安装在计算机中的一段程序，它可以通过网络将用户凭据存储并发送给某些黑客。以下是某些众所周知的程序威胁的列表。

Operating system’s processes and kernel do the designated task as instructed. If a user program made these process do malicious tasks, then it is known as Program Threats. One of the common example of program threat is a program installed in a computer which can store and send user credentials via network to some hacker. Following is the list of some well-known program threats.

Trojan Horse − Such program traps user login credentials and stores them to send to malicious user who can later on login to computer and can access system resources.
Trap Door − If a program which is designed to work as required, have a security hole in its code and perform illegal action without knowledge of user then it is called to have a trap door.
Logic Bomb − Logic bomb is a situation when a program misbehaves only when certain conditions met otherwise it works as a genuine program. It is harder to detect.
Virus − Virus as name suggest can replicate themselves on computer system. They are highly dangerous and can modify/delete user files, crash systems. A virus is generatlly a small code embedded in a program. As user accesses the program, the virus starts getting embedded in other files/ programs and can make system unusable for user

System Threats

系统威胁是指滥用系统服务和网络连接给用户带来麻烦。系统威胁可用于在称为程序攻击的整个网络上发起程序威胁。系统威胁创建这样的环境，以致于操作系统资源/用户文件被滥用。以下是某些众所周知的系统威胁的列表。

System threats refers to misuse of system services and network connections to put user in trouble. System threats can be used to launch program threats on a complete network called as program attack. System threats creates such an environment that operating system resources/ user files are misused. Following is the list of some well-known system threats.

Worm − Worm is a process which can choked down a system performance by using system resources to extreme levels. A Worm process generates its multiple copies where each copy uses system resources, prevents all other processes to get required resources. Worms processes can even shut down an entire network.
Port Scanning − Port scanning is a mechanism or means by which a hacker can detects system vulnerabilities to make an attack on the system.
Denial of Service − Denial of service attacks normally prevents user to make legitimate use of the system. For example, a user may not be able to use internet if denial of service attacks browser’s content settings.

Computer Security Classifications

根据美国国防部可信计算机系统评估标准，计算机系统中有四种安全级别：A、B、C、D。这是一种广泛使用的规范，用来确定和模拟系统和安全解决方案的安全性。以下是每种级别的简要说明。

As per the U.S. Department of Defense Trusted Computer System’s Evaluation Criteria there are four security classifications in computer systems: A, B, C, and D. This is widely used specifications to determine and model the security of systems and of security solutions. Following is the brief description of each classification.

S.N.	Classification Type & Description
1	Type A Highest Level. Uses formal design specifications and verification techniques. Grants a high degree of assurance of process security.
2	Type B Provides mandatory protection system. Have all the properties of a class C2 system. Attaches a sensitivity label to each object. It is of three types. B1 − Maintains the security label of each object in the system. Label is used for making decisions to access control. B2 − Extends the sensitivity labels to each system resource, such as storage objects, supports covert channels and auditing of events. B3 − Allows creating lists or user groups for access-control to grant access or revoke access to a given named object.
3	Type C Provides protection and user accountability using audit capabilities. It is of two types. C1 − Incorporates controls so that users can protect their private information and keep other users from accidentally reading / deleting their data. UNIX versions are mostly Cl class. C2 − Adds an individual-level access control to the capabilities of a Cl level system.
4	Type D Lowest level. Minimum protection. MS-DOS, Window 3.1 fall in this category.

Operating System - Linux

Linux 是 UNIX 操作系统流行版本之一。它是开源的，因为它的源代码是免费提供的。它免费使用。Linux 的设计考虑了 UNIX 兼容性。它的功能列表与 UNIX 非常相似。

Linux is one of popular version of UNIX operating System. It is open source as its source code is freely available. It is free to use. Linux was designed considering UNIX compatibility. Its functionality list is quite similar to that of UNIX.

Components of Linux System

Linux 操作系统主要有三个组件

Linux Operating System has primarily three components

Kernel − Kernel is the core part of Linux. It is responsible for all major activities of this operating system. It consists of various modules and it interacts directly with the underlying hardware. Kernel provides the required abstraction to hide low level hardware details to system or application programs.
System Library − System libraries are special functions or programs using which application programs or system utilities accesses Kernel’s features. These libraries implement most of the functionalities of the operating system and do not requires kernel module’s code access rights.
System Utility − System Utility programs are responsible to do specialized, individual level tasks.

Kernel Mode vs User Mode

内核组件代码在称为 kernel mode 的特殊特权模式下执行，可以完全访问计算机的所有资源。此代码表示一个进程，在单个地址空间中执行，不需要任何上下文切换，因此非常高效且快速。内核运行每个进程并向进程提供系统服务，向进程提供对硬件的受保护访问。

Kernel component code executes in a special privileged mode called kernel mode with full access to all resources of the computer. This code represents a single process, executes in single address space and do not require any context switch and hence is very efficient and fast. Kernel runs each processes and provides system services to processes, provides protected access to hardware to processes.

不需要在内核模式下运行的支持代码位于系统库中。用户程序和其他系统程序在 User Mode 中运行，它们无法访问系统硬件和内核代码。用户程序/实用程序使用系统库访问内核功能以获取系统的底层任务。

Support code which is not required to run in kernel mode is in System Library. User programs and other system programs works in User Mode which has no access to system hardware and kernel code. User programs/ utilities use System libraries to access Kernel functions to get system’s low level tasks.

Basic Features

以下列出了 Linux 操作系统的一些重要功能。

Following are some of the important features of Linux Operating System.

Portable − Portability means software can works on different types of hardware in same way. Linux kernel and application programs supports their installation on any kind of hardware platform.
Open Source − Linux source code is freely available and it is community based development project. Multiple teams work in collaboration to enhance the capability of Linux operating system and it is continuously evolving.
Multi-User − Linux is a multiuser system means multiple users can access system resources like memory/ ram/ application programs at same time.
Multiprogramming − Linux is a multiprogramming system means multiple applications can run at same time.
Hierarchical File System − Linux provides a standard file structure in which system files/ user files are arranged.
Shell − Linux provides a special interpreter program which can be used to execute commands of the operating system. It can be used to do various types of operations, call application programs. etc.
Security − Linux provides user security using authentication features like password protection/ controlled access to specific files/ encryption of data.

Architecture

下图显示了 Linux 系统的架构 −

The following illustration shows the architecture of a Linux system −

Linux 系统的架构由以下层组成 −

The architecture of a Linux System consists of the following layers −

Hardware layer − Hardware consists of all peripheral devices (RAM/ HDD/ CPU etc).
Kernel − It is the core component of Operating System, interacts directly with hardware, provides low level services to upper layer components.
Shell − An interface to kernel, hiding complexity of kernel’s functions from users. The shell takes commands from the user and executes kernel’s functions.
Utilities − Utility programs that provide the user most of the functionalities of an operating systems.