操作系统第二次作业

操作系统第二次作业

  1. 进程的三种状态:

    1. 运行态(running,在该时刻实际占用处理机 )
    2. 就绪态(Ready,可运行,因为其他进程正在进行而暂时被挂起)
    3. 阻塞态(Blocked,除非某种外部事件发生,否则不能运行)

  2. 目前计算机上,中断处理程序使用汇编语言编写的原因:中断处理程序,以操作系统最底层的调度器为例,需要使用汇编语言程序存储寄存器值,设置新的栈等,即汇编语言代码要为新的当前进程进行装入寄存器值和内存映射并启动等现场保存工作.

  3. 进程和线程的本质区别:多个线程的执行流组成进程,进程是用来集合资源的,而线程是CPU调度中的实体.

  4. 在使用线程的系统中,每个线程都有一个堆栈,它存储着执行的历史.

  5. 竞争条件:两个多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,称为竞争条件.

  6. 若采用时间片调度而不是优先级调度,是否会H继续陷入死循环:

    1. 采用优先级调度陷入死循环的原因在于低优先级的进程永远处于被调度队列的较后位置,而正好于处于临界区时无法有其他进程再被调度形成死锁,故会陷入死循环;
    2. 采用时间片调度也会发生这种情况,虽然时间片调度作为一种非抢占式进程,在时间片到、进程运行完毕或者进程执行原语操作时都会面临进程切换的问题,而当进程切换发生时,死锁也就会相应发生了.但是时间片调度仍然很大的避免了优先级高的无法离开临界区的问题.

  7. 读者-写者问题的3种形式化:

    1. 读者优先: 当读者在读时,写者不能进行写,当有新的读者到来时,如果没有写,那么就可以立刻开始读.当写完成时,如果有一些读者和写者都在等待队列中时,读者的启动的优先级高,这些读者都可以同时启动.
    2. 读者和写者具有公平的情况:读读共享,写写互斥,写读互斥.当我们开始进行读的时候我们需要一次性将读者队列读完.当我们进行写时,也要一次一次将写者等待队列写完.
    3. 写者优先:当等待队列中有写者时,读者不可以被启动.即当有任何进程完成时,有写者在等待,读者都不可以被启动.

  8. 以下各种情况下的CPU运行公式:

    1. $\frac{T}{S+T}$

    2. $\frac{T}{S+T}$

    3. 考虑context switch的次数:

      Context switch的次数为:$\frac{T}{ST/Q+T}$

    4. 当Q=S时,考虑$T<Q时$,CPU利用率为:$\frac{T}{S+T}$当$T\ge Q$时,CPU 利用率为50$.

    5. 随着时间片越来越小,上下文切换花销所占的比重会越来越大,CPU会趋近于0.

  1. 平均响应时间最短,最短作业优先在批处理系统中常常伴随着最短平均响应时间.

    所以调度的顺序在于x的值,x的大小在不同的位置有不同的调度顺序.

  2. 对于每种不同的调度算法计算不同的平均进程周转时间.

    1. 时间片轮转: 程序具有多道处理能力,作业均获得公平的CPU份额.所以每个进程都占用$\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{1}{2},1$的CPU. 完成的时间为:10,8,6,4,2;故完成的时间为10,18,24,28,30.

      平均时间为110/5=22

    2. 优先级调度,按照:优先级54321的顺序,即6,8,10,2,4的顺序,故相应的完成时间为6,14,24,26,30,平均时间为:20

    3. 相应的完成时间为:10,16,18,22,30,平均时间为19.2

    4. 按照:2,4,6,8,10,相应的完成时间为:2,6,12,20,30,平均时间为 14

  3. $\frac{35}{50}+\frac{20}{100}+\frac{10}{200}+\frac{x}{250}\le1$

    故$x\le12.5$

  4. 优先级调度算法会引起饥饿问题.所以minix3的优先级调度(多级排队系统)会产生饥饿.

    对于某个低优先级而无穷等待的CPU,和超载的计算机系统,稳定的更高优先级的进程流会组织低优先级的进程获得CPU,此时对于低优先级的进程而言,就有饥饿的可能.

展开全文 >>

操作系统 W9 进程概述与进程实现

操作系统 W9 进程概述与进程实现

main初始化流程(main.c)

