一些前端小知识查漏补缺

HttpOnly

HttpOnly是加在cookies上的一个标识,用于告诉浏览器不要向客户端脚本(document.cookie或其他)暴露cookie。

1
Set-Cookie: Name=Value; expires=Wednesday, 01-May-2020 12:45:10 GMT; HttpOnly

HttpOnly知会浏览器在保存cookie,但不要向客户端脚本开放访问权限。

另外还有一个安全标识可以强制浏览器发送cookie的时候采用安全通道,比如HTTPS,可以防止被监听。尤其是在HTTPS连接被一些工具(比如SSLStrip等)降级到HTTP。
该语法为:

1
Set-Cookie: Name=Value; expires=Wednesday, 01-May-2020 12:45:10 GMT; Secure

Secure标识知会浏览器使用安全的加密通道发送cookie。

defer和async的区别

img

当浏览器碰到 script 脚本的时候:

没有 defer 或 async,浏览器会立即加载并执行指定的脚本,“立即”指的是在渲染该 script 标签之下的文档元素之前,也就是说不等待后续载入的文档元素,读到就加载并执行。

有 async,加载和渲染后续文档元素的过程将和 script.js 的加载与执行并行进行(异步)。

有 defer,加载后续文档元素的过程将和 script.js 的加载并行进行(异步),但是 script.js 的执行要在所有元素解析完成之后,DOMContentLoaded 事件触发之前完成。

Load 事件触发代表页面中的 DOM,CSS,JS,图片已经全部加载完毕。DOMContentLoaded 事件触发代表初始的 HTML 被完全加载和解析,不需要等待 CSS,JS,图片加载。

实用角度

然后从实用角度来说呢,首先把所有脚本都丢到 </body> 之前是最佳实践,因为对于旧浏览器来说这是唯一的优化选择,此法可保证非脚本的其他一切元素能够以最快的速度得到加载和解析。

接着,我们来看一张图:
img

  • 蓝色线代表网络读取,
  • 红色线代表执行时间,这俩都是针对脚本的;
  • 绿色线代表 HTML 解析。

此图告诉我们以下几个要点:

  • defer 和 async网络读取(下载)这块儿是一样的,都是异步的(相较于 HTML 解析)
  • defer 和 async的差别在于脚本下载完之后何时执行,显然 defer 是最接近我们对于应用脚本加载和执行的要求的
  • 关于 defer,此图未尽之处在于它是按照加载顺序执行脚本的,这一点要善加利用
  • async 则是一个乱序执行的主,反正对它来说脚本的加载和执行是紧紧挨着的,所以不管你声明的顺序如何,只要它加载完了就会立刻执行
  • 仔细想想,async 对于应用脚本的用处不大,因为它完全不考虑依赖(哪怕是最低级的顺序执行),不过它对于那些可以不依赖任何脚本或不被任何脚本依赖的脚本来说却是非常合适的,最典型的例子:Google Analytics

总结

  • async : 并行加载js,下载完毕立即解释执行代码,不会按照页面上的script顺序执行。
  • defer : 并行下载js,在页面解析完毕之后,会按照页面上的script标签的顺序执行,同时会在document的DOMContentLoaded之前执行。
    • 注: HTML5规范要求脚本执行应该按照脚本出现的先后顺序执行,但实际情况下,延迟脚本不一定按照先后顺序执行
  • 原文链接: defer和async的区别 - qiqi715 - 博客园 (cnblogs.com)

meta标签

meta是html语言head区的一个辅助性标签。移动前端开发中添加一些专属的HTML5头部标签,帮助浏览器更好解析HTML代码,更好地将移动web前端页面表现出来。
meta标签的作用有:搜索引擎优化(seo),定义页面使用语言,自动刷新并指向新的页面,实现网页转换时的动态效果,控制页面缓冲,网页定级评价,控制网页显示的窗口等等等等!
meta标签的组成:共有两个属性,它们分别是name属性和http-equiv属性,不同的属性又有不同的参数值,这些不同的参数值就实现了不同的网页功能。

name属性主要用于描述网页,与之对应的属性值为content,content中的内容主要是便于搜索引擎机器人查找信息和分类信息用的。

……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
<!DOCTYPE html> <!-- 使用 HTML5 doctype,不区分大小写 -->
<html lang="zh-cmn-Hans"> <!-- 更加标准的 lang 属性写法 http://zhi.hu/XyIa -->
<head>
<!-- 声明文档使用的字符编码 -->
<meta charset='utf-8'>
<!-- 优先使用 IE 最新版本和 Chrome -->
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"/>
<!-- 页面描述 -->
<meta name="description" content="不超过150个字符"/>
<!-- 页面关键词 -->
<meta name="keywords" content=""/>
<!-- 网页作者 -->
<meta name="author" content="name, [email protected]"/>
<!-- 搜索引擎抓取 -->
<meta name="robots" content="index,follow"/>
<!-- 为移动设备添加 viewport -->
<meta name="viewport" content="initial-scale=1, maximum-scale=3, minimum-scale=1, user-scalable=no">
<!-- `width=device-width` 会导致 iPhone 5 添加到主屏后以 WebApp 全屏模式打开页面时出现黑边 http://bigc.at/ios-webapp-viewport-meta.orz -->


<!-- iOS 设备 begin -->
<meta name="apple-mobile-web-app-title" content="标题">
<!-- 添加到主屏后的标题(iOS 6 新增) -->
<meta name="apple-mobile-web-app-capable" content="yes"/>
<!-- 是否启用 WebApp 全屏模式,删除苹果默认的工具栏和菜单栏 -->

