OS

Overview 进程间是相互保持独立的，内存管理中，就是保护进程的地址空间不被其他进程访问。而进程间通信 ( Inter-process Communication IPC) 用于在一个或多个进程间交换数据 进程间合作是那些可以影响或受其他过程影响的过程。例如网站包含 JS、H5、Flash，当有一个相应缓慢时，会发生整个网站的布局或其他功能的展示。 通常情况下进程间合作被允许的原因有： 信息共享：多个进程需要访问同一个文件。（如管道） 计算加速：将复杂功能拆分为多个子任务（多处理器时效果更佳），可以更快地解决问题 模块化：将整体系统架构分为不同功能模块，模块间相互协作 便利：单用户可以同时多任务处理，如 编辑、编译、打印等 Communications model (a) 消息队列（间接通信）                 (b) 共享内存（直接通信） Message Passing IPC背后关键的一点是消息的传递，即一个进程发消息，一个进程接收消息 而为了使进程间通信，就必须在进程间建立连接，连接可以是单/双向。连接可以使用直接通信和间接通信来实现 Direct Communication 直接通信，必须明确声明发送者或接收者的名称，通常定义为： Send(P, message)：发送信息到进程 P Receive(Q, message)：接收来自进程 Q 的信息 在直接通信中，一般连接的属性有以下特征： 一个链路与一对进程相关联 自动建立链接 链接是通用的双向链接 Indirect Communication 间接通信，为异步通信，通常情况下互通信都需要有消息队列；发送者将信息放置消息队列中，接受者从消息队列中取出消息 Send(P, message)：像消息队列发送消息 Receive(Q, message)：接受消息队列中的消息 每个进程都有唯一ID 共享一个消息队列 在间接通信中，一般连接的属性有以下特征： 一对进程共享消息队列时，才会在进程之间建立链接 链接可以被许多进程关联 链接可以是单向也可以是双向 每个进程可以有多个链接   直接通信                                            间接通信 Synchronization 从另一方面来讲，消息传递可以是阻塞 Blocking 或非阻塞 Non-Blocking 的；同步 synchronous 会阻塞一个进程，直到发送完成。异步 asynchronous 则是是非阻塞的，发送操作完成后会立即返回不等待返回结果 Buffer 消息通过队列传递，队列的容量则具有下列三种配置之一： 0容量：消息不能存储在队列中，因此发送者必须阻塞，直到接收者接受消息 有限容量：队列中有一定的预先约定大小的容量。如果队列已满，发送者必须阻塞，直到队列中有可用空间（反之为空，接受者阻塞），否则可能是阻塞的或非阻塞的 无限容量：具有无限容量的队列，发送者永远不会被迫阻塞 至此整节围绕对消息传递功能的三个方面做了介绍：...

Overview 文件系统和文件 文件系统: 一种用于持久性存储的系统抽象，决定了辅存中的内容如何组织与存储的抽象概念 文件：文件系统中的一个单元的相关数据在操作系统中的抽象，展现给用户的抽象概念 文件系统的功能： 分配文件磁盘空间 管理文件块(哪一块属于哪一个文件) 管理空闲空间(哪一块是空闲的) 分配算法(策略) 管理文件集合 定位文件及其内容 命名：通过名字找到文件的接口 最常见：分层文件系统 文件系统类型(组织文件的不同方式) 提供的便利及特征 保护：分层来保护数据安全 可靠性，持久性：保持文件的持久即使发生崩溃,媒体错误,攻击等 为什么需要文件系统： 如果将文件放入一个房间中，整个房间都是堆积的文件 有了文件系统的存在将会改变一切 空间管理、元数据、数据加密、文件访问控制和数据完整性等等都是文件系统的职责。 文件属性 文件具有名称和数据，还存储文件创建日期和时间、当前大小、上次修改日期等元信息。所有这些信息都称为文件系统的属性。常见的文件属性有 名称：它是以人类可理解的形式。 标识符：每个文件都由文件系统中的唯一标记号标识，称为标识符。 位置：设备上的文件位置。 类型：支持各种类型文件的系统需要此属性。 大小：当前文件大小的属性。 保护：分配和控制读、写和执行文件的访问权限。 时间、日期和安全：用于对文件的保护、安全，也用于监控 文件描述符 文件头 File Header；类似于Unix的 inode，在存储元数据中保存了每个文件的信息，保存文件的属性，跟踪哪一块存储块属于逻辑上文件结构的哪个偏移 文件描述符 （file-descriptor）；是唯一标识操作系统中打开文件的数字（整形），用于用户和内核空间之间的接口，以识别 文件/Socket 资源。因此，当使用 open() 或 socket()（与内核接口的系统调用）时，会得到一个文件描述符，一个整数。因此，如果直接与内核交互，使用系统调用 read(), write() 等 close()。使用的是一个文件描述符句柄。 在 C 语言中 stdin，stdout、 和 stderr ，在 UNIX 中分别映射到文件描述符 0 1 2 text 1 2 3 4 5 f = open(name, flag); ... ....