.s文件与.c文件

  • 初始化中断控制器
  • 初始化进程表与特权控指表
  • 初始化boot image中的进程
  • 设置IDLE为第一个运行的进程
  • 显示欢迎信息
  • 调用mpx386.s文件中的_restart函数开始进程调度(上下文切换)

硬件中断处理

  • 通过CPU INT管脚通知CPU发生了中断
  • CPU发出INTA信号

硬件中断

硬件产生中断信号

通过中断控制器，决定给CPU发送发送何数值，给CPU发送相应的中断服务历程。

  • 中断控制器将数据放在系统数据总线上并通知处理器应执行哪个服务历程

软件中断

执行汇编指令

中断处理过程

硬件

  1. 硬件发送中断信号
  2. 中断控制器
    1. 打断CPU
    2. send digital identification of the interrupting device
  3. Kernel:
    1. 保存寄存器
    2. Send notification message to driver
    3. Restart a process

系统调用（软件)

  1. Caller
    1. 将相应消息保存到CPU
    2. execute software interrupt instruction。
  2. Kernel 同

_restart

Cold boot->restart

进程间通讯

拷贝：从内核的物理拷贝(跨逻辑地址空间拷贝)

1
2
3
B：Send(A,&m);
A:Receive(B,&m);
//对应两个不同的内核区域，故拷贝只能由内核来做。

  • 若目标进程未在等待消息，则发送者被标记为阻塞，并挂入一个等待将消息发送到接受进程的进程队列中。

    即在接受进程的进程表里，接收进程维护一个链表，加一个指针指向发送者。

    在当一个进程执行RECEIVE时，内核检查该队列中是否存在向他发送消息的进程。如果存在，则消息从被阻塞的发送进程拷贝到接受进程。

    如果不存在这样的进程，则接受进程也会被阻塞。

  • 如何将队列挂到连表中?

    Sys_call(proc.c)

进程调度

展开全文 >>

操作系统 W8 进程调度

2.4进程调度

第2章课程设计：修改和实现相应功能的调度

进程行为

  • 做计算
  • 做I/O[磁盘/网络读写]

按CPU计算时间与I/O时间的比例：

  • 计算密集型
  • I/O密集型

进程的调度一定要 考虑到 负载的特征workload

相应的再实行相应的调度算法

调度时机

  • 进程退出
  • 进程在I/O或信号量上阻塞
  • 创建新进程
  • I/O中断发生
  • 时钟中断发生
    • 抢占式：执行时可以被打断
    • 非抢占式

调度算法

  • 操作系统决定进程运行的向后顺序
  • 调度器：执行
  • 调度算法：如何调度

不同的应用场景：[很难有普适的适用于任何场景的调度算法]

  • 批处理系统
  • 交互式系统
  • 实时系统

目标

  • 共同的目标：公平策略强平衡
  • 批处理系统：最大的吞吐量(批处理没有交互，单位时间内能处理更多，即最大化CPU利用率)
  • 交互式系统：立刻有相应，最小化响应时间，均衡性
  • 实时系统：截止时间、可预测性(第二次课程设计)

性能指标

面向时间

吞吐量/CPU利用率/各种设备的均衡利用

面向系统

同样的硬件集群好的调度算法可能给10000个用户提供服务

批处理系统调度

先来先服务FCFS

是比较基础的方法

短作业

预计执行时间短的作业进行CPU的分派。

SJF的变形

最短剩余时间优先

最高响应比优先HRRN

​ 响应比：(等待时间+要求执行时间)/要求执行时间

多级调度(三个层次上进行调度)

  • 准入调度
  • 内存调度
  • CPU调度

交互式系统调度

时间片轮转(Round Robin)

  • 将系统中所有就绪的进程按照FCFS形成队列
  • CPU让进程执行时间片
  • 在时间片结束时，发生时钟中断
  • 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
  • 进程可以未使用完一个时间片，就出让CPU(如阻塞)

时间片长度的确定

  • 时间片长度变化的影响

    • 过长->退化为FCFS
    • 过短->context switch的开销变大了

  • 对响应时间的要求：

    ​ 响应时间=进程数目$\times$时间片长度

    Trade off between those 2.

  • 影响时间片长度的因素：

    • 就绪进程的数目
    • 系统的处理能力

优先级调度

谁的优先级高，先调度谁

  • 静态优先级
  • 动态优先级：在运行时做相应的优先级调整

多类优先级调度

在各类之间采用优先级调度，而各类进程内部采用时间片轮转调度。

