Computer Organization and Architecture

Operating System Support

Outline

• Operating System Overview

• Scheduling

• Memory Management

Operating System Overview

• 什么是操作系统

操作系统是一组主管并控制计算机操作、运用和运行硬件、软件资源和提供公共服务来组织用户交互的相互关联的系统软件程序。根据运行的环境，操作系统可以分为桌面操作系统，手机操作系统，服务器操作系统，嵌入式操作系统等

• 有哪些常用的操作系统
  • DOS
  • windows
  • UNIX
  • Linux
  • OS/2
  • IOS,Android
  • Mac OS

Operating System Objectives and Functions

• Operating system, or OS for short, is a computer program that manages computer hardware and software resources

• The operating system deals with such basic matters as

  • managing and configuring memory

  • determining the priority of system resource supply and demand

  • controlling input devices and output devices

  • operating networks and managing file systems

• The operating system also provides an operation interface for users to interact with the system

Objectives and Functions

• A system program developed to improve resource utilization and enhance computer system performance

• Convenience

  • Shields the details of computer hardware

  • Provides convenient interfaces for users

  • Making the computer easier to use

• Efficiency

  • Process scheduling

  • Memory management

  • Fully exploit the power of computer

Characteristic

• The most fundamental system program is the operating system

  • Provides an interface between the user and the computer

  • Manages the computer resources

  • Provides an environment for the application program execution

  • Improves the efficiency and stability of program execution

Layers of a Computer System

• 系统软件是指控制和协调计算机及外部设备,支持应用软件开发和运行的系统，主要功能是调度，监控和维护计算机系统

• 系统软件包括操作系统和一系列基本的工具，比如编译器，数据库管理，存储器格式化，文件系统管理等，支持计算机系统正常运行并实现用户操作

• 操作系统是最重要的系统软件，位于硬件和工具之间

• 使得上层方便地访问和使用计算机系统提供的资源和服务

Operating system services

• Program creation

• Program execution

• Access to I/O devices

• Controlled access to files

• System access

• Error detection and response

• Accounting

OS as a resource management

• 操作系统是一个计算机程序，执行也是由处理器来进行，通过给处理器提供一系列指令，来执行操作系统程序

• 操作系统不能一直占用了处理器，而是需要放弃对处理器的控制，让处理器去执行应用程序。之后，它再次获得控制权，为下一个应用程序的执行进行准备(System Call)

• 操作系统有一部分驻留在内存中，称为操作系统内核

• 操作系统还要对I/O的使用进行分配

Types of Operating Systems

Operating system support batch processing or not?

• Interactive

  • User usually interacts with the computer by keyboard or display

  • Request to execute jobs or process transactions

• Batch

  • Multiple user programs are packaged and submits to the computer in batches for processing

  • After processing, print the results

---

Support multiple programs or not?

• Single program (Uni-programming)

  • Processor can only process one program at a time

• Multi-programming (Multi-tasking)

  • Processor can process multiple programs at one time

  • Multiple programs loaded into memory at the same time

  • processor switches between programs and processes

Memory layout for resident monitor

• 多程序批量处理系统中，内存划分为监控程序和用户程序两个区域

  • 监控程序包括：中断处理，设备驱动程序，作业排序，控制语言解释器

  • 通过监控程序，实现了作业的调度

• 用户程序提交之后，就可以按照顺序处理，不会浪费处理器

Required hardware support

• Memory protection

  • To protect the Monitor

• Timer

  • To prevent a job monopolizing the system

• Privileged instructions

  • Only executed by Monitor
  • e.g. I/O

• Interrupts

  • Allows operation system for relinquishing and regaining control

Multi-programmed batch system

• Batch system performs monitoring and user programs in turn, which improves the utilization of the whole system

• I/O devices very slow

• Processors are also often idle

• Multi-programmed batch systems

  • Memory load multiple user programs

  • When one program is waiting for I/O, another can use the CPU

  • CPU keeps working

  • Core idea of modern operation system

Single program

Multi-Programming with two programs

Multi-Programming with three programs

• 同时有三个程序处于执行状态

• CPU等待状态的时间更少

• CPU效率更高

Utilization

• 单个程序逐个执行，总共需要30个时间单位

