操作系统期中复习课

第一章

operating system

What is a operating system:

• a program that acts as an intermediary(中介) between a user of a computer and the computer hardware。

Goals：

• excute(执行) user program
• conventient the computer to use
• use the computer hardware in an efficient manner

Definition：

• resource allocator(资源分配器)
• control program(程序控制器)
• privides interface between computer hardware and other system and application programs(提供调用计算机硬件的接口)

OS = kernel + system programs

• kernel：The one program running at all times on the computer
• everything else is ether
  • a system program
  • an application program

Computer System Organization

Computer Startup/Booting

• bootstrap program(引导程序) is loaded at power-up or reboot.
• job:
  • Typically stored in ROM or EPROM, gengrally known as firmware.
  • Initializes all aspects of system
  • Loads operating system kernel and strats execution(执行)

Interrupt：

• Interrupt transfers control to the interrupt service routing(中断服务程序)，through the interrupt vector(中断向量)， which contains ths addresses of all the service routines.
• when some events occur, the programs currently running on ths CPU are interrupted, CPU control is transferred to the interrupt service routine to handle the events.

Categories：

• hard interrupt：caused by hardware interrupt signals, trigged(触发) by external events.
• System call/monitor cass：an interrupt triggered by software。from user request program that a OS service be performed.
• Trap or exception：software-generated interrupt caused by an error

Dual-mode & Privilege instructions

Goal：

• protect OS and other system components from errant(错误的) users。

Privilege instruction：

• identify machine instructions that may cause harm, and designate(指定) these instructions as privileged instructions

Dual-mode：

mode bit provided by hardware/CPU to indicate the current operation mode.

0：kernel mode

1：user mode

• user mode：if user programs in user mode attempt to execute privileged instructions, a trap is generated and CPU control is passed to OS to handle this errors.
• kernel mode：privileged instructions are only executable in kernel mode.

Protection and Security

Protection：

• any mechanism(机制) for controlling access of processes or users to resources

Security：

• defense of the system against internal and external attacks.

第二章

Operating Systems Service

Functions：

• User interface
• Program execution
• I/O operations
• File-system manipulation(操纵)
• Communications(通讯)
• Error detection
• Resources allocation
• Accounting(统计)-track of which users how much and what kinds of computer resources
• Protection and Security

System Call

System calls provide the programming interface to the services made available by the operating system.

Mostly accessed by programs via a high-level Application Program Interface(API) rather than direct system call use.

System Call Parameter Passing

Three general methods used to pass parameters to the OS：

• Simplest：pass the parameters in registers
• Parameters stored in a block(块), or table(表), in memory, and address of block passed as a parameter in a register
• Parameters placed, or pushed, onto the stack by the program and popped off the stack by the operating system

Block and stack methods do not limit the number or length of parameters bing passed

Categories：

• Process control
• File management
• Device management
• Information maintenance(信息维护)
• Communications
• Protection

Operating System Structure

General-purpose OS is very large program

Various ways to structure ones:

• simple structure
• more complex
• layered 分层的
• Modules 模块化的
• microkernel 微内核
• hybrid system 混合架构

Microkernel System Structure

OS is structured by removing all nonessential components from the kernel in the kernel mode, and implement them as system-level and user-level programs

Feature:

• the removed OS functional components run as server processes in user mode.
• Communication takes place between user modules using message passing

System Boot

When power initialized on system, execution starts at a fixed memory location

• Firmware ROM used to hold initial boot code

Small piece of code - bootstrap loader, stored in ROM or EEPROM locates(定位) the kernel, loads it into memory, and starts it.

Kernel loads and system is then running

Booting (系统引导/启动/加载)

• Starting a computer by loading OS kernel

BIOS(Basic Input Output System)

konwn as bootstrap or a part bootstrap

jobs：

• test hardware
• start OS
• support the tansfer of data among hardware devices.

第三章

Process Concept

In mutiprogramming(多道程序设计) systems and time-shared systems：

• one program may execute several times, processing different data in each time
• more than one programs execute concurrently

Process are thus used for describing of concurrent(并发) executing of programs

Process：

• a program in execution
• process execution must prograss in sequential fashion
• OS allocates CPU, memory, devices to process

Consists of：

• text section(代码段)
• program counter
• Stack
• Data section 数据段
• Heap

Process state:

PCB：

• Process state
• Program counter
• CPU registers
• CPU scheduling information
• Memory-management information
• Accounting information
• I/O status information

Proess Scheduling

Selecting processes and allocating CPU, devices

Maintains scheduling queues of processes：

• Job queue：set of all processes in the system
• Ready queue：set of all processes residing(放在) in main memory, ready and waiting to execute
• Device quques：set of processes waiting for an I/O device
• Processes migrate among the various queues

Schedulers

调度类型分类：

• Short-term scheduler(CPU scheduler)：selects which process should be executed next and allocates CPU.

  • invoked(调用) frequently，milliseconds.