多重队列

彩票调度

公平分享调度

实时系统调度

  • 实时调度系统氛围硬实时和软实时

  • 可调度的实时系统

  • 针对多周期的事件流：

    若有周期性事件m个，事件i的周期为Pi,其中每个事件需要Ci秒的CPU时间，

    $\sum_{i=1}^m\frac{C_i}{P_i}\le1$

调度策略与机制

  • 将调度问题分解为调度策略与调度机制

线程调度

  • 线程的实现方式决定线程的调度模式：
    • 用户
    • 内核
  • 用户级线程的阻塞会引起整个进程的阻塞
  • 在用户级线程方式下，可以为应用定制特定的调度器

2.5 MINIX3进程概述

minix3系统结构

minix3微内核结构，是一组进程的集合，内核功能较少，更多的功能由用户进程实现，进程间通过IPC机制进行通信。

minix3的四层结构

  • Kernel 层

  • Device drivers

  • Server process

  • User process

内核层

  • 负责进程的调度
  • 时钟任务
  • 系统任务读写I/O，跨地址空间复制数据
  • C+汇编

设备驱动层

  • 读写I/O端口的数据
  • 不同类型设备需要相应的设备驱动程序
  • 也可以调用其他内核调用

服务器层

  • 进程服务器
    • 创建，终止进程:fork, exec,wait
    • 信号相关的系统调用:alarm,kill
    • 管理内存,brk
  • 文件系统服务器
    • 执行文件系统的调用,read,mount,chdir
  • 再生服务器
    • 启动或重启相关的设备驱动程序

用户进程层

  • 包含所有的用户进程
    • Shell，编辑器，编译器等工具程序
    • 用户运行的程序
    • 守护进程

设备驱动层和服务器层的进程称为系统进程，是操作系统的组成

内核>设备>服务器>用户

Minix系统启动

启动顺序

Bootstrap[引导程序]->boot(boot image)->Kernel->系统任务、时钟任务->系统进程->Init进程->其它用户进程及…

引导映像(boot image)

  • 由boot装载至内存的适当位置
  • 包括多个：内核、进程管理器、filesystem
  • 每个部分都是独立的程序

进程树初始化

  • init进程

MINIX进程间通讯

IPC原语

  • 内核将消息从发送者复制到接受者
  • 系统进程，时钟任务，系统任务只允许与特定的进程通信
  • 当一个进程发送消息，而目标进程尚未开始接收消息时，发送进程将阻塞。
1
send(dest,&message)

notify原语

不会阻塞

对于系统进程，用位图来记录其他系统进程发给它的通知

MINIX进程调度

  • minix3采用多级排队系统，定义为16个队列[16个优先级]

  • 系统任务和时钟任务最高优先级

  • IDLE最低

    当系统无其余有效或就绪时，会使空闲进程在上面跑。

  • 一个进程可以根据不同需要在不同优先级的队列中移动

  • 只有高优先级的队列中没有就绪进程时，才运行低优先级的进程队列。

  • 不同的优先级的时间片长度不一

    • 驱动程序进程和服务器进程需要运行其至阻塞

  • 使用一个改进的轮转调度算法

    • 进程转为非就绪时，从队列中取出，当它再变回就绪时，将其放在队首，分配的时间片 为上次时间片中的剩余时间

    实现不同的调度功能

展开全文 >>

计算机网络W7:P2P/CDN/socket

计算机网络W7:P2P/CDN/socket

P2P architecture

对等：所有的节点既可能是client也可能是server。

examples:

  • file distribution(Bit Torrent)
  • server transmission/client/clients【设一共有NF个bits,最终目的是让每一个client都有一个F】

$\sum u_i$，随着客户端数量的增大，上传负载增大，但是同时server端的服务能力也增大；

$D_{p2p}\ge max{F/u_s,F/d_{min},NF/(u_s+\sum u_i)}$

注意这里的下界是理论上最小的，但是实质上需要思考的是如何并行，可以做到逼近下界。

v.s. CS 架构【数据来源仅仅是server端】

随着客户端数量的增大，上传负载增大，但是负载不会被分担。

P2P file distribution: BitTorrent