• 多道程序同时执行，只需要15个时间单位

• 节省了一半时间

Time sharing systems

• Multi-programmed batch system

  • Improve the efficiency of system operation

  • Disadvantage is that the response to users is not timely

• For multiple interactive job scenarios, a time-sharing system is proposed

  • Multiple users to share processor time and interact with the processor

  • Operating system responds to each user’s request in time slices computer

  • For each user, he thinks the processor only serves him

Scheduling

• Key to multi-programming

• Determines the efficiency of multiprogramming

• Includes long term, medium term, short term

  • Long term: determines the number of processes added to the pending process pool

  • Medium term: determines the number of processes added to main memory

  • Short term: decide which process the processor will execute

Five state process model

• 新建状态：调度程序提交一个程序，操作系统为这个程序创建一个进程，并将进程移入就绪状态

• 就绪状态：进程已经准备就绪，等待处理器的执行

• 运行状态：进程正在由处理器执行

• 等待状态：进程在等待资源，处于挂起状态

• 终止状态：进程运行结束

What is process? ! ! !

• A program in execution

  • An instance of a program running on a computer

  • The entity that can be assigned to and executed on a processor

  • A unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system instructions

Process elements

• A process is comprised of

  • Program code (possibly shared)

  • A set of data

  • A number of attributes describing the state of the process

• Process elements

  • Identifier

  • State

  • Priority

  • Program counter

  • Memory pointers

  • Context data

  • I/O status information

  • Accounting information

Process control block

• Contains the process elements

• Created and manage by the operating system

• Allows support for multiple processes

Trace of the process

• The behavior of an individual process is shown by listing the sequence of instructions that are executed

  • This list is called a Trace

• Processor needs to execute multiple processes one by one

  • Dispatcher is responsible for scheduling the process

  • Dispatcher is a small program which switches the processor from one process to another

Virtual memory

• 虚拟存储器是内存管理的一种技术，允许程序从逻辑的角度对内存进行寻址，而不考虑物理上可用的内存空间

• 本质上是一种内存扩充技术，不会使内存的物理空间大小发生改变，但是能够使程序访问内存的方式更灵活

• 由于虚拟内存的存在，所以程序中可以只将其中的一部分加载到物理内存中。只有当需要的程序段不在内存中的时候，才通过换页的方式将它加载到内存中

Execution of a process

• Entire program does not need to be loaded to memory

  • Operating system brings into main memory a few pieces of the program

  • Resident set - portion of process that is in main memory

• An interrupt is generated when an address is needed that is not in main memory

  • Operating system places the process in a blocking state

---

• Piece of process that contains the logical address is brought into main memory

  • Operating system issues a disk I/O Read request

  • Another process is dispatched to run while the disk I/O takes place

  • An interrupt is issued when disk I/O complete which causes the operating system to place the affected process in the Ready state

Implications of this new strategy

• More processes may be maintained in main memory

  • Only load in some of the pieces of each process

  • With so many processes in main memory, it is very likely a process will be in the Ready state at any particular time

• A process may be larger than all of main memory

Wording mode of OS

• 操作系统中维护一个长期队列和一个短期队列

• 长期队列是等待系统资源的作业列表，短期队列包含所有就绪状态的进程

• 中断发生时，操作系统接管处理器的控制权，执行中断处理程序

• 进程调用服务时，操作系统执行服务调用处理程序

• 中断或服务调用程序处理完成后，短期调度会调度某个进程进入到运行状态

• 每个I/O设备有一个I/O队列

Process scheduling ！ ！ ！

• 进程请求进入长期队列

• 进程的请求满足后，进程进入就绪状态并进入短期队列

• 如果进程请求I/O，则进入I/O队列

• I/O完成后，继续进入短期队列，完成进程的执行

Memory Management

• Uni-program

  • Memory split into two

  • One for Operating System (monitor)

  • One for currently executing program

• Multi-program

  • “User” part is sub-divided and shared among active processes

• Memory management

  • Make full use of the memory space

  • keep the CPU busy

  • avoid idle CPU due to IO waiting

Methods of memory management

• Swapping

• Partitioning

• Paging

• Virtual Memory

• Translation Lookaside Buffer

