CSCI3150 L08 Scheduling: Proportional Share

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L08 Scheduling: Proportional Share，第 3 部分 / 共 4 部分 · 原件 L08-CPU调度-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.34–44 定位：能把票数换成全局份额，追踪Lottery中奖区间与Stride的pass，并正确解读短期公平指标。 前后：上一份 Part II · 下一份 Part IV

p.34 Part III分节页。

让CPU份额服从权重

票数表示相对份额（p.35–36）【新】

p.35 Fair-share scheduler

Guarantee that each job obtain a certain percentage of CPU time.

Not optimized for turnaround or response time

p.36 Tickets

Represent the share of a resource that a process should receive

The percent of tickets represents its share of the system resource in question.

Example

There are two processes, A and B.

Process A has 75 tickets  receive 75% of the CPU

Process B has 25 tickets  receive 25% of the CPU

p.35切换目标：比例份额关注各任务取得多少CPU，而非首先让某个任务结束或响应。p.36中A75票、B25票，总100，因此目标份额A=75/100=75%，B=25%。票数是相对量：所有票同时翻倍，比例不变；仅一个任务增加票数则所有人的分母也变了。

抽签的短期结果与票币换算（p.37–38）

p.37 The scheduler picks a winning ticket.

Load the state of that winning process and runs it.

Example

There are 100 tickets

Process A has 75 tickets: 0 ~ 74

Process B has 25 tickets: 75 ~ 99

p.37 63 85 70 39 76 17 29 41 36 39 10 99 68 83 63

p.37 The longer these two jobs compete,

The more likely they are to achieve the desired percentages.

p.38 Ticket currency

A user allocates tickets among their own jobs in whatever currency they would like.

The system converts the currency into the correct global value.

Example

There are 200 tickets (Global currency)

Process A has 100 tickets

Process B has 100 tickets

p.38 User A  500 (A’s currency) to A1  50 (global currency)

 500 (A’s currency) to A2  50 (global currency)

p.38 User B  10 (B’s currency) to B1  100 (global currency)

题面（同原件 · Lottery scheduling · p.37）

p.37 There are 100 tickets

p.37 Process A has 75 tickets: 0 ~ 74

p.37 Process B has 25 tickets: 75 ~ 99

p.37 Scheduler’s winning tickets: 63 85 70 39 76 17 29 41 36 39 10 99 68 83 63

逐个比较中奖号：小于75为A，75–99为B，得到A B A A B A A A A A A B A B A。算一遍：A出现11次，B4次，实际份额11/15≈73.33%与26.67%；目标75/25不要求每个有限窗口都精确相等。票数决定每次概率，长时间统计才更接近期望。

p.38中用户A和B各有100全局票。A内部给A1/A2各500本地票，先算内部比例500/1000=1/2，再乘100，各50全局票；B内部10票全部给B1，因此B1仍取得100全局票。不能跨用户直接比较500与10，否则混淆不同币值单位。

转移、膨胀与累计区间实现（p.39–40）

p.39 Ticket transfer

A process can temporarily hand off its tickets to another process.

Ticket inflation

A process can temporarily raise or lower the number of tickets it owns.

If any one process needs more CPU time, it can boost its tickets.

p.40 Example: There are three processes, A, B, and C.

Keep the processes in a list:

课件程序与接口（p.40，原页片段）

1   // counter: used to track if we’ve found the winner yet
2   int counter = 0;
3
4   // winner: use some call to a random number generator to
5   // get a value, between 0 and the total # of tickets
6   int winner = getrandom(0, totaltickets);
7
8   // current: use this to walk through the list of jobs
9   node_t *current = head;
10
11  // loop until the sum of ticket values is > the winner
12  while (current) {
13      counter = counter + current->tickets;
14      if (counter > winner)
15          break; // found the winner
16      current = current->next;
17  }
18  // ’current’ is the winner: schedule it...

p.39允许临时转票，表达把自己的份额交给另一任务；票数膨胀则临时增减权重。补充：膨胀需在可信管理规则下使用，否则任务自行无限增票就破坏公平。

p.40链表A100、B50、C250，总400。遍历累计边界100、150、400，选第一个严格大于中奖号的节点。算一遍：winner=120（数字是我为演示取的，讲义没给），A累计100不大于120，继续；B累计150>120，选B。合法中奖整数为0–399；若随机函数包含400而算法还用严格大于，则没有节点命中，边界必须统一。

