[TOC]
计算机科学导论学习笔记 第 4 部分 计算机软件与算法 此部分包含第7 、8 、9 、10 章，包含了计算机操作系统、问题求解算法、程序设计语言之旅、软件工程等相关知识，加深我们对开发的认识，为后续开发打下一个基础。
原文地址: https://mp.weixin.qq.com/s/FxYxTxZ1L3AjTy422QYfSg
第 7 章.操作系统 7.1 基础介绍 (1) 引言定义 计算机系统是由硬件和软件两个主要部分组成：硬件: 是计算机的物理设备。软件: 则是使得硬件能够正常工作的程序的集合, 其中又分成两大类操作系统和应用程序.
操作系统：则控制计算机系统用户对硬件的访问
定义
操作系统是一个非常复杂的系统, 有多个不同的的定义, 此处例举一些常见的定义：
操作系统是介于计算机硬件和用户（程序或人）之间的接口。
操作系统是一种用来使得其他程序更加方便有效运行的程序（或程序集）。
操作系统作为通用管理程序管理着计算机系统中每个部件的活动, 并确保计算机系统中的硬件和软件资源能够更加有效地使用, 当出现资源使用冲突时，操作系统应能够及时处理排除冲突。
设计目标: 有效地使用硬件, 更容易地使用资源.
总结: 操作系统是计算机硬件和用户（程序和人）的一个接口，它使得其他程序更加方便有效地运行，并能方便地对计算机硬件和软件资源进行访问控制。
(2) 自举过程 操作系统为其他程序提供支持，它负责把其他程序装入内存以便运行, 但由于操作系统本身也是程序，所以也需要被装入内存和运行。
最开始时, 通常使用ROM技术把操作系统存储（由制造商完成）在内存中，然后由CPU的程序计数器指到ROM的开始之处，之后当计算机被加电时CPU从ROM中读取指令并执行它们。
缺点：非常低效, 因为内存的很大一部分需要由ROM构成，而不能被其他程序使用。
当前方案, 它釆用两阶段过程，其中有很小一部分内存用ROM构成，主要用于存储自举程序，当计算机被加电时，CPU计数器被设置为自举程序的第一条指令，并执行程序中的指令（将操作系统程序从磁盘中读取并装入到RAM内存中），当装入完成后CPU中的程序计数器就被设置为RAM中操作系统的第一条指令，操作系统就被执行。
[TOC]
计算机科学导论学习笔记 第 4 部分 计算机软件与算法 此部分包含第7 、8 、9 、10 章，包含了计算机操作系统、问题求解算法、程序设计语言之旅、软件工程等相关知识，加深我们对开发的认识，为后续开发打下一个基础。
原文地址: https://mp.weixin.qq.com/s/FxYxTxZ1L3AjTy422QYfSg
第 7 章.操作系统 7.1 基础介绍 (1) 引言定义 计算机系统是由硬件和软件两个主要部分组成：硬件: 是计算机的物理设备。软件: 则是使得硬件能够正常工作的程序的集合, 其中又分成两大类操作系统和应用程序.
操作系统：则控制计算机系统用户对硬件的访问
定义
操作系统是一个非常复杂的系统, 有多个不同的的定义, 此处例举一些常见的定义：
操作系统是介于计算机硬件和用户（程序或人）之间的接口。
操作系统是一种用来使得其他程序更加方便有效运行的程序（或程序集）。
操作系统作为通用管理程序管理着计算机系统中每个部件的活动, 并确保计算机系统中的硬件和软件资源能够更加有效地使用, 当出现资源使用冲突时，操作系统应能够及时处理排除冲突。
设计目标: 有效地使用硬件, 更容易地使用资源.
总结: 操作系统是计算机硬件和用户（程序和人）的一个接口，它使得其他程序更加方便有效地运行，并能方便地对计算机硬件和软件资源进行访问控制。
(2) 自举过程 操作系统为其他程序提供支持，它负责把其他程序装入内存以便运行, 但由于操作系统本身也是程序，所以也需要被装入内存和运行。
最开始时, 通常使用ROM技术把操作系统存储（由制造商完成）在内存中，然后由CPU的程序计数器指到ROM的开始之处，之后当计算机被加电时CPU从ROM中读取指令并执行它们。
缺点：非常低效, 因为内存的很大一部分需要由ROM构成，而不能被其他程序使用。
当前方案, 它釆用两阶段过程，其中有很小一部分内存用ROM构成，主要用于存储自举程序，当计算机被加电时，CPU计数器被设置为自举程序的第一条指令，并执行程序中的指令（将操作系统程序从磁盘中读取并装入到RAM内存中），当装入完成后CPU中的程序计数器就被设置为RAM中操作系统的第一条指令，操作系统就被执行。
温馨提示：中间省略了BIOS(Basic Input Output System)相关步骤，实际上BIOS是电脑启动时加载的第一个软件, 此处只是简单了解。
(3) 发展演化 1) 批处理操作系统 ：设计于20世纪50年代，目的是控制大型计算机，当时用穿孔卡片进行输入数据，用行式打印机输出结果，用磁带设备作为辅助存储介质。
特点：此操作系统非常简单，它们只保证计算机所有资源被从一个作业转换到另一个作业。
2) 分时操作系统 : 为了有效使用计算机资源，引入了多道程序的概念，又由其多道程序带来了分时的概念，最终利用分时技术的多道程序极大地改进了计算机的使用效率。
多道程序：它可以将多个作业同时装入内存, 并且仅当该资源可用时分配给需要它的作业。
例如，当一个程序正使用输入/输出设备时, CPU则处于空闲状态，并可以供其他程序使用。
分时：资源可以被不同的作业分享，每个作业可以分到一段时间来使用资源。
因为，计算机运行速度很快，所以分时系统对于用户是隐藏的，每个用户都感觉整个系统在为自己服务。
但是，它们需要有一个更加复杂的操作系统，它必须可以调度。
调度：即在此处可以理解为给不同的程序分配资源并决定哪一个程序什么时候使用哪一种资源。
进程：即为一个作业是一个要运行的程序，一个进程则是在内存中等待分配资源的程序。
3) 单用户操作系统 : 当个人计算机产生后，需要有一类适合这类计算机的操作系统，此时单用户操作系统就应运动而生了，如DOS （磁盘操作系统）。
4) 并行系统 : 此操作系统比单CPU操作系统更加复杂，由于在并行系统的计算机中安装多个CPU，每个CPU可处理一个程序或者一个程序的部分，意味着很多任务可以并行地处理而不再是串行处理。
5) 分布式系统 : 由于网络化和网络互联的发展，扩大了操作系统的内涵，即一台机器上运行的进程可以通过网络使用多台远程计算机中的资源，分布式系统结合了以往系统的特点和新的功能，例如，安全控制，资源调度。
6) 实时系统 : 在特定时间限制内完成任务，它们被用在实时应用程序中，这些应用程序监控、响应或控制外部过程或环境。例如，应用在交通控制、病人监控或军事控制系统中。此处，实时操作系统的需求经常与通用系统的需求是不同的，我们简单了解一下即可。
7.2 组成部分 现代操作系统设计十分复杂，其中最重要的是它必须可以管理系统中的不同资源，实现功能也比较多，至少具有以下4种功能（存储管理、进程管理、设备管理、文件管理），操作系统下还有一个专门的用户界面或命令解释程序，它负责操作系统与外界通信。
操作系统其结构类似于一个公司管理部门，并且相互协调，如下图所示：
weiyigeek.top-操作系统组成部分图
(1) 用户界面 每个操作系统都有用户界面，即指用来接收用户（进程）的输入并向操作系统解释这些请求的程序。
命令解释程序（shell）：通常用于Linux、Unix操作系统，即命令行终端接收用户输入以及结果输出。
窗口可视化：通常指明它是一个由菜单驱动的并有着GUI （图形用户接口）的部件，最开始通常所指Windows操作系统，而当前Linux各发行版本中也支持窗口化。
(2) 内存管理 内存管理是操作系统是现代计算机操作系统最重要的职责，由于程序和数据也越来越大,针对内存分配必须进行管理以避免“内存溢出”的错误。
操作系统按照内存管理可以分为两大类：单道程序和多道程序。
单道程序 ：多数内存用来装载单一的程序（我们考虑数据作为程序的一个部分被程序处理），仅仅一小部分用来装载操作系统，当程序结束后程序区域由其他程序取代，即将程序载入内存、运行它、再装入新程序 ，此处简单了解即可它属于旧事物了。
存在的问题：
程序必须能够载入内存，即内存容量一定比程序占有小。
一个程序运行时，其他程序不能运行，只能等待其运行结束后才会被装载执行。（PS: CPU使用效率低下）
多道程序 : 同一时刻可以装入多个程序并且能够同时被执行，CPU轮流为其服务，在20世纪60年代通过改进后，出现四种比较有特征的技术，即两种非交换（分区、分页），两种交换（请求分页、请求分段）。
weiyigeek.top-单道程序与多道程序
分区调度：此模式下，内存被分为不定长的几个部分或者分区，每个部分或分区保存一个程序，CPU在各个程序之间交替服务，当然CPU也可进行优化级管理，用于控制分配给每个程序的CPU时间。
工作流程：它由一个程序开始， 执行一些指令，直到有输入/输出操作或者 分配给程序的时限到达为止。
优点：每个程序完全载入内存，并占用连续的地址，改进CPU使用效率。
缺点：
分区的大小必须由内存管理器预先决定，如果分区过小程序就不能载入到内存，反之将会出现空闲区。
即使分区在刚开始时比较合适，但随着新程序的交换载入内存后有可能出现空闲区。
当空闲区过多时，内存管理器能够紧缩分区并删除空闲区和创建新区，但这将增加系统额外开销。
分页调度：此模式下，内存被分成大小相等的若干个部分称为帧，而程序则被分为大小相等的部分称为页，通常页和帧的大小是一致的，并且与系统用于从存储设备中提取信息的块大小相等
工作流程：当程序开始执行指令时，页被载入内存中的帧，如果一个程序有3页，它就在内存中占用3个帧。
优点：提高执行效率，程序在内存中不必是连续的，两个连续的页可以占用内存中不连续的两个帧。例如，一个需要6个帧的程序可以代替两个各占有不连续的3个帧的程序，而不必等到有6个连续的帧出现后再载入内存。
缺点：程序仍需要在运行前全部载入内存，意味着在只有4个不连续帧时，一个需要6个空闲帧的程序是不能载入的。
weiyigeek.top-分页与分区
请求分页调度：此模式下，程序被分成页，页可以依次载入内存、运行, 然后被另一个页代替，即内存可以同时载入多个程序的页。此外，来自同一个程序的连续页可以不必载入同一个帧，一个页可以载入任何一个空闲帧。
例如，两页来自程序A, 一页来自程序B, 一页来自程序C,这4页在内存中，如下图所示
请求分段调度：此模式下，其似于分页调度的技术，程序实际是分为大小相等的页（程序通常由主程序和子程序组成, ），程序将按程序员的角度划分成段，它们载入内存中、执行，然后被来自同一程序或其他程序的模块所代替。
例如，如下请求分段调度的一个例子，因为在内存中的段是等长的，所以段的一部分可能是空的。
当然我们可将请求分页与请求分调度进行组合，它可以提高系统效率，一个段（程序）或许太大而不能载人内存中的空闲区，内存可分很多帧，一个程序也可分为很多页，然后依次载入内存中运行。
weiyigeek.top-请求分页与请求分段
虚拟内存
如今几乎所有的操作系统都使用了该技术，它包含了请求分页调度、请求分段调度两种模式。使用虚拟内存时当程序运行时，一部分程序驻留在内存中，一部分则放在硬盘上，此时分页文件是硬盘中的一块区域，在 Windows 系统中当作RAM进行使用。
例如，10 MB内存可以运行10个程序。每个程序3MB一共30 MB，任意时候10个程序中10 MB在内存中，还有20 MB在磁盘上，但实际上只有10 MB内存但却有30 MB的虚拟内存。
weiyigeek.top-虚拟内存
扩展，如何在 Windows 系统设置虚拟内存?
适用环境：windows 10
我的电脑 => 属性 => 高级设置 => 性能选项 => 高级 => 虚拟内存。
weiyigeek.top-Windows虚拟内存设置
(3) 进程管理器 1) 程序、作业、进程概念
现代操作系统关于指令集有三个术语程序、作业和进程, 不同的操作系统对于它们的定义并不一致，此处在本节中做一个方便大家理解的定义。
程序（program）：由程序员编写的一组稳定的指令，存在磁盘(或磁带)上，它可能会也可能不会成为作业。
作业（task）：当程序开始执行到其运行结束并再次成为一个程序的这段过程，即当一个作业执行完毕(正常或不正常)，它又变成程序代码并再次驻留于硬盘中（等待调入内存），操作系统不再支配该程序（需等待CPU执行）。
重点：每个作业都是程序，但并不是所有的程序都是作业。
进程（process）：一个运行中的程序并未处于结束状态，即进程是一个驻留在内存中运行的作业，它是从众多等待作业中选取出来并装入内存中的作业，一个进程可以处于运行状态或者等待CPU调用，只要作业装入内存就成为一个进程。
重点：每个进程都是作业，而作业未必是进程。
2) 程序、作业、进程的关系以及程序生命周期
当程序被操作系统选中时成为作业（此时处于保持状态) 等待载入内存，当内存可以整体或者部分地载入该程序时作业变成进程（此时处于就绪状态），当被CPU调用执行后处于运行状态后，但也可能出现下面三种情况之一:
进程运行直至它需要I/O资源，在第一种情况下，进程进入等待状态直至输入/输出结束
进程可能耗尽所分配的时间片，在第二种情况下，它直接进入就绪状态
进程终止，在第三种情况下，它进入终止状态，并且不再是进程
weiyigeek.top-程序生命周期
总结生命周期五种状态：保存、就绪、等待、运行、终止。
温馨提示：如果系统使用虚拟内存，并且需要在内存中将程序交换出或换入，状态图可能更加复杂。
3) 调度器
进程管理器使用了两个调度器（作业调度器和进程调度器），将作业或进程从一个状态改变为另一个状态.
作业调度器：将一个作业从保持状态转入就绪状态，或是从运行状态转入终止状态。即作业调度器负责从作业中创建一个进程和终止一个进程。
进程调度器：将一个进程从一个状态转入另一个状态，分为如下四种情况。
当一个进程等待某事件发生时，它使这一进程从运行状态进入等待状态。
当一个事件发生时，进程将从等待状态进入就绪状态。
当一个进程所分配的时间片用完时，这个进程将从运行状态进入就绪状态。
当CPU准备执行这个进程时，进程调度器将让这个进程从就绪状态进入执行状态。
其他调度器：某些操作系统使用其他类型的调度器使得进程之间的转换更为有效。
weiyigeek.top-调度器
4) 队列
程序生命周期过程中，实际上会有很多的作业和进程相互竞争计算机资源，所以为处理多个进程和作业资源竞争问题，进程管理器使用队列（等待列表）来解决。
例如，当一些作业进入内存时，其他的就必须等待直到有了可用空间。
例如，当一个进程正在使用CPU时，其他进程就必须等待直到CPU空闲为止。
进程管理器在队列中存储的是作业或进程控制块，即每一作业或进程相关的是存有这些作业和进程信息的作业控制块或进程控制块，作业和进程仍保存在内存或硬盘中，它们因为太大而无法被复制到队列中，这些作业控制块或进程控制块就是等待中的作业和进程的代表。
一个操作系统有很多个队列，例如图示中的作业和进程在三个队列里循环，即作业队列、就绪队列和I/O队列。
作业队列: 用来保存那些等待内存的作业。
就绪队列: 用来保存那些已经在内存中准备好运行但在等待CPU的进程。
I/O队列: 用来保存那些正在等待I/O设备的进程（这里可以有多个I/O队列，每一个对应一个输入/输出设备，这里为了简单只画 出一个）。
进程管理器可以用多种策略从队列中选择下一个作业或进程，可以是先入先出（FIFO）、 最短长度优先、最高优先级等.
5) 进程同步
进程管理的思想都是使得拥有不同资源的不同进程同步, 当资源可以被多个用户（进程）同时使用，那么它就可能有两种有问题的状态死锁和饿死.
死锁：当操作系统没有对进程资源进行限制时将发生死锁，即死锁发生在操作系统允许一个进程运行, 而不用首先检查它所必需的资源是否准备好, 是否允许这个进程占有资源直到它不需要为止。
weiyigeek.top-死锁
饿死：它是与死锁相反的情况，它发生在当操作系统对进程分配资源有太多限制的时候，例如假使一个操作系统中规定一个进程只有在所需的所有资源都为其占有时才能执行。
weiyigeek.top-饿死问题
6) 设备管理器
设备管理器也叫输入/输出管理器，它负责访问输入/输出设备。由于在计算机系统中输入/输出设备存在着数量和速度上的限制，并且与CPU和内存比起来速度要慢很多，所以当一个进程访问输入/输出设备时，在该段时间内这些设备对其他进程而言是不可用的，所以此时需要一个设备管理器让其使用更加高效。
此处简要地列出设备管理器的功能：
不停地监视所有的输入/输出设备，以保证它们能够正常运行，即监听其进程占用完成信息，并为队列中下一个进程服务。
为每一个输入/输出设备维护一个队列，或是为类似的输入/输出设备维护一个或多个队列。
控制用于访问输入/输出设备的不同策略。
(4) 文件管理器 现今操作系统使用文件管理器来控制对文件的访问，此节简单介绍一下一下文件管理器的功能：
控制文件的访问（rwx）权限，即控制进程针对资源文件拥有可读r、可读写rw、可执行x等权限。
管理文件的创建、删除和修改。
管理文件命名。
管理文件的存储。
负责归档和备份。
总结： 现代操作系统至少有4个功能区域内存管理器、进程管理器、 设备管理器、文件管理器，操作系统还提供用户界面。
现代操作系统的第一职责是内存管理：内存分配必须由操作系统控制。内存管理技术可以分成两类：单道程序和多道程序。在单道程序中，内存的大部分容量都为一个程序独享。在多道程序中，多个程序同时在内存中。
现代操作系统的第二职责是进程管理：进程是运行的程序，进程管理使用调度器和队列来管理进程。进程管理涉及具有不同资源的不同进程间的同步问题。这可能潜在地造成资源死锁和饿死。死锁是指一个进程由于其他进程无限制地使用资源导致无法运行的情况。饿死是指一个进程由于资源分配限制太多而不能执行的情况。
现代操作系统的第三职责是设备或I/O管理：在计算机系统中，输入/输出设备在数 目和速度上都有限制。因为这些设备与CPU和内存相比，速度很慢，所以当一个 进程访问输入/输出设备时，它对其他进程就不可用。设备管理器负责输入/输出设备的高效使用。
现代操作系统的第四职责是文件管理：操作系统使用文件管理器控制对文件的访问。只有进程或用户被允许访问指定文件时才允许被访问，注意其访问的类型可以改变。
7.3 主流操作系统 当下用户熟悉及常用的操作系统有UNIX、Linux和Windows。
(1) Unix 在1969年，由贝尔实验室的计算机科学研究小组的Thomson和Ritchie开发，它是程序设计员和计算机科学家中较为流行的操作系统,，例如苹果的 Mac OS 就是基于Unix开发的。
1) 特点
UNIX是多用户、多道程序、可移植的操作系统，它被设计来方便编程、文本处理、通信和其他许多希望操作系统来完成的任务。
第一，UNIX是一个可移植的操作系统，它可以不经过较大的改动而方便地从一个平台移植到另一个平台。原因是它主要是由C语言编写的（而不是特定于某种计算机系统的机器语言）。
第二，UINX 拥有一套功能强大的工具（命令），它们能够组合起来（在可执行文件中被称为脚本）去解决许多问题，而这一工作在其他操作系统中则需要通过编程来完成。
第三，它具有设备无关性，因为操作系统本身就包含了设备驱动程序，这意味着它可以方便地配置来运行任何设备。
2) 结构
UNIX由4个主要部分构成：内核、命令解释器、一组标准工具和应用程序。
内核（Kernel）：UNIX系统的心脏，其包含操作系统最基本的部分内存管理、进程管理、设备管理和文件管理，系统资源调用主要是通过内核来执行。
命令解析器（Shell）：UNIX结构的最重要的组成部分，它用于接收和解释用户输入的命令。
工具（Tools）：UNIX标准程序，它为用户提供支持过程，常用的三个工具是文本编辑器(vim、emacs、nano)、搜索程序find和排序程序sort。
应用（Application）：是由系统管理员、专职程序员或用户编写的是对系统功能的扩展，现在基本成了系统的一部分。
weiyigeek.top-组成部分
(2) Linux 在1991年，由芬兰Helsinki大学的学生Linus Torvalds开发了一个新的操作系统，当下用得最多的操作系统之一，衍生出众多发行版本（Debian、Ubuntu、CentOS、SUSE）等。
在1997 年，发布的Linus 2.0内核成为商业操作系统，它具有传统UNIX的所有特性。
1) 结构
内核：内核负责处理所有属于内核的职责，如：内存管理、进程管理、设备管理和文件管理。
系统库：系统库含有一组被应用程序使用的函数(包括命令解释器)，用于与内核交互。
系统工具: 是使用系统库提供的服务，执行管理任务的各个程序。
2) 网络
它支持三层套接字接口、协议驱动和网络设备驱动。
3) 安全
Linux的安全机制提供了传统上为UNIX定义的安全特性，如身份验证和访问控制。
当下现对比于Windows来说安全性好，只不过随着操作系统的发展以及使用人数增多，其安全性也正在接受各种挑战。
(3) Windows Windows 是 微软（Microsoft）流行的操作系统家族 ，它是是面向对象的、多层，提供可视化友好的的操作系统。
20世纪80年代后期（985年），在Dave Cutler的领下，微软开始开发替代MS-DOS (微软磁 盘操作系统)的新的单用户操作系统。
1987年12月9日，发布 Windows 2.0 ，和1.0一样都是ms-dos操作系统
1990年5月22日，发布 windiws3.0
1992年4月， 发布Windows3.1
1994年 发布 Windows3.2这个版本开始有了中文的windows
1995年8月24日，发布 Windows 95 （记忆尤新，我小学接触的第一台计算机操作系统）
1996年10月，Windows 95的OSR2版(OEM Service Release 2，被称为Windows97)
1998年6月25日，发布 Windows 98
1999年5月5日，发行 Windows 98 SE（win98第二版）于
1999年12月19日，发行 Windows 2000
2000年9月14日，发布Windows ME( Windows Millennium Edition，简称WindowsME)
2001年10月，发布 Windows XP 于 2014年停止（家里的第一台电脑，XP真的是经典，我玩得第一个游戏QQ飞车）
2007年1月30日，发布 windows Vista 于 2017年4月11日停止
2009年10月，推出 Win7 2020年1月停止（怀念经典，记忆中是玩得 CF ）
2012年10月26日，推出 Windows 8 于 2016年1月12日停止
2013年10月17日，推出 Windows 8.1 于 2023年1月10日停止
2015年7月29日，推出 windows10 于 最长的企业版ltsc预计在2029年停止 （当前使用较多的Windows版本，由于Win7不发布补丁更新了）
2021年6月23日，推出 windows11 于 官方预览版渠道预先发布，正式版将于2021年10月和windows10 21H2版本一起推出
1) 设计目标
可扩展性：设计成具有多层的模块化体系结构。意图是允许高层随时间而改变，而不影响底层。
可移植性：像UNIX-样，Windows是用C或C++编写的，这个语言是独立于它所运行的计算机的机器语言的。
可靠性：设计成能处理包括防止恶意软件的错误条件。
兼容性：设计成能运行为其他操作系统编写的程序，或Windows早期版本。
性能：设计成对运行在操作系统顶部的应用程序，具有快速响应时间。
2) 结构体系
HAL：硬件抽象层(HAL)为上层隐藏了硬件的差异。
内核：内核是操作系统的心脏。它是面向对象软件的一个片段。该面向对象的软件把任何实体都看成对象。
执行者: 为整个操作系统提供服务。它由6个子系统构成：对象管理器、安全引用监控器、进程管理器、虚拟内存管理器、本地过程调用工具和I/O管理。大多子系统是我们前面讨论操作子系统中所熟悉的。有些子系统(像对象管理器)被加到Windows中，是因为它的面向对象的本质，执行者运行在内核态(特权)。
环境子系统: 设计用来允许Windows运行那些为Windows、其他操作系统或Windows 早期版本设计的应用程序。运行为Windows设计的应用的本地子系统称为Win32，环境子系统运行在用户态(无特权)。
特别注意：硬件抽象层、内核、执行者都是工作于内核态，而环境子系统运行在用户态（无特权）