• Segmentation

Swapping

• Problem

  • I/O is so slow compared with CPU

  • Even in multi-programming system，CPU is idle most of the time

• Solutions

  • Increase main memory，more process in memory

    • Expensive

    • Leads to larger programs

  • Swapping

What is swapping?

• Long term queue of processes stored on disk

  • Processes “swapped” in as space becomes available

  • As a process completes it is moved out of main memory

• If none of the processes in memory are ready (i.e. all I/O blocked)

  • Swap out a blocked process to intermediate queue

  • Swap in a ready process or a new process

  • Swapping is an I/O process

Use of swapping

• 简单的进程调度中，磁盘维护一个长周期队列。当内存中有作业完成了，会将它从内存中去掉，同时将长周期队列中的一个作业放到内存中

• 交换调度中，磁盘中维护了一个中间队列。阻塞进程将会被“交换”到中间队列中，并从中间队列中调入一个已经就绪的进程。如果中间队列没有就绪的进程，就从长期队列中调度一个新的进程到内存中

• 通过中间队列，可以在进程均处于阻塞的时候进行进程的有效调度，提高CPU效率

Partitioning

• Swapping does not explain how memory is managed

• Memory management mode

  • Partitioning

  • Paging

  • Segmentation

• Partitioning: Splitting memory into sections to allocate to processes (including Operating System)

Fixed partitioning

• 分区大小固定，但不一定都是一样大

• 进程分配内存时，分配到能容纳它的最小分区

• 存在内存浪费的现象

• 采取非固定大小分区可能会更好

Variable sized partitions

• Allocate exactly the required memory to a process

• This leads to a hole at the end of memory, too small to use

  • Only one small hole - less waste

• When all processes are blocked, swap out a process and bring in another process，leads to another hole

• A process is completed and swapped out，new process is swapped in. May leads to a hole

• Eventually have lots of holes (called fragmentation)

• Solutions

  • Coalesce - Join adjacent holes into one large hole

  • Compaction- From time to time go through memory and move all hole into one free block (like $\rightarrow$ disk de-fragmentation)

Effect of Dynamic Partitioning

• 分配进程1~3的时候，按需求分配，剩下$4M$的空间

• 进程2交换出去了，进程4进来了。进程4只有$8M$，在进程4和进程3之间，形成了一个$6M$的空块

• 进程1交换出去了，进程2进来。进程1有$20M$，进程2只有$14M$，在进程2和进程4之间，又形成了一个$6M$的空块

• 有2个$6M$空块和1个$4M$空块

Problem about relocation

• No guarantee that process will load into the same place in memory

• Instructions contain addresses information

  • Locations of data

  • Addresses for instructions (e.g. branching)

• If a fixed address is used, memory address of process changes after the process is swapped out and then swapped in

• Data and instructions cannot be addressed

---

• Using logical address and physical address

  • Logical address - relative to beginning of program

  • Physical address - actual location in memory (this time)

• Starting unit address of the current process is set as the base address

• Addressing data and instructions using logical addresses in programs

Paging

• Partitioning will lead to waste of memory

• Paging Management

  • Split memory into equal sized, small chunks -page frames

  • Split programs (processes) into equal sized small chunks – pages

  • Allocate the required number page frames to a process

• Operating System completes paging management

  • A process does not require contiguous page frames

  • Use page table to keep track

---

• Each process has its own page table

• Each page table entry contains the frame number of the corresponding page in main memory

• Two extra bits are needed to indicate

  • whether the page is in main memory or not

  • Whether the contents of the page has been altered since it was last loaded

Paging table

• 寻址的虚拟地址为“页号+偏移量”

• 页表中指明了这个页对应的内存的帧序号

• 通过[页$\rightarrow$帧]的转换，以及页内的偏移量，就可以得到逻辑地址在内存中的实际地址

Allocation of free frames

• 内存中帧13-15是空闲的，分配给了进程A地第1-3页

• 帧16、17其他进程占用

• 帧18分配给进程A的0页

• 分配帧的时候，既不要求是连续的，也不要求前后顺序

Real and virtual memory

• On the basis of logical address, expand the memory, which leads to the concept of virtual memory