<meta name="apple-itunes-app" content="app-id=myAppStoreID, affiliate-data=myAffiliateData, app-argument=myURL">
<!-- 添加智能 App 广告条 Smart App Banner(iOS 6+ Safari) -->
<meta name="apple-mobile-web-app-status-bar-style" content="black"/>
<!-- 设置苹果工具栏颜色 -->
<meta name="format-detection" content="telphone=no, email=no"/>
<!-- 忽略页面中的数字识别为电话,忽略email识别 -->
<!-- 启用360浏览器的极速模式(webkit) -->
<meta name="renderer" content="webkit">
<!-- 避免IE使用兼容模式 -->
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<!-- 不让百度转码 -->
<meta http-equiv="Cache-Control" content="no-siteapp" />
<!-- 针对手持设备优化,主要是针对一些老的不识别viewport的浏览器,比如黑莓 -->
<meta name="HandheldFriendly" content="true">
<!-- 微软的老式浏览器 -->
<meta name="MobileOptimized" content="320">
<!-- uc强制竖屏 -->
<meta name="screen-orientation" content="portrait">
<!-- QQ强制竖屏 -->
<meta name="x5-orientation" content="portrait">
<!-- UC强制全屏 -->
<meta name="full-screen" content="yes">
<!-- QQ强制全屏 -->
<meta name="x5-fullscreen" content="true">
<!-- UC应用模式 -->
<meta name="browsermode" content="application">
<!-- QQ应用模式 -->
<meta name="x5-page-mode" content="app">
<!-- windows phone 点击无高光 -->
<meta name="msapplication-tap-highlight" content="no">
<!-- iOS 图标 begin -->
<link rel="apple-touch-icon-precomposed" href="/apple-touch-icon-57x57-precomposed.png"/>
<!-- iPhone 和 iTouch,默认 57x57 像素,必须有 -->
<link rel="apple-touch-icon-precomposed" sizes="114x114" href="/apple-touch-icon-114x114-precomposed.png"/>
<!-- Retina iPhone 和 Retina iTouch,114x114 像素,可以没有,但推荐有 -->
<link rel="apple-touch-icon-precomposed" sizes="144x144" href="/apple-touch-icon-144x144-precomposed.png"/>
<!-- Retina iPad,144x144 像素,可以没有,但推荐有 -->
<!-- iOS 图标 end -->

<!-- iOS 启动画面 begin -->
<link rel="apple-touch-startup-image" sizes="768x1004" href="/splash-screen-768x1004.png"/>
<!-- iPad 竖屏 768 x 1004(标准分辨率) -->
<link rel="apple-touch-startup-image" sizes="1536x2008" href="/splash-screen-1536x2008.png"/>
<!-- iPad 竖屏 1536x2008(Retina) -->
<link rel="apple-touch-startup-image" sizes="1024x748" href="/Default-Portrait-1024x748.png"/>
<!-- iPad 横屏 1024x748(标准分辨率) -->
<link rel="apple-touch-startup-image" sizes="2048x1496" href="/splash-screen-2048x1496.png"/>
<!-- iPad 横屏 2048x1496(Retina) -->

<link rel="apple-touch-startup-image" href="/splash-screen-320x480.png"/>
<!-- iPhone/iPod Touch 竖屏 320x480 (标准分辨率) -->
<link rel="apple-touch-startup-image" sizes="640x960" href="/splash-screen-640x960.png"/>
<!-- iPhone/iPod Touch 竖屏 640x960 (Retina) -->
<link rel="apple-touch-startup-image" sizes="640x1136" href="/splash-screen-640x1136.png"/>
<!-- iPhone 5/iPod Touch 5 竖屏 640x1136 (Retina) -->
<!-- iOS 启动画面 end -->

<!-- iOS 设备 end -->
<meta name="msapplication-TileColor" content="#000"/>
<!-- Windows 8 磁贴颜色 -->
<meta name="msapplication-TileImage" content="icon.png"/>
<!-- Windows 8 磁贴图标 -->

<link rel="alternate" type="application/rss+xml" title="RSS" href="/rss.xml"/>
<!-- 添加 RSS 订阅 -->
<link rel="shortcut icon" type="image/ico" href="/favicon.ico"/>
<!-- 添加 favicon icon -->

<!-- sns 社交标签 begin -->
<!-- 参考微博API -->
<meta property="og:type" content="类型" />
<meta property="og:url" content="URL地址" />
<meta property="og:title" content="标题" />
<meta property="og:image" content="图片" />
<meta property="og:description" content="描述" />
<!-- sns 社交标签 end -->

<title>标题</title>
</head>

毕业设计项目流程

技术选型

2021年9月12日 放弃微服务架构.

前端

VUE,NEXT,ElementUI

后端

Springboot Springcloud(TODO) MbatisPlus

项目模块

