游戏背景

银河帝国的超光速引擎技术使得跨星域的交通运输成为可能，然而超光速通讯却遇到了瓶颈，为了维持银河帝国的统治与发展，借助超光速飞船进行信息传递的专用航行自律存储载具“信使”应运而生，玩家作为“信使”中的一员，超越光速，在庞大的银河帝国中探险，担负起传递信息的使命。

游戏玩法

剧情向rougelike，代表玩家的飞船从星系中心出发，查看星图，在各个不同类型的行星系之间切换，依据玩家状态以及行星系类型触发一系列随机事件，游戏没有固定胜利目标，系统将会在固定步数后进行结算或由玩家提前触发结算，结合玩家数据以及结算触发原因按不同模板生成结算文字。

游戏内容

• 游戏机制
  • 游戏流程
  • 游戏场景的生成机制
  • 行星系模板
  • 玩家
  • NPC
  • 路径点
  • 星际旅行
  • 任务生成
  • 新手引导
  • 随机事件
  • 数值&结算系统
• UI
  • 游戏主界面
  • 游戏界面
  • HUD
• 文案
  • 一般任务
  • （如果来得及做的话）特殊任务
  • 随机事件
  • 结算模板
  • 新手引导
• 美术
  • 2D
  • 3D模型
  • 特效&演出效果
• 音效/配乐
  • 音效
  • BGM

游戏机制

游戏流程

游戏场景的生成机制

新游戏开始，玩家输入名字，进入世界生成阶段，这个阶段里生成所有行星系的位置和行星系的编号、类型（包含什么设施，哪些星球），具体的分布情况以无向连通图（星图）的形式展现给玩家，生成的各类行星系的比例可调玩家在星图页面确定前往该行星系后，播放演出效果（跃迁），系统根据玩家的状态和已经生成的行星系信息该场景内将原行星系变为要前往的行星系，故游戏的绝大部分操作都在一个场景内完成。

行星系模板：

一颗恒星+n条固定的行星轨道（半径）+随机的角度（在轨道上的哪个位置），在生成星图时就规定好了所有行星系的构成（一个string解决的事情：例：行星系编号1-123a1b2d3e4:I类行星系，第123号行星系，a轨道（恒星位置）放置第1类恒星，b轨道放置第2类行星，d轨道（c空着）放置第3类行星，e轨道放置第4类行星，），还应包含当前星系的任务池（根据当前星系的任务位置生成

玩家

玩家的属性包括但暂不局限于：耐久值（血条）、弹药、燃料（行动点）、上一颗访问的行星系（随机事件用）、道具、任务，初始给予一定总点数，玩家自行分配（燃料需高于一定值。举例：设初始点数100，燃料应不低于50，耐久不能为0）。
玩家的外形应当是一艘飞船，可以在场景内做二维移动（参考群星），通过鼠标点击场景引导飞船移动

NPC

当前版本NPC只会在剧情中出现

路径点

路径点（行星系）有三种类型：
I类行星系（殖民地）：信件收发（任务领取/结算），应当包含一座空间站和至少一颗殖民地类型星球
II类行星系（船坞/资源开采）：补充资源，引导至少包含一座星际船坞
III类行星系（未知）：随机事件触发，至少包含3颗行星

星际旅行

入场：场景变化结束后，播放演出效果，飞船播放从画面左下角进入星系的动画
出场：让飞船到达指定区域后弹出选项，选择“前往下一星系”后弹出星图，玩家选中目的地，弹出选项，再次点击“确定”，回到场景，播放飞船跃迁动画，播放演出效果，在点击最后的“确定”之前，玩家都可以按esc退回到上一个页面。

任务生成

任务生成将根据固定的模板和玩家的状态生成。
任务类型：转发类（比如通缉令，玩家到达指定几个星系即可），普通类（玩家到达指定地点的目标星球进行任务交付），目的地应当在星图上高亮标记。
例1：（玩家所在星系名 星域 邮局）：（玩家名），请把这些邮件送到（目的地名）。
例2：（玩家所在星系名 星域 邮局）：辛苦了，（玩家名），请稍事休息，信息正在上传，这是补给：（弹出奖励窗口）。
在行星系生成的时候，就从任务池里挑范围个（范围内roll个数）随机事件类型，再分别判断当前行星系的位置能否满足这些类型的任务能被完成，不能完成的事件类型就从当前星系的事件池中去掉，对于剩下的类型，从这些类型对应的模板库当中去roll对应的文案模板，进行填空（比如目的地）。

新手引导

新手引导任务只会在玩家第一次进行各类操作时触发并调用新手任务模板，需要进行特判。

随机事件

飞船残骸：随机生成燃料、弹药、道具，roll点数来决定获取多少资源或何种道具。
星际海盗：选择 “逃跑”或“战斗”或“投降”：逃跑会返回上一行星系并丢失双倍于平时跃迁的燃料；战斗和投降会让双方先后投骰子，根据骰子的大小关系判定结果。
星际风暴：进入所有星系时都会有较低概率触发，根据玩家选择的选项和骰子的大小判定结果，玩家前往某些行星系所花费的行动点将会大幅增加并有一定概率损失固定耐久。
“Sweets”：一些可能会有惊喜（指获取道具）的小事件，根据玩家选择的选项产生不同结果。
例：设骰子1d20，1-5大成功，6-10成功，11-15失败，16-20大失败。

数值&结算系统

先给一个大致的数据系统供逻辑上的参考
玩家：初始50点燃料（行动点），15点弹药，25点耐久，10点闪避，每次星系间移动花费5点燃料，星系内移动不消耗燃料，若燃料耗尽且无法在当前星系获取燃料，玩家只能重开，结算页面将采用模板1（迷失结局）;若玩家耐久耗尽，自动触发结算页面，采用模板2（毁灭结局）;若回合数为0，结合当前玩家数据进行判断：燃料耗尽且在III类行星系，采用结算模板1、燃料耗尽但在I\II类行星系，采用结算模板3（探险仍将继续）、耐久耗尽自动触发结算页面，采用模板4（光荣退役）。
每个结算模板除触发原因外还需要获取玩家的游玩情况，比如遇到多少种哪类事件，到达了多少个不同的星系，打败了多少海盗，获得多少种道具之类。
结算页面将在单独设置的场景内进行，根据不同的结局生成对应场景。

UI

游戏主界面

静态UI动态背景，背景暂定为几段画面来回播放（利用游戏内资源另外制作）

游戏界面

参考群星，从斜上方俯视整个行星系，相机可以在全局视角和第三人称视角切换，可以双击选中任意天体进行观察（缩放，视角以天体为中心进行旋转），按esc退回上一状态。
（见9.22号的PPT）

游戏地图

注意外观和游戏内恒星的外观绑定（至少是颜色）

HUD

（见9.22号的PPT）

设置

分辨率和游戏内音量调整

道具栏

文案

新手引导

新手引导单独给一套任务，任务文案附说明文字

任务模板

随机事件模板

结算模板

美术

2D美术素材

游戏标题（logo的设计和制作）
UI所需各类素材

3D模型

飞船模型：玩家和星际海盗、飞船残骸
行星模型
恒星模型
空间站模型
游戏道具模型（骰子）

特效

飞船迁入迁出的特效
飞船爆炸的视觉效果

音效/配乐

音效

交互类：按钮、人物对话
提示类：弹框，随机事件触发，任务生成，获得物资/奖励
演出效果类：任务完成、跃迁、爆炸、结算页面

BGM

（暂定从群星和戴森球里面挑）

分工

策划案（策划）
文案（策划）
3D模型制作（美术）
2D美术素材制作（美术）
UI设计、制作（程序、美术）
玩家制作（程序)
特效、演出效果制作（TA)
任务系统、结算系统制作（程序)
游戏场景加载、生成（程序)
游戏地图生成（程序)

目前需要解决的问题

队伍名称
游戏名称
数值设计

参考

今日题目

正则表达式匹配
通配符匹配
复制带随机指针的链表
合并K个排序链表
最小覆盖子串

正则表达式匹配（动态规划）

题目链接
.匹配任意单个字符，要么匹配长度为0的子串要么匹配长度不为0的和前一个字符一样的子串。和上一题类似，我们用一个二维bool数组dp=new bool[m+1,n+1]来存储s中1到i，p中1到j的匹配情况。而dp[i,j]的递推公式，我们发现，当p[j-1]，即第j个字符为字母的时候，只要判断和当前的第i个字符是否匹配即可，即dp[i,j]=dp[i-1,j-1]&&s[i-1]==p[j-1];
当其为’.’的时候，直接i++,j++;当其为’‘的时候，我们先判断s[i-1]是否等于p[j-2]，如果不相等就等同于匹配长度为0的子串，即dp[i,j]=dp[i,j-2]，如果相等，就仍然和最开始的那样有两种选择。如果匹配长度为0的子串，直接dp[i,j]=dp[i,j-2]即可，如果匹配长度不为0的子串，则有以下的规律：
f[i][j]=f[i−1][j−2],if s[i]=p[j−1]
f[i][j]=f[i−2][j−2],if s[i−1]=s[i]=p[j−1]
f[i][j]=f[i−3][j−2],if s[i−2]=s[i−1]=s[i]=p[j−1]
⋯⋯
我们可以转成一个很巧妙的带有递归思想的式子：dp[i,j]=dp[i-1,j]，如果s[i-2]=p[j-2]的话，将继续触发dp[i-2,j]，如此往复直至到达这串相同字母的最左侧。
来看代码：

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

public class Solution {
    public bool IsMatch(string s, string p) {//正则表达式匹配
        int m = s.Length;
        int n = p.Length;
        bool[,] dp = new bool[m+1,n+1];
        dp[0,0] = true;
        for(int i = 0;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                if(p[j-1]=='*'){
                    dp[i,j]=dp[i,j-2];
                    if(match(s,p,i,j-1)){
                        dp[i,j]=dp[i,j]||dp[i-1,j];
                    }
                }else{
                    if(match(s,p,i,j)){
                        dp[i,j]=dp[i-1,j-1];
                    }
                }
            }
        }
        return dp[m,n];
    }
    public bool match(string s,string p,int i,int j){
        if(i==0)
           return false;
        if(p[j-1]=='.')
           return true;
        return s[i-1]==p[j-1];
    }
}

通配符匹配（动态规划）

题目链接
(和上面的类似，实在不想写了)
来看代码：

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

public class Solution {
    public bool IsMatch(string s, string p) {//通配符匹配
        int m = s.Length;
        int n = p.Length;
        bool[,] record= new bool[m+1,n+1];
        record[0,0]=true;
        for(int i = 1;i<n+1;i++){
            if(p[i-1]=='*'){
                record[0,i]=true;
            }else{
                break;
            }
        }
        for(int i = 1;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                if(p[j-1]=='*'){
                    record[i,j]=(record[i,j-1]||record[i-1,j]);//要么不匹配，要么匹配
                }else if(p[j-1]=='?'||p[j-1]==s[i-1]){
                    record[i,j]=record[i-1,j-1];
                }
            }
        }
        return record[m,n]==true;
    }
}

复制带随机指针的链表（链表、哈希表）

题目链接
使用哈希表存储新链表中结点和旧链表的对应关系，同时我们可以通过HashMap.get(p.random)直接获取对应的q.random
来看代码：

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

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {//复制带随机指针的链表-Java
        Node p = head;//
        Node q = new Node(0);
        Node res = q;
        Node tempRandom = new Node(0);//指向random的指针
        HashMap<Node,Node> record = new HashMap<>();
        while(p!=null){//录入新旧链表中结点的对应关系
             q.next = new Node(p.val);
             record.put(p,q.next);
             p=p.next;
             q=q.next;
        }   
        p=head;
        q=res.next;
        while(p!=null){
             tempRandom=record.get(p.random);
             q.random=tempRandom;
             p=p.next;
             q=q.next;
        }  
        return res.next;
    }
}

合并K个升序链表（链表、分治法）

题目链接
分治法的思路就是用相同的步骤将大的问题分解成多个小问题解决。这个题我们将多个链表进行分组，每个组只有一个链表或两个链表，将两个链表合并成一个链表，如此递归向上直至返回结果。
来看代码：

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {//排序链表-分治法：化大为小，思路统一
          if(lists.Length==0)//如果没有链表
            return null;
          return FenZhi(lists,0,lists.Length-1);
    }
    public ListNode FenZhi(ListNode[] lists,int left, int right){
         if(left==right)//如果就一个链表了
            return lists[left];
         if(left>right)
            return null;
         int m = right+left>>1;//实际上就是(r+l)/2,利用了运算符优先级
         return merge(FenZhi(lists,left,m),FenZhi(lists,m+1,right));//将几个链表拆分到最小组，然后递归merge
    }
    public ListNode merge(ListNode l1,ListNode l2){
        if(l1==null)
          return l2;
        if(l2==null)
          return l1;
        ListNode res= new ListNode();//新链表的头结点，res.next才是结果的头结点
        ListNode temp = res;//指向当前插入位置的前一个结点
        while(l1!=null&&l2!=null){//如果两个链表都不为空
            if(l1.val<l2.val){
                temp.next=l1;
                l1=l1.next;
            }else{
                temp.next=l2;
                l2=l2.next;
            }
            temp=temp.next;
        }
        if(l1!=null){
            temp.next=l1;
        }else{
            temp.next=l2;
        }
        return res.next;
    }
}

最小覆盖子串（滑动窗口）

题目链接
滑动窗口的核心思路就是反复调整左右边界以实现目的。在本题中如果当前窗口满足条件了（包含t中的所有字符），就收缩左边界直至不满足条件了，然后右边界扩张直至满足条件，如此循环。
来看代码：

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