从0至总票数减1均匀抽一个整数
累计票数从0开始
依次加入每个任务票数
第一次累计值大于中奖号时选中该任务

公平指标与样本长度（p.41–42）

p.42 There are two jobs.

Each jobs has the same number of tickets (100).

本页正文是位图，已视觉读取。两个等长作业各需10，若分别在10和20完成，U=10/20=0.5；若接近同时结束，U接近1。名称虽为unfairness metric，方向却是越接近1越公平，不能按单词直觉把0解释成最好。

图（p.42）：平均U随作业长度增加 元素：横轴Job Length约1–1000、纵轴Unfairness (Average)约0–1，曲线由约0.5上升至接近1。 看什么：短作业抽签次数少，随机波动更明显；长期比例正确不等于短期完成时刻公平。

补充：概率、份额和完成时刻分别是什么。 A 有75%的票，表示在每次按相同票池均匀抽签时，A 中签概率为0.75。若连续四次都选A，这一具体事件的概率为 $0.75^4=0.31640625$；因此“四片里一定给B一片”不是彩票算法的承诺。这里假设各次独立抽签、任务一直可运行、票数不变，是为解释随机波动自取的窗口。

份额还取决于计量单位。如果中奖者每次运行的片长相同，获奖次数可近似代表 CPU 服务；若有的任务提前阻塞，单数中奖次数不能直接当实际CPU时间。原表默认的可比较片长是算比例的前提。

Stride 用虚拟进度代替抽签：权重大者每运行一次只走较小一步，因此会较频繁地落在最小 pass 一侧。pass 不是已经运行的真实毫秒数；不同权重下，同样一片加的 pass 不同。每次选择前比较旧 pass，选择后只更新该任务，才能复现 p.44 的表。

用确定性步长接近比例

Stride与pass（p.43–44）【新】

p.43 Stride of each process

(A large number) / (the number of tickets of the process)

Example: A large number = 10,000

Process A has 100 tickets  stride of A is 100

Process B has 50 tickets  stride of B is 200

A process runs, increment a counter(=pass value) for it by its stride.

Pick the process to run that has the lowest pass value

课件程序与接口（p.43，原页片段）

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

stride是每运行一片增加的虚拟进度，设常数K=10000，A100票得到100，B50票得到200，C250票得到40。票越多，步子越小，因而更快再次成为最小pass。每次只增加被选者的pass，不把所有任务都加一次。

表（p.44）：课件的运行前pass与选择

算一遍：8片内A2次、B1次、C5次，比例2:1:5，与100:50:250相同；同pass时按表给出的顺序打破平局。若老任务pass都200，新任务从0开始且stride40，则先跑5次才追到200，这解释新任务零初始化为什么可能暂时独占。补充：实际加入策略要与当前虚拟进度对齐，不能一律从零开始。

考试角度：（C 级 通识）常见考法是给票数手算随机中奖区间或stride表，并解释随机公平和确定性比例的差别。

补充：原表为什么每八片回到一次共同进度。 表内 A 每片走 100，B 每片走 200，C 每片走 40。让三者从 0 都走到 200，A 需要 200/100=2 片，B 需要 200/200=1 片，C 需要 200/40=5 片；合计八片，恰好解释表末的三个 200。不是先规定运行 2、1、5 次再硬排顺序，而是“总选最小 pass”逐步产生这个结果。

共同 pass 不等于各自获得相同 CPU 时间。它代表按各自权重折算后的进度追平；服务次数恰恰不同，才实现不同票数对应的份额。若手算中每轮给未被选者也增加 stride，所有人都会在没有获得服务时虚增进度，原来的比例意义就消失了。平局时可用明确固定顺序继续，但不能从这一段八片的精确比例推出任意长度的前缀都精确满足 2:1:5。

本讲核心考点

• 份额=自身票数/总票数（p.35–38，C 级通识考法）。
• Lottery短期可偏离目标比例（p.37、41–42，C 级通识考法）。
• 本地票币先换为全局权重（p.38，C 级通识考法）。
• Stride选最小pass，运行后仅给选中者加stride（p.43–44，C 级通识考法）。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

• 原件：L08-CPU调度-2022未核.pptx（本地课件）；PDF副本（本地课件） p.34–44。本文页码均为 PDF 页号。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。