Linux内核分析之调度算法
inux调度算法在2.6.32中采用调度类实现模块式的调度方式。这样，能够很好的加入新的调度算法。
linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，他允许多种不同哦可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，调度代码会按照优先级遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那个程序。
linux上主要有两大类调度算法，CFS(完全公平调度算法）和实时调度算法。宏SCHED_NOMAL主要用于CFS调度，而SCHED_FIFO和SCHED_RR主要用于实时调度。如下面的宏定义：
1./*
2.* Scheduling policies
3.*/
4./*支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR.
5.*/
6.
7./*(也稱為SCHED_OTHER): 主要用以排程
8.一般目的的Task.*/
9.#define SCHED_NORMAL 0
10.#define SCHED_FIFO 1
11./*task預設的Time Slice長度為100 msecs*/
12.#define SCHED_RR 2
13./*主要用以讓Task可以延長執行的時間
14.(Time Slice),減少被中斷發生Task Context-Switch
15.的次數.藉此可以提高Cache的利用率
16.(每次Context-Switch都會導致Cache-Flush). 比
17.較適合用在固定週期執行的Batch Jobs任
18.務主機上,而不適合用在需要使用者互
19.動的產品(會由於Task切換的延遲,而
20.感覺到系統效能不佳或是反應太慢).*/
21.#define SCHED_BATCH 3
22./* SCHED_ISO: reserved but not implemented yet */
23./*為系統中的Idle Task排程.*/
24.#define SCHED_IDLE 5
linux调度算法实现的高层数据结构主要有运行实体、调度类、运行队列，下面我们主要看看这几个数据结构的字段和意义。
运行实体，rq结构体每个cpu有一个，主要存储一些基本的用于调度的信息，包括实时调度的和CFS调度的
1./*每个处理器都会配置一个rq*/
2.struct rq {
3./* runqueue lock: */
4.spinlock_t lock;
5.
6./*
7.* nr_running and cpu_load should be in the sa
me cacheline because
8.* remote CPUs use both these fields when doin
g load calculation.
9.*/
10. /*用以记录目前处理器rq中执行task的数量*/
11. unsigned long nr_running;
12.#define CPU_LOAD_IDX_MAX 5
13. /*用以表示处理器的负载，在每个处理器的rq中
14.都会有对应到该处理器的cpu_load参数配置，在每次
15.处理器触发scheduler tick时，都会呼叫函数
16.update_cpu_load_active,进行cpu_load的更新。在系统初始化
的时候
17.会呼叫函数sched_init把rq的cpu_load array初始化为0.
18.了解他的更新方式最好的方式是通过函数update_cpu_load,公
式如下澹?
19.cpu_load[0]会直接等待rq中load.weight的值。
20.cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2
21.cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4
22.cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8
23.cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16
24.呼叫函数this_cpu_load时，所返回的cpu load值是
cpu_load[0]
25.而在进行cpu blance或migration时，就会呼叫函数
26.source_load target_load取得对该处理器cpu_load index
值，
27.来进行计算*/
28. unsigned long cpu_load[CPU_LOAD_IDX_MAX];
29.#ifdef CONFIG_NO_HZ
30. unsigned long last_tick_seen;
31. unsigned char in_nohz_recently;
32.#endif
33. /* capture load from *all* tasks on this cpu:
*/
34. /*load->weight值，会是目前所执行的schedule entity的
35.load->weight的总和，也就是说rq的load->weight越高，
36.也表示所负责的排程单元load->weight总和越高
37.表示处理器所负荷的执行单元也越重*/
38. struct load_weight load;
39. /*在每次scheduler tick中呼叫update_cpu_load时，
40.这个值就增加一，可以用来反馈目前cpu
41.load更新的次数*/
42. unsigned long nr_load_updates;
43. /*用来累加处理器进行context switch的次数，会在
44.函数schedule呼叫时进行累加，并可以通过函数
45.nr_context_switches统计目前所有处理器总共的
context switch
46.次数，或是可以透过查看档案/proc/stat中的ctxt位得知目
前
47.整个系统触发context switch的次数*/
48. u64 nr_switches;
49.
50. u64 nr_migrations_in;
51. /*为cfs fair scheduling class 的rq*/
52. struct cfs_rq cfs;
53. /*为real-time scheduling class 的rq*/
54. struct rt_rq rt;
55.
56./*用以支援可以group cfs tasks的机制*/
57.#ifdef CONFIG_FAIR_GROUP_SCHED
58. /* list of leaf cfs_rq on this cpu: */
59. /*在有设置fair group scheduling 的环境下，
60.会基于原本cfs rq中包含有若干task的group
61.所成的排程集合，也就是说当有一个group a
62.就会有自己的cfs rq用来排程自己所属的tasks,
63.而属于这group a的tasks所使用到的处理器时间
64.就会以这group a总共所分的的时间为上限。
65.基于cgroup的fair group scheduling 架构，可以创造出
66.有阶层性的task组织，根据不同task的功能群组化
67.在配置给该群主对应的处理器资源，让属于
68.该群主下的task可以透过rq机制排程。使用属于
69.该群主下的资源。
70.这个变数主要是管理CFS RQ list，操作上可以透过函数
71.list_add_leaf_cfs_rq把一个group cfs rq加入到list中，
或透过
72.函数list_del_leaf_cfs_rq把一个group cfs rq移除，并可
以
73.透过for_each_leaf_cfs_rq把一个rq上得所有leaf cfs_rq
走一遍
74.*/
75. struct list_head leaf_cfs_rq_list;
76.#endif
77./*用以支援可以group real-time tasks的机制*/
78.#ifdef CONFIG_RT_GROUP_SCHED
79. /*类似leaf_cfs_rq_list所扮演的角色，只是这里
80.是针对属于real-time的task,在实际操作上可以
81.透过函数list_add_leaf_rt_rq,list_del_leaf_rt_rq或
82.巨集for_each_leaf_rt_rq*/
83. struct list_head leaf_rt_rq_list;
84.#endif
85.
86. /*
87.* This is part of a global counter where onl
y the total sum
88.* over all CPUs matters. A task can increase
this counter on
89.* one CPU and if it got migrated afterwards
it may decrease
90.* it on another CPU. Always updated under the
runqueue lock:
91.*/
92. /*一般来说，linux kernel 的task状态可以为
TASK_RUNNING
93.TASK_INTERRUPTIBLE(sleep),
94.TASK_UNINTERRUPTIBLE(Deactivate Task,此时Task会从rq
中
95.移除)或TASK_STOPPED.
96.透过这个变数会统计目前rq中有多少task属于
97.TASK_UNINTERRUPTIBLE的状态。当呼叫函数
98.active_task时，会把nr_uninterruptible值减一，并透
过该函数
99.enqueue_task把对应的task依据所在的scheduling class 100.放在对应的rq中，并把目前rq中nr_running值加一*/
101.unsigned long nr_uninterruptible;
102./*curr:指向目前处理器正在执行的task;
103.idle:指向属于idle-task scheduling class 的idle task;
104.stop:指向目前最高等级属于
stop-task scheduling class
105.的task;*/
106.struct task_struct *curr, *idle;
107./*基于处理器的jiffies值，用以记录下次进行处理器
108.balancing 的时间点*/
109.unsigned long next_balance;
110./*用以存储context-switch发生时，前一个task的memory management
111.结构并可用在函数finish_task_switch中，透过函数mmdrop释放前一个
112.task的记忆体资源*/
113.struct mm_struct *prev_mm;
114./*用以记录目前rq的clock值，基本上该值会等于透过sched_clock_cpu
115.(cpu_of(rq))的回传值，并会在每次呼叫scheduler_tick 时透过
116.函数update_rq_clock更新目前rq clock值。
117.在实作部分，函数sched_clock_cpu会透过sched_clock_local或
118.ched_clock_remote取得对应的sched_clock_data,而处理的sched_clock_data
119.值，会透过函数sched_clock_tick在每次呼叫scheduler_tick时进行更新；
120.*/
121.u64 clock;
122./*用以记录目前rq中有多少task处于等待i/o的sleep 状态
123.在实际的使用上，例如当driver接受来自task的调用，但处于等待i/o
124.回复的阶段时，为了充分利用处理器的执行资源，这时125.就可以在driver中呼叫函数io_schedule，此时
126.就会把目前rq中的nr_iowait加一，并设定目前task的io_wait为1
127.然后触发scheduling 让其他task有机会可以得到处理器执行时间*/
128.atomic_t nr_iowait;
129.
130.#ifdef CONFIG_SMP
131./*root domain是基于多核心架构下的机制，
132.会由rq结构记住目前采用的root domain，其中包括了133.目前的cpu mask(包括
span,online rt overload), reference count 跟cpupri
134.当root domain有被rq参考到时，refcount 就加一，反之就减一。而cpu
135.mask span表示rq可挂上的cpu mask,noline为rq目前已经排程的
136.cpu mask cpu上执行real-time task.可以参考函数pull_rt_task，当一个rq中属于
137.real-time的task已经执行完毕，就会透过函数pull_rt_task从该
138.rq中属于rto_mask cpu mask 可以执行的处理器上，找出是否有一个处理器
139.有大于一个以上的real-time task，若有就会转到目前这个执行完成
140.real-time task 的处理器上
141.而cpupri不同于Task本身有区分140個(0-139)
142.Task Priority (0-99為RT Priority 而100-139為Nice值-20-19).
143.CPU Priority本身有102個Priority (包括,-1 為Invalid,
144.0為Idle,1為Normal,2-101對應到
Real-Time Priority 0-99).
145.參考函式convert_prio, Task Priority如果是140就會對應到
146.CPU Idle,如果是大於等於100就會對應到CPU Normal,
147.若是Task Priority介於0-99之間,就會對應到CPU Real-Time Priority 101-2之間.)
148.在實際的操作上,例如可以透過函式cpupri_find
149.帶入一個要插入的Real-Time Task,此時就會依據cpupri 中
150.pri_to_cpu選擇一個目前執行Real-Time Task且該Task
151.的優先級比目前要插入的Task更低的處理器,
152.並透過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask.
153.實作的部份可以參考檔案kernel/sched_cpupri.c.
154.在初始化的過程中,會透過函式sched_init呼叫函式init_defrootdomain,
155.對Root Domain與CPU Priority機制進行初始化. 156.*/
157.struct root_domain *rd;
158./*Schedule Domain是基於多核心架構下的機制.
159.每個處理器都會有一個基礎的Scheduling Domain, 160.Scheduling Domain可以有階層性的架構,透過parent 161.可以找到上一層的Domain,或是透過child找到
162.下一層的Domain (NULL表示結尾.).並可透過span 163.栏位,表示這個Domain所能涵蓋的處理器範圍.
164.通常Base Domain會涵蓋系統中所有處理器的個數, 165.而Child Domain所能涵蓋的處理器個數不超過它的166.Parent Domain. 而當在進行Scheduling Domain 中的Task Balance
167.時,就會以該Domain所能涵蓋的處理器為最大範圍. 168.同時,每個Schedule Domain都會包括一個或一個以上的
169.CPU Groups (結構為struct sched_group),並透過next變數把
170.CPU Groups串連在一起(成為一個單向的
Circular linked list),
171.每個CPU Group都會有變數cpumask來定义這個CPU Group
172.所涵蓋的處理器範圍.並且CPU Group所包括的處理器173.範圍,必需涵蓋在所屬的Schedule Domain處理器範圍中.
174.當進行Scheduling Domain的Balancing時,會以其下的CPU Groups
175.為單位,根據cpu_power （會是該Group所涵蓋的處理器
176.Tasks Loading的總和）來比較不同的CPU Groups的負荷,
177.以進行Tasks的移動,達到Balancing的目的.
178.在有支援SMP的架構下,會在函式sched_init中,呼叫open_softirq,
179.註冊SCHED_SOFTIRQ Software IRQ与其对应的Callback函式
180.run_rebalance_domains. 並會在每次呼叫函式scheduler_tick時,
181.透過函式trigger_load_balance确认是否目前的jiffies 值已經
182.大於RunQueue下一次要觸發Load Balance的next_balance時間值,
183.並透過函式raise_softirq觸發
SCHED_SOFTIRQ Software IRQ.
184.在Software IRQ觸發後,就會呼叫函式
run_rebalance_domains,
185.並在函式rebalance_domains中,進行后续處理器上的186.Scheduling Domain Load Balance動作.
187.有關Scheduling Domain進一步的內容,也可以參考188.Linux Kernel文
件Documentation/scheduler/sched-domains.txt.
189.*/
190.struct sched_domain *sd;
191./*這值會等於函式idle_cpu的返回值,如果為1表示192.目前CPU RunQueue中執行的為Idle Task. 反之為0,
193.則表示處理器執行的不是Idle Task (也就是說
194.處理器正在忙碌中.).*/
195.unsigned char idle_at_tick;
196./* For active balancing */
197./*若這值不為0,表示會有在Schedule排程動作
198.結束前,要呼叫的收尾函式. (实作為inline函式
199.post_schedule in kernel/sched.c),目前只有Real-Time Scheduling
200.Class有支援這個機制(會呼叫函式
has_pushable_tasks
201.in kernel/sched_rt.c).*/
202.int post_schedule;
203./*當RunQueue中此值為1,表示這個RunQueue正在進行204.Fair Scheduling的Load Balance,此時會呼叫stop_one_cpu_nowait
205.暫停該RunQueue所屬處理器的排程,並透過函式
206.active_load_balance_cpu_stop,把Tasks從最忙碌的處理器,
207.移到Idle的處理器上執行.*/
208.int active_balance;
209./*用以儲存目前進入Idle且負責進行Load Balance 210.流程的處理器ID. 呼叫的流程為,在呼叫函式schedule 時,
211.若該處理器RunQueue的nr_running為0 (也就是目前沒有
212.正在執行的Task),就會呼叫idle_balance,並觸發後續Load
213.Balance流程.*/
214.int push_cpu;
215./* cpu of this runqueue: */
216./*用以儲存目前运作這個RunQueue的處理器ID*/
217.int cpu;
218./*為1表示目前此RunQueue有在對應的處理器掛上219.並執行.*/
220.int online;
221./*如果RunQueue中目前有Task正在執行,這個值會222.等於目前該RunQueue的Load Weight除以目前RunQueue
223.中Task數目的均值.
224.(rq->avg_load_per_task = rq->load.weight / nr_ running;).*/
225.unsigned long avg_load_per_task;
226.
227.struct task_struct *migration_thread;
228.struct list_head migration_queue;
229./*這個值會由Real-Time Scheduling Class呼叫函式230.update_curr_rt,用以統計目前Real-Time Task執行時間的
231.均值,在這函式中會以目前RunQueue的clock_task
232.減去目前Task執行的起始時間,取得執行時間的
233.Delta
值. (delta_exec = rq->clock_task –curr->se.exec_start;
).
234.在透過函式sched_rt_avg_update把這Delta值跟原本235.RunQueue中的rt_avg值取平均值. 以運作的週期來看,
236.這個值可反應目前系統中Real-Time Task平均被
237.分配到的執行時間值.*/
238.u64 rt_avg;
239./*這個值主要在函式sched_avg_update更新,以笔者手中
240.的Linux Kernel 2.6.38.6的實作來說,當RunQueue Clock
241.減去age_stamp大於0.5秒(=sched_avg_period),就會把這值
242.累加0.5秒(單位都是nanoseconds). 從函式scale_rt_power
243.的實作來說,age_stamp值離RunQueue Clock越遠,表示total
244.值越大,available值也越大,而函式scale_rt_power返回的
245.div_u64計算結果也越大,最終RunQueue的cpu_power 246.與Scheduling Domain中的Scheduling Group的cpu_power
247.值也就越大. (可參考函式update_cpu_power的實作).*/
248.u64 age_stamp;
249./*這值會在觸發Scheduling時,若判斷目前處理器
250.RunQueue沒有正在運作的Task,就會透過函式
251.idle_balance更新這值為為目前RunQueue的clock值. 252.可用以表示這個處理器是何時進入到Idle的
253.狀態*/
254.u64 idle_stamp;
255./*會在有Task運作且idle_stamp不為0 (表示前一個256.狀態是在Idle)時以目前RunQueue的clock減去
257.idle_stmp所計算出的Delta值為依據,更新這個值258.. 可反應目前處理器進入Idle狀態的時間長短*/
259.u64 avg_idle;
260.#endif
262./* calc_load related fields */
263./*用以記錄下一次計算CPU Load的時間,初始值
264.為目前的jiffies加上五秒與1次的Scheduling Tick 的
265.間隔(=jiffies + LOAD_FREQ,且
LOAD_FREQ=(5*HZ+1))*/
266.unsigned long calc_load_update;
267./*會等於RunQueue中nr_running與nr_uninterruptible 的
268.總和.（可參考函式calc_load_fold_active）.*/
269.long calc_load_active;
270.
271.#ifdef CONFIG_SCHED_HRTICK
272.#ifdef CONFIG_SMP
273./*在函式init_rq_hrtick初始化
RunQueue High-Resolution
274.Tick時,此值預設為0.
275.在函式hrtick_start中,會判斷目前觸發的RunQueue 276.跟目前處理器所使用的RunQueue是否一致,
277.若是,就直接呼叫函式hrtimer_restart,反之就會
278.依據RunQueue中hrtick_csd_pending的值,如果
279.hrtick_csd_pending為0,就會透過函式
280.__smp_call_function_single讓RunQueue所在的另一個
281.處理器執行rq->hrtick_csd.func 所指到的函式
282.__hrtick_start. 並等待該處理器執行完畢後,
283.才重新把hrtick_csd_pending設定為1.
284.也就是說, RunQueue的hrtick_csd_pending是用來作為
285.SMP架構下,由處理器A觸發處理器B執行
286._hrtick_start函式的一個保護機制.而有關在
287.SMP下如何由一個處理器觸發另一個處理器
288.執行函式的機制,可以參考kernel/smp.c中
289.相關smp_call_function_xxxxxxx的實作.s*/
290.int hrtick_csd_pending;
291./*用以儲存hrtick機制中,要跨處理器執行的
292.函式結構.*/
293.struct call_single_data hrtick_csd;
294.#endif
295./*為High-Resolution Tick的结构,會透過函式
296.hrtimer_init初始化.*/
297.struct hrtimer hrtick_timer;
298.#endif
300.#ifdef CONFIG_SCHEDSTATS
301./* latency stats */
302./*為Scheduling Info.的統計結構,可以參考
303.include/linux/sched.h中的宣告. 例如在每次觸發304.Schedule時,呼叫函式schedule_debug對上一個Task 305.的lock_depth進行確認(Fork一個新的Process 時, 306.會把此值預設為-1就是No-Lock,當呼叫
307.Kernel Lock時, 就會把Current Task的lock_depth 加一.),
308.若lock_depth>=0,就會累加Scheduling Info.的bkl_count值,
309.用以代表Task Blocking的次數.*/
310.struct sched_info rq_sched_info;
311./*可用以表示RunQueue中的Task所得到CPU執行
312.時間的累加值.
313.在發生Task Switch時,會透過sched_info_switch呼叫
314.sched_info_arrive並以目前RunQueue Clock值更新315.Task 的sched_https://www.doczj.com/doc/c211399266.html,st_arrival時間,而在Task所分配時間
316.結束後,會在函式sched_info_depart中以現在的
317.RunQueue Clock值減去Task的
sched_https://www.doczj.com/doc/c211399266.html,st_arrival
318.時間值,得到的Delta作為變數rq_cpu_time的累319.加值.*/
320.unsigned long long rq_cpu_time;
321./* could above be rq->cfs_rq.exec_clock + rq ->rt_rq.rt_runtime ? */
322.
323./* sys_sched_yield() stats */
324./*用以統計呼叫System Call sys_sched_yield的次數.*/
325.unsigned int yld_count;
326.
327./* schedule() stats */
328.unsigned int sched_switch;
329./*可用以統計觸發Scheduling的次數. 在每次觸發330.Scheduling時,會透過函式schedule呼叫
schedule_debug,
331.呼叫schedstat_inc對這變數進行累加.*/
332.unsigned int sched_count;
333./*可用以統計進入到Idle Task的次數. 會在函式
334.pick_next_task_idle中,呼叫schedstat_inc對這變數進行
335.累加.*/
336.unsigned int sched_goidle;
337.
338./* try_to_wake_up() stats */
339./*用以統計Wake Up Task的次數.*/
340.unsigned int ttwu_count;
341./*用以統計Wake Up 同一個處理器Task的次數.*/
342.unsigned int ttwu_local;
343.
344./* BKL stats */
345.unsigned int bkl_count;
346.#endif
347.};
调度类，sched_class为对模块编程的上层支持，对于每个linux新添加进来的调度算法都需要有自己的调度类实例。
1./*CFS排程機制在設計時,考慮到排程機制的
2.彈性,定義了Scheduler Class的機制,讓排程機制
3.可以根據設計的需求,延伸不同的排程模
4.組進來,每個新加入的排程機制都必須要
5.提供Scheduler Class的實作,結構為struct sched_class*/
6.struct sched_class {
7./*會指向下一個Scheduling Class,以筆者所採用
8.的Linux Kernel 2.6.38.6而言,Scheduling Class的順序
為
9.stop_sched_class->rt_sched_class->fair_sched_class->idl
e_sched_class*/
10. const struct sched_class *next;
11. /*當Task屬於Runnable狀態時,就會呼叫這個函式
12.把Task配置到RunQueue RBTree中,進行排程動作,
13.並呼叫inc_nr_running將RunQueue中nr_running的值
14.加一.(nr_running用以代表目前RunQueue有多少
15.Runnable Task進行排程)*/
16. void(*enqueue_task) (struct rq *rq, struct task_
struct *p, int wakeup);
17. /*當Task不需要執行時,就會呼叫這個函式
18.把Task從RunQueue RBTree中移除,並呼叫
19.dec_nr_running將RunQueue中nr_running的值減一.*/
20. void(*dequeue_task) (struct rq *rq, struct task_
struct *p, int sleep);
21. /*用以暫停目前正在執行中的Task,如果
22.sysctl_sched_compat_yield有設定,就會找出目前
23.RBTree中最右邊的Task(也就是vrruntime最多
24.的Task),讓目前Task的vrruntime值等於最右邊
25.Task值的vrruntime加一(可參考:
26.se->vruntime = rightmost->vruntime + 1),如此在下
次
27.排程觸發時就會透過函式put_prev_task把目前
28.的Task放到RBTree的最右邊,也就等同於暫停
29.Task,讓該Task下次被執行到的機會最低.*/
30. void(*yield_task) (struct rq *rq);
31. /*用以決定一個Task是否可以中斷目前正在
32.運作的Task,取得執行權.以CFS本身的實作來說
33.(in sched_fair.c).如果想要取代目前Task的Task本身
34.的Scheduling Policy為Batch或是Idle時,會直接返回,
35.不會用來取代目前正在執行中的Task.反之,
36.如果目前正在執行中的Task的Scheduling Policy
37.為Idle,就會直接由所傳入的Task取代目前正
38.在執行的Task.*/
39. void(*check_preempt_curr) (struct rq *rq, struct
task_struct *p, int flags);
40. /*用以在排程觸發時,從RunQueue RBTree中,
41.取出符合目前Scheduling邏輯的下一個要
42.被執行的Task.*/
43. struct task_struct * (*pick_next_task) (struct rq
*rq);
44. /*用以在排程觸發時,把上一個執行完畢的
45.Task放到目前RunQueue RBTree中對應的位置.*/
46. void(*put_prev_task) (struct rq *rq, struct task
_struct *p);
47.
48.#ifdef CONFIG_SMP
49. /*通常用在執行一個新的程序,或是WakeUp
50.一個Task時,會根據目前SMP下每個處理器的
51.負荷,決定Task是否要切換到另一個處理器
52.的RunQueue去執行,執行時會返回最後目標
53.處理器的值.*/
54. int(*select_task_rq)(struct task_struct *p, int
sd_flag, int flags);
55.
56. unsigned long(*load_balance) (struct rq *this_rq,
int this_cpu,
57. struct rq *busiest, unsigned long
max_load_move,
58. struct sched_domain *sd, enum cpu_i
dle_type idle,
59. int*all_pinned, int*this_best_prio
);
60.
61. int(*move_one_task) (struct rq *this_rq, int thi
s_cpu,
62. struct rq *busiest, stru
ct sched_domain *sd,
63. enum cpu_idle_type idle);
64. void(*pre_schedule) (struct rq *this_rq, struct
task_struct *task);
65. void(*post_schedule) (struct rq *this_rq);
66. void(*task_wake_up) (struct rq *this_rq, struct
task_struct *task);
67.
68. void(*set_cpus_allowed)(struct task_struct *p,
69. const struct cpumask *newm
ask);
70.
71. void(*rq_online)(struct rq *rq);
72. void(*rq_offline)(struct rq *rq);
73.#endif
74. /*這個函式用以改變Task目前所屬的Scheduling
75.Class與改變Task Group.*/
76. void(*set_curr_task) (struct rq *rq);
77. /*這是Scheduler的Timer Tick來源,系統中觸發的
78.Scheduling Tick會呼叫這個函式(看HZ設定多少,
79.100就是每秒呼叫這函式100次,1000就是每秒
80.呼叫這函式1000次),
81.用以讓排程機制可以決定哪些Task應該要配
82.執行與哪些Task應該要被移出RunQueue.*/
83. void(*task_tick) (struct rq *rq, struct task_str
uct *p, int queued);
84. void(*task_new) (struct rq *rq, struct task_stru
ct *p);
85.
86. void(*switched_from) (struct rq *this_rq, struct
task_struct *task,
87. int running);
88. void(*switched_to) (struct rq *this_rq, struct t
ask_struct *task,
89. int running);
90. void(*prio_changed) (struct rq *this_rq, struct
task_struct *task,
91. int oldprio, int running);
92.
93. unsigned int(*get_rr_interval) (struct task_struct
*task);
94.
95.#ifdef CONFIG_FAIR_GROUP_SCHED
96. void(*moved_group) (struct task_struct *p);
97.#endif
98.};
调度实体，调度实体用于调度时间记账，linux中CFS和实时调度使用不同的调度实体。调度运行队列，对于不用的调度算法同样运用不用的运行队列，对于CFS调度，运用的是红黑树，而对于实时调度为组链表。在后面具体的调度算法介绍中我们会看到他们的运用。
上层调度，linux调度的核心函数为schedule，schedule函数封装了内核调度的框架。细节实现上调用具体的调度类中的函数实现。schedule函数主要流程为：
1，将当前进程从相应的运行队列中删除；
2，计算和更新调度实体和进程的相关调度信息；
3，将当前进重新插入到调度运行队列中，对于CFS调度，根据具体的运行时间进行插入而对于实时调度插入到对应优先级队列的队尾；
4，从运行队列中选择运行的下一个进程；
5，进程调度信息和上下文切换；
当进程上下文切换后（关于进程切换在前面的文章中有介绍），调度就基本上完成了，当前运行的进程就是切换过来的进程了。
1./*内核和其他部分用于调用进程调度器的入口，选择
2.哪个进程可以运行，何时将其投入运行。schedule通常
3.都需要和一个具体的调度类相关联，也就是说，他
4.会找到一个最高优先级的调度类，后者需要有自己的
5.可运行队列，然后问后者谁才是下一个该运行的进程
6.该函数唯一重要的事情是，他回调用pick_next_task*/
7.asmlinkage void__sched schedule(void)
8.{
9.struct task_struct *prev, *next;
10. unsigned long*switch_count;
11. struct rq *rq;
12. int cpu;
13.
14.need_resched:
15. preempt_disable();
16. cpu = smp_processor_id();
17. rq = cpu_rq(cpu);/*得到特定cpu的rq*/
18. rcu_sched_qs(cpu);
19. prev = rq->curr;/*当前的运行进程*/
20. switch_count = &prev->nivcsw;/*进程切换计数*/
21.
22. release_kernel_lock(prev);
23.need_resched_nonpreemptible:
24.
25. schedule_debug(prev);
26.
27. if(sched_feat(HRTICK))
28. hrtick_clear(rq);
29.
30. spin_lock_irq(&rq->lock);
31. update_rq_clock(rq);/*更新rq的clock属性*/
32. clear_tsk_need_resched(prev);/*清楚prev进程的调度位
*/
33.
34. if(prev->state && !(preempt_count() & PREEMPT_ACT
IVE)) {
35. if(unlikely(signal_pending_state(prev->state,
prev)))
36. prev->state = TASK_RUNNING;
37. else/*从运行队列中删除prev进程,根据调度类的
38.不同，实现不同*/
39. deactivate_task(rq, prev, 1);
40. switch_count = &prev->nvcsw;
41. }
42. /*现只对实时进程有用*/
43. pre_schedule(rq, prev);
44.
45. if(unlikely(!rq->nr_running))
46. idle_balance(cpu, rq);
47. /*将当前进程，也就是被切换出去的进程重新
48.插入到各自的运行队列中，对于CFS算法插入
49.到合适的位置上，对于实时调度插入到同一个
50.优先级队列的链表尾部*/
51. put_prev_task(rq, prev);
52. /*从各自的运行队列中选择下一个进程来运行*/
53. next = pick_next_task(rq);
54.
55. if(likely(prev != next)) {
56. /*更新切换出去和进来进程以及对应rq的相关变量
*/
57. sched_info_switch(prev, next);
58. perf_event_task_sched_out(prev, next, cpu);
59.
60. rq->nr_switches++;/*切换记录*/
61. rq->curr = next;
62. ++*switch_count;
63. /*上下文切换，在进程切换已经介绍*/
64. context_switch(rq, prev, next); /* unlocks
the rq */
65. /*
66.* the context switch might have flipped
the stack from under
67.* us, hence refresh the local variables
.
68.*/
69. cpu = smp_processor_id();
70. rq = cpu_rq(cpu);
71. } else
72. spin_unlock_irq(&rq->lock);
73. /*对于实时进程有用到*/
74. post_schedule(rq);
75.
76. if(unlikely(reacquire_kernel_lock(current) < 0))
77. goto need_resched_nonpreemptible;
78.
79. preempt_enable_no_resched();
80. if(need_resched())
81. goto need_resched;
82.}
对于cpu_rq函数
1./*通过向上加偏移的方式得到rq，这里可以看出
2.runqueues为一个rq结构的数组，cpu为数组下标*/
3.#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
deactivate_task函数实现
1./*
2.* deactivate_task - remove a task from the runqueue.
3.*/
4.static void deactivate_task(struct rq *rq, struct task_st
ruct *p, int sleep)
5.{
6.if(task_contributes_to_load(p))
7.rq->nr_uninterruptible++;
8./*具体操作*/
9.dequeue_task(rq, p, sleep);
10. dec_nr_running(rq);/*rq中当前进程的运行数减一*/
11.}
我们看具体的操作
1.static void dequeue_task(struct rq *rq, struct task_struc
t *p, int sleep)
2.{
3.if(sleep) {/*如果sleep不为0，更新se中相关变量*/
4.if(p->https://www.doczj.com/doc/c211399266.html,st_wakeup) {
5.update_avg(&p->se.avg_overlap,
6.p->se.sum_exec_runtime - p->s
https://www.doczj.com/doc/c211399266.html,st_wakeup);
7.p->https://www.doczj.com/doc/c211399266.html,st_wakeup = 0;
8.} else{
9.update_avg(&p->se.avg_wakeup,
10. sysctl_sched_wakeup_granularity
);
11. }
12. }
13. /*更新进程的sched_info数据结构中相关属性*/
14. sched_info_dequeued(p);
15. /*调用具体调度类的函数从他的运行队列中删除*/
16. p->sched_class->dequeue_task(rq, p, sleep);
17. p->se.on_rq = 0;
18.}
可见，调用了具体运行队列的删除函数，我们看最关键的选择下一个进程的方式。
1./*
2.* Pick up the highest-prio task:
3.*/
4./*以优先级为序，从高到低，一次检查每个调度类
5.并且从高优先级的调度类中，选择最高优先级的进程
6.*/
7.static inline struct task_struct *
8.pick_next_task(struct rq *rq)
9.{
10. const struct sched_class *class;
11. struct task_struct *p;
12.
13. /*
14.* Optimization: we know that if all tasks are
in
15.* the fair class we can call that function d
irectly:
16.*/
17. if(likely(rq->nr_running == rq->cfs.nr_running)) {
18. p = fair_sched_class.pick_next_task(rq);
19. if(likely(p))
20. return p;
21. }
22.
23. class= sched_class_highest;
24. for( ; ; ) {/*对每一个调度类*/
25. p = class->pick_next_task(rq);/*调用该调度类
中的函数，找出下一个task*/
26. if(p)
27. return p;
28. /*
29.* Will never be NULL as the idle clas
s always
30.* returns a non-NULL p:
31.*/
32. /*访问下一个调度类*/
33. class= class->next;
34. }
35.}
可见，对于调度类的选择，同样以优先级进行。
对于进程调度信息的切换最终会调用__sched_info_switch
1./*
2.* Called when tasks are switched involuntarily due, t
ypically, to expiring
3.* their time slice. (This may also be called when
switching to or from
4.* the idle task.) We are only called when prev !=
next.
5.*/
6.static inline void
7.__sched_info_switch(struct task_struct *prev, struct task_s
truct *next)
8.{
9.struct rq *rq = task_rq(prev);
10.
11. /*
12.* prev now departs the cpu. It's not intere
sting to record
13.* stats about how efficient we were at schedu
ling the idle
14.* process, however.
15.*/
16. if(prev != rq->idle)/*如果被切换出去的进程不是idle
进程*/
17. sched_info_depart(prev);/*更新prev进程和他对应
rq的相关变量*/
18.
19. if(next != rq->idle)/*如果切换进来的进程不是idle进
程*/
20. sched_info_arrive(next);/*更新next进程和对应队
列的相关变量*/
21.}
1./*
2.* Called when a process ceases being the active-runni
ng process, either
3.* voluntarily or involuntarily. Now we can calculate
how long we ran.
4.* Also, if the process is still in the TASK_RUNNING
state, call
5.* sched_info_queued() to mark that it has now again
started waiting on
6.* the runqueue.
Linux内核崩溃原因分析及错误跟踪技术 随着嵌入式Linux系统的广泛应用，对系统的可靠性提出了更高的要求，尤其是涉及到生命财产等重要领域，要求系统达到安全完整性等级3级以上[1]，故障率（每小时出现危险故障的可能性）为10-7以下，相当于系统的平均故障间隔时间（MTBF）至少要达到1141年以上，因此提高系统可靠性已成为一项艰巨的任务。对某公司在工业领域14 878个控制器系统的应用调查表明，从2004年初到2007年9月底，随着硬软件的不断改进，根据错误报告统计的故障率已降低到2004年的五分之一以下，但查找错误的时间却增加到原来的3倍以上。 这种解决问题所需时间呈上升的趋势固然有软件问题，但缺乏必要的手段以辅助解决问题才是主要的原因。通过对故障的统计跟踪发现，难以解决的软件错误和从发现到解决耗时较长的软件错误都集中在操作系统的核心部分，这其中又有很大比例集中在驱动程序部分[2]。因此，错误跟踪技术被看成是提高系统安全完整性等级的一个重要措施[1]，大多数现代操作系统均为发展提供了操作系统内核“崩溃转储”机制，即在软件系统宕机时，将内存内容保存到磁盘[3]，或者通过网络发送到故障服务器[3]，或者直接启动内核调试器[4]等，以供事后分析改进。 基于Linux操作系统内核的崩溃转储机制近年来有以下几种： (1) LKCD（Linux Kernel Crash Dump）机制[3]; (2) KDUMP（Linux Kernel Dump）机制[4]； (3) KDB机制[5]； (4) KGDB机制[6]。 综合上述几种机制可以发现,这四种机制之间有以下三个共同点： (1) 适用于为运算资源丰富、存储空间充足的应用场合； (2) 发生系统崩溃后恢复时间无严格要求； (3) 主要针对较通用的硬件平台，如X86平台。 在嵌入式应用场合想要直接使用上列机制中的某一种，却遇到以下三个难点无法解决： (1) 存储空间不足 嵌入式系统一般采用Flash作为存储器，而Flash容量有限，且可能远远小于嵌入式系统中的内存容量。因此将全部内存内容保存到Flash不可行。
操作系统实验报告（二） 实验题目：进程调度算法 实验环境：C++ 实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较 各种算法的性能优劣。 实验内容：编程实现如下算法： 1.先来先服务算法； 2.短进程优先算法； 3.时间片轮转调度算法。 设计分析： 程序流程图： 1.先来先服务算法 开始 初始化PCB，输入进程信息 各进程按先来先到的顺序进入就绪队列 结束 就绪队列？ 运行 运行进程所需CPU时间 取消该进程 2.短进程优先算法
3.时间片轮转调度算法 实验代码： 1.先来先服务算法 #include
int atime; //进程到达时间 int runtime; //进程运行时间 }fcs; void main() { int amount,i,j,diao,huan; fcs f[n]; cout<<"请输入进程个数:"<
linux源代码分析:Linux操作系统源代码详细分析 疯狂代码 https://www.doczj.com/doc/c211399266.html,/ ?:http:/https://www.doczj.com/doc/c211399266.html,/Linux/Article28378.html 内容介绍: Linux 拥有现代操作系统所有功能如真正抢先式多任务处理、支持多用户内存保护虚拟内存支持SMP、UP符合POSIX标准联网、图形用户接口和桌面环境具有快速性、稳定性等特点本书通过分析Linux内核源代码充分揭示了Linux作为操作系统内核是如何完成保证系统正常运行、协调多个并发进程、管理内存等工作现实中能让人自由获取系统源代码并不多通过本书学习将大大有助于读者编写自己新 第部分 Linux 内核源代码 arch/i386/kernel/entry.S 2 arch/i386/kernel/init_task.c 8 arch/i386/kernel/irq.c 8 arch/i386/kernel/irq.h 19 arch/i386/kernel/process.c 22 arch/i386/kernel/signal.c 30 arch/i386/kernel/smp.c 38 arch/i386/kernel/time.c 58 arch/i386/kernel/traps.c 65 arch/i386/lib/delay.c 73 arch/i386/mm/fault.c 74 arch/i386/mm/init.c 76 fs/binfmt-elf.c 82 fs/binfmt_java.c 96 fs/exec.c 98 /asm-generic/smplock.h 107 /asm-i386/atomic.h 108 /asm- i386/current.h 109 /asm-i386/dma.h 109 /asm-i386/elf.h 113 /asm-i386/hardirq.h 114 /asm- i386/page.h 114 /asm-i386/pgtable.h 115 /asm-i386/ptrace.h 122 /asm-i386/semaphore.h 123 /asm-i386/shmparam.h 124 /asm-i386/sigcontext.h 125 /asm-i386/siginfo.h 125 /asm-i386/signal.h 127 /asm-i386/smp.h 130 /asm-i386/softirq.h 132 /asm-i386/spinlock.h 133 /asm-i386/system.h 137 /asm-i386/uaccess.h 139 //binfmts.h 146 //capability.h 147 /linux/elf.h 150 /linux/elfcore.h 156 /linux/errupt.h 157 /linux/kernel.h 158 /linux/kernel_stat.h 159 /linux/limits.h 160 /linux/mm.h 160 /linux/module.h 164 /linux/msg.h 168 /linux/personality.h 169 /linux/reboot.h 169 /linux/resource.h 170 /linux/sched.h 171 /linux/sem.h 179 /linux/shm.h 180 /linux/signal.h 181 /linux/slab.h 184 /linux/smp.h 184 /linux/smp_lock.h 185 /linux/swap.h 185 /linux/swapctl.h 187 /linux/sysctl.h 188 /linux/tasks.h 194 /linux/time.h 194 /linux/timer.h 195 /linux/times.h 196 /linux/tqueue.h 196 /linux/wait.h 198 init/.c 198 init/version.c 212 ipc/msg.c 213 ipc/sem.c 218 ipc/shm.c 227 ipc/util.c 236 kernel/capability.c 237 kernel/dma.c 240 kernel/exec_do.c 241 kernel/exit.c 242 kernel/fork.c 248 kernel/info.c 255 kernel/itimer.c 255 kernel/kmod.c 257 kernel/module.c 259 kernel/panic.c 270 kernel/prk.c 271 kernel/sched.c 275 kernel/signal.c 295 kernel/softirq.c 307 kernel/sys.c 307 kernel/sysctl.c 318 kernel/time.c 330 mm/memory.c 335 mm/mlock.c 345 mm/mmap.c 348 mm/mprotect.c 358 mm/mremap.c 361 mm/page_alloc.c 363 mm/page_io.c 368 mm/slab.c 372 mm/swap.c 394 mm/swap_state.c 395 mm/swapfile.c 398 mm/vmalloc.c 406 mm/vmscan.c 409
先来先服务FCFS和短作业优先SJF进程调度算法 1、实验目的 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 2、需求分析 (1) 输入的形式和输入值的范围 输入值：进程个数Num 范围：0 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 4、详细设计 5、调试分析 (1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析 ○1开始的时候没有判断进程是否到达，导致短进程优先算法运行结果错误，后来加上了判断语句后就解决了改问题。 ○2 基本完成的设计所要实现的功能，总的来说，FCFS编写容易，SJF 需要先找到已经到达的进程，再从已经到达的进程里找到进程服务时间最短的进程，再进行计算。 (2)算法的改进设想 改进：即使用户输入的进程到达时间没有先后顺序也能准确的计算出结果。（就是再加个循环，判断各个进程的到达时间先后，组成一个有序的序列） (3)经验和体会 通过本次实验，深入理解了先来先服务和短进程优先进程调度算法的思想，培养了自己的动手能力，通过实践加深了记忆。 6、用户使用说明 （1）输入进程个数Num 本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。 E-mail: wwwlkk@https://www.doczj.com/doc/c211399266.html, 来源: https://www.doczj.com/doc/c211399266.html,/?business&aid=6&un=wwwlkk#7 linux2.6.35内核IMQ源码实现分析 （1）数据包截留并重新注入协议栈技术 (1) （2）及时处理数据包技术 (2) （3）IMQ设备数据包重新注入协议栈流程 (4) （4）IMQ截留数据包流程 (4) （5）IMQ在软中断中及时将数据包重新注入协议栈 (7) （6）结束语 (9) 前言：IMQ用于入口流量整形和全局的流量控制，IMQ的配置是很简单的，但很少人分析过IMQ的内核实现，网络上也没有IMQ的源码分析文档，为了搞清楚IMQ的性能，稳定性，以及借鉴IMQ的技术，本文分析了IMQ的内核实现机制。 首先揭示IMQ的核心技术： 1.如何从协议栈中截留数据包，并能把数据包重新注入协议栈。 2.如何做到及时的将数据包重新注入协议栈。 实际上linux的标准内核已经解决了以上2个技术难点，第1个技术可以在NF_QUEUE机制中看到，第二个技术可以在发包软中断中看到。下面先介绍这2个技术。 （1）数据包截留并重新注入协议栈技术 （2）及时处理数据包技术 QoS有个技术难点：将数据包入队，然后发送队列中合适的数据包，那么如何做到队列中的数 激活状态的队列是否能保证队列中的数据包被及时的发送吗？接下来看一下，激活状态的队列的 证了数据包会被及时的发送。 这是linux内核发送软中断的机制，IMQ就是利用了这个机制，不同点在于：正常的发送队列是将数据包发送给网卡驱动，而IMQ队列是将数据包发送给okfn函数。 探究linux内核,超详细解析子系统 Perface 前面已经写过一篇《嵌入式linux内核的五个子系统》，概括性比较强，也比较简略，现在对其进行补充说明。 仅留此笔记，待日后查看及补充！Linux内核的子系统 内核是操作系统的核心。Linux内核提供很多基本功能，如虚拟内存、多任务、共享库、需求加载、共享写时拷贝（Copy-On-Write）以及网络功能等。增加各种不同功能导致内核代码不断增加。 Linux内核把不同功能分成不同的子系统的方法，通过一种整体的结构把各种功能集合在一起，提高了工作效率。同时还提供动态加载模块的方式，为动态修改内核功能提供了灵活性。系统调用接口用户程序通过软件中断后，调用系统内核提供的功能，这个在用户空间和内核提供的服务之间的接口称为系统调用。系统调用是Linux内核提供的，用户空间无法直接使用系统调用。在用户进程使用系统调用必须跨越应用程序和内核的界限。Linux内核向用户提供了统一的系统调用接口，但是在不同处理器上系统调用的方法 各不相同。Linux内核提供了大量的系统调用，现在从系统 调用的基本原理出发探究Linux系统调用的方法。这是在一个用户进程中通过GNU C库进行的系统调用示意图，系 统调用通过同一个入口点传入内核。以i386体系结构为例，约定使用EAX寄存器标记系统调用。 当加载了系统C库调用的索引和参数时，就会调用0x80软件中断，它将执行system_call函数，这个函数按照EAX 寄存器内容的标示处理所有的系统调用。经过几个单元测试，会使用EAX寄存器的内容的索引查system_call_table表得到系统调用的入口，然后执行系统调用。从系统调用返回后，最终执行system_exit，并调用resume_userspace函数返回用户空间。 linux内核系统调用的核心是系统多路分解表。最终通过EAX寄存器的系统调用标识和索引值从对应的系统调用表 中查出对应系统调用的入口地址，然后执行系统调用。 linux系统调用并不单层的调用关系，有的系统调用会由 作业调度实验报告 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解三 .实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: 执行程序: 2)实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W 。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 二.最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include <> #include <> #include <> #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 int n; float T1=0,T2=0; int times=0; struct jcb .\n",p->name); free(p); .wait...",time); if(times>1000) 代替 代替 Linux内核分析方法 Linux的最大的好处之一就是它的源码公开。同时，公开的核心源码也吸引着无数的电脑爱好者和程序员；他们把解读和分析Linux的核心源码作为自己的最大兴趣，把修改Linux源码和改造Linux系统作为自己对计算机技术追求的最大目标。 Linux内核源码是很具吸引力的，特别是当你弄懂了一个分析了好久都没搞懂的问题；或者是被你修改过了的内核，顺利通过编译，一切运行正常的时候。那种成就感真是油然而生！而且，对内核的分析，除了出自对技术的狂热追求之外，这种令人生畏的劳动所带来的回报也是非常令人着迷的，这也正是它拥有众多追随者的主要原因： ?首先，你可以从中学到很多的计算机的底层知识，如后面将讲到的系统的引导和硬件提供的中断机制等；其它，象虚拟存储的实现机制，多任务机制，系统保护机制等等，这些都是非都源码不能体会的。 ?同时，你还将从操作系统的整体结构中，体会整体设计在软件设计中的份量和作用，以及一些宏观设计的方法和技巧：Linux的内核为上层应用提供一个与具体硬件不相关的平台； 同时在内核内部，它又把代码分为与体系结构和硬件相关的部分，和可移植的部分；再例如，Linux虽然不是微内核的，但他把大部分的设备驱动处理成相对独立的内核模块，这样减小了内核运行的开销，增强了内核代码的模块独立性。 ?而且你还能从对内核源码的分析中，体会到它在解决某个具体细节问题时，方法的巧妙：如后面将分析到了的Linux通过Botoom_half机制来加快系统对中断的处理。 ?最重要的是：在源码的分析过程中，你将会被一点一点地、潜移默化地专业化。一个专业的程序员，总是把代码的清晰性，兼容性，可移植性放在很重要的位置。他们总是通过定义大量的宏，来增强代码的清晰度和可读性，而又不增加编译后的代码长度和代码的运行效率； 他们总是在编码的同时，就考虑到了以后的代码维护和升级。甚至，只要分析百分之一的代码后，你就会深刻地体会到，什么样的代码才是一个专业的程序员写的，什么样的代码是一个业余爱好者写的。而这一点是任何没有真正分析过标准代码的人都无法体会到的。 然而，由于内核代码的冗长，和内核体系结构的庞杂，所以分析内核也是一个很艰难，很需要毅力的事；在缺乏指导和交流的情况下，尤其如此。只有方法正确，才能事半功倍。正是基于这种考虑，作者希望通过此文能给大家一些借鉴和启迪。 由于本人所进行的分析都是基于2.2.5版本的内核；所以，如果没有特别说明，以下分析都是基于i386单处理器的2.2.5版本的Linux内核。所有源文件均是相对于目录/usr/src/linux的。 方法之一：从何入手 要分析Linux内核源码，首先必须找到各个模块的位置，也即要弄懂源码的文件组织形式。虽然对于有经验的高手而言，这个不是很难；但对于很多初级的Linux爱好者，和那些对源码分析很 作业调度 一、实验目的 1、对作业调度的相关内容作进一步的理解。 2、明白作业调度的主要任务。 3、通过编程掌握作业调度的主要算法。 二、实验内容及要求 1、对于给定的一组作业, 给出其到达时间和运行时间，例如下表所示： 2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。 3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。 测试数据 workA={'作业名':'A','到达时间':0,'服务时间':6} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} 运行结果 先来先服务算法 调度顺序:['A', 'B', 'C', 'D', 'E', 'F'] 周转时间: 带权周转时间: 短作业优先算法 调度顺序:['A', 'D', 'F', 'C', 'E', 'B'] 周转时间: 带权周转时间:1. 响应比高者优先算法 调度顺序:['A', 'D', 'F', 'E', 'C', 'B'] 周转时间: 带权周转时间: 五、代码 #encoding=gbk workA={'作业名':'A','到达时间':0,'服务时间':6,'结束时间':0,'周转时间':0,'带权周转时间':0} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} list1=[workB,workA,workC,workD,workE,workF] list2=[workB,workA,workC,workD,workE,workF] list3=[workB,workA,workC,workD,workE,workF] #先来先服务算法 def fcfs(list): resultlist = sorted(list, key=lambda s: s['到达时间']) return resultlist #短作业优先算法 def sjf(list): time=0 resultlist=[] for work1 in list: time+=work1['服务时间'] listdd=[] ctime=0 for i in range(time): for work2 in list: if work2['到达时间']<=ctime: (work2) if len(listdd)!=0: li = sorted(listdd, key=lambda s: s['服务时间']) (li[0]) (li[0]) ctime+=li[0]['服务时间'] listdd=[] Linux的内核源代码可以从很多途径得到。一般来讲，在安装的linux系统下，/usr/src/linux 目录下的东西就是内核源代码。另外还可以从互连网上下载,解压缩后文件一般也都位于linux目录下。内核源代码有很多版本，目前最新的版本是2.2.14。 许多人对于阅读Linux内核有一种恐惧感，其实大可不必。当然，象Linux内核这样大而复杂的系统代码，阅读起来确实有很多困难，但是也不象想象的那么高不可攀。只要有恒心，困难都是可以克服的。任何事情做起来都需要有方法和工具。正确的方法可以指导工作，良好的工具可以事半功倍。对于Linux内核源代码的阅读也同样如此。下面我就把自己阅读内核源代码的一点经验介绍一下，最后介绍Window平台下的一种阅读工具。 对于源代码的阅读，要想比较顺利，事先最好对源代码的知识背景有一定的了解。对于linux内核源代码来讲，基本要求是：⑴操作系统的基本知识；⑵对C语言比较熟悉，最好要有汇编语言的知识和GNU C对标准C的扩展的知识的了解。另外在阅读之前，还应该知道Linux内核源代码的整体分布情况。我们知道现代的操作系统一般由进程管理、内存管理、文件系统、驱动程序、网络等组成。看一下Linux内核源代码就可看出，各个目录大致对应了这些方面。Linux内核源代码的组成如下（假设相对于linux目录）： arch这个子目录包含了此核心源代码所支持的硬件体系结构相关的核心代码。如对于X86平台就是i386。 include这个目录包括了核心的大多数include文件。另外对于每种支持的体系结构分别有一个子目录。 init此目录包含核心启动代码。 mm此目录包含了所有的内存管理代码。与具体硬件体系结构相关的内存管理代码位于arch/*/mm目录下，如对应于X86的就是arch/i386/mm/fault.c。 drivers系统中所有的设备驱动都位于此目录中。它又进一步划分成几类设备驱动，每一种也有对应的子目录，如声卡的驱动对应于drivers/sound。 ipc此目录包含了核心的进程间通讯代码。 modules此目录包含已建好可动态加载的模块。 fs Linux支持的文件系统代码。不同的文件系统有不同的子目录对应，如ext2文件系统对应的就是ext2子目录。 kernel主要核心代码。同时与处理器结构相关代码都放在arch/*/kernel目录下。 net核心的网络部分代码。里面的每个子目录对应于网络的一个方面。 lib此目录包含了核心的库代码。与处理器结构相关库代码被放在arch/*/lib/目录下。 《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include linux源代码分析实验报告格式 Linux的fork、exec、wait代码的分析 指导老师：景建笃 组员：王步月 张少恒 完成日期:2005-12-16 一、 设计目的 1.通过对Linux 的fork 、exec 、wait 代码的分析,了解一个操作系统进程的创建、 执行、等待、退出的过程,锻炼学生分析大型软件代码的能力； 2.通过与同组同学的合作,锻炼学生的合作能力。 二、准备知识 由于我们选的是题目二，所以为了明确分工，我们必须明白进程的定义。经过 查阅资料，我们得知进程必须具备以下四个要素： 1、有一段程序供其执行。这段程序不一定是进程专有，可以与其他进程共用。 2、有起码的“私有财产”，这就是进程专用的系统堆栈空间 3、有“户口”，这就是在内核中有一个task_struct 结构，操作系统称为“进程控制 块”。有了这个结构，进程才能成为内核调度的一个基本单位。同时，这个结构又 是进程的“财产登记卡”，记录着进程所占用的各项资源。 4、有独立的存储空间，意味着拥有专有的用户空间：进一步，还意味着除前述的 系统空间堆栈外，还有其专用的用户空间堆栈。系统为每个进程分配了一个 task_struct 结构，实际分配了两个连续的物理页面（共8192字节），其图如下： Struct task_struct (大约1K) 系统空间堆栈 （大约7KB ）两个 连续 的物 理页 面 对这些基本的知识有了初步了解之后，我们按老师的建议，商量分工。如下： 四、 小组成员以及任务分配 1、王步月：分析进程的创建函数fork.c ，其中包含了get_pid 和do_fork get_pid, 写出代码分析结果，并画出流程图来表示相关函数之间的相互调用关系。所占工作 比例35%。 2、张少恒：分析进程的执行函数exec.c,其中包含了do_execve 。写出代码分析结 果，并画出流程图来表示相关函数之间的相互调用关系。所占工作比例35% 。 3、余波：分析进程的退出函数exit.c,其中包含了do_exit 、sys_wait4。写出代码 分析结果，并画出流程图来表示相关函数之间的相互调用关系。所占工作比例30% 。 五、各模块分析： 1、fork.c 一）、概述 进程大多数是由FORK 系统调用创建的.fork 能满足非常高效的生灭机制.除了 0进程等少数一,两个进程外,几乎所有的进程都是被另一个进程执行fork 系统调 用创建的.调用fork 的进程是父进程,由fork 创建的程是子进程.每个进程都有一 看完了路由表，重新回到netif_receive_skb ()函数，在提交给上层协议处理前，会执行下面一句，这就是网桥的相关操作，也是这篇要讲解的容。 view plaincopy to clipboardprint? 1. s kb = handle_bridge(skb, &pt_prev, &ret, orig_dev); 网桥可以简单理解为交换机，以下图为例，一台linux机器可以看作网桥和路由的结合，网桥将物理上的两个局域网LAN1、LAN2当作一个局域网处理，路由连接了两个子网1.0和2.0。从eth0和eth1网卡收到的报文在Bridge模块中会被处理成是由Bridge收到的，因此Bridge也相当于一个虚拟网卡。 STP五种状态 DISABLED BLOCKING LISTENING LEARNING FORWARDING 创建新的网桥br_add_bridge [net\bridge\br_if.c] 当使用SIOCBRADDBR调用ioctl时，会创建新的网桥br_add_bridge。 首先是创建新的网桥： view plaincopy to clipboardprint? 1. d ev = new_bridge_dev(net, name); 然后设置dev->dev.type为br_type，而br_type是个全局变量，只初始化了一个名字变量 view plaincopy to clipboardprint? 1. S ET_NETDEV_DEVTYPE(dev, &br_type); 2. s tatic struct device_type br_type = { 3. .name = "bridge", 4. }; 然后注册新创建的设备dev，网桥就相当一个虚拟网卡设备，注册过的设备用ifconfig 就可查看到： view plaincopy to clipboardprint? 1. r et = register_netdevice(dev); 最后在sysfs文件系统中也创建相应项，便于查看和管理： view plaincopy to clipboardprint? 1. r et = br_sysfs_addbr(dev); 将端口加入网桥br_add_if() [net\bridge\br_if.c] 当使用SIOCBRADDIF调用ioctl时，会向网卡加入新的端口br_add_if。 创建新的net_bridge_port p，会从br->port_list中分配一个未用的port_no，p->br会指向br，p->state设为BR_STATE_DISABLED。这里的p实际代表的就是网卡设备。 view plaincopy to clipboardprint? 1. p = new_nbp(br, dev); 将新创建的p加入CAM表中，CAM表是用来记录mac地址与物理端口的对应关系；而刚刚创建了p，因此也要加入CAM表中，并且该表项应是local的[关系如下图]，可以看到，CAM表在实现中作为net_bridge的hash表，以addr作为hash值，链入 net_bridge_fdb_entry，再由它的dst指向net_bridge_port。 FCFS和SJF进程调度算法实验报告 【实验题目】：编写程序，实现FCFS和SJF算法，模拟作 业调度过程，加深对作业调度的理解。 【实验内容】 实现FCFS和SJF调度算法。 –数据结构设计（JCB，后备作业队列） –算法实现与模拟（排序、调度） –输出调度结果，展示调度过程并解释 【实验要求】 1. 设计作业控制块(JCB)的数据结构 –应包含实验必须的数据项，如作业ID、需要的服务时间、进入系 统时间、完成时间，以及实验者认为有必要的其他数据项。 2. 实现排序算法（将作业排队） –策略1：按“进入系统时间”对作业队列排序(FCFS) –策略2：按“需要的服务时间”对作业队列排序（SJF） 3. 实现调度过程模拟 （1）每个作业用一个JCB表示，如果模拟FCFS，按策略1将作业排队，如果模拟SJF，按策略2将作业排队（2）选择队首的作业，将其从后备队列移出 （3）（作业运行过程，在本实验中，无需实现，可认为后备队列的 作业一但被调度程序选出，就顺利运行完毕，可以进入第4步） （4）计算选中作业的周转时间 （5）进行下一次调度（去往第2步） 4.实现结果输出 –输出作业状态表，展示调度过程 ?初始作业状态（未调度时） ?每次调度后的作业状态 设计作业控制块(JCB)的数据结构 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下：typedef struct jcb{ char name[10]; /* 作业名*/ char state; /* 作业状态*/ int ts; /* 提交时间*/ float super; /* 优先权*/ int tb; /* 开始运行时间*/ int tc; /* 完成时间*/ float ti; /* 周转时间*/ float wi; /* 带权周转时间*/ int ntime; /* 作业所需运行时间*/ char resource[10]; /* 所需资源*/ struct jcb *next; /* 结构体指针*/ } JCB; JCB *p,*tail=NULL,*head=NULL; 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。 文章编号:1004-485X (2003)03-0030-04 收稿日期:2003-05-10 作者简介:王艳春,女(1964 ),副教授,主要从事操作系统、中文信息处理等方面的研究工作。 Linux 源代码分析 存储管理 王艳春 陈 毓 葛明霞 (长春理工大学计算机科学技术学院,吉林长春130022) 摘 要:本文剖析了Linux 操作系统的存储管理机制。给出了Linux 存储管理的特点、虚存的实现方法,以及主要数据结构之间的关系。 关键词:Linux 操作系统;存储管理;虚拟存储中图分类号:T P316 81 文献标识码:A Linux 操作系统是一种能运行于多种平台、源代码公开、免费、功能强大、与Unix 兼容的操作系统。自其诞生以来,发展非常迅速,在我国也受到政府、企业、科研单位、大专院校的重视。我们自2000年开始对Linux 源代码(版本号是Linux 2 2 16)进行分析,首先剖析了进程管理和存储管理部分,本文是有关存储管理的一部分。主要介绍了Linux 虚存管理所用到的数据结构及其相互间的关系,据此可以更好地理解其存储管理机制,也可以在此基础上对其进行改进或在此后的研究中提供借鉴作用。作为一种功能强大的操作系统,Linux 实现了以虚拟内存为主的内存管理机制。即能够克服物理内存的局限,使用户进程在透明方式下,拥有比实际物理内存大得多的内存。本文主要阐述了Linux 虚存管理的基本特点和主要实现技术,并分析了Linux 虚存管理的主要数据结构及其相互关系。 1 Lin ux 虚存管理概述 Linux 的内存管理采用虚拟页式管理,使用多级页表,动态地址变换。进程在运行过程中可以动态浮动和扩展,为用户提供了透明的、灵活有效的内存使用方式。 1)32 bit 虚拟地址 在Linux 中,进程的4GB 虚存需通过32 bit 地址进行寻址。Linux 中虚拟地址与线性地址为同一概念,虚拟地址被分成3个子位段,而大小为4k,如图1所示。 2)Linux 的多级页表结构 图1 32位虚拟地址 标准的Linux 的虚存页表为三级页表,依次为页目录(Pag e Directory PGD)、中间页目录(Pag e Middle Directory PMD )、页表(Page Table PT E )。在i386机器上Linux 的页表结构实际为两级,PGD 和PMD 页表是合二为一的。所有有关PMD 的操作关际上是对PGD 的操作。所以源代码中形如*_pgd _*()和*_pmd_*()函数实现的功能也是一样的。 页目录(PGD)是一个大小为4K 的表,每一个进程只有一个页目录,以4字节为一个表项,分成1024个表项(或称入口点),表项的索引即为32位虚拟地址的页目录,该表项的值为所指页表的起始地址。页表(PTE)的每一个入口点的值为此表项所指的一页框(page frame),页表项的索引即为32位虚拟地址中的页号。页框(page reame)并不是物理页,它指的是虚存的一个地址空间。 3) 页表项的格式 图2 Linux 中页目录项和页表项格式 4)动态地址映射 Linux 虚存采用动态地址映射方式,即进程的地址空间和存储空间的对应关系是在程序的执行过 第26卷第3期长春理工大学学报 Vol 26N o 32003年9月 Journal of Changchun University of Science and T echnology Sep.2003 实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解 三.实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: zuoye.c 执行程序: zuoye.exe 2)实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业 完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、 所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待 W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周 转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 代替 二.最短作业优先算法 代替 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include linux内核IMQ源码实现分析
探究linux内核,超详细解析子系统
作业调度实验报告
读Linux内核源代码
操作系统实验报告-作业调度
Linux内核源代码阅读与工具介绍
作业调度算法(先来先服务算法,短作业算法)
linux源代码分析实验报告格式
Linux内核分析-网络[五]：网桥
FCFS和SJF进程调度算法实验报告
Linux源代码分析_存储管理
操作系统作业调度实验报告
相关主题
文本预览