public class Solution {
    public string MinWindow(string s, string t) {
        char[] S = s.ToCharArray();
        char[] T = t.ToCharArray();//匹配的时候用这俩数组和字典，截取的时候用 res=s.Substring()
        //字典是这个题的要素，字典内的值有两种，一种是缺省值Int32.MaxValue，用来判断当前字母在t里有没有
        //另一种是会变化的，用来表示滑动窗口内至少应该包含多少个该类字母，如果右边界右扩的时候遇到需要的字母，对应的值就会-1，表示收集到了一个这类字母，而左边界右缩的时候如果遇到了该类字母，对应的值就要+1，表示该类字母在滑动窗口内的需求量+1。
        Dictionary<char,int> dict = new Dictionary<char,int>();
        int l = S.Length;
        int min = Int32.MaxValue;
        string res = "";
        int threshold = 0;
        int cnt = 0;//cnt用于统计当前滑动窗口内的目标字母集齐了多少个，cnt++的触发条件是字典中t里包含的字母对应的数量变为0，即滑动窗口内有和t一样多的该字母
        int left = 0;
        int right = 0;
        for(int i = 0;i< T.Length;i++){
            if(!dict.ContainsKey(T[i])){
                dict.Add(T[i],0);
            }
            int val = dict[T[i]]+1;
            if(val==1)
              threshold++;//指的是有t里有多少种字母
            dict[T[i]]=val;
        }
        while(right<l){
            if(!dict.ContainsKey(S[right])){
                dict.Add(S[right],Int32.MaxValue);
            }
            int rval = dict[S[right]];
            if(rval == Int32.MaxValue){
                right++;
                continue;
            }
            if(--rval==0){//怎么着都要减，如果这个字母的数量减为0了，说明滑动窗口内该字母的数量达到要求，也就是集齐了这个字母
                cnt++;
            }
            dict[S[right]]=rval;
            while(cnt==threshold && left<=right){
                int length = right - left+1;
                if(length<min){
                    min = length;
                    res=s.Substring(left,length);
                }
                int lval = dict[S[left]];
                if(lval==Int32.MaxValue){//如果left指向的字母t里没有，说明没啥用，可以继续缩小左边界
                    left++;
                    continue;
                }
                if(lval==0){//如果left指向的字母在滑动窗口内的数量刚好满足要求，然而left右移会导致滑动窗口内缺一个该字母，导致滑动窗口不满足要求，从而触发当前while循环终止，进入right右扩循环
                    cnt--;
                }
                dict[S[left]]=++lval;//能执行到这里的都是left指向的字母在t里有，left右扩会导致窗口需要更多的该字母，所以字典内对应的值+1
                left++;
            }
            right++;
        }
        return res;
    } 
}

今日题目

最大交换
课程表I
二叉树最近公共祖先
二叉树中的最大路径和
删除无效的括号

最大交换(lambda排序)

题目链接
思路是将整数先通过ToString转换为string，再通过ToCharArray转换为可以进行单数位交换操作的字符数组ans，借助lambda表达式和Array.Sort对其进行降序排列得到temp，再与原数字进行逐位比较，找到第一个不相等的位置i，由于需要返回一次转换能产生的最大值，故要在后面的数位里去找值为temp[i]的最小一位，得到该位置后进行转换，最后将ans通过string的构造方法的重载转换为string，再由int.Parse()转换为最终值。
来看代码：

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

public class Solution {
    public int MaximumSwap(int num) {//最大交换
        if(num<=9)
           return num;
        string s = num.ToString();
        char[] temp = s.ToCharArray();
        char[] ans = s.ToCharArray();
        int res = 0;
        Array.Sort(temp,(a,b)=>{return b-a;});
        for(int i = 0;i<temp.Length;i++){//temp将所有数字降序排列，s存储的是原数字
            if(temp[i]!=ans[i]){
                int lastlocation = i+1;
                for(int j = i+1;j<temp.Length;j++){
                     if(ans[j]==temp[i]){
                         lastlocation=j;
                     }
                }
                ans[lastlocation]=ans[i];
                ans[i]=temp[i];
                break;
            }
        }
        string s2=new string(ans);
        res = int.Parse(s2);
        return res;
    }
}

课程表I（有向图生成、环检测、回溯、DFS）

题目链接
该题要求验证是否能找到一个排课顺序，按照这个顺序，所有课在开课前都能修完需要提前修的课程，那么，我们根据这种前趋关系建立一个有向图，只用检查有向图中是否存在环即可，如果存在环，说明不存在该顺序。对于出度为0的点，其顺序可任意安排，故不影响结果。
我们首先建立存储有向图各结点有向边信息的List类型数组graph，对其进行初始化遍历存储前趋关系的交错数组prerequisites，prerequisites[i][0]为有向边终点，prerequisites[i][1]为起点，按照prerequisites[i][1]找到graph对应List将有向边终点存入，完成图的建立。
对于环的检测，我们使用！bool类型数组onPath[] 和visited[]，前者用于判断当前检查的路径是否存在环（即该点是否已经存在于路径上）如果存在环， onPath[0]就置为true，后者用于记录已经在其他路径上遍历过的结点，防止超时（比如“灯笼”型有向图，多个路径指向同一个结点，而这个结点在DFS中已经被在第一条路径中注册了，到遍历其他路径时就不必重复，然而这种情况又要和onPath区分开，不能被误认为环）。以当前结点出发的子路径均检查完毕后，按照回溯，应当将当前结点的onPath置回false，再进行其他路径的检查
来看代码：

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

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {//课程表：有向图的环检测
          List<int>[] graph = BuildGraph(numCourses,prerequisites);//课程总数，课程对
          bool[] visited = new bool[numCourses];
          bool[] onPath = new bool[numCourses+1];
          for(int i = 0;i<numCourses;i++){
              DFS(graph,i,visited,onPath);
          }
          return !onPath[0];//onPath[0]记录是否有环，有就是false，没有就是true，所以要置反
    }
    public List<int>[] BuildGraph(int numCourses,int[][] prerequisites){
        List<int>[] graph = new List<int>[numCourses];//用List<int>数组建立图，每个List都存着从该点出发的下一个点
        for(int i = 0;i<numCourses;i++){
            graph[i] = new List<int>();
        }
        for(int i = 0;i<prerequisites.Length;i++){
            int from =prerequisites[i][1];//先修课程为有向边起点，课程为有向边终点
            int to = prerequisites[i][0];
            graph[from].Add(to);
        }
        return graph;//graph
    }
    public void DFS(List<int>[] graph,int s,bool[] visited,bool[] onPath){
        if(onPath[s+1]){//如果这个地方已经在路径上了，说明有环
              onPath[0]=true;
        }
        if(visited[s]||onPath[0]){//如果已经访问过了（由于是DFS，所以可能这个结点已经在已知的路径里了）或者已经证明有环了，那就返回。onPath判断在后用时最短（因为能通过的例子里onPath都是负，还要再判断visited[s]是不是true）
            return;
        }
        visited[s]=true;
        onPath[s+1]=true;
        List<int> temp=graph[s];
        for(int i = 0;i < temp.Count;i++){
            DFS(graph,temp[i],visited,onPath);
        }
        onPath[s+1]=false;//这个回溯至关重要，如果没有这个回溯，就会出现因为visied[s]==true（即在前面遍历过）而导致onPath[0]=true
    }
}

二叉树的最近公共祖先（二叉树、DFS）

题目链接
这道题的一个重要条件就是两个值均在二叉树中，所以对于p和q而言，只会有以下三种情况：
p和q都不是对方的最近公共祖先
p或q是最近公共祖先（两种）
如果遇到p或q，直接返回该结点，若其他子树返回的是null（即到了叶结点也没找到p或q，那就只能在返回不为null的子树里），就说明该结点是最近公共祖先
如果p和q分别在该结点的左右子树找到了（返回不为null），就说明当前结点是最近公共祖先，返回该结点
如果p和q都没找到，自己也不是p或q，就返回null
来看代码：

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//二叉树最近公共祖先
        if(root==q||root==p||root==null)
         return root;
        TreeNode left=LowestCommonAncestor(root.left,p,q);
        TreeNode right=LowestCommonAncestor(root.right,p,q);
        TreeNode res=new TreeNode();
        if(left==null&&right==null){
            res= null;
        }else if(left!=null&&right!=null){
            res= root;
        }else if(left!=null&&right==null){
            res= left;
        }else if(right!=null&&left==null){
            res= right;
        }
        return res;
    }
}

二叉树中的最大路径和（二叉树，DFS）

题目链接
这种情况适合DFS，从叶结点开始向祖先结点返回其子树的最大路径和，同时每个结点应先比较以下四个值，取最大值：
当前最大值
左右子树最大路径和较大者+自身值
自身值
自身值+左右子树的最大路径
向上返回时，比较自身值和自身+左右子树最大路径和较大者，返回较大的。
来看代码：

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
private int res = Int32.MinValue;
    public int MaxPathSum(TreeNode root) {//二叉树中的最大路径和
        DFS(root);
        return res;
    }
    public int DFS(TreeNode root){//算是DFS吧，前序遍历
        if(root==null)
           return 0;
        int left = DFS(root.left);
        int right = DFS(root.right);
        int max = Math.Max(left,right);
        int[] arr = {res,root.val+left+right,root.val,root.val+max};
        Array.Sort(arr);
        res = arr[3]; //将当前最大值、当前子树和、根值、根与最大子路径和进行比较
        return Math.Max(root.val,root.val+max);//要么返回根结点，要么返回根结点与最大子路径和
    }
}

删除无效的括号（BFS）

题目链接
我们使用HashSet来存储每层进行删除一个括号后所产生的所有结果以避免重复，针对相连左右括号和字符串首的括号进行删除操作。由于题目要求返回删除次数最小的有效字符串，故一旦当前步数（层数）产生了有效字符串（HashSet.Count>0)，就返回结果。
检查当前字符串是否有效的逻辑是遍历该字符串，记录需要右括号的左括号个数，若左括号小于0则说明当前字符串无效，若遍历后左括号个数大于0说明缺少右括号，即当前字符串无效。
来看代码：

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

public class Solution {
    public IList<string> RemoveInvalidParentheses(string s) {//删除无效的括号-BFS
         List<string> res = new List<string>();
         ISet<string> cur = new HashSet<string>();
         cur.Add(s);
         while(true){
            foreach(string str in cur){
                if(IsValid(str)){
                    res.Add(str);
                }
            }
            if(res.Count>0){
                return res;
            }
             ISet<string> next = new HashSet<string>();
            foreach(string str in cur){
                for(int i = 0;i<str.Length;i++){
                    if(i>0&&str[i]==str[i-1]){
                        continue;
                    }if(str[i]=='('||str[i]==')')
                       next.Add(str.Substring(0,i)+str.Substring(i+1)); //SubString的两种重载用法：前者返回以0位起点的i长度子串，后者截取以i+1为起点的字符串剩余部分，这两个重载结合起来的用法就是生成删除了当前位字符的字符串。             
                }
            }
            cur = next;
         }
    }
    public bool IsValid(string s){
        int left=0;
        for(int i = 0;i<s.Length;i++){
             if(s[i]=='('){
                  left++;
             }else if(s[i]==')'){
                 left--;
             }
             if(left<0)
                return false;
         }
         return left==0;
    }
}

【前言】：写给无意中点进来的你

（主要是因为博客好久没更新了，打算重新利用起来）代码有一部分是借鉴评论区和官方题解的，所以在力扣写题解就难免不太合适，然而记笔记的需求是确切存在的，博客的tag查找也很方便，就打算在博客写笔记了，也方便我快速回忆起知识点省得再去CSDN（垃圾堆）里找，尽量每日一更，之前积攒下来的题也会慢慢加更上来。

今日题目

雇佣K名工人的最低成本
计算右侧小于当前元素的个数
分割回文串
单词搜索II
修剪二叉搜索树

雇佣K名工人的最低成本（优先级队列，lambda排序）

题目链接
这道题的核心在于根据什么去挑工人。我们定义“价性比”=期望工资/工作量，即每单位工作量对应的工资。
我们再看题目的两个关键要求：
1.工资要按工作量占比分配
2.每个工人得到的工资应大于等于其期望工资
我们将所有工人按价性比从低往高排列，如果按第k个人的价性比付工资，则能满足以上两个条件。
那么如何满足成本最低呢？
我们易知成本=价性比*工作总量，如果成本要最低的，那么工作总量也要尽量小。我们使用优先级队列，先将前k-1个人的工作量入队，从第k个人开始，我们将当前遍历到的工人的工作量加入k-1个工人的工作量中得到总工作量，再乘以当前工人对应的效费比，将结果与最小值进行比较以更新结果，最后返回。
来看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public double MincostToHireWorkers(int[] quality, int[] wage, int k) {//雇佣K名工人的最低成本
         int l = quality.Length;
         int[] q = new int[l];
         double res =1e9,totalq=0.0;
         for(int i = 0;i<l;i++){//这个数组是用来存储按效费比排列后工人的序号，以获取对应工作量和工资
             q[i]=i;
         }
         Array.Sort(q,(a,b)=>{return wage[a]*quality[b]-wage[b]*quality[a];});//将数组通过lambda表达式按升序排列，前者比后者大则调转，即升序
         PriorityQueue<int,int> PQ = new PriorityQueue<int,int>();//通过优先级队列实现最大堆，优先级队列中维护的是最小的k个工作量
         for(int i =0;i<k-1;i++){//先获取前k-1个工人的工作量之和，并将他们的工作量入队
             totalq+=quality[q[i]];
             PQ.Enqueue(quality[q[i]],-quality[q[i]]);//C#的最大堆优先级是根据第二个参数的大小升序排列的，要想让工作量从大到小排，就让工作量的相反数从小到大排
         }      
         for(int i =k-1;i<l;i++){
             totalq+=quality[q[i]];//得到当前k个工人的工作量
             double cur = ((double)wage[q[i]]/quality[q[i]])*totalq;//得到结果
             res = Math.Min(res,cur);//取较小值
             PQ.Enqueue(quality[q[i]],-quality[q[i]]);//将当前工人的工作量入队进行比较
             totalq-=PQ.Dequeue(); //将最大的工作量出队，此时totalq是最小的k-1个工作量之和  
         }
         return res;
    }
}

计算右侧小于当前元素的个数（二分查找）

题目链接
从右往左遍历数组，单独用一个List存入，每次存入前先通过二分查找获取该数在List中的位置（按升序排列），设该类数的最小索引为k，即有k个数在该数右侧且比该数小。
由于是从右往左遍历数组，每次遍历得到的结果也是从右往左加入作为结果的List，故需要对List进行翻转后再返回。
来看代码：

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