死锁问题 死锁 deadlock；是一组阻塞的进程，每个进程都持有一个资源并等待获取另一个进程持有的资源。 死锁的示例：交通桥 如图所示，桥是资源，进程是车辆，两个不同方向的车辆同时占用桥，此时发生谁也过不去的情况（死锁的发生）； 当死锁发生时，如果一辆车倒车（抢占资源和回滚）就可以解决死锁问题 死锁发生时，可能需要后退多台车辆 饥饿，而饥饿并不一定是死锁 系统模型 在正常情况下，进程必须在使用之前请求资源，并在完成后释放它，顺序如下： 请求：如果不能立即授予请求，则进程等待，直到它需要的资源变得可用。例如，系统调用 open()、malloc()、new() 、request() 等。 使用：进程使用资源，例如文件中读取数据；使用硬件。 释放：进程完成后放弃资源，以便其可用于其他进程。如，close()、free()、delete() 、 release()。 当在集合中的每个进程都在等待当前分配给集合中另一个进程的资源时，这一组进程就会发生死锁 资源分配 通过实例来理解死锁， 一组资源： ${ R_1,\ R_2,\ R_3,\ ….,\ R_N }$；为方形，图形内的点代表资源数量 一组进程： ${ P_1,\ P_2,\ P_3,\ ….,\ P_N }$ 请求边缘 Request Edge：进程需要一些资源，被称为请求边缘；如 $P_i\ →\ R_j$ 分配边缘 Assign Edge：当资源已经被分配给进程，被称为分配边缘；如 $R_j\ →\ P_i$ 当请求被授予时，可以通过反转方向的线将请求边缘转换为分配边缘 类型 示意图 Process Resource $P_i$ 请求的 $R_j$ 实例 $P_i$ 持有一个 $R_j$ 的实例 也可以说 $R_j$ 被 $P_i$ 所持有 资源分配图 资源分配图 如图所示，资源类型为：...

Backgound 信号量 semaphores，是操作系统中非常重要的技术，通过使用一个简单的整数值来管理并发进程，信号量只是一个在线程之间共享的整数变量。该变量用于解决临界区问题并实现进程同步。 信号量具有两个原子操作： P()：sem减一，如果sem<0，等待；否则继续 V()：sem加一，如果sem≤0，唤醒一个等待的P； Semaphore 信号量的使用 型号量的特点： 两个类型信号量 二进制信号量 Binary Semaphore：也称为互斥锁。它只能有两个值0和1。它的值被初始化为1。它用于实现多进程临界区问题的解决。 计数信号量 Counting Semaphore：值可以跨越一个不受限制的域（可以取任何非负数）。它用于控制对具有多个实例的资源的访问。 信号量是被保护的变量 初始化完成后，唯一改变一个信号量的值的办法是通过P() 和 V() 操作必须是原子 P() 能够阻塞，V() 不会阻塞 信号量可以用在2个方面 互斥 条件同步(调度约束 —— 一个线程等待另一个线程的事情发生) 信号量实现的互斥 c 1 2 3 4 5 6 7 mutex = new Semaphore(1); mutex->P(); // 临界区前p ... critical section ... mutex->V(); // 临界区后v 信号量实现调度约束 c 1 2 3 4 5 6 7 8 9 10 condition = new Semaphore(0); // Thread A ....

Overview CPU调度 (cpu scheduling )，是决定在一个时间窗口内，哪个进程可以拥有CPU而另外一个个进程会被暂停的过程。CPU调度的作用是为了确保每当CPU空闲时，操作系统至少选择就绪队列中一个可用的进程执行。这个选择过程将由CPU调度器来执行。 调度程序：挑选就绪进程的内核函数 调度策略：依据什么挑选进程？ 调度时机：什么时间进行调度？ 进程从运行状态切换到等待状态 进程退出 非抢占式：当前进程主从放弃CPU时， 抢占式：当前进程被抢占 时间片用完 进程从等待切换到就绪（当前就绪进程优先级高于当前运行进程） 调度准则 CPU的调度策略 抢占式调度 抢占式调度（Preemptive）在分配进程时有对应的优先级。而在另一个较低优先级进程之前运行具有较高优先级的进程很重要，即使较低优先级的进程仍在运行。较低优先级的进程扔会等待一段时间，让较高优先级的进程完成执行后恢复。 抢占式调度主要发生在运行状态切换到就绪或等待状态 非抢占式调度 非抢占式调度 （Non-Preemptive），在这种类型的调度中，一旦将资源（CPU 周期）分配给一个进程，该进程就会持有CPU使用权，直到它被终止或达到等待状态。 抢占式调度主要发生在运行状态终止的情况下 如何确定调度是抢占式还是非抢占式？ 一般来讲，确定调度的方式是通过以下四点来确定的： 当进程从运行状态切换到等待状态；如I/O请求或调用 wait() 系统调用 当进程从运行状态切换到就绪状态；如响应中断。 当进程从等待状态切换到就绪状态；如在 I/O 完成或从 wait() 返回时。 进程完成执行并终止； 如果调度发生在1 4情况下，则为非抢占式，否则为抢占式 程序执行模型 需要关注的是进程在计算机系统中运行时存在什么状态？ 几乎所有进程都在一个连续的循环的两种模型之间交替：即CPU突发和I/O突发中交替 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU 在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU CPU突发和 I/O突发的交替序列逻辑 CPU 突发型的持续时间 调度指标 在了解评价指标前，需要对CPU调度中的一些术语需要了解 CPU突发 （Burst Time BT）：进程开始执行的时间，从到达到开始执行花费的时间 到达时间 （Arrival Time AT）：进程到达就绪队列的时间 完成时间（End Time ET 或 Completion Time CT）：进程执行完成的时间 等待时间 （Waiting Time WT）：进程在就绪队列中等待轮到 CPU 占用的时间；$WT = TT - BT$ 周转时间 （Turnaround Time TT）：完成时间和到达时间的差 $TT=CT-AT$ 相应时间（Response Time RT）：开始响应请求所需的时间。第一次请求到相应的时间。 吞吐量 (Throughput)：单位时间内完成的进程数。$Throughput = (Number\ of\ processes\ completed) \div (Time\ unit)$ 一般情况下，需要的服务”越快“越好，而快的定义：...