• Long-term scheduler(job scheduler)：selects which processes should be brought into the ready queue.

  • invoked infrequently，seconds, minutes
  • controls the degree of multiprogramming(多道程序数)

进程类型分类：

• I/O-bound process(I/O密集型进程)
• CPU-bound process(CPU密集型进程)

Context Switch：

• When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch
• Context-switch time is overhead(开销), the system does no useful work while switching

Operations on Processes

OS must provide mechanisms(机制), by system calls, for:

• process creation创建
• process termination终止

Process Creation

OS and other processes use creation primitive(原语)/system call to creation a new process

Parent process create children processes， which， in turn creation other processes， forming a tree of processes.

Resource sharing options：

• Parent and children share all resources.
• Children share subset of parent’s resources
• Parent and child share no resources

内核初始化init模块为0号模块

Process Termination

Process execute last statement and then asks the operating system to delete it using the exit() system call.

Parent may terminal the execution of children processes using the abort() system call.

cascading termination(级联终止)：a process terminates, then all its children must also be terminated.

• Zombie process(僵尸进程)：child is terminated by exit() and its resources is released, but no parent invoke wait, child is at the Zombie state.
• Orphan process(孤儿进程)：if parent terminated without incoking wait, the child becomes a orphan.
• init is then taken as its parent

Interprocess Communication（IPC）

two models of IPC：

• Shared memory(in user mode)
• Message passing(in kernel mode)

Shared Memory

An area of memory shared among the processes that wish to communication.

Message Passing

If process P and Q wish to communicate, they need to:

• Establish a communication link between whtm
• Exchange messages via send/receive

Direct Communication

Process must name each other explicitly(明确的)：

• send(Q, message)
• receive(P, message)

Indirect Communication

Message are directed and received from mailboxes.

• Each mailbox has a unique id
• Process can communicate only if they share a mailbox

create a new mailbox A:

• send(A, message);
• receive(A, message);

Synchronization

Message mey be either blocking or non-blocking

Blocking :

• send：the sender is blocked until the message is received
• receive：the receiver is blocked until a message is available

Non-blocking：

• send：the sender sends the message and continue
• receive：the receiver receives

第四章

Thread

why thread needed？

To reduce costs of process management and improve degrees of concurrency and parallelism.

Thread definition

• a basic unit for CPU scheduling

并行VS并发：

• Parallelism：implies a system can perform more than one task simutaneously(同时地)
• Concurrency：support more than one task making progress.

Multithread Programming Models

The threads can be identified as

• user threads, or user-level threads(UTL)
• kernel threads, or kernel-level threads(KLT)

kernel-level threads are managed by OS, while user-level threads by thread library.

UTL to KTL Mapping

• many to one
• one to one
• many to many

Thread Pools

Thread pool：

• a set of pre-created threads, the number of threads in this set is limited

CPU密集型任务：

• 线程数量 = CPU核数

I/O密集型任务：

• M = N*(1+WT/CT)

CT：count time计算时间

WT：wait time等待时间

Thread-Local Storage(TLS)

thread might its own copy of certain data.

第五章

Scheduling Criteria(调度标准)

• CPU utilization CPU利用率
• Throughput 吞吐量：the number of process that complete their execution per time unit
• Turnarount time 周转时间：amount of time taken to complete a particular process
• Waiting Time 等待时间：the sum of the periods spent waiting in the ready queue
• Response time 响应时间：the time from the submission of a request until the first response in produced

Scheduling Algorithms(调度算法)

• First-Come First-Served(FCFS)
• Shortest-Job-First(SJR)
• Priority scheduling
• preemptive 抢占式
• nonpreemptive 非抢占式
• Round Robin(RR, 时间片轮转)
• Multilevel quque 多级队列
• Multileve feedback queue 多级反馈队列
• Highest Response Rate First(HRRF)
• Scheduling in real-time system

第六章

mutual exclusory methods 互斥方法

The Critical-Section Problem

• Critical section(临界区)：访问临界资源的代码段称为临界区
• Critical resources(临界资源)：需要互斥访问的资源

Necessary conditions for correct solutions to critical-section problems

• mutual exclusion：互斥访问
• process：空闲则进
• bounded waiting：有限等待

Peterson Solution

Bakery Algorithm

Semaphores 信号量

• Binary semaphore 二元信号量：integer value can range only between 0 and 1, also called mutex lock.
• Counting semaphore：the value can range over an unrestricted(无限制的) domain.

wait(S)；

signal(S);

Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers-Writers Problem
• Dining-Philosophers Problem
• Sleep-barer problem

Monitors 管程

consists of :

• shared variables 共享数据结构
• condition variables 条件变量
• concurrent procedures 并发程序
• initialization codes 初始化代码

condition variables

Condition variable can only be used with the operations wait and signal.

• x.wait()：the process invoking this operation is suspended(挂起) until another process incokes signal()
• x.signal()：the x.signal operation resumes(唤醒) exactly one suspended process. if no process is suspended, then the signal operation has no effect.