public class Solution {
    public IList<int> CountSmaller(int[] nums) {//计算右侧小于当前元素的个数-二分查找
          IList<int> res = new List<int>();
          List<int> sortedList = new List<int>();
          int[] resTemp = new int[nums.Length];
          for(int i = nums.Length-1;i>-1;i--){
              int location = bFind(sortedList,nums[i]);
              resTemp[i]=location;
              sortedList.Insert(location,nums[i]);
          }
        res = resTemp.ToList();
        return res;
    }
    public int bFind(List<int> sortedList,int num){
        if(sortedList.Count==0)
            return 0;
        int left = 0,right = sortedList.Count-1;
        while(left<=right){
            int mid = (left+right)>>1;
            if(num>sortedList[mid]){
                left=mid+1;
             }else{
                right = mid-1;
                //num=sortedList[mid]或num<sortedList[mid]都得right=mid-1，后者的原因显而易见，而前者的原因是这道题要求的是当前元素右侧小于（划重点）该元素的元素个数，如果是小于等于则可直接返回mid，但为了排除相等的元素，我们则要去找这段连续的相同数字的左边界
            }
        }
        return left;
    }
    // public void Reverse(IList<int> res){//由于力扣的C#版本中Reverse存在问题，然而重写Reverse会导致超时，最后用数组和ToList方法取代。
    //     Stack<int> stack = new Stack<int>();
    //     int l  = res.Count;
    //     for(int i  = 0;i<l;i++){
    //         stack.Push(res[0]);
    //         res.RemoveAt(0);
    //     }
    //     for(int i = 0;i<l;i++){
    //         res.Add(stack.Pop());
    //     }
    //     return ;
    // }
}

分割回文串（回溯、DFS）

题目链接
题目的要求是返回一个List，List里是这个字符串分成多个回文串组合的所有分法。这是一个考察枚举的题
我们先用一个bool类型的二维数组record记录i和j为左右端点的回文串是否存在，如果存在即为true，类似于动态规划，我们通过上一个回文串来判断当前的子串是否是回文串
设字符串为s,i为左端点，j为右端点，则record[i,j]的递推式如下：
record[i,j]= i>=j? true: (record[i+1,j-1]==true&&s[i]==s[j]?true:false) 意会，不严谨，首先判断i是否大于等于j，即当前串是否为空串或长度为1的串，如果不是，则需要查询该子串的上一个状态s[i+1]-s是否是回文串，如果是回文串且当前指向的两个字符相等，才返回为true。
通过以上步骤，我们获取了字符串所有的回文串，接下来解决怎么分的问题。
由于是枚举，我们可以通过DFS+回溯的方式来枚举。设一个指针i，0~i的子串被枚举完了，又设一个指针j，j在i和最后一个字符间枚举当前分法的下一个回文子串两端，i再指向j。
来看代码：

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

public class Solution {
    bool[,] record;
    int l ;
    IList<IList<string>> res = new List<IList<string>>();
    IList<string> ans = new List<string>();
    public IList<IList<string>> Partition(string s) {//分割回文串
            l = s.Length;
           record = new bool[l,l];
           for(int i =0;i<l;i++){
               for(int j = 0;j<l;j++){
                   record[i,j]=true;
               }
           }
           for(int i = l-1;i>-1;--i){
               for(int j = i+1;j<l;j++){
                   record[i,j]=(s[i]==s[j]&&record[i+1,j-1]);
               }
           }
           DFS(s,0);
           return res;
    }
    public void DFS(string s,int i){
        if(i==l){
           res.Add(new List<string>(ans));
           return;
        }
        for(int j = i;j<l;j++){
            if(record[i,j]){
                ans.Add(s.Substring(i,j-i+1));
                DFS(s,j+1);
                ans.RemoveAt(ans.Count-1);
            }
        }
    }
}

单词搜索II（字典树，回溯）

题目链接
字典树是一种用于快速查找单词的数据结构，它基于字典实现，每个结点的孩子结点值（即字符）和所属字典树的对应关系都用字典存储。将单词插入到字典树中的步骤是遍历单词的字符，若当前字典树/字典子树不存在与该字符相等的键（即不存在以当前字符为首字母的单词），则将该字符与新字典树组成的键值对加入字典，当遍历到当前单词的最后一个字符时，将该单词存入字典树结点的word属性。在遍历时，我们以board中的每个格为起点做DFS，在该格子对应的DFS结束后进行回溯，再以下一个格子为起点进行DFS。查找时，若当前字典树结点为叶结点或不匹配（字典不存在当前字符对应的键，当前字符不在路径上）则返回，若存在对应键且该键对应的值（字典树）的word属性为单词，说明找到了一个单词，将单词存入ISet，ISet是C#提供的用于集的抽象的基接口，用HashSet实现时，其Add方法保证最后结果的元素互不相同，使用ISet存储结果完美避免了重复的问题。
来看代码：

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

public class Solution {
    int[][] direction = new int[][]{
        new int[]{1,0},
        new int[]{-1,0},
        new int[]{0,-1},
        new int[]{0,1}
    };
    public IList<string> FindWords(char[][] board, string[] words) {//单词搜索II
           Trie trie = new Trie();
           foreach(string word in words){//构造字典树
               trie.Insert(word);
           }
           ISet<string> ans = new HashSet<string>();//用于集的抽象基接口ISet，可以用HashSet或SortedSet实现
           //使用HashSet的一个重要原因是HashSet中的元素互不相同，和哈希表类似（键互不相同）
           for(int i = 0;i<board.Length;i++){
               for(int j = 0;j<board[0].Length;j++){
                   DFS(board,trie,i,j,ans);
               }
           }
        return new List<string>(ans);
    }
    public void DFS(char[][] board,Trie now,int i1,int j1, ISet<string> ans){
        if(!now.children.ContainsKey(board[i1][j1])){
            return;//没有以当前字母为前缀的单词、当前结点为叶结点或不匹配
        }
        char ch = board[i1][j1];
        now=now.children[ch];
        if(!"".Equals(now.word)){//如果词不为空
            ans.Add(now.word);//这里不return的原因是可能存在以当前词为前缀的词语
        }
        board[i1][j1]='#';
        foreach(int[] dir in direction){
            int i2=i1+dir[0],j2=j1+dir[1];
            if(i2>=0&&i2<board.Length&&j2>=0&&j2<board[0].Length){
               DFS(board,now,i2,j2,ans);
            }
        }
        board[i1][j1]=ch;
    }
}
public class Trie{//字典树模板
    public string word;
    public Dictionary<char,Trie> children;
    public Trie(){
        this.word = "";
        this.children = new Dictionary<char,Trie>();
    }
    public void Insert(string word){
        Trie cur = this;
        foreach(char c in word){
            if(!cur.children.ContainsKey(c)){
                cur.children.Add(c,new Trie());
            }
            cur = cur.children[c];
        }
        cur.word=word;//当遍历结束时，cur指向的是以单词最后一个字母为根结点的字典树，让该字典树的word等于存入的word，当DFS遍历到该结点时，如果该结点的word为单词，就说明找到了这个词
    }
}

ISet C#文档链接
HashSet C#文档链接
SortedSet C#文档链接

修剪二叉搜索树（二叉树、前序遍历、递归）

题目链接
对出范围的结点做如下处理：
结束递归条件：结点为空
出左边界：返回遍历其右子树的结果
出右边界：返回遍历其左子树的结果
对在范围内的结点，对其左右子树均进行同样的遍历
来看代码：

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode TrimBST(TreeNode root, int low, int high) {//修剪二叉搜索树
          if(root==null)
             return root;
          if(root.val<low)//如果当前结点出左边界，就在该结点的右子树去找
             return TrimBST(root.right,low,high);
          if(root.val>high)//如果当前结点出右边界，就在该结点的左子树去找
             return TrimBST(root.left,low,high);//处理正常的结点
          root.left=TrimBST(root.left,low,high);
          root.right=TrimBST(root.right,low,high);
          return root;
    }
}

0.前言（套盾）

本文档仅供项目组内部参考使用
本文档内链接均用于学习
本文档所属项目仅为学习用demo，非商业化作品
本文档中包含游戏机制、游戏道具、各类属性的说明与策划给出的部分实现思路

1.项目目标

• 实现多人联机功能：

  • 房间的创建、删除
  • 地图加载
  • 房间的进入、退出
  • 同步

• 实现FPS的基本内容：

  • 战斗
    • 武器
    • 道具
    • 技能
    • 动作
  • 角色
    • 角色定位
    • 外观
    • 数值
    • 技能（是在地图里获取技能还是角色自带技能）
  • 交互
    • UI
    • 键位
    • 与场景交互
  • 地图/场景
    • 地图加载/销毁
    • 地图内设施
    • 道具刷新点

• 实现游戏核心机制：

  • 角色
    • 角色选择
    • 角色创建与初始化
      • 角色数值初始化
      • 出生点选择
    • 角色状态与转换
      • 健康
      • 负伤
      • 死亡（盒子）
      • 转换
    • 角色掉落
      • 部分掉落
      • 完全掉落
    • 角色属性与变化机制
    • 角色销毁
      • 撤离点
      • 被击杀
      • 迷失
  • 限时撤离
  • 胜利目标

2.项目设定

2.1分工（这个清清来吧，还是需要一个书面的东西来详细划定的）

2.2项目参考 （更新中）

利用Photon实现服务器
搭建服务器框架和实现联机大厅
Unity C#服务器
UnityFPS官方示例
枪械后坐力参考
逃离塔科夫枪械后坐参数说明

3.具体设计说明

3.0 游戏总体设计

玩家在初始界面设定联机ID创建角色，连接进入游戏大厅，选择房间或创建房间。开始游戏后，玩家先有若干秒选择角色，同时地图上随机刷新资源，倒计时结束后出生在随机出生点。玩家可在地图上搜集资源。击杀其他玩家时，可以获取其携带物资和标识，并获得少量分数，当地图上仅剩一名玩家时，游戏界面倒计时撤离时间，若最后一名玩家未在规定时间内撤出，则会被强制击杀。被击杀或撤离时弹出结算界面和分数，物资可兑换少量分数，击杀玩家可兑换大量分数。游戏结束后，分数汇总生成表格推送给玩家。

3.1 武器与战斗（策划与动画、美术、叶宝对接）

3.1.0 战斗的大致介绍

主要以中近程战斗为主，玩家使用武器与自身技能击杀敌人，使用道具回复血量与护甲，击杀敌人后获取1击杀数，并根据被击杀玩家的击杀数获取奖励分数，敌人变成道具箱（道具箱UI同角色背包）；被击杀则在倒地后画面逐渐变黑，显示被击杀页面

3.1.1 武器

武器的基本设定

• 外观
• 射击条件（枪械配件槽内有弹匣、弹匣内有子弹方可射击，只有这个配件决定枪械是否开火）
• 枪声（枪声的更改发生在消音器被安装/取下的时候）
• 射速（理解为枪口生成子弹的速度）
• 后坐力（分为水平和垂直，水平后坐力导致枪身左右晃动，垂直导致枪身上下晃动）
• 枪口回落速度（射击停止后枪口朝向回到原方向的时间，也可以设置为速度）
• 子弹散布（我的思路是后坐力方向变化范围，参考2.2给出的塔科夫枪械后座参数说明）
• 可用弹种
• 可使用配件（配件将可能对枪械的基本属性进行更改）
• 枪械本身分值（枪械本身不含配件的分数）

武器种类与数值

较为具体的设计我在表格内已经给出了，这里要补充的一点是半自动步枪的定位。半自动步枪的定位是精准，因此初始散布应当是最小的，且具有最快的枪口回落速度。

3.1.2 战斗

• 射击（鼠标左键）：使用不同瞄具的瞄准和腰射
  • 需要考虑的要素：当前使用的瞄具，当前使用的握把，后坐力的大小，目前站姿势（站立、蹲、趴）
  • 注意：跳跃不可射击
  • 弹匣内无弹药且背包内无可用弹药时再按鼠标左键切换武器
• 换弹匣（R）
  • 需要考虑的要素：弹匣的种类，技能是否开启（对换弹时间的改变）
• 切换枪械（1和2）：一支在手里一支在背上（背上可以放置武器的地方在背两侧），当切换枪械时，先将手里的换到背上空出的地方，再将另一把从背上换到手里，播放完动画才可进行其他对武器的操作
  • 需要考虑的要素：枪械大小，枪械移位与角色部位活动的绑定
• 改装武器（动作可以先不做，但改装武器必须花费时间）每更换一次配件，整个枪的状态就要更新一次，更换配件的方法是将背包内的配件拖到配件槽上，更换时间结束后两个配件的图标交换，更换时间=原配件的更换时间（见表格）+新配件的更换时间（见表格），若枪械配件槽为空，则只计算新配件的更换时间
• 一个准则：对武器的操作之间是互斥进行的（瞄准包含在射击内）

  3.2 道具（策划与叶宝对接）

  3.2.1 道具分类

• 弹药
  • 手枪弹药：低伤害低分数带的多
  • 步枪弹药：高伤害高分数带的少
  • 弹药击中玩家屏幕中央给出击中X形图标反馈，由枪械生成。暂时不做弹道下坠，弹药击中场景内物体（除弹药箱、玩家死后变成的盒子、玩家外）生成贴图
• 回复道具（护甲回复与血量回复）
  • 维修套装（一次性）：中刷新中分值
  • 血量回复
    • 急救包（一次性回血）：高刷新低分值
    • 回血针（持续回血）：低刷新高分值
• 配件
  • 带倍率瞄具：试着做镜内放大吧
  • 机瞄和红点：实际上是两种类型的机瞄
  • 握把和后托，握把实现垂直后坐力的削弱和枪口散布范围的缩小，后托实现水平后坐力的削弱
• 稀有道具（高分极低刷）
  • 金/银/铜球

3.2.2 道具刷新

道具的刷新点、爆率、特性已经在表格内给出。

3.3 角色（策划与动画、叶宝对接）

3.3.1 角色的属性

• 血量（见表格）
• 护甲值（见表格）
• 技能点（见表格）
• 技能回复速度：固定为2点/s（数值见表格）
• 移速（具有三档速度，数值举例见表格，按x进入/退出静步，静步将不再发出声音，按shift进入快跑，快跑持续时间和回复速度待定）
• 耐力（见表格，决定了玩家能连续跑多久）
• 耐力消耗速度/回复速度（见表格）
• 击杀数（见表格）
• 得分（玩家按两下3即可在画面右上角显示，显示时间为3s，3s内再发出查询命令则重置计时器）