• Real memory

  • Main memory, the actual RAM

• Virtual memory

  • Memory on disk

• Allows for effective multiprogramming and relieves the user of tight constraints of main memory

---

Support deeded for virtual memory

• Hardware must support paging and segmentation

• Operating system must be able to manage the movement of pages and/or segments between secondary memory and main memory

---

Virtual memory

• Page load-demand paging

  • Do not require all pages of a process in memory

  • Bring in pages as required

• Page fault

  • Required page is not in memory

  • Operating System must swap in required page

  • May need to swap out a page to make space

  • Select page to throw out based on recent history

---

Thrashing

• Too many processes in too little memory

• Operating System spends all its time swapping

• Little or no real work is done

• Disk light is on all the time

• Solutions

  • Good page replacement algorithms

  • Reduce number of processes running

  • Fit more memory

---

Advantage of virtual memory

• Do not need all of a process in memory for it to run

• Swap in pages as required

• So can now run processes that are bigger than total memory available!

• Main memory is called real memory

• User/programmer sees much bigger memory - virtual memory

---

Page tables

• Each process must have a page table to convert logical address or virtual address to physical address

• Some processes are very large, and their page tables themselves are very large

  • Page tables are also stored in virtual memory

  • When a process is running, part of its page table is in main memory

  • Load the required page table through exchange

Address Translation for Hierarchical page table

• 虚拟地址包括根页表段、用户页表段和页内偏移量

• 根据根页表指针和根页表段，得到用户页表段的基准地址

• 加上用户页表段地址，得到用户页表地址

• 再加上页内偏移量，得到在实际内存中的地址

---

Problem about page tables

• A drawback of the type of page tables is that their size is proportional to that of the virtual address space

  • Each virtual space page needs a row in the page table

  • If the virtual space of the user program is large, the page table will also be very large

• An alternative is Inverted Page Tables

Inverted page table

• Used on PowerPC, UltraSPARC, and IA-64 architecture

• Page number portion of a virtual address is mapped into a hash value

• Hash value points to inverted page table

• Fixed proportion of real memory is required for the tables regardless of the number of processes

• 反向页表的行数是物理内存的帧数，和进程数无关

---

• Each entry in the page table includes

  • Page number

  • Process identifier

    • The process that owns this page

  • Control bits

    • includes flags, such as valid, referenced, etc

  • Chain pointer

    • the index value of the next entry in the chain

---

Use of inverted page table

• 虚拟地址中的页号通过散列函数，形成一个散列值，映射到反向页表

• 通过页号的散列值和进程ID，确定虚拟地址的页是否在内存中

• 通过链技术来提高查找的速度

Translation lookaside buffer

• Every virtual memory reference causes two physical memory access

  • Fetch page table entry

  • Fetch data

• To overcome this problem a high-speed cache is set up for page table entries

  • Called a Translation Lookaside Buffer (TLB)

  • Contains page table entries that have been most recently used

---

TLB operation

• 根据虚拟地址中的页地址，去快表中查找是否有页帧地址

• 如果有，接就可以生成物理地址

• 如果没有，就去看内存中的页表中是否有这个页

• 如果在内存中的话，就先更新快表，然后生成物理地址

• 如果也没有，就要去读取I/O，然后更新内存页表

Segmentation

• Paging is not (usually) visible to the programmer

• Segmentation is visible to the programmer

• Usually different segments allocated to program and data

• May be a number of program and data segments

---

Advantage of segmentation

• Simplified management

  • Programmers need not know how much space data needs

  • Data can be allocated to its own segment and can be dynamically expanded

• Allows programs to be altered and recompiled independently

• The segment can be shared among multiple processes

• Protections from assigning access privileges

---

Segment tables

• Corresponding segment in main memory

• 段需要有段表来实现地址转换

• 虚拟地址中包含段号，从段表中找到该段号对应的段基址，就可以根据偏移量到内存中得到这个虚拟地址对应的物理地址

---

Combined segmentation and paging

• 程序员将进程分为若干个段

• 系统将每个段分为多个页

• 在进行地址转换的时候，根据段号，到段表中找到段基址，根据页号，到页表中找到对应的帧号，然后段基址和帧号结合，可以得到实际的物理地址