peer

  1. 哪些可以使用？[可供数据交换]

  2. 一个大的数据包被划分成chunk，但是chunk有可能是被损坏的，如何检查chunk是否是完整的?

    计算块的哈希值【默克尔的】

    P2P保证块的完整性

  3. 如何拿到完整的以后不再贡献带宽，即如何保证不打边撤就走?

    IPFS：激励机制，使用激励机制来完成，可以避免节点自私的离开。[星际文件]

    结对条件/协议设计条件：索取的时候即一定要付出。

Bit Torrent预防问题3的技术手段：[一报还一报/投桃报李]

  • 某个peer维护其拿数据最快的4个邻居节点[跟自己的速率匹配，且是最快的4个伴侣top4]，同样，也它的数据也给其邻居节点发送。
  • 这4个伴侣会与alice相互交换。
  • 即拿数据时结成对子。

当节点的速率发生变化时：

​ 以固定的时间间隔检验是否节点速率发生变化；

​ 每固定的时间间隔随机选4个邻居外的另外一个[测别的邻居]，如果好，则进行邻居的迭代与淘汰。

我永远都在寻找与我速率最匹配的4个人。

最稀缺优先

当一块数据我好几个邻居有，别的一块数据只有一个邻居有，这是我会把只有一个邻居有的拿过来。

对于整个网络来说，如果存储了相同的副本，实质上是没有较大意义的。

CDN 视频内容分发网络

  • 像素：数据阵列
  • 上下帧之间传输的可能只是差异[增量]

DASH协议

Dynamic,Adaptive,Streaming over HTTP

  • server:

    • divides video file into multiple chunks
    • Each Chunk stored, encoded at different rates
    • manifest file:

  • client:

    • 周期性测量带宽
    • 等

  • what is related to HTTP:

    ​ client端

    • when to request chunk：缓存机制
    • What编码速率(拿什么)
    • 哪里去拿:看那个清单

内容分发网

  • 深入：视频服务器深入到各个ISP的网络中
  • 邀请做客：IXP(internet exchange point)。
  • 不是单点的，而是部署在离用户较近的点。

OOT

CDN遇到的challenge

内容服务商

将内容爬下来/建倒排索引(key word)

搜索引擎/爱奇艺等都是内容提供商

socket programming /UDP /TCP

应用进程和传输进程交换的门

传输层的协议:UDP(不可靠的报文:摸着石头过河)/TCP(3次握手，面向连接的可靠的，建桥先)

Socket 编程：不同机器(终端)上的两个进程间的相互通讯

CS机构下，两台机器上两个进程

  1. client端读取数据发给server
  2. server端转换成大写
  3. 大写发给client
  4. client展示到屏幕

UDP 过程

  • sender直接通过receiver的IP和端口号进行发送

  • 接收者收到数据发送回去时，IP和端口从收到的报文(sender发送的)中解析出来。

    没有连接的知道对方的过程

  • Client：主动发起连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from socket import *
serverName='hostname'
serverPort=##1024以后的不保留，随便选
clientSocket=socket()
message=raw_input()
clientSocket.sendto()
##发送，是不同进程上交互的过程
modifiedMessage,serverAddress=
print()
##UDP server
serverPort=#注意这里的socket的端口号要约定好
serverSocket=
serverSocket.bind()
#busy loop():
	message,clientAddress=##地址解析出来

TCP过程

  1. 建立连接，server端监听
  2. client 建立TCP连接
  3. 允许server同时与多个client端进行交互

注意TCP和UDP的差别

  • ​ server先建立连接，监听
    • server端先运行，一个程序先运行
  • client发起连接，server accept，相当于socket建立，连接建立完成
  • 通过连接，在连接的socket上发送消息
  • 两端都需要关闭。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
##TCPClinet
SOCK_STREAM
serverName=
ServerPort=
AF_INET#ipv4
connet((serverName,ServerPort))
#没有servername：IP地址也可以
#建立连接：发送，接受，print，

##TCPServer
serverSocket.listen(1)
循环:
  接受
  拿数据
  大写
  发送回去
关闭

一台机器即可以做client也可以做server，利用机器上的网卡交换信息，此时只要约定一个端口号，即在本地完成。

TCP程序一定要让server先运行起来！

也可以运行多个client端，但每个client端要注意区分?

即TCP的一对多。

展开全文 >>

本站总访问量次

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br><br>个人随笔笔记为主<br>有很多不足<br>谢谢大家～<br><br>可以搜索我的微信号联系我：Habseligkeit030<br><br><br>也可以给我发邮件xinning_chi@163.com