3.3.2 角色状态、数值的转化机制

• 玩家被击中时若有护甲，则被击中产生的伤害80%由护甲承担，剩余20%为真伤，该伤害判定在击中时发生，若剩余护甲小于子弹伤害的80%，则护甲置0，剩余伤害均为真伤。
• 玩家可通过回复道具回复血量，产生的溢出不会被计算。
• 若判定玩家承受该子弹伤害后血量<=0，则触发死亡退出机制，使用布娃娃系统实现脱力倒地成为尸体，可以搜刮。

3.3.3 角色的动作

• 移动：匍匐（z）、蹲走（ctrl）、静步（x）、快走、跑步、跳跃
• 战斗：举枪、瞄准、射击、换弹、切换武器、死亡
• 拿取物品（暂定为静止不动）
• 恢复：包扎（急救包）、扎针（回血针）、修补护甲（参照apex）
• 技能
• 在原有动作上进行更改（比如增速技能就提高跑步动画的播放速度）
• 死亡（先倒地再黑屏后结算）
• 迷失：超过每局最大时长仍未撤离（先黑屏后结算）

3.3.4 角色的背包

每个角色的背包是和角色绑定的，不会变化。玩家进入游戏并选好角色后按照表格内给出的刷新概率刷新物品，并更新玩家的得分。玩家被击杀时，计算背包内物品的总分数，玩家对背包内物品的每次调整都将刷新分数，玩家随时可以查询。角色的背包由通用武器槽、子弹槽、回复道具槽和任意物品槽四类槽位构成，各个槽位能放置的物品及其数量上限见表格，不能放在槽内的物品被拖拽时将不会被换入槽内，结束拖拽，图标将自行归位。

子弹的消耗机制（涉及到背包）

每个槽内只能放一种子弹，当玩家换弹时自动查询弹药槽，只会消耗放在弹药槽内的弹药若有该类弹匣对应的子弹则自动填充，若没有则按3.1.2对换弹的说明进行切换武器，如果弹药在任意物品槽内则不会被自动消耗，需玩家自行拖拽至弹药槽内。

你可以把不要的东西丢出去！

如果你想丢掉一些东西，选中它（鼠标移上去就会高亮）左键点击选择抛出数量，右键点击则全部抛弃，然后这个物体的模型将从身体周围生成并掉到地上。

我后悔了怎么办

对于半径1m以内的物体看向它（轮廓会高亮）高亮教程，然后按左键，将对背包进行查询，如果有位置就能放入。

3.4 地图（策划与美术、叶宝对接）

3.4.0 地图设定

目前的方案是训练基地（主要是可以大量复用素材）的一个区域，多楼层，多房间，多过道，中央是一个天井供中距离战斗，包含多个出生点且均有随机性，撤离点有通用撤离点、限时撤离点、随机撤离点、触发撤离点四种，房间最大人数10，具体每层的设计后续会和美术磋商。

3.4.1 出生点

出生点是玩家刷新的地方，角色初始满甲满血，按表格内给出的爆率在背包内刷新物品。出生点的数量和房间内最大玩家容量一致且均匀分布在地图角落，玩家在哪个出生点进入游戏是随机的。玩家在各个刷新点的刷新概率应均等（这个好做，比如在玩家池中随机选出一个玩家，然后随机安排出生点，再从剩余玩家里接着选一个并安排，以此类推），每个玩家的出生点都被设置好，所有资源均加载完毕后进入游戏。

3.4.2 撤离点

撤离点是玩家触发退出机制的地方，若撤离点可用，则玩家进入判定区域将弹出倒计时页面，待一段时间就可撤离并进入结算页面，不会留下任何东西。

通用撤离点

玩家进入游戏后随时都可撤离，将会被放在武器库的门口、通风管道这样的地方，难以找到或比较偏僻。

限时撤离点

会在特定的时间点开启，并有限定时间，比如临时开启的大门

随机撤离点 （搁置）

会在每局开始时就决定是否开启，若开启则会有外观的变化（比如某处墙壁是否有裂口）。

触发撤离点

满足某种条件才可激活（比如拉电闸），需在一定时间内赶到撤离点撤离，否则需重新触发，比如电梯。

3.4.3 物品箱

物品箱的种类和道具爆率等设定均已在表格内给出。

3.5 游戏机制

3.5.1 房间（策划与lzy对接）

进入游戏，设定用户名，分配玩家ID，连接到游戏大厅，玩家点击开始游戏，若当前没有可加入的房间则生成一个房间，客户端显示一定时长的倒计时，若在时间内房间满员则开始游戏，进入角色选择页面（给30s准备时间）并加载地图内资源，30s倒计时结束且地图资源加载完毕即可进入游戏；如果倒计时结束没有足够玩家（2人）则退回主页面。游戏结束（所有玩家都已完成游戏或每局时间上线已到）后对玩家分数进行排名，生成分数记录榜并通过邮件系统推送给玩家（实现服务器的用户连接、创建房间、加入房间、玩家信息记录、玩家同步、排行榜的创建）

3.5.2 游戏内机制补充（策划与ycy对接）

撤离点和出生点（见3.4.1与3.4.2）

玩家分数的计算规则

如果你死亡玩家得分=玩家击杀分（规则见表格）+ 道具得分 + 剩余血量x10 + 剩余护甲x2.5
如果你在最后10分钟内撤离玩家得分=玩家击杀分（规则见表格）+ 道具得分 + 剩余血量x10 + 剩余护甲x2.5 +1000
如果你在最初5分钟撤离玩家得分=玩家击杀分（规则见表格）+ 道具得分 + 剩余血量x10 + 剩余护甲x2.5 -1000
如果你迷失玩家得分=玩家击杀分（规则见表格）+ 道具得分 + 剩余血量x10 + 剩余护甲x2.5 -1500

游戏结束的触发条件

场上玩家均死亡/迷失/撤离

4.美术需求（动画、美术、策划对接）

4.1 模型 目前暂时以现有素材替代，借助现有素材完成动画制作后再套新模型

• 人物的模型
• 各类武器、道具、配件的模型（种类表格内已给出）
• 场景需要的模型
  • 建筑物（地图本身）
  • 各类摆设
  • 各类道具箱
  • 撤离点

4.2 UI

4.2.1 图标 目前需要的Sprite暂以现有素材替代

图标

• 武器、配件、道具的图标均为模型的截图
• 此外还需要：HUD（弹匣内弹药数/总弹药数，血条、技能条、护甲条、耐力条、击杀反馈图标、受伤反馈），背包内图标（配件槽的图标（配件槽可使用/配件槽不可使用）、各类道具槽的图标），道具箱内图标（武器槽、弹药槽、配件槽、药品槽、随机槽）

互动方案

光标移到图标上自动弹出文字介绍

4.2.2 面板 目前需要的Sprite暂以现有素材替代

• HUD
• 背包的面板
• 各类道具箱的面板
• 服务器选房间的面板
• 选择角色页面的面板：选择角色的页面我想做成滑动的
• 被击杀页面的面板：显示存活时间、最终分数、击杀数和击杀者（每颗子弹带有击杀者信息，角色需记录并更新最后一颗射向自己的子弹是谁，初始为NULL，死亡时调用这个属性）

4.2.3 字体（实在没空就先默认字体吧，有空再做）

4.3 动画与特效

角色

动作分类我已在3.1.2和3.3.3给出，不过技能和护甲受击是否需要做特效呢？

场景

撤离点状态的切换（比如仓库大门的打开和关闭）
道具箱状态的切换（打开和关闭）

5.音乐与音效需求

5.1 背景音乐 （有空再找）

主场景、选择角色、结算

5.2 音效

• 玩家移动的各类音效
• 枪械切换、射击、换弹的各类音效
• 技能开启的音效
• 与场景互动的音效
• 护甲被击中的音效
• 受伤、濒死的声音反馈
• 回复道具使用的音效

视频组成（自上而下为时间轴）

• 场景展示
• 成员介绍
• 实操视频
• 项目细节展示

预期时长6-8分钟
分辨率固定为1K

实现方案

场景展示

• 包含内容：三个场景的展示
• 拍摄方式：使用unity camera recorder录制并导出main camera画面
• 排序原因：先用视觉元素唬住评委

  成员介绍

• 包含内容：成员介绍（分工）
• 拍摄方式：由五个短片段组成，每个短片段5s左右，每个片段内容如下：
  
  拍摄的时候让成员做一些操作，比如lzy的片段可以是：拖动场景内的某个物体，或者修改水面参数，然后弹出弹窗：lzy——技术美术
• 排序原因：介绍团队最好放在偏开头的地方，让评委认识你

  实操视频

• 包含内容：完整的游玩过程（主场景——灯谜场景，玩一个灯谜——园林场景，刻几个字——回到主场景）
• 拍摄方式：画面主要是游戏内画面，即使用unity camera recorder录制并导出main camera画面，玩家实况以小窗形式在画面左下角，将场景切换的部分以加速方式压缩
• 需要注意的：
  • 场景切换时尽量不要动头（因为动头会露出锯齿状的画面边缘）
  • 在主场景就需要将玩家移动方式（走动、传送）和大部分UI交互（按钮动态效果、制作人员名单，国赛要用）展示出来
  • 刻字要慢，增强笔画连续性，刻几个字就行，展示临摹UI和介绍UI，在场景内移动时尽量不要让人看出穿模
  • 灯谜只用做一个，然后让评委看到下一个灯谜的内容（在下一个灯谜只用将提示触发即可）
  • 一次录完，不要分段拼凑
• 排序原因：全视频的核心

  项目细节展示

• 包含内容：代码截图和shader graph截图
• 拍摄方式：几秒过一张图
• 排序原因：因为是最无聊的部分，故放在最后

目前问题

• unity camera recorder功能仍需论证
• 必剪有待上手
• 考虑飞花令玩法是否加入和加入后对视频结构的影响，目前仍然需要留插入的空余

依照学校教学安排，第二章为进程的描述与控制

本帖仅供个人学习使用

使用虚拟机平台VMware Workstation

2.1 前趋图和程序执行（考点）

2.1.1 前趋图（要求会画并发执行和顺序执行的）

• 前趋图是一个有向无循环图，用于描述进程之间执行的先后顺序，图中的每个结点可以用来表示一个进程或程序段乃至一条语句，结点间的有向边表示两个结点之间的偏序关系或前驱关系。
• 直接前趋和直接后继：设前趋图中某有向边为Pi->Pj，则称Pi为Pj的直接前趋，Pj为Pi的直接后继
• 初始结点：没有直接前趋的结点
• 终止结点：没有直接后继的结点
• 为什么前趋图不能存在循环路径：若图中Pi和Pj间存在循环路径，则会导致Pi开始执行前要求Pj先执行完毕，Pj开始执行前要求Pi先执行完毕，这是相互矛盾的

  2.1.2 程序顺序执行（考点）

  程序的顺序执行

• 输入操作I要在计算操作C之前执行，打印操作P要在输入操作I和计算操作C后执行
• 即使是一个程序段，也可能存在着执行顺序问题，下面给出了一个包含了三条语句的程序段：
  S1:a=x+y
  S2:b=a-1
  S3:c=b+2
  其中，语句S2必须在语句S1后（因为需要先得到a的值），语句S3必须在语句S2后（因为要先得到b的值），因此三条语句存在的前趋关系为S1->S2->S3

  程序顺序执行时的特征

  由上述可知，在程序顺序执行时具有这样三个特征：
• 顺序性：处理机严格地按照程序规定的顺序执行
• 封闭性：程序在封闭的环境下运行，程序运行时独占全机资源，资源的状态（除初始状态外）只有程序能改变它，程序一旦开始执行，其执行结果不受外界影响
• 可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行还是“停停走走式”执行，都可获得相同的结果

  2.1.3 程序并发执行（考点）

• 程序顺序执行虽然便利了程序员，但系统资源的利用率却很低，为此引入多道程序技术使程序或程序段间能并发执行。然而，并非所有程序都能并发执行，只有没有直接前趋关系的程序之间才能并发执行

  程序并发执行时的特征

• 程序并发执行功能虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，以及它们为完成同一项任务而相互合作，导致这些并发执行的程序间必将形成相互制约的关系
• 程序并发执行的新特征：
  • 间断性：由于并发执行的程序共享资源导致它们之间存在制约关系，因此只有当使其暂停执行的因素消失后程序才可执行，由此可见，相互制约导致并发程序具有执行-暂停-执行的间断活动规律
  • 失去封闭性：由于并发执行的程序共享资源，导致任何一个程序运行时都不能独占全机资源，即它们的运行环境能够被其它程序影响，故失去了封闭性
  • 不可再现性：由于程序并发执行时失去了封闭性，也将导致其失去可再现性，因为程序的结果不再只受初始环境和条件影响，也在运行过程中受到影响

2.2 进程的描述（考点）

2.2.1 进程的定义和描述(搭配1.3.1食用)

进程的定义

• 需求：由于在并发执行的程序失去了顺序性、封闭性、可再现性，尤其是后两者，所以导致通常的程序运行结果不能保障，也就失去了意义。为了让程序能够并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了进程的概念
• 进程控制块PCB：为了让并发执行的每个程序能够独立运行，操作系统中必须为之配置一个专门的数据结构：进程控制块，这样由程序段、相关数据、程序控制块三部分组成了进程实体，即进程，所谓创建进程，实质是创建进程中的PCB，相对应的，撤销进程实质上就是撤销进程中的PCB
• 进程的定义 梅开二度：在系统中能独立运行并作为资源分配的基本单位，由进程控制块、相关数据和程序段组成，是一个能独立运行的活动实体，是操作系统运行的基础。

  进程的特征

• 动态性：由创建而产生，由调度而执行，由撤销而消亡
• 并发性：多个进程同存于内存中，且能在一段时间内并发执行
• 独立性：进程实体是一个能独立运行、独立获得资源、独立接收调度的基本单位
• 异步性：进程是按异步方式运行的，即“执行-暂停-执行”

  2.2.2 进程的基本状态及转换

  进程的三种基本状态