总体基于咖啡厅(模块进行扩展

权限管理模块-RenrenFast 3

通讯模块

负责项目通讯似于QQ,提供通讯服务

TODO 模块

  1. 添加任务

    1. 设置任务类型 : 类型包括 一次,重复
      2. 设置截止时间
      3. 设置所属任务
      4. 设置是否星标
      5. 设置备注
      6. 设置关联文章
      7. 添加子任务
  2. 筛选/检索

    1. 按标记筛选

    2. 按任务组筛选

    3. 标题

    4. 是否关联文章

其他:

​ CRUD

项目待完善

网盘模块

基于阿里云OSS 实现简单的CRUD

咖啡厅

动态

展示 日记 动态

博客

个人的博客园

image-20211012083056186

数据库表设计:

日记模块

是否公开

可设置文章标题默认为文章前几个字

添加日记

设置日期

心情

添加日记 可设置类型 日记/总结

时间轴

可以单独查看 日记 和 总结 也可以合并

ID,创建日期,content,是否公开,副标题,类型

image-20210707214539419

影院

休闲娱乐

无需数据库

一起看

小工具

神奇的工具箱

前端开发

基本框架

image-20210602144146078

数据格式

左侧Navbar功能菜单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
funList: [
{
icon: 'http://q1.qlogo.cn/g?b=qq&nk=2513356652&s=640',
title: '待办',
routeTo: {path: '/todo'} // 路由跳转
},
{
icon: 'http://q1.qlogo.cn/g?b=qq&nk=2513356652&s=640',
title: '项目',
routeTo: {path: '/project'}
},
{
icon: 'http://q1.qlogo.cn/g?b=qq&nk=2513356652&s=640',
title: '日历',
routeTo: {path: '/calendar'}
},
{
icon: 'http://q1.qlogo.cn/g?b=qq&nk=2513356652&s=640',
title: '网盘',
routeTo: {path: '/files'}
}
]

页面

登录第一屏

image-20210601204429116

登录第二屏

首页

image-20210602155054422

TODO代办

image-20210601204521467

项目

image-20210601204532211

image-20210601204550982

image-20210601204634121

image-20210601204641372

image-20210601204657054

image-20210609144828321

日历

image-20210601204718115

网盘

image-20210601204843548

// Alibaba

咖啡厅

影视,社区,娱乐

image-20210609153437979

后端开发

数据库设计

  • 博客

  • 论坛

    • 优化表结构

    • 关注表

      image-20210902111440563

## 功能模块列表

权限管理模块

ToDO

功能列表:

添加CRUD,

项目规划

文件系统

咖啡厅模块

社区

影视

日记

影视模块

功能需求

网络资源采集 360影视

社区模块

TODO待办模块

网盘

项目待办

数据库设计

基本架构

功能

CRUD,异常处理,权限认证Token,

协同办公,通讯模块

  • 及基本架构

    • 权限管理
    • 用户认证
    • 后台系统
  • 社区模块

    • 基本功能开发
      • 日记
  • 通讯模块

    创建聊天组

    用户通讯

流程记录

项目准备(BUG)

数据库

CRUD

  • MybatisPlus

    1. Springboot Pom 2种方式

    2. 默认错误Error - 未导入thymeleaf 依赖无法解析

    3. SpringBoot测试空指针异常 - 导错junit4,SpringBootTest 指定

      异常:

1
Unable to find a @SpringBootConfiguration, you need to use @ContextConfiguration or @SpringBootTest(classes=...) with your test

​ @SpringBootTest(classes = Application.class) 指定启动类

项目结构

依赖参考:

1
2
3
4
5
6
7
8
  <modelVersion>4.0.0</modelVersion>

<groupId>org.example</groupId>
<artifactId>Test</artifactId>
<version>1.0-SNAPSHOT</version>

<module>ToDoProject</module>
</modules>
1
2
3
4
5
6
7
<parent>
<artifactId>TeamProjectEnd</artifactId>
<groupId>com.xxhoz</groupId>
<version>1.0-SNAPSHOT</version>
</parent>
<modelVersion>4.0.0</modelVersion>
<artifactId>ToDoProject</artifactId>

异常处理

  • Common模块

    切面日志

    异常处理

    字段验证

    Utils工具类

搭建项目结构解决依赖

分布式服务搭建-认证服务

后端技术

  • SpringBoot
  • Spring Security
  • JWT
  • MyBatis
  • Druid
  • Fastjson

前端技术

  • Vue
  • Vuex
  • Element-ui
  • Axios
  • Sass
  • Quill

后台系统

博客模块

ToDo模块

影视模块

通讯模块

随手记

社区,影视,TODO,通讯

image-20210909152356191

社区模块

基于人人fast快速开发,添加一个注册功能.权限管理由renren-fast接管,专注开发业务.

用户注册

用户配置

发布文章

分类区分板块:

​ 博客,日记,

将博客系统改造为多人

用户通讯 TODO

  • TODO

  • 按需开发

Video

  • 通用解析模块

通讯模块

2021年9月12日

​ 放弃微服务架构.

2021年9月14日:

​ 新环境搭建 - 依赖BUG

2021年9月15日:

​ 无依赖问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<dependencyManagement>
<dependencies>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-dependencies</artifactId>
<version>2.3.2.RELEASE</version>
<type>pom</type> <!-- 没加这两行!!!!!! -->
<scope>import</scope>
<!-- import只能用在dependencyManagement块中,它将spring-boot-dependencies 中 dependencyManagement下的dependencies插入到当前工程的dependencyManagement中,所以不存在依赖传递。
当没有<scope>import</scope>时,意思是将spring-boot-dependencies 的dependencies全部插入到当前工程的dependencies中,并且会依赖传递。
-->
</dependency>
</dependencies>
</dependencyManagement>

奇奇怪怪的依赖问题

搞了三个小时项目结构~! 细节问题

2021年9月16日:

​ 搞项目结构第三天遇到奇奇怪怪的BUG折磨不同包下出现Bean异常,放到相同路径就没问题.捣鼓最后还是吧fast包路劲改成com.xxhoz浪费几天时间项目还没开始业务逻辑编写~

2021年9月18日:

​ 这两天还是浪了~知识忘了,依赖循环IDEA小BUG

​ mybatisplus @TableField(exist = false) 自定义map可用

2021年9月20日:

​ 社区基本CRUD完成,Mybatsi-Plus 就是方便~

​ 开始编写TODO板块

2021年9月22日:

​ 编写影视爬虫部分

​ 通用爬取工具

2021年9月23日:

​ 抽离公共用户注册登录接口 …..

2021年9月27日:

​ Websoket stomp!! 网上文章乱七八糟~还是得看看源码

1
2
3
4
5
6
7
8
9
@SendTo@SendToUser 是Spring的STOMP协议中注解的标签。
@SendTo
会将接收到的消息发送到指定的路由目的地,所有订阅该消息的用户都能收到,属于广播。

@SendToUser
消息目的地有UserDestinationMessageHandler来处理,会将消息路由到发送者对应的目的地。默认该注解前缀为/user。如:用户订阅/user/hi ,在@SendToUser('/hi')查找目的地时,会将目的地的转化为/user/{name}/hi, 这个name就是principal的name值,该操作是认为用户登录并且授权认证,使用principal的name作为目的地标识。发给消息来源的那个用户。(就是谁请求给谁,不会发给所有用户,区分就是依照principal-name来区分的)。

此外该注解还有个broadcast属性,表明是否广播。就是当有同一个用户登录多个session时,是否都能收到。取值true/false.

2021年9月28日:

​ websocket token认证 由后端携带用户ID生成 token websocket连接中cookie携带token进行认证 websocket握手前认证 http阶段进行

2021年9月29日:

​ 捣鼓前端页面之前创建了一个是ts项目发现用不到,Parameter ‘XXX’ implicitly has an ‘any’ type,

1
2
3
4
配置文件:
"strict": false,
或添加
"noImplicitAny": false,
axios 使用配置~~忘了搞了老久~ 突然又从新理解了promise和async await~ 忘得差不多

2021年9月30日:

Vue style里面使用@import引入外部css, 作用域是全局的解决方案 - 宝,卡粉了 - 博客园 (cnblogs.com)

2021年10月3日:

​ 这几天啥也没干~

​ 项目待办:前端完善,TODO,社区,影视,后端优化,全局弹窗提示

​ 前端优化:路由优化,依赖优化,结构,页面优化

​ 计划:

​ 前端小优化:路由 ,页面调整, 熟悉配置,前端复习 1天

​ TODO后端完善后台联调 2天

​ 社区功能开发-包括前端页面 5天

​ 影视功能开发 2天

​ 通讯功能

​ 系统监控,完善日志系统

​ 网站首页

​ 文本编辑器

2021年10月9日:

​ 前端小优化: 路由 , 页面调整, 熟悉配置, 前端复习 1天

​ TODO 后端完善后台联调 2天

2021年10月10日:

​ 值传递报错 TODO

​ 修改TODO状态 mybatis-plus构造器

​ 传值~ 提交组件BUG

​ 无法父子传值原因:

1
2
3
props: {
msg:String
},

​ TODO基本完成,添加注册页面

​ 通讯界面基本框架

2021年10月11日:

注册功能完成 - 修改页面浪费时间

添加SQL拦截权限校验

重复校验 实现分析

.

系统监控

影视通用爬虫

博客页面

2021年10月13日 :

​ 博客前端页面编写

2021年10月14日:

​ 用户数据权限认证 通过MybatisPlus拦截无法获取到userId… 解决: 未登录获取不到!! 添加异常处理

2021年10月15日:

END

《操作系统导论》第9章调度-比例份额

在本章中,我们来看一个不同类型的调度程序——比例份额(proportional-share)调度程序,有时也称为公平份额(fair-share)调度程序。比例份额算法认为,调度程序的最终目标是确保每个工作获得一定比例的CPU时间,而不是优化周转时间和响应时间。它的基本思想很简单:每隔一段时间,都会举行一次彩票抽奖,以确定接下来应该运行哪个进程。越是应该频繁运行的进程,越是应该拥有更多地赢得彩票的机会。关键的问题就是,如何设计调度程序来按比例分配CPU?

使用彩票数表示份额

在彩票调度中,彩票数代表了进程占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比,就是它占有资源的份额。假设有两个进程A和B,A拥有75张彩票,B拥有25张。因此我们希望A占用75%的CPU时间,而B占用25%。

通过不断且定时地抽取彩票,彩票调度从概率上获得这种份额比例。抽取彩票的过程很简单:调度程序知道总共的彩票数(在我们的例子中,有100张)。调度程序抽取中奖彩票,这是从0和99之间的一个数,拥有这个数对应的彩票的进程中奖。假设进程A拥有0到74共75张彩票,进程B拥有75到99的25张,中奖的彩票就决定了运行A或B。调度程序然后加载中奖进程的状态,并运行它。彩票调度利用了随机性,这导致了从概率上满足期望的比例。随着这两个工作运行得时间越长,它们得到的CPU时间比例就会越接近期望。

随机方法相对于传统的决策方式,至少有3点优势。第一,随机方法常常可以避免奇怪的边角情况,较传统的算法(LRU替换策略)可能在处理这些情况时遇到麻烦。虽然LRU通常是很好的替换算法,但在有重复序列的负载时表现非常差。随机方法就没有这种最差情况。

第二,随机方法很轻量,几乎不需要记录任何状态。在传统的公平份额调度算法中,记录每个进程已经获得了多少的CPU时间,需要对每个进程计时,这必须在每次运行结束后更新。而采用随机方式后每个进程只需要非常少的状态(即每个进程拥有的彩票号码)。

第三,随机方法很快。只要能很快地产生随机数,做出决策就很快。因此,随机方式在对运行速度要求高的场景非常适用。当然,越是需要快的计算速度,随机就会越倾向于伪随机。

彩票机制

彩票调度还提供了一些机制,以不同且有效的方式来调度彩票。一种方式是利用彩票货币(ticket currency)的概念。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币,将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。

比如,假设用户A和用户B每人拥有100张彩票。用户A有两个工作A1和A2,他以自己的货币,给每个工作500张彩票(共1000张)。用户B只运行一个工作,给它10张彩票(总共10张)。操作系统将进行兑换,将A1和A2拥有的A的货币500张,兑换成全局货币50张。类似地,兑换给B1的10张彩票兑换成100张。然后会对全局彩票货币(共200张)举行抽奖,决定哪个工作运行。

1
2
3
User A -> 500 (A's currency) to A1 ->  50 (global currency)
-> 500 (A's currency) to A2 -> 50 (global currency)
User B -> 10 (B's currency) to B1 -> 100 (global currency)

另一个有用的机制是彩票转让(ticket transfer)。通过转让,一个进程可以临时将自己的彩票交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用,在这种场景中,客户端进程向服务端发送消息,请求其按自己的需求执行工作,为了加速服务端的执行,客户端可以将自己的彩票转让给服务端,从而尽可能加速服务端执行自己请求的速度。服务端执行结束后会将这部分彩票归还给客户端。

最后,彩票通胀(ticket inflation)有时也很有用。利用通胀,一个进程可以临时提升或降低自己拥有的彩票数量。当然在竞争环境中,进程之间互相不信任,这种机制就没什么意义。一个贪婪的进程可能给自己非常多的彩票,从而接管机器。但是,通胀可以用于进程之间相互信任的环境。在这种情况下,如果一个进程知道它需要更多CPU时间,就可以增加自己的彩票,从而将自己的需求告知操作系统,这一切不需要与任何其他进程通信。

实现

彩票调度实现起来非常简单,只需要一个随机数生成器来选择中奖彩票和一个记录系统中所有进程的数据结构,以及所有彩票的总数。假设我们使用列表记录进程,下面的例子中有A、B和C这3个进程,每个进程有一定数量的彩票。

img

在做出调度决策之前,首先要从彩票总数400中选择一个随机数。假设这里选择了300,然后我们遍历链表,用一个计数器帮我们找到这个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// counter: used to track if we've found the winner yet
int counter = 0;

// winner: use some call to a random number generator to
// get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);

// current: use this to walk through the list of jobs
node_t *current = head;

// loop until the sum of ticket values is &gt; the winner
while (current) {
counter = counter + current->tickets;
if (counter < winner) break; // found the winner
current = current->next;
} // 'current' is the winner: schedule it...

这段代码从前向后遍历进程列表,将每张票的值加到counter上,直到值超过winner。这时,当前的列表元素所对应的进程就是中奖者。在我们的例子中,中奖彩票是300。首先,计A的票后,counter增加到100。因为100小于300,继续遍历。然后counter会增加到150(B的彩票),仍然小于300,继续遍历。最后,counter增加到400(显然大于300),因此退出遍历,current指向C(中奖者)。一个更有效率的做法是将列表项按照彩票数递减排序。这个顺序并不会影响算法的正确性,但能保证用最小的迭代次数找到需要的节点,尤其当大多数彩票被少数进程掌握时。

一个例子

为了更好地理解彩票调度的运行过程,我们现在简单研究一下两个互相竞争工作的完成时间,每个工作都有相同数目的100张彩票,以及相同的运行时间RR,我们希望两个工作在大约同时完成,由于彩票调度算法的随机性,有时一个工作会先于另一个完成。为了量化这种区别,我们定义了一个简单的不公平指标UU(unfairness metric),将两个工作完成时刻相除得到UU的值。比如,运行时间RR为10,第一个工作在时刻10完成,另一个在20,那么U=10/20=0.5U=10/20=0.5。如果两个工作几乎同时完成,UU的值将很接近于1。因此,完美的公平调度程序可以做到U=1U=1。

img

上图展示了当两个工作的运行时间从1到1000变化时,30次试验的平均UU值。可以看出,当工作执行时间很短时,平均不公平度非常糟糕。只有当工作执行非常多的时间片时,彩票调度算法才能得到期望的结果。

如何分配彩票#

关于彩票调度的一个关键问题就是如何为工作分配彩票?这是一个非常棘手的问题,系统的运行严重依赖于彩票的分配。假设用户自己知道如何分配,因此可以给每个用户一定量的彩票,由用户按照需要自主分配给自己的工作。然而这种方案似乎什么也没有解决——还是没有给出具体的分配策略。因此对于给定的一组工作,彩票分配的问题依然没有最佳答案。

步长调度

步长调度也很简单。系统中的每个工作都有自己的步长,这个值与票数值成反比。在上面的例子中,A、B、C这3个工作的票数分别是100、50和250,我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用10000除以这些票数值,得到了3个进程的步长分别为100、200和40。我们称这个值为每个进程的步长(stride)。每次进程运行后,我们会让它的计数器(称为行程值)增加它的步长,记录它的总体进展。

1
2
3
4
current = remove_min(queue);       // pick client with minimum pass
schedule(current); // use resource for quantum
current->pass += current->stride; // compute next pass using stride
insert(queue, current); // put back into the queue

在我们的例子中,3个进程(A、B、C)的步长值分别为100、200和40,初始行程值都为0。因此,所有进程都可能被选择执行。假设选择A,A执行一个时间片后,更新它的行程值为100。然后运行B,并更新其行程值为200。最后执行C,C的行程值变为40。这时,算法选择最小的行程值,是C,执行并增加为80(C的步长是40)。然后C再次运行(依然行程值最小),行程值增加到120。现在运行A,更新它的行程值为200(现在与B相同)。然后C再次连续运行两次,行程值也变为200。此时,所有行程值再次相等,这个过程会无限地重复下去。下表展示了一段时间内调度程序的行为。

img

可以看出,C运行了5次、A运行了2次,B运行了1次,正好是票数的比例——200、100和 50。彩票调度算法只能一段时间后,在概率上实现比例,而步长调度算法可以在每个调度周期后做到完全正确。

既然有了可以精确控制的步长调度算法,为什么还要彩票调度算法呢?相比于步长调度,彩票调度的优势是不需要全局状态。假如一个新的进程在步长调度执行过程中加入系统,应该怎么设置它的行程值呢?设置成0吗?这样的话,它就独占CPU了。而彩票调度算法不需要对每个进程记录全局状态,只需要用新进程的票数更新全局的总票数就可以了。因此彩票调度算法能够更合理地处理新加入的进程。

本章介绍了比例份额调度的概念,并简单讨论了两种实现:彩票调度和步长调度。彩票调度通过随机值做到了按比例分配;步长调度算法能够确定的获得需要的比例。然而两者并没有作为CPU调度程序被广泛使用。一个原因是这两种方式都不能很好地适合I/O;另一个原因则是票数分配问题并没有确定的解决方式。因此,比例份额调度程序只有在这些问题可以相对容易解决的领域更有用。例如在虚拟数据中心中,我们可能会希望分配1/4的CPU周期给Windows虚拟机,剩余的给Linux系统,比例分配的方式可以更简单高效。

计算机组成原理

计算机基本组成

计算机发展史

系统总线

主存储器

组存基本组成

image-20210607164435072

image-20210607165101241

image-20210607170915735

image-20210607171244329

半导体存储芯片简介

image-20210607171533395

image-20210607171819534

image-20210607172149387

image-20210607172539899

image-20210607173538443

大容量不合适

image-20210607173821581

随机存取存储器(RAM)

静态RAM

image-20210607174312334

image-20210607175036685

image-20210607175354624

image-20210607175538379

image-20210607180224272

image-20210607180612549

动态RAM

image-20210607180810065

image-20210608141514515

image-20210608141817898

image-20210608142710641

刷新放大器,维持电容中信息

image-20210608143141920

image-20210608143833683

动态RAM刷新

维持电容状态

刷新与行地址有关

image-20210608144202632

image-20210608144419721

image-20210608144540195

比较

image-20210608144852107

只读存储器

image-20210608145728430

image-20210608150026431

image-20210608150158183

image-20210608150331411

存储器与CPU的连接

image-20210608151021849

存储器容量的扩展

image-20210608151241940

image-20210608151831646

image-20210608152306831

存储器与CPU的连接

image-20210608153516902

存储器的校验

image-20210609090853762

image-20210609091203626

编码的纠错检错能力与编码的最小距离有关

image-20210609091449424

image-20210609092111474

image-20210609092810702

image-20210609093016644

image-20210609093553691

image-20210609093825268

二的倍速

image-20210609094152590

image-20210612145124358

image-20210612145423297

image-20210612150227925

提高访存速度的措施

image-20210612150729326

image-20210612151154609

image-20210612151534142

image-20210612151602809

image-20210612151926417

image-20210612152003299

image-20210612152039299

image-20210612152249799

高速缓冲存储器

image-20210612152632685

image-20210612152933142

image-20210612153314107

image-20210612153439907

image-20210612153830327

image-20210612154117613

image-20210612154619919

image-20210612155015283

image-20210612155209058

image-20210612155436923

主存的地址映射

image-20210612155547448

image-20210612155750657

image-20210612155853274

image-20210612160057857

image-20210612160338865

不灵活 , 成本高

## 辅助存储器

输入输出系统

image-20210614143542496

image-20210614143952995

image-20210614144815552

image-20210614144952799

程序查询方式

image-20210614145254551

image-20210614145532054

image-20210614145856728

程序中断方式

image-20210614150308030

image-20210614150504769

image-20210614150626372

image-20210614150923057

image-20210614151107024

储备知识数电~待学

结束硬件部分~~

数字

image-20210614151356611

image-20210614151622519

image-20210614151637996

无符号数和有符号数

image-20210614152343140

image-20210614152821607

image-20210614153828103

image-20210614154202033

image-20210614154833951

image-20210614155721602

image-20210614160101716

image-20210614160428144

浮点数

image-20210617172252100

image-20210617172719544

image-20210617172951433

image-20210617173322328

image-20210617173410538

image-20210617173820611

计算机的运算方法

image-20210619142829664

image-20210619143819728

image-20210619150527308

image-20210619151025748

image-20210619151409947

image-20210619151752796

image-20210619151837000

image-20210619152208756

image-20210619153822078

image-20210619154716084

image-20210619154145479

image-20210619154804789

image-20210619155440944

image-20210619155951916

image-20210620141356183

image-20210620141720627

image-20210620141942398

image-20210620142039290

image-20210620142452745

image-20210620142647888

image-20210620143143404

image-20210620143742104

image-20210620144618706

image-20210620144847468

image-20210620150825898

image-20210620151000125

image-20210620151424501

image-20210620151529109

image-20210620151559468

image-20210620151611699

image-20210620152214487

image-20210620152720195

image-20210620153117419

image-20210620153350576

算术逻辑单元

image-20210621151620820

image-20210621151913003

image-20210621152234578

image-20210621152554099

image-20210621152736418

image-20210621152911412

image-20210621153036424

image-20210621153227907

image-20210621154301162

image-20210621154336247

image-20210621154359110

image-20210621154456796

image-20210621154532898

指令系统

image-20210621154850709

image-20210621154949395

机器指令

image-20210621155027450

image-20210621155132730

image-20210621155323879

image-20210621160152107

image-20210621160700674

image-20210621161151246

image-20210621161421314

image-20210621162038678

image-20210621162110501

操作数类型和种类

image-20210621162616659

image-20210621162736155

image-20210621162834270

image-20210621163050547

image-20210621163147398

image-20210621163216016

image-20210621163234762

image-20210621163338289

寻找方式

image-20210621163544155

image-20210621163748444

image-20210621163915598

image-20210621164011481

image-20210621164144778

image-20210621164349612

image-20210621164508111

image-20210621164617172

image-20210621164645410

image-20210621164752357

image-20210621164817527

image-20210621164907906

image-20210621165023371

image-20210621165105942

image-20210621165124695

image-20210621165238851

image-20210621165344461

image-20210621165402965

指令格式举例

image-20210622142218196

image-20210622142437482

image-20210622142714780

RISC技术

image-20210622143101546

image-20210622143202378

image-20210622143329690

image-20210622143417663

CPU的结构和功能

image-20210622143749191

image-20210622143957921

image-20210622145519221

CPU的寄存器

image-20210622145804345

指令周期

image-20210622150503806

image-20210622150624230

image-20210622150755901

image-20210622150934854

image-20210622151648814

image-20210622151910189

image-20210622152034447

image-20210622152355148

指令流水

image-20210622152709568

image-20210622152858499

image-20210622153436949

image-20210622153828046

image-20210622153924502

image-20210622154156183

image-20210622154908419

image-20210622154940209

image-20210622155051884

image-20210622155521530

image-20210622155547265

image-20210622155635327

image-20210622155651325

image-20210622155709123

image-20210622155902569

image-20210622155938969

image-20210622160046931

image-20210622160213124

image-20210622160247164

image-20210622160403074

中断系统

image-20210624162844630

image-20210624163211904

image-20210624163359876

image-20210624163932927

image-20210624164001891

image-20210624164108169

image-20210624164501575

image-20210624164650141

image-20210624164953686

image-20210624165131550

image-20210624165317481

image-20210624165506983

image-20210624165757803

image-20210624165933969

image-20210624170107892

image-20210624170154838

image-20210624170240775

image-20210624170423482

image-20210624170652761

控制单元

image-20210624171031209

image-20210624171337028

image-20210624171446984

image-20210624171651696

image-20210624171911704

image-20210624171946361

image-20210624172027420

image-20210624172052261

《操作系统导论》第7章进程调度介绍

探讨可能的调度策略之前,我们先做一些简化假设。这些假设与系统中运行的进程有关,有时候统称为工作负载(workload)。确定工作负载是构建调度策略的关键部分。这里做的工作负载假设是不切实际的,但我们会逐渐放宽这些假定,并最终开发出一个完全可操作的调度准则。

我们对操作系统中运行的进程(有时也叫工作任务)做出如下的假设:

  1. 每一个工作运行相同的时间
  2. 所有的工作同时到达
  3. 一旦开始,每个工作保持运行直到完成
  4. 所有的工作只使用CPU(即没有I/O操作)
  5. 每个工作的运行时间是已知的

评价指标

除了做出工作负载假设之外,还需要一个东西能让我们比较不同的调度策略:调度指标。任务的周转时间TturnaroundTturnaround定义为任务完成时间TcompletionTcompletion减去任务到达系统的时间TarrivalTarrival。更正式的周转时间定义为:

T响应时间= T首次运行−T到达时间

注意到,周转时间是一个性能指标,而另一个有趣的指标是公平。性能和公平在调度系统中往往是矛盾的。例如,调度程序可以优化性能,但代价是以阻止一些任务运行,这就降低了公平。

先进先出(FIFO)

最基本的算法被称为先进先出(First In First Out)调度,有时候也称为先到先服务(First Come First Served)。它很简单,易于实现,而且对于目前的假设效果不错。

img

假设3个工作A、B和C在大致相同的时间到达系统。因为FIFO必须将某个工作放在前面,所以我们假设当它们都同时到达时,A比B早一点点,然后B比C早到达一点点。假设每个工作运行10s,从图上可以看出,A在10s时完成,B在20s时完成,C在30s时完成。因此,这3个任务的平均周转时间就是(10+20+30)/3=20s(10+20+30)/3=20s。

现在,我们放宽假设1,每个任务的运行时间不再相同。这种情况下FIFO的表现如何?具体来说,我们再次假设3个任务(A、B和C),但这次A运行100s,而B和C运行10s。

img

如图所示,A先运行100s,B或C才有机会运行。因此,系统的平均周转时间是比较高的(100+110+120)/3=110s(100+110+120)/3=110s。这个问题通常被称为护航效应(convoy effect),一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后。

最短任务优先(SJF)

事实上,我们一个非常简单的方法来解决护航问题。这个新的调度准则被称为最短任务优先(Shortest Job First,SJF),即先运行最短的任务,然后是次短的任务,以此类推。

img

还是上面的例子,但这次以SJF作为调度策略。上图展示的是运行A、B和C的结果。通过在A之前运行B和C,SJF将平均周转时间从110s降低到(10+20+120)/3=50s(10+20+120)/3=50s。在所有工作同时到达的情况下,可以证明SJF是一个最有调度算法。

现在,让我们放宽假设2,即工作可以随时到达,而不是同时到达。假设A在t=0时到达,且需要运行100s。而B和C在t=10时到达,且各需要运行10s。使用SJF,可以得到如下所示的调度。

img

从图中可以看出,即使B和C在A之后不久到达,它们仍然被迫等到A完成,从而遭遇同样的护航问题。这3项工作的平均周转时间为(100+(110−10)+(120−10))/3=103.33s(100+(110−10)+(120−10))/3=103.33s。

最短完成时间优先(STCF)

为了解决这个问题,需要放宽假设3(工作必须保持运行直到完成)。也就是说,当B和C到达时,调度程序可以做其他事情:它可以抢占(preempt)工作A,并决定运行另一个工作,或许稍后继续工作A。根据我们的定义,SJF是一种非抢占式(non-preemptive)调度程序,因此还是存在护航问题。

通过向SJF添加抢占,我们可以得到最短完成时间优先(Shortest Time-to-Completion First,STCF)调度程序。每当新工作进入系统时,它就会确定剩余工作和新工作中,谁的剩余时间最少,然后调度该工作。因此,在我们的例子中,STCF将抢占A并运行B和C以完成。只有在它们完成后,才能调度A的剩余时间。

img

根据上图,3项工作的平均周转时间是((20−10)+(30−10)+120)/3=50s((20−10)+(30−10)+120)/3=50s。基于新的假设,可证明STCF是最优的。

响应时间

如果我们知道任务长度,任务只使用CPU,且唯一的衡量是周转时间,那么STCF将是一个很好的策略。然而,引入分时系统改变了这一切。现在,用户将会坐在终端前面,同时也要求系统的交互性好。因此,一个新的度量标准诞生了:响应时间(response time),它定义为任务到达系统到首次运行该任务的时间:

T响应时间= T首次运行−T到达时间

显然,STCF和相关方法在响应时间上并不是很好。如果3个工作同时到达,第三个工作必须等待前两个工作全部运行后才能运行。这种方法虽然有很好的周转时间,但对于响应时间和交互性是相当糟糕的。

轮转(RR)

为了提高响应时间,我们将引入轮转(Round-Robin,RR)调度。其基本思想很简单:在一个时间片内运行一个工作,然后切换到运行队列中的下一个任务,而不是运行一个任务直到结束,它反复执行,直到所有任务完成。注意,时间片长度必须是时钟中断周期的倍数。因此,如果时钟中断是每10ms中断一次,则时间片可以是10ms、20ms或10ms的任何其他倍数。

假设3个任务A、B和C在系统中同时到达,并且它们都希望运行5s。如下所示,SJF调度程序必须运行完当前任务才可运行下一个任务,其平均响应时间是(0+5+10)/3=5s(0+5+10)/3=5s。

img

相比之下,1s时间片的RR可以快速地循环工作,其平均响应时间为(0+1+2)/3=1s(0+1+2)/3=1s。

img

显然,时间片长度对于RR是至关重要的。时间片越短,RR在响应时间上表现越好。然而,时间片太短是有问题的:突然上下文切换的成本将影响整体性能。因此,系统设计者需要权衡时间片的长度,使其足够长,以便摊销上下文切换成本,而又不会使系统不及时响应。

结合I/O

接下来我们放宽假设4,现在所有的程序都会执行I/O。调度程序显然要在工作发起I/O请求时做出决定,因为当前正在运行的作业在I/O期间不会使用CPU,它被阻塞等待I/O完成。如果将I/O发送到硬盘驱动器,则进程可能会被阻塞几毫秒或更长时间。因此,这时调度程序应该在CPU上安排另一项工作。调度程序还必须在I/O完成时做出决定。发生这种情况时,会产生中断,操作系统运行并将发出I/O的进程从阻塞状态移回就绪状态。当然,它甚至可以决定在那个时候运行该项工作。操作系统应该如何处理每项工作?

假设有两项工作A和B,每项工作需要50ms的CPU时间。但是A先运行10ms,然后发出I/O请求(假设I/O每个都需要10ms),而B只是使用CPU 50ms,不执行I/O。调度程序先运行A,然后运行B。

img

毫无疑问,上图所示的调度是非常糟糕的。常见的方法是将A的每个10ms的子工作视为一项独立的工作。因此,当系统启动时,它的选择是调度10ms的A,还是50ms的B。STCF会选择较短的A。然后,A的工作已完成,只剩下B,并开始运行。然后提交A的一个新子工作,它抢占B并运行10ms。这样做可以实现重叠,一个进程在等待另一个进程的I/O完成时使用CPU,系统因此得到更好的利用。

img

有了应对I/O的基本方法,我们来到最后的假设5:调度程序知道每个工作的长度。如前所述,这可能是可以做出的最糟糕的假设。事实上,操作系统通常不知道每个作业的长度。因此,我们将在第8章利用最近的历史预测未来,从而解决这个问题。