• 就绪：进程已经分配到除CPU外的所有必要资源
• 执行：进程已获得CPU并正在执行，单处理机系统中只有一个进程处于执行状态，多处理机系统中有多个进程处于执行状态
• 阻塞：正在执行的某进程因为发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行的状态，此时引起进程调度，将阻塞进程放入阻塞队列中等待，一般出于提高系统效率的需要，根据阻塞原因的不同，会设置多个阻塞队列

  三种基本状态的切换

  见图
  
• 补充-时间片：操作系统分配给每个进程在CPU上的一段执行时间

  创建状态与中止状态

• 需求：为了满足PCB对数据及操作的完整性要求以及增强管理的灵活性，通常在系统中又为进程引入了两种常见的状态：创建状态和终止状态。
• 创建状态：进程由创建而产生，创建一个进程的过程要通过多个步骤：进程申请一个空白PCB，向PCB中填写用于控制和管理进程的信息，为该进程分配除CPU外必须的资源，将进程转入就绪状态并插入就绪队列中。将进程申请PCB开始到加入就绪队列前的这个状态称为创建状态。
• 终止状态：进程的终止也要通过两个步骤：等待操作系统进行善后处理，再将PCB清理并返还系统。进程到达自然结束点，若出现无法克服的错误，或被操作系统终结，或被其它有终止权的进程所终结，它将进入终结状态，进入终结状态的进程不能再被执行，但在操作系统中保留记录供其它进程收集，一旦其它进程完成收集，操作系统将删除该进程并清零PCB、返还给系统。
  

  2.2.3 挂起操作和进程状态的转换

• 在许多系统中，进程除了就绪、执行、阻塞三个基本状态外,为了系统和用户观察和分析进程的需要，还引入了一个对进程的重要操作：挂起。当挂起操作作用域某个进程时，该进程将被挂起，意味着此时该进程处于静止状态，如果该进程正在执行，它将暂停执行，若该进程处于就绪状态，则该进程此时暂不接受调度，与挂起操作对应的操作是激活操作。

  挂起操作的引入

• 终端用户的需要：发现可疑问题需要暂停程序运行
• 父进程请求：用于协调各子进程
• 负荷调节的需要
• 操作系统的需要：检查运行中的资源使用状况

  引入挂起原语操作后三个进程基本状态的转换（需要会画图）

• 补充-原语：指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。
• 挂起原语Suspend：用于活动->静止的转换
• 激活原语Active：用于静止->活动的转换
• 活动就绪Readys：处于活动就绪状态的进程可以被调度执行
• 静止就绪Readya：处于静止就绪状态的进程不再被调度执行
• 活动阻塞Blockeda：处于活动阻塞状态的进程完成I/O后变为活动就绪状态等待调度使用
• 静止阻塞Blockeds：处于静止阻塞状态的进程完成I/O后变为静止就绪状态等待激活成为活动就绪

  引入挂起操作后五个进程状态的转换（需要会画图）

• 创建->活动就绪：若当前系统性能和内存容量均允许，完成创建的必要操作 （申请PCB、填写PCB、分配除CPU外资源）后，相应的系统进程将进程的状态转换为活动就绪状态
• 创建->静止就绪：若当前系统性能和内存容量不允许加入新的进程，则不分配给新建进程所需资源，将进程转为静止就绪状态，被安置在外层，此时进程创建工作尚未完成（也就是处于创建状态）
• 执行->终止：当一个进程已完成任务时，或是出现了无法克服的错误，或是被OS或是被其他进程所终结，此时将进程的状态转换为终止状态

  2.2.4 进程管理中的数据结构

  操作系统中用于管理控制的数据结构（考点）

• OS管理需要的数据结构的分类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB
• OS中的数据结构包含了资源或进程的标识、描述、状态等信息以及一批指针。

  PCB的作用（考点）

• PCB的作用：使一个在多道程序环境下不能独立运行的程序称为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。
• PCB的作用：
  • 作为独立运行基本单位的标志
  • 能实现间断性运行方式
  • 提供进程管理所需要的信息
  • 提供进程调度所需要的信息
  • 实现与其它进程的同步与通信

PCB中的信息（考点）

• 进程标识符：用于唯一地标识一个进程
  • 内部标识符：为每一个进程赋予一个唯一的数字标识符，方便系统使用
  • 外部标识符：由创建者提供，通常由字母、数字组成，往往由用户进程访问该进程时使用
• 处理机状态：也称为处理机的上下文，由处理机各寄存器中的内容组成：通用寄存器、指令计数器、程序状态字PSW、用户栈指针
• 进程调度信息：进程状态、进程优先级、进程调度所需的其他信息、阻塞原因
• 进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针

  进程控制块的组织方式

• 线性方式：将系统中的所有PCB组织在一张线性表中，将该表首地址存放在一个专用区域内。
• 链接方式：将具有同一状态的PCB用其中的链接字链接成一个队列，排成执行队列、就绪队列、阻塞队列或空白队列等，用相对应的队列指针指向这些队列的第一个PCB。
  
• 索引方式：系统根据所有进程状态的不同，建立几张索引表如就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。（用表取代队列）。

2.3 进程控制

进程控制、进程同步、进程通信、处理机调度是操作系统处理机管理功能的四个主要组成，进程的控制包含进程创建、进程终止、进程阻塞和唤醒，由OS内核中的原语来实现

2.3.1 操作系统内核

OS内核：在具有分层结构的OS中由常驻内存且与硬件紧密相关的各类驱动程序和运行频率较高的模块所组成的部分。
使用内核的目的：便于对这些软件进行保护、提高OS的运行效率
系统态和用户态：为了保护OS本身及关键数据，通常将处理机的执行状态分为系统态和用户态。

• 系统态/管态/内核态：具有较高特权的执行状态，能执行一切指令，访问所有寄存器和存储区
• 用户态/目态：具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区。一般情况下，应用程序只能在用户态运行，不能去执行OS指令及访问OS区域。

OS内核包含的两大功能（考点）

• 支撑功能：中断处理、时钟管理、原语操作
  • 中断处理:是整个操作系统赖以活动的基础，内核在对中断进行有限处理后，便转入相关的进程，由这些进程继续完成后续的处理工作。
  • 时钟管理:对进程的执行提供时间控制
  • 原语操作:原语是一个不可分割的基本单位，由若干条指令构成，在执行过程中不允许被中断。原语在系统态下执行，常驻内存。
• 资源管理功能：进程管理、存储器管理、设备管理
  • 进程管理：为了提高进程管理的效率和满足多种功能的需要，这些操作相关的原语被放在内核中。
  • 存储器管理：存储器管理软件的运行模块（逻辑地址与物理地址映射、地址转换，内存保护，内存分配和回收等）因为使用频率较高，故也放在内核中。
  • 设备管理：由于设备管理与硬件紧密相关，因此设备管理的相关模块（缓和CPU与I/O速率不匹配矛盾的缓冲管理，各类设备的驱动程序，设备分配等）也放在内核中。

2.3.2 进程的创建

进程的层次结构

• 子进程和父进程：在OS中，允许一个进程创建另一个进程，我们称创建进程的进程为父进程，被创建的进程为子进程，子进程能够继承父进程的所有资源 （父进程打开的文件、父进程所分配到的缓冲区等），相对应的，撤销子进程时，应当将继承的资源返还给父进程，父进程被撤销时其生成的子进程也必须同时撤销。
• 补充：在WINDOWS中不存在进程层次概念，所有的进程地位相同，而取代上下级控制关系的是句柄，拥有句柄的进程就拥有了控制其它进程的权限，句柄也可以进行传递。因此在WINDOWS中，进程之间不是层级关系，而是控制与被控制关系。

  进程图

• 用于描述进程的家族关系，是一棵有向树，树的根结点称为进程家族的祖先

  引起创建进程的事件（考点）

• 用户登录（为用户创建进程）
• 作业调度（为用户创建进程）：在多道批处理系统中，当作业调度程序按一定的算法调度到某个作业时，将它们装入内存，并为它们创建进程、插入就绪队列中
• 提供服务（为用户创建进程）：当运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户程序需要的服务
• 应用请求（用户自己创建进程）：用户进程自己创建新进程以使新进程和创建者进程并发运行完成某些特定任务，从而提高运行效率

  进程的创建

• Step1：申请空白PCB
• Step2：为新进程分配资源
• Step3：PCB初始化（填写控制进程所需要的信息如：标识符、状态信息、优先级等）
• Step4：如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列

  2.3.3 进程的终止

  引起进程终止的事件

• 正常结束：进程任务已经完成，准备退出运行。在任何系统中都应该有一个用于表示进程已经运行完成的指示。在批处理系统中对应的指令是Halt，在分时系统中对应的指令是Logs off，当程序运行到这个指令时，产生一个中断告诉OS进程已运行完毕
• 异常结束：进程在运行时发生了某种异常事件，使程序无法继续运行，常见的异常事件有：
  • 越界错：程序访问的存储区超出规定区域
  • 保护错：进程试图访问一个不被允许访问的文件
  • 非法指令：指令不存在
  • 特权指令错：进程视图执行一条只允许OS执行的指令
  • 运行超时：进程执行时间超过规定的最大值
  • 等待超时：进程等待某事件的时间超过规定最大值
  • 算术运算错：进程试图执行一个被禁止的运算
  • I/O故障：I/O过程发生了错误
• 外界干预：进程应外界请求终止运行，这些干预有：
  • 操作员或操作系统干预
  • 父进程请求
  • 父进程终止

进程的终止进程

• Step1：根据被终止进程的标识符从PCB集合中检索对应PCB，读取该进程的状态
• Step2-1：若被终止进程处于执行状态，立刻终止该进程执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
• Step2-2：若该进程有子孙进程，应一并终止其所有子孙进程
• Step3：将被终止进程及其子孙进程的所有资源或者还给其父进程，或者还给系统
• Step4：将被终止进程的PCB从所在队列/链表中一出，等待其它程序来搜索信息

  2.3.4 进程的阻塞与唤醒

  引起进程阻塞和唤醒的事件

• 向系统请求共享资源失败：资源被其它进程占用-阻塞，释放-唤醒
• 等待某种操作的完成：操作没完成-阻塞等待，完成-唤醒
• 新数据尚未到达：未到达-因没有数据而阻塞等待，完成-唤醒
• 新进程尚未到达：没有需要处理的新进程-进程自我阻塞，有新进程要处理-唤醒

  进程阻塞过程

• Step1：调用阻塞原语Block将自己阻塞
• Step2：若仍在执行则停止执行，并将PCB中的执行状态改为阻塞
• Step3：PCB被插入阻塞队列
• Step4：转给调动程序重新调度，将处理机分配给另一就绪进程

  进程唤醒过程

• Step1：由有关进程调用唤醒原语Wakeup唤醒进程
• Step2：将进程从阻塞队列中调出
• Step3：将该进程的PCB由阻塞状态改为就绪
• Step4：将该进程插入就绪队列中

2.3.5 进程的挂起与激活

进程的挂起

• Step1：由OS调用挂起原语suspend挂起进程
• Step2：检查被挂起进程的状态，若活动就绪则改为静止就绪，若活动阻塞则改为静止阻塞
• Step3：将该进程PCB复制到某指定内存区域
• Step4：若被挂起进程正在执行，则转向调度程序重新调度

  进程的激活

• Step1：由OS调用激活原语active激活进程
• Step2：被激活进程从外存调入内存
• Step3：检查该进程状态，若静止就绪则改为活动就绪，若静止阻塞则改为活动阻塞
• Step4：若为静止就绪，改为活动就绪后，将其优先级和队列中其他进程优先级进行比较，若优先级低则不必重新调度，否则直接剥夺当前进程的运行，将处理机分配给刚被激活的进程

2.4 进程同步

2.4.1 进程同步的基本概念

进程同步机制的主要任务是对并发执行的多个相关进程在执行次序上进行协调

两种形式的制约关系

在多道程序环境下对于同处于一个系统中的多个进程，它们之间可能存在两种形式的制约关系

• 间接相互制约关系：多个进程在并发执行时由于共享CPU、I/O设备等一次只能允许一个进程访问的资源，导致这些并发执行的程序之间形成了间接相互制约关系。对于这类临界资源，必须保证多个进程对之间只能互斥地访问，这类资源由系统实施统一分配，即用户在使用之前应先提出申请。
• 直接相互制约关系：对于合作完成某一任务的多个进程而言，它们之间会因进程的异步性、并发性和执行顺序导致的无法从缓冲中及时取出数据而产生阻塞，即进程之间的直接制约关系。为了杜绝这种因为不正确的访问顺序而产生的“与时间有关的错误”，系统必须对进程的执行次序进行协调。
  

  临界资源（考点，会写伪代码）

临界资源：进程采用互斥访问方式共享的资源，如各类I/O设备、处理机等。
生产者-消费者问题
问题描述：有一群生产者在生产产品（数据），同时有一群消费者在消费产品（数据），为了能使生产者（进程）和消费者（进程）并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将产生的数据放入缓冲区中，消费者进程可从缓冲区取出数据，虽然这两类进程的执行是异步的，但是它们对缓冲区的数据存取必须同步，即不能让消费者进程从空的缓冲区取数据，也不能让生产者进程将数据存入满的缓冲区
生产者-消费者问题的伪代码表示如下：

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

int in=0, out =0,count =0;//输入、输出指针初始化，counter表示当前缓冲区中的数据量
item buffer[n];//buffer为缓冲池
void producer(){//生产者进程
   while(1){
      produce an item in nextp;//将生产的数据存入nextp，nextp和nextc均为局部变量
      ...
      while (counter == n);//counter表示当前缓冲池内数据量，counter==n表示当前缓冲池内数据满，不能将nextp中暂存的数据放入池中，故等待。
         ...
         buffer[in] = nextp;//将nextp中的数据存入当前输入指针指向的缓冲区
         in = (in+1)%n;//in向前移动
         counter++;//数据量++
   }
}

void consumer(){//消费者进程
   while(1){
      while(counter==0);//counter==0表示当前缓冲池空，无数据可取
         ...
         nextc = buffer[out];//将当前输出指针指向缓冲区内容存入nextc
         out = (out+1)%n;//输出指针指向下一个
         counter--;//数据量--
         consumer the item in nextc;//消费nextc中暂存的数据
         ...
   }
}

这两个进程交替执行不会有任何问题，但如果这两个进程的语句是交替进行的会导致counter偏离理论值，因此，生产者进程和消费者进程要互斥地访问临界资源缓冲池和变量counter

临界区（考点）

由上述可知无论是硬件临界资源还是软件临界资源，多个并发执行的进程必须互斥地进行访问，我们将这些进程中访问临界资源的代码段称为临界区。若要保证进程对临界资源的互斥访问，要让每个进程在进入临界区之前，检查欲访问的临界资源是否在被其他进程访问。由此可知，在进程的临界区前要加上一段对临界资源进行预检查的代码段，即进入区，相应地，在临界区后也要加上一段退出临界资源访问的代码，即退出区，进程中除进入区、临界区、退出区外的剩余部分被称为剩余区，故一个访问临界资源的循环进程描述如下：

1
2
3
4
5
6
7

while(1){
   剩余区;
   进入区;
   临界区;
   退出区;
   剩余区;
}

同步机制应遵循的规则（考点）

• 空闲让进：临界资源空闲（无进程进入临界区）时应允许一个请求进入临界区的进程立即进入临界区。
• 忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待。
• 有限等待：进程等待进入临界区的时间应该有上限。
• 让权等待：当进程不能进入自己的临界区时，应立即释放分配给这个进程的处理机

  2.4.2 硬件同步机制

  由于使用软件指令解决临界区问题有一定难度且有局限性，因此目前许多计算机提供了硬件指令解决临界区问题。
  • 临界区管理提供一个作为锁的标识，“锁开”进入，“锁关”等待
  • 初始状态下锁为打开状态，每个进入临界区的进程必须对锁进行测试
  • 为了不让所同时进行多个测试，故测试和关锁操作必须连续（原语操作），先关锁后开锁

关中断

进入锁测试前关闭中断，完成锁测试并关锁后打开中断，进程在临界区时计算机系统不响应中断，不会引发调度，缺点：

• 滥用关中断可能导致严重后果
• 关中断时间过长会影响系统效率
• 不适用于多CPU系统

利用Test-and-Set （测试并建立）指令实现互斥

在进程内实现互斥访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14

boolean TS(boolean *lock){//获取lock参数，*lock==TRUE时，表示锁关；*lock==FALSE时，表示锁开
   boolean old;
   old = *lock;//将lock存储的地址指向的空间内内容赋给old
   *lock = TRUE;
   return old;
}
do{//进程代码
   ...
   while (TS(&lock));//这个代码逻辑妙啊，如果lock第一次传入时是true，即锁关，那么传出来的old也是true，进程将阻塞在while语句，而lock仍保持true（锁关）
   //而如果lock第一次传入时是false，即锁开，那么传出来的old是false，进程跳出while循环继续执行，而false将改为true，表示当前进程进入临界区并关锁，关锁和传参（测试）是在一块的，因此不可分开，也就实现了逻辑上的连续
   critical section;//临界区
   *lock:=FALSE;//:=为赋值语句
   remainder section;//退出区、剩余区
}while(TRUE);

利用Swap指令实现进程互斥

在资源中实现互斥访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void Swap(boolean *a,boolean *b){
   boolean temp;
   temp = *a;
   *a = *b;
   *b = temp;
}
do{
   key = TRUE;//给资源的初始状态是“可访问”
   do{
      swap(&lock,&key);
   }while(key!=FALSE);//先进行do操作，若，lock为false，key为true，则第一次测试可以访问该资源，lock和key转换，表示该进程正在被访问，而key变为false后则不再进行转换操作，即其它进程的访问无效，直至lock变为true后再次重头访问该进程时（退出区）再度交换释放该资源。
   lock = FALSE;
   ...
}while(1);

2.4.3 信号量机制

信号量是一种卓有成效的进程同步工具，它包含：

• 整型信号量

  1 2 3 4 5 6 7

  wait(S){//P操作 while(S<=0);//信号量少于0，即表示没有资源，则一直wait（阻塞） S--;//能操作了，占用资源，S-- } signal(S){//V操作 S++;//释放了资源，S++ }

• 记录型信号量

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  typedef struct{ int value;//表示某类资源数目，若value值为1，则可实现进程互斥 struct process_control_block *list;//进程列表指针list }semaphore;//记录型信号量定义 wait(semaphore *S){//P操作 S->value --;//请求一个单位的该类资源 if (S->value<0)//若该资源已经被分配完毕，进程调用block原语自我阻塞 block(S->list); } signal(S){//V操作 S->value ++;//释放一个单位的该类资源 if(S->value<=0)//若仍有等待该类资源的进程被阻塞 wakeup(S->list);//调用wakeup原语，唤醒链表中的第一个等待进程 }

• AND型信号量
  整型信号量和记录型信号量的问题

  1 2 3 4 5

  //若进程A和进程B为两个共享数据D和E的进程，它们按下列次序交替进行wait操作，Dmutex和Emutex的初始值均为1以实现互斥访问 processA: wait(Dmutex);//Dmutex = 0 processB: wait(Emutex);//Emutex = 0 processA: wait(Emutex);//Emutex = -1，A阻塞 processB: wait(Dmutex);//Dmutex = -1，B阻塞，两个进程死锁。

  AND同步机制的思想：将进程所需要的所有资源一次性分配

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  Signal（S1，S2，···，Sn）{//释放所有资源 for(i=1;i<=n;i++){ Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue.//有了资源，将所有需要Si的进程移入就绪队列 } } Swait（S1，S2，···，Sn）{ while（true）{ if（S1≥1andS2≥1and...andSn≥1）{//若需要的所有类型资源都有 for(i=1;i<=n;i++)// Si=Si–1;//分别发出请求 break; } else{ place the process in the waiting queue associated with the first Si found with Si＜1, and set the program count of this process to the beginning of Swait operation.//一旦发现第i类资源不满足要求，则将该进程调入与Si相关联的等待队伍，还要将此进程中PCB的程序计数器设置到Swait操作的开始处。 } } }

• 信号量集
  在每次分配时，采用信号量集来控制，可以分配多个资源

  1 2 3 4 5 6 7 8 9 10 11 12 13

  Swait（S1，t1，d1，...，Sn，tn，dn）{//满足ti≥di，Si、ti、di分别对应资源信号量、资源下限值、需求量 if(S1≥t1&...&Sn≥tn){//如果所有资源都就绪了 for(i=1;i<=n;i++){ Si＝Si－di; } } else{ Place the executing process in the waiting queue of the first Si with Si＜ti and set its program counter to the beginning of the Swait operation。将该进程调入与Si相关联的等待队伍并将此进程中PCB的程序计数器设置到Swait操作的开始处。 } } //Swait(S,d,d)：允许每次申请d个资源。当资源数少于d时，不予分配。 //Swait(S,1,1)：S>1，记录型信号量。S=1时，互斥型信号量。 //Swait(S,1,0)，可控开关，当S>=1时，允许进入，S<1时，不能进入。

  2.4.4 信号量的应用

  利用信号量实现互斥访问

  为了使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait（mutex）和signal（mutex）操作之间即可。

  1 2 3 4 5 6 7 8 9

  semaphore mutex=1; process1(){// or process2 while(1){ wait(mutex);//为了实现进程对资源的互斥访问，wait和signal必须成对出现，缺少wait(mutex)会导致系统混乱，不能实现互斥访问。 critical section;//临界区 signal(mutex);//缺少signal(mutex)会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程不能被唤醒。 remainder section;//剩余区 } }

  利用信号量实现前趋关系（可能考看伪代码画前趋图或看前趋图写伪代码，希望不会是后者）

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  p1(){S1；signal（a）；signal（b）；}//浅显易懂 p2(){wait(a);S2；signal（c）；signal（d）;} p3(){wait（b）；S3；signal（e）；} p4(){wait（c）；S4；signal（f）；} p5(){wait（d）；S5；signal（g）；} p6(){wait（e）；wait（f）；wait（g）；S6；} voidmain(){ semaphorea,b,c,d,e,f,g; a.value=b.value=c.value=0; d.value=e.value=f.value=g.value=0; cobegin p1();p2();p3();p4();p5();p6(); coend; }

  2.4.5 管程机制

  管程的定义

  当共享资源用共享数据结构semaphore表示时，资源管理程序可用对该数据结构进行操作的一组过程来表示（如资源的请求和释放），我们把这样一组相关的数据结构和过程一并称为管程

管程：一个管程定义了一个数据结构和能被并发进程在该数据结构上所执行的一组操作，这组操作能够同步进程和改变管程中的数据。

管程的组成

• 管程的名字
• 管程局部的共享数据结构的说明
• 对该数据结构进行操作的一组过程
• 对管程局部的数据设置初始值的语句

  管程的主要特点

• 局部数据变量只能被管程的过程访问，任何外部过程都不能访问
• 一个进程通过调用管程的一个过程进入管程
• 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变为可用的

2.5 经典进程的同步问题

2.5.1 生产者-消费者问题

利用记录型信号量解决生产者-消费者问题

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

int in=0,out=0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;//初始状态下所有缓冲区都是空的
void producer();
void consumer();
void main(){
   //cobegin 
      producer();
      consumer();
   //coend
}
void producer(){
   do{
      ...
      produce an item in nextp;
      ...
      wait(empty);
      wait(mutex);
      buffer(in):=nextp;
      in:=(in+1) % n;
      signal(mutex);
      signal(full);
      ...
   }while(TRUE);
   ...
}
void consumer(){
   do{
      wait(full);
      wait(mutex);
      nextc:=buffer(out);
      out:=(out+1) % n;
      signal(mutex);
      signal(empty);
      consume an item in nextc;
      ...
   }while(TRUE);
   ...
}

利用AND信号量解决生产者-消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int in =0,out = 0;
item buffer[n];
semaphoremutex = 1, empty = n,full = 0;
void producer(){
   do{
      ...
      produce an item in nextp;
      ...
      wait(empty,mutex);
      buffer[in]=nextp;
      in:=(in+1)%n;
      signal(mutex,full);
   }while(True);
}
void consumer{
   do{
      wait(full,mutex);
      nextc = buffer[out];
      out = (out+1)%n;
      signal(mutex,empty);
      consumer the item in nextc;
   }whiel(TRUE);
}

2.5.2 哲学家进餐问题

问题描述

五个哲学家共用一张圆桌，每个人之间有一只筷子，哲学家要么思考，要么吃饭，吃饭时先左后右拿起两边的筷子，思考前放下筷子。若五个哲学家要同时吃饭，则它们同时拿起左边的筷子后，都等待右边的筷子被放下，从而引发死锁。
对于死锁，有以下几种解决方法：

• 至多只允许有四位哲学家同时去拿左边的筷子，保证至少有一位哲学家能进餐
• 仅当哲学家的左右两只筷子均可用时才允许进餐
• 规定奇数号哲学家先左后右拿筷子，偶数号科学家先右后左拿筷子，这样总有哲学家能进餐

  利用AND信号量机制解决哲学家进餐问题

  1 2 3 4 5 6 7 8 9 10 11

  semaphore chopstick[5]={1,1,1,1,1}; do{ ... //think ... wait(chopstick[(i+1)%5],chopstick[i]); ... ///eat ... signal(chopstick[(i+1)%5],chopstick[i]); }while(true);

  2.5.3 读者-写者问题

  问题描述

  存在读者和写者两类进程，我们将只读取文件的进程称为Reader进程，其它进程则称为Writer进程，读进程可共享同一对象，写进程不可共享同一对象，即我们允许多个Reader进程同时访问一个共享对象，但不允许Writer进程和其它任何类型进程同时访问数据对象，因为会引起混乱。因此Writer进程必须互斥地与其它进程访问共享对象。

  利用记录型信号量解决读者-写者问题

  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

  semaphore rmutex=1,wmutex=1;//设置两个信号量：读信号量和写信号量，初始值均为1，故先写还是先读都可以 int readcount=0;//readcount用于表示当前有多少个进程在执行读操作，是读进程释放写信号量的判断依据 void reader(){ do{ wait(rmutex);//先等待读信号量为1（表示可以开始执行读进程，注意是开始进程不是正式读），且读信号量并不由写进程控制 if(readcount==0)//如果当前没有其他读进程在读程序，也有第二层含义是没有其它读进程有可能是因为有写进程在执行，因此要进行进一步检查 wait(wmutex);//检查当前是否有写进程在写文件，如果有（即wmutex=0）则等待，没有（即wmutex=1）则wmutex--，不让新的写进程执行 readcount++;//计数器++,表示该读进程正式进入读文件环节，也让其它并发执行的读进程得知有读进程在执行故可以跳过上面的if语句 signal(rmutex);//释放读信号量供并发读进程使用 ... perform read operation;//正式读取操作 ... wait(rmutex);//要结束了，需要释放写信号量，故进入检查环节 readcount --;//表示该进程已经结束读文件环节 if(readcount==0)//检查当前还是否有其它进程在读文件，并保证释放写信号量的进程是最后一个在执行的读进程 signal(wmutex);//注意，要先释放写信号量以防止新的读进程挤入导致写进程无法执行，然后再释放读信号量 signal(rmutex); }while(TRUE); } void writer(){ do{ wait(wmutex);//要么初始情况下先于读进程写，要么等读进程释放再写 perform write operation; signal(wmutex); }while(TRUE); } void main(){ //cobegin writer();//这里私认为读进程还是写进程在前并不重要 reader(); //coend }

  利用信号量集机制解决读者-写者问题

  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

  int RN;//同时读进程最大数量 semaphore L=RN,mx=1;//初始化，mx为互斥信号量 void Reader(){ do{ wait(L,1,1);//如果还能允许多一个读进程，就进入，否则等待 wait(mx,1,0);//满足ti≥di才能执行下一步，Si、ti、di分别对应资源信号量、资源下限值、需求量，这里是mx阻止读进程和写进程同时进行的步骤，若ti<di即mx=0，则说明有写进程在执行，读进程需等待 ... perform read operation;//正式读取操作 ... signal(L,1);//将占用的一个读进程位（姑且这么叫）释放 }while(TRUE); } void writer(){ do{ wait(mx,1,1);//先抢占写进程位以实现互斥写入（写进程间）和互斥读写（读写进程间） wait(L,RN,0);//满足ti≥di才能执行下一步，Si、ti、di分别对应资源信号量、资源下限值、需求量，这里是检查是否还有其他读进程在执行的步骤，若L<RN，则说明有读进程在执行，写进程需等待 perform write operation;//正式写入操作 signal(mx,1);//写入完毕，立即释放占用的写进程位 }while(TRUE); } void main(){ cobegin Reader();//顺序不重要 Writer(); coend }

2.6 进程通信

进程通信，即进程之间的信息交换，分为两类

• 低级通信：以信号量机制为代表，它存在的缺点：
  • 效率低：生产者每次只能向缓冲池内投放一个产品/信息，消费者每次只能从缓冲池中取出一个产品
  • 通信对用户不透明 （我觉得就是根本没有）：OS只为进程间的通信提供了共享存储器，而关于进程之间通信需要的数据结构、数据传送、进程互斥和同步机制都需要程序员实现，这对用户而言是不方便的
• 高级通信：使用OS提供的高级通信工具，其特点是：
  • 便于使用：OS将进程通信封装为一组用于实现高级通信的原语，用户直接利用它实现进程之间的通信
  • 高效地传送大量数据：用户可直接利用高级通信命令/原语高效地传送大量数据

    2.6.1 进程通信的类型

    共享存储器系统

• 基于共享数据结构的通信方式，如生产者-消费者问题中的缓冲区
• 基于共享存储区的通信方式，在内存中划出一块共享存储区域，数据的形式、位置和访问控制都是进程而不是OS负责，进程向OS申请得到存储区域中的一个分区，读写完成或不再需要时归还给共享存储区

  管道通信系统

• 指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，向管道提供输入的写进程以字符流形式将大量数据送入管道，读进程接收管道输出的数据
• 建立管道通信需要提供以下三方面的协调能力：
  • 互斥
  • 同步
  • 对方是否存在

    消息传递系统

• 目前主要的通信方式，信息单位：消息（报文）
• 实现方式：将通信数据封装在报文中，利用OS提供的一组通信命令/原语，在进程间进行消息传递
• 基于消息传递系统的通信方式属于高级通信方式，因其实现方式的不同，可分为两类：
  • 直接通信方式：发送进程利用OS提供的发送原语直接把消息发送给目标进程
  • 间接通信方式：发送和接收进程都通过共享中间实体（邮箱）进行消息的发送和接收

    客户机-服务器系统（略）

    2.6.2 消息传递通信的实现方式

    直接消息传递系统

    直接消息传递系统指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程

    直接通信原语

• 对称寻址方式（1 to 1发送进程和接收进程都必须以显式方式提供对方的标识符）
  • 系统提供下述两条通信命令/原语：
    • send(Receiver,message)
    • receive(Sender,message)
    • 不足：一旦改变进程的名称，则可能需要找到有关该进程旧名称的所有引用以便修改，不利于进程定义的模块化
• 非对称寻址方式（1 to n在接收进程原语中，不需要命名发送进程，只填写表示源进程的参数，即完成通信后的返回值，而发送进程仍需要命名接收进程）
  • 系统中该方式的发送和接收原语表示为：
    • send(P,message)
    • receive(id,message)//id也可以是进程名字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void producer(){
   do{
      ...
      produce an item in nextp;
      ...
      send(receiver,nextp);
   }while(TRUE);
}
void consumer(){
   do{
      ...
      receive(producer,nextc);
      ...
      consume the item in nextc;
   }while(TRUE);
}

间接通信/信箱通信

进程之间需要通过共享数据结构的实体进行通信，该实体建立在随机存储器的公用缓冲区上，通常把这种中间实体称为信箱。系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤销和消息的发送、接收等

信箱的结构

信箱的创建和撤销

• 进程可利用信箱创建原语来建立一个新信箱，创建者进程需给出：
  • 信箱名称
  • 信箱属性/类型（公用、私用或共享）
    • 私用邮箱：邮箱是创建邮箱进程的一部分，随进程消失
    • 公用邮箱：邮箱供系统中的所有核准进程使用，所有核准进程均可对邮箱进行信息送取操作，通常公用邮箱在系统运行期间始终存在
    • 共享邮箱：由某进程创建，在创建时或创建后指明它是可共享的，并给出共享进程/用户的名字，创建进程和其它共享进程权限相同，均可对邮箱进行信息送取操作

信箱的发送和接收

1
2

Send(mailbox,message)
Receive(mailbox,message)//浅显易懂

2.6.3 直接消息传送系统实例

消息缓冲队列通信机制中的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区（一种数据缓冲区）
typedef struct message_buffer{
   int sender;//发送者进程标识符
   int size;//消息长度
   char*text;//消息正文
   message_buffer*next;//指向下一个发送区的指针
}
//PCB中有关通信的数据项
typedef struct processcontrol_block{
   ...
   struct message_buffer * mq;//消息队列队首指针
   semaphore mutex;//消息队列互斥信号量
   semaphore sm;//消息队列资源信号量
}

发送原语

1
2
3
4
5
6
7
8
9
10
11
12

void send(receiver,a){//a和下面的b都是message_buffer类型数据，但a是发送区，b是接收区
   getbuf(a.size,i);//根据a的size申请缓冲区
   i.sender = a.sender;//这行起的三行的意思是将发送区a中的信息复制到消息缓冲区之中
   i.size=a.size;
   copy(i.text,a.text);
   i.next=0;//或者也可以说i.next=null
   getid(PCBset,receiver.j);//获得接收进程内部标识符
   wait(j.mutex);//等待接收进程内部标识符状态为“队列可插入”
   insert(&j.mq,i);//将消息缓冲区插入消息队列j
   signal(j.mutex);//释放以供其他进程使用
   signal(j.sm);//这块没看懂，应该是++，毕竟是资源信号量，但是书上却没写wait(j.sm)，求解惑
}

接收原语

1
2
3
4
5
6
7
8
9
10
11

void receive(b){
   j = internal name;//j为接收进程内部的标识符
   wait(j.sm);
   wait(j.mutex);
   remove(j.mq,i);//将消息队列中第一个消息移出
   signal(j.mutex);
   b.sender=i.sender;
   b.size=i.size;
   copy(b.text,i.text);//将消息缓冲区i中的信息复制到接收区b
   releasebuf(i);//释放消息缓冲区
}

2.7 线程的基本概念

2.7.1 线程的引入

线程：为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性

进程的两个基本属性

• 进程 三羊开泰：在系统中能独立运行并作为资源分配的基本单位，由进程控制块、相关数据和程序段组成，是一个能独立运行的活动实体，是操作系统运行的基础。
• 进程是一个可独立调度和分派的基本单位

  程序并发执行所需付出的时空开销

• 创建进程：需要分配资源
• 撤销进程：需要回收资源
• 进程切换：内存访问域变化，占用处理机时间
• 以上这些限制了系统中所设置进程的数目，且进程切换也不宜过于频繁，从而限制了并发程度的进一步提高

  2.7.2 线程和进程相比 我还是觉得我们线程牛批

  线程 threads：线程是一个被调度和分派的基本单位并可独立运行的实体。大多数与执行相关的信息可以保存在线程级的数据结构中，线程是对进程的进一步细分。
• 线程具有以下性质：
  • 线程可以并发执行
  • 线程是系统资源分配和调度的基本单位
  • 同一进程内的线程共享进程资源，它们驻留在同一块地址空间中，并且可以访问到相同的数据
  • 线程具有独立性
  • 线程的切换代价、创建和删除开销要远小于进程
  • 线程支持多处理机系统
    

2.7.3 线程的状态和线程控制块TCB

线程运行的三个状态

• 执行状态：表示线程已经获得处理机且正在运行
• 就绪状态：表示线程已具备了各种执行条件，只需再获得CPU（处理机）便可立即执行
• 阻塞状态：表示线程在执行中因某事件受阻而处于暂停状态

  线程控制块TCB

• 如同每个进程有一个进程控制块一样，系统也为每个线程配置了一个线程控制块，将所有用于控制和管理线程的信息记录在线程控制块中。
• 线程控制块的内容通常由以下几项构成：
  • 线程标识符
  • 一组寄存器：包含程序计数器、状态寄存器和通用寄存器
  • 线程运行状态
  • 优先级
  • 线程专有存储区：存放现场保护信息和线程运行相关统计信息
  • 信号屏蔽
  • 堆栈指针：用于线程调用，保存局部变量和返回地址
• 备注：线程运行状态不是线程的上下文，线程/进程的上下文是在改变线程/进程的状态时的参考

多线程OS中的进程属性

• OS支持在一个进程中的多个线程能并发执行，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：
  • 进程是一个可拥有资源的基本单位（以前是可独立调度和分派的基本单位）
  • 一个进程内的多个线程可并发执行
  • 进程已不是可执行的实体。在多线程OS中，把线程作为独立运行/调度分派的基本单位，但进程仍具有执行相关的状态。如“执行状态”指的是进程中的某线程正在执行;被挂起的进程中的所有线程也被挂起;被激活的进程中的所有线程也被激活

线程状态变化的四种基本操作

• 派生：当产生一个新进程时，同时也为该进程派生了一个初始化线程，随后，可以在同一个进程中派生另一个线程，新线程被放置在就绪队列中
• 阻塞：当线程需要等待另一个事件时，它将阻塞，此时处理器转而执行另一个就绪线程
• 解除阻塞：当阻塞一个线程的事件发生时，该线程被转移到就绪队列中
• 结束：当一个线程完成时，其寄存器的信息和栈都被释放

2.8 线程的实现

2.8.1 线程的实现方式

在OS中的所有进程，无论是系统进程还是用户进程，都是在操作系统内核的支持下运行的。

内核支持线程KST

• 无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤销和切换等，也是依靠内核实现的
• 在内核空间为每一个内核线程设置了一个线程控制块，内核是根据该控制块而感知某线程的存在的，并对其加以控制
• 内核支持线程的四个主要优点
  • 在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行
  • 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可以运行其它进程中的线程
  • 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小
  • 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率
• 内核支持线程的主要缺点：对于用户的线程切换而言其模式切换的开销较大，需要从用户态转到和心态，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的

  用户级线程ULT

• 用户级线程是在用户空间中实现的，线程的创建、撤销、同步和通信等功能都无需内核支持，用户级线程是与内核无关的
• 用户级线程的优点：
  • 线程控制块设置在用户空间，内核完全不知道用户级线程的存在，这样可以节省模式切换系统开销
  • 各进程可以独立选择线程调度算法
  • 用户级线程与操作系统平台无关，甚至可以在不支持线程机制的操作系统平台上实现
• 用户级线程的缺点：
  • 当线程执行系统调用引起进程阻塞时，进程中所有的线程都会被阻塞，会削弱进程中的线程的并发性，而内核支持线程不存在这个问题
  • 由于内核每次给一个进程分配一个CPU（处理机），用户级线程不能有效利用多处理机进行进程内的多线程并行操作，进程中仅有一个线程能够执行，在该线程释放处理机前，其它线程只能等待

组合方式：同时支持内核线程和用户线程

• 三种模式：
  • 多对一（多个用户线程映射到一个内核控制线程）：纯用户线程模式
  • 一对一：内核线程模式、轻量级进程模式
  • 多对多（多个用户线程映射到同样数量或更少数量的内核线程上）：组合模式

2.8.2 线程的实现

内核支持线程的实现

在仅设置了内核支持线程的OS中，系统在创建一个新进程时便为它分配一个任务数据区PTDA，其中包括若干个TCB空间，在每一个TCB中可保存线程标识符、优先级、线程运行的CPU状态等信息，每当进程要创建一个线程时，便为新线程分配一个TCB并将有关信息填入TCB中、为之分配必要的资源。当PTDA中的所有TCB空间已用完，而进程又要创建新的进程时，只要其所创建的线程数目未超过系统的允许值，系统可为再为其分配新的TCB空间。在撤销一个线程时，要么由系统回收，要么由进程回收供进程内的其它线程使用

用户级线程的实现

运行时系统

运行时系统，即用于管理和控制线程的函数（过程）的集合，其中包括用于创建和撤销线程的函数、线程同步和通信的函数以及实现线程调度的函数等。因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，作为用户级线程和内核之间的接口。用户层对用户级线程的全部支持

内核控制线程

内核控制线程，也称为轻型进程LWP，每一个进程都可拥有多个LWP。每个LWP都有自己的数据结构（和2.7.3中给出的一样）他们也可以共享进程所拥有的资源。LWP可以通过系统调用来获得内核提供的服务，这样可使用户级线程运行时只用连接到一个LWP上便具有内核支持线程的所有属性。用户级线程进行系统调用的接口

2.8.3 线程的创建和终止（略）

依照学校教学安排，第一章为操作系统引论

本帖仅供个人学习使用

使用虚拟机平台VMware Workstation

1.1 操作系统的目标和作用

1.1.1 操作系统的目标（考点）

• 方便性：没有OS的计算机是极难使用的，只能使用机器语言，OS对计算机操作进行了抽象化，使计算机便于易学易用。
• 有效性：OS可以通过合理地组织计算机的工作流程，加速程序的运行，缩短程序的运行周期，提高系统的吞吐量。
• 可扩充性：为适应计算机硬件、体系结构以及计算机应用发展的要求，OS必须具有很好的可扩充性，这与OS的结构有十分紧密的联系，由此推动OS从早期的无结构发展为模块化结构，进而又发展为层次化结构，近年来OS已广泛采用微内核结构。
• 开放性：为适应计算机应用日益普及的要求和互联网时代的发展，使OS的应用环境从单机转向网络环境，其使用环境必须更为开放，要求OS必须能遵循世界标准规范，从而兼容以相同标准开发的硬件软件。

1.1.2 操作系统的作用（考点）（见1.4）

• OS是用户与计算机硬件系统之间的接口
• OS是计算机系统资源的管理者
• OS实现了对计算机资源的抽象
• OS/虚拟机是计算机硬件平台上的虚拟机器

1.1.3 推动操作系统发展的主要动力（考点）

• 不断提高计算机资源利用率
• 方便用户
• 硬件的不断更新换代
• 计算机体系结构的不断发展
• 不断提出新的应用需求

1.2 操作系统的发展过程

• 人工操作方式：卡带I/O，一个程序运行完毕并取走计算结果（卡带）后下一个人/程序才能上机，效率极低，人工读带（参考《功勋》里面于敏那集，人工读机器语言，属实是黑客帝国现实版了）。
• 脱机I/O方式：事先将装有用户程序和数据的纸带装入纸带输入及，在一台外围机的控制下将卡带上的数据或程序输入到磁带上，当CPU需要这些程序或数据时再从磁带上高速地调入内存。输出时先从内存高速输送到磁带上，然后在外围机控制下通过相应输出设备输出。（个人理解是用磁带来当一个缓存），减少了CPU的空闲时间，I/O操作均由外围机操作，提高了I/O速度。
• 单道批处理系统：处理完一个作业后紧接着处理下一个作业以减少机器的空闲等待时间，旨在提高系统资源利用率，但缺点也在用提高的不够充分，这是因为在内存中仅有一道程序，必须在I/O完成后才能运行，又因为I/O设备的低速性，更使CPU的利用率显著降低。若通过增大内存来提高效率，则会因为实际中80%以上的作业都属于中小型而造成在单道程序环境下对内存的浪费。
• 多道批处理系统：用户所提交的作业先存放在外存上，并排成一个队列称为“后备队列”然后由作业调度程序按一定的算法，从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源，让它们交替在CPU上运行
  • 多道性、调度性、无序性
  • 优点：资源利用率高、系统吞吐量大
  • 缺点：平均周转时间长（作业要排队依次进行处理），无交互能力（用户不能与自己的程序交互直至作业完成）
  • 要解决的问题：处理机争用问题、内存分配和保护问题、I/O设备分配问题、文件的组织和管理问题、作业管理问题、用户与系统的接口问题…（后续都会进一步讨论）
• 分时系统
  • 需求：人机交互、共享主机（支持多设备同时I/O，多用户共享计算机资源）
  • 关键问题：及时接收、及时处理
  • 特征：多路性（允许多台终端同时连接到一台主机上，并按分时原则为每个用户服务）、独立性（每个用户彼此之间互不干扰）、及时性（用户请求短时间内获得响应）、交互性（用户可通过终端与系统进行广泛的人机对话）
• 实时系统
  • 任务类型：周期性实时任务和非周期性实时任务、硬实时任务和软实时任务
  • 实时系统与分时系统特征的比较
    区别|实时系统|分时系统

–:|:–:|:–
多路性|系统周期性地对多路现场信息进行采集、对多个对象进行控制|系统按分时原则为多个终端用户服务
独立性|信息采集和对对象控制互不干扰，多用户与系统交互互不干扰|多用户与系统交互互不干扰
及时性|以控制对象所要求的的截止时间来决定对实时性的要求|对实时性的要求（延迟）是依据人能所接受的等待时间决定的
交互性|交互性仅限于访问系统中某些特定的专用服务程序|能向终端用户提供数据处理、资源共享等服务，实现广泛的人机对话
可靠性|要求系统高度可靠，采用多级容错措施| 要求系统可靠

• 多道批处理系统、分时系统、实时系统是三种基本操作系统
• 微机操作系统的发展（略）

1.3 操作系统的基本特性（考点）

• 操作系统的四个基本特征：并发、共享、虚拟、异步

1.3.1 并发

并行与并发

• 并行：在同一时刻发生多个事件
• 并发：在同一时间间隔内发生多个事件
• 并行有并发，并发无并行

进程的引入

• 进程：在系统中能独立运行并作为资源分配的基本单位，由机器指令、数据和堆栈等组成，是一个能独立运行的活动实体，多个进程之间可以并发执行和交换信息，是操作系统运行的基础
• 进程将程序的执行分段化，使得多个程序可以并发执行，大大提高资源系统的利用率，增加系统的吞吐量

1.3.2 共享

• 共享：系统中的资源可供内存中多并发作业共同使用
• 互斥共享方式：一个进程访问资源时其他进程需要等待，我们将这种一段时间内只允许一个进程访问的资源称为 临界资源，系统中给的绝大多数物理设备以及栈、变量和表格都属于临界资源，只能被互斥地共享。
• 同时访问方式：这里的“同时”在单处理机环境下是宏观意义上的，而在微观上，这些进程对资源的访问是交替进行的。
• 并发和共享是多用户OS的两个最基本特征

1.3.3 虚拟 无中生有

• 时分复用技术（时间）：多个用户交替使用处理机/物理IO设备
  • 虚拟处理机技术：为每道程序建立至少一个进程，让多个程序并发执行，虽然微观上系统只有一台处理机，但通过分时复用方法在宏观将处理机虚拟为多台逻辑上的处理机
  • 虚拟设备技术：将一台物理I/O设备在宏观上虚拟为多台逻辑上的I/O设备，在微观上让不同应用的进程交替使用I/O设备
  • 虚拟设备处理速度≤V/n，n为虚拟设备/并发应用个数，V为处理机处理速度
• 空分复用技术（空间）：每次只向内存中导入程序中被需要的部分，实现程序在比它小的内存中运行，并实现多个程序对内存的同时使用。，空分复用体现在将内存分为多个小部分供多个应用同时使用，时分复用体现在每个应用每次只导入当前需要的部分，用完就置换，让应用的每个部分分时进入内存。
  • 虚拟设备占用空间≤S/N，n为虚拟设备/并发应用个数，S为内存大小

1.3.4 异步

• 异步：每个程序不知何时执行何时结束。
• 由于资源等因素的限制，进程在发出资源请求时通常不能及时得到满足，因此进程的执行通常不是一气呵成而是以停停走走的方式运行，导致了程序的执行时间是不可知的。

1.4 操作系统的主要功能

1.4.1 处理机管理功能（考点）

• 进程控制
• 进程同步
• 进程通信
• 处理机调度

  1.4.2 存储器管理功能（考点）

• 内存分配：
  • 为每道程序分配内存空间
  • 提高存储器的利用率
  • 允许正在运行的程序申请附加的内存空间
  • 分配方式：
    • 静态分配方式：每个作业的内存空间是在作业装入时确定的
    • 动态分配方式：每个作业的内存空间在作业装入是基本确定，反允许作业在运行过程中继续申请添加新的附加内存空间
• 内存保护：
  • 确保每道用户程序都互不干扰，仅在各自内存中运行
  • 绝不允许用户程序访问操作系统的程序和数据，也不允许用户程序转到非共享的其它用户程序中去执行
• 地址映射：使各程序段的逻辑地址转换为内存空间中与之相对应的物理地址
• 内存扩充：借助虚拟存储技术从逻辑上扩充内存容量（比如1.3.3提到的空分复用技术）

  1.4.3 设备管理功能（知道有就行）

• 缓冲管理
• 设备分配
• 设备处理

  1.4.4 文件管理功能（知道有就行）

• 文件存储空间的管理
• 目录管理
• 文件的读写管理与保护

  1.4.5 操作系统与用户之间的接口（知道有就行）

• 用户接口：让用户直接或间接地控制自己的作业
• 程序接口：让程序方便地使用系统调用

  1.4.6 现代操作系统的新功能：系统安全、网络功能和服务、支持多媒体

  1.5 OS结构设计

  1.5.1 传统操作系统结构

• 古早的无结构操作系统：单人设计，规模小，缺乏首尾一致的设计思想，复杂又混乱
• 模块化结构OS：有较为清晰的结构，由若干个具有一定独立性和大小的模块构成，每个模块分工不同，模块内又划分为若干个小模块，规定好各子模块之间的接口和模块间的接口
  • 优点：提高了OS设计的准确性、可理解性和可维护性、增强了OS的可适应性、加速了OS的开发过程
  • 缺点：设计时对各模块间的接口规定很难满足在模块设计完成后对接口的实际需求，设计者的决策必须基于上一个决策，造成可靠性的难以保障
• 分层式结构OS：目标系统An和裸机系统（物理硬件）A0之间铺设若干个层次的软件，使An通过这些层次的软件最终在A0上运行，在OS中通常采用自底向上法来铺设这些中间层
  • 优点：由于自底向上保证了决策的顺序性，从而易于保证系统的正确性；在系统中增加、修改、替换一个层次中的模块或整个层次只要不改变相应层次间的接口就不会影响其他层次，这使系统维护和扩充更加容易
  • 缺点：OS每执行一个功能，通常要自上而下地穿越多个层次，增加了系统的通信开销，导致系统效率的降低

    1.5.2 客户服务器模式 （详情请见计网笔记第一章）

• 客户服务器系统的三个部分：客户机、服务器、网络系统
• 过程：客户机发送请求——服务器接收消息——服务器回送消息——客户机接收消息
• 优点：数据分布处理和存储提升了可靠性、缓解了处理能力瓶颈；便于集中管理；具有灵活性和可扩充性；支持且易于改编应用软件
• 缺点：若系统只有一个服务器，则一旦服务器故障，将导致整个网络瘫痪，也存在处理瓶颈，可通过增加网络中服务器数量来缓解该问题

  1.5.3 面向对象程序设计技术

• 啊这……就是抽象，将数据类型、数据结构、数据文件等进行抽象，方便调用，具体不细说了x
• 优点：通过重用提高产品质量和生产率、使系统具有更好的易修改性和易扩展性、更易于保证系统的正确性和可靠性

  1.5.4 微内核OS结构

  什么是微内核

• 内核：能实现现代OS最基本核心功能的小型内核，微内核并非是一个完整的OS，只是具有OS最基本的部分，通常包含：与硬件处理紧密相关的部分、一些较为基本的功能、客户和服务器之间的通信

  微内核的基本功能

• 进程管理
• 低级存储器管理
• 中断和陷入处理

  微内核操作系统的优点

• 提高了系统的可扩展性
• 增强了系统的可靠性
• 可移植性强
• 提供了对分布式系统的支持
• 融入了面向对象技术，提高系统正确性、可靠性、易修改性、易扩展性，同时减少开发系统的开销

依照学校教学安排，第四章为数据库设计与实现

本帖仅供个人学习使用

使用软件 pgAdmin4, Power Designer

（更新中）

4.1 数据库设计概述

4.1.1 数据库设计方案

数据库设计是数据库应用系统开发的重要内容。在实现数据库之前，必须有明确的设计方案。数据库设计方案主要体现为数据库设计报告及其设计模型。在数据库设计报告中，需要明确：

• 数据库设计目标
• 数据库设计思路
• 数据库设计约束
• 数据库命名规则
• 数据库应用结构
• 数据库应用访问方式
• 数据库设计模型
  …

数据库设计方案的核心内容有数据库应用架构设计、数据库结构模型设计、数据库应用访问方法设计

数据库应用架构设计

在不同应用需求场景中，数据库的应用架构方式是不同的。数据库应用架构可分为单用户结构、集中式结构、客户-服务器结构和分布式结构。

数据库结构模型设计

数据库结构模型设计一般分为概念层设计、逻辑层设计、物理层设计，它们的设计模型分别为概念数据模型、逻辑数据模型和物理数据模型。

数据库应用访问方法设计

数据库应用对数据库访问可以有多种方式，如直接本地接口连接访问、基于标准结构连接访问、基于数据访问层框架连接访问

4.1.2 数据库结构模型

• 概念数据模型是一种面向用户的系统数据模型，它用来描述现实世界的系统概念化数据结构。使数据库设计人员在系统设计的初始阶段摆脱计算机系统及DBMS的具体技术问题，集中精力分析业务数据以及数据之间的联系等，描述系统的数据对象及其组成关系。
• 逻辑数据模型是在概念数据模型的基础上，从系统设计角度描述系统的数据对象组成及其关联结构，并考虑这些数据对象符合数据库对象的逻辑表示。
• 物理数据模型是在逻辑数据模型基础上，针对具体DBMS所设计的数据模型。它用于描述系统数据模型在具体DBMS中的数据对象组织、存储方式、索引方式、访问路径等实现信息。

  4.1.3 数据库开发过程及设计策略

  数据库开发过程

• 数据需求分析阶段
  • 从现实业务获取数据表单、报表、查询、业务规则、数据更新的说明
  • 分析系统的数据特征、数据类型、数据取值约束
  • 描述系统的数据关系、数据处理要求
  • 建立系统的数据字典
• 数据库设计阶段
  • 数据库模型结构设计（概念数据模型、逻辑数据模型、物理数据模型）
  • 数据库索引、视图、查询设计
  • 数据库表约束设计
  • 数据库触发器、存储过程设计
• 数据库实现阶段
  • 数据库创建
  • 数据模型物理实现
• 数据库测试阶段
  • 数据库数据上线
  • 数据库系统测试

设计策略

• 自底向上设计：首先具体分析各业务数据需求，并抽象各业务的数据实体及其关系，然后设计各个业务的数据模型。在设计过程中，不断地概括、分类与规范数据模型，并建立反应整个组织的全局数据模型。
• 自顶向下设计：首先从组织机构全局角度规划设计组织机构顶层的数据模型，然后分别对各部门所涉及的业务数据进行实体联系建模。在设计过程中，自顶向下逐步细化数据模型设计。
• 自内向外设计策略：首先确定组织机构的核心业务，对核心业务数据进行建模设计，然后逐步扩散到其它外围业务的数据模型设计。
• 混合策略设计：融合以上设计策略，对组织机构数据库进行建模设计，同时应用多种设计策略进行数据建模，避免单一设计策略导致的数据库建模设计局限。

4.1.4 主流数据库建模工具Power Designer

当今，数据库设计都必须借助系统建模工具来实现模型设计，此处介绍Power Designer。
Power Designer 是一种面向软件开发生命周期的建模工具，它提供软件需求模型、业务流程模型、数据库模型、面向对象模型、自定义模型的开发支持。

4.1.5 Power Designer各个数据模型之间的关系

在通常数据库设计中，首先设计概念数据模型，然后将其转换设计为逻辑数据模型，最后针对选型的数据库DBMS将逻辑数据模型转化为支持该DBMS的物理数据模型。若设计中不考虑规范化问题，可以将概念数据模型直接转换设计为物理数据模型。当完成PDM物理数据模型设计后，便可将其在DBMS系统中进行数据库实现。

4.2 E-R模型方法

4.3 数据库建模设计

4.4 数据库规范化设计

4.5 数据库设计模型SQL实现

4.6 基于Power Designer的数据库设计建模实践（略）