基于操作系统作业调度算法的红绿灯调度.doc

本科毕业论文（设计）

题 目
红绿灯调度算法的研究及实现

学生姓名
侯永顺
学 　号
2009110813
系 名
数学与计算机信息工程系
专业年级
计算机科学与技术2009级
指导教师
梁碧珍
职　 称
副教授
单　　位
百色学院
辅导教师

职 称

单　　位

完成日期 2013年5月20日

目 录

百色学院本科毕业论文（设计）任务书 I
百色学院本科毕业论文（设计）开题报告 II
百色学院本科毕业论文（设计）中期自查表 IV
摘 要： V
ABSTRACT: V
1 绪论 1
1.1系统研究的背景及意义 1
1.2国内外研究现状 1
1.3 主要技术路线 2
2 主要问题论述 3
2.1车道汽车流向 3
2.2 单车道分级限速问题 6
2.3动态优先级值的计算 7
2.3.1优先级计算 7
2.3.2具体车道优先级计算 8
3 关于不同调度算法的说明 8
3.1 轮换调度算法 8
3.2 基于动态优先级的调度过程 9
3.2.1软抢占式调度 9
3.2.2硬抢占调度方式 10
3.2.3常规优先级调度 11
4 系统控制流程 14
4.1 优先级方差S² 14
4.2 临界值K 14
4.3 控制流程 14
4.4结果分析及结论 15
总 结 17
致 谢 18
参考文献： 19
百色学院本科毕业论文（设计）诚信保证书 20

百色学院本科毕业论文（设计）任务书

题目名称 红绿灯调度算法的研究及实现
学生姓名
侯永顺
所学专业
计算机科学与技术
班 级
计科本092班
指导教师姓名
梁碧珍
所学专业
计算机应用技术
职 称
副教授
完成期限
2013年5月20日
1.毕业论文（设计）主要内容或主要技术指标
基于操作系统作业调度算法的红绿灯调度是一个能管十字路口三车道，车流相位、互斥问题，生成通行的优先级，从而智能选择最优调度算法，为通行汽车提供最佳行车方案。本项目所涉及到的专业知识有数据库的应用技术、软件工程理论及应用等。编程语言C++，数据采用二进制文件存储形式。
2.毕业论文（设计）基本要求
（1）认真调研，做好文献查阅工作，对设计方案进行论证。
（2）设计要勇于创新，敢于实践，注意各种能力的锻炼和培养，完成设计要求。
（3）毕业论文的撰写格式要求等严格按照学院要求做，各相关引用文献要标注清楚、规范。
（4）撰写毕业论文时，做到条理清晰，逻辑性强，符合科技写作规范，并严格按照学校所规定的本科生毕业论文要求进行撰写、打印和装订。
3.毕业论文（设计）进度安排
（1）2012 年1 月完成开题报告。
（2）2012 年2 月完成项目的总体规划及项目文档的框架。
（3）2013年3月1 日至2013年4月1日： 完成系统初步设计及测试。
（4）2013年4月1日至2013年5月1日： 完成系统要求功能及进行局部测试。
（5）2013年5月1日至2013年5月18日：完成系统开发，进行最终系统测试。
（6）2013年5月20日：完成文档编写及答辩准备。

指导教师签名： 年 月 日

I

百色学院本科毕业论文（设计）开题报告
学号
2009110813
学生姓名
侯永顺
系 名
数学与计算机信息工程系
专业年级
计算机科学与技术
2009级
指导教师
梁碧珍
职称
副教授
论文（设计）题目
红绿灯调度算法的研究及实现
1.本论题国内外研究动态及研究意义：
传统的十字路口交通控制灯，通常是事先经过交通流量的调查，运用统计的方
法将两个方向红绿灯的延时预先设置好，一般红绿灯的维持和转变是定周期。而这种传统的控制灯已然不能满足如今城市发展带来的交通问题。
针对当前城市车流量大急剧增加，交通拥堵日益严重的现状，为解决城市交通拥堵问题，保证车辆高效的通行。国内外相关研究如雨后春笋，基于交通灯智能调度的研究成果很多。一定程度上对当前交通现状有所改善，但是在我国，虽然大中型城市型城市已有比较先进的调度设施，但是随着城镇化的推进，一些后劲崛起的小城市仍然沿用传统的控制等调度方式，没有合适小型城市的智能控制灯调度系统，使得小城市也饱受交通拥堵之祸。现针对一些小城市的交通现状，通过对车流的统计，变换调度优先级，根据不同交通情况引入不同的调度算法，实现交通灯指挥疏导交通的智能化。为车流疏导提供一种合理的解决办法。
2.毕业论文（设计)研究内容、拟解决的主要问题：
（1）十字路口三车道，车流相位问题，相位互斥；
（2）车道分级设置缓冲区，缓冲区内限速；
（3）车道获得通行的优先级的生成；
（4）具体路况智能选择最优调度算法；
（5）为通行汽车提供最佳行车方案。
3.毕业论文（设计)研究方法、步骤及措施：
（1）通过研读相关书籍，对车道通行优先级生成，调度算法，最短路基算法进行研究和初步的实现；
（2）在老师指导下，使用Microsoft Visual C++ 6.0作为开发工具，开始早期的MFC桌面应用程序；
（3）2012年1月20日至2012年3月1日：完成材料收集；
（4）2012年3月1 日至2012年4月1日： 完成系统初步设计及测试。
（5）2012年4月1日至2012年5月1日： 完成系统要求功能及进行局部测试。
（6）2012年5月1日至2012年5月18日：完成系统开发，进行最终系统测试。
（7）2012年5月20日：完成文档编写及答辩准备。
4.主要参考文献：
[1]汤子瀛.操作系统（第五版）[M].北京：清华大学出版社，2009.
[2]严蔚敏.数据结构[M]. 北京：清华大学出版，2009.
[3]谭浩强. c++面向对象程序设计教程（第三版）[M].北京：清华大学出版社，2009.
[4]侯捷.深入浅出MFC（第二版）[M].华中科技大学出版社,2001.
[5]（美）帕罗赛斯.北京博彦科技发展有限责任公司 译 .MFC Windows程序设计（第2版）[N].清华大学出版社,2007.
[6]（美）Stanley B. Lippman Barbara E.Moo Josée LaJoie 著，李师贤 等译. C++ Primer中文版[M].人民邮电出版社，2006.　
[7] (美)Walter Savitch著，周靖译.C++面向对象程序设计——基础、数据结构与编程思想[N].清华大学出版社，2004.
[8] (美)AI Stevens著，林瑶 等译.C++大学自学教程[M].电子工业出版社，2004.
[9]刘瑞新主编.Visual C++面向对象程序设计[M].机械工业出版社，2004.
是否可以进入论文（设计）研究：

指导教师签名：
年 月 日　

是否可以进入论文（设计）研究：

系主任签名：
年 月 日

百色学院本科毕业论文（设计）中期自查表
系 名
数学与计算机信息工程系
年 级
2009
专 业
计算机科学与技术
本人投入的时间和精力
每周平均工作 30 小时，出勤情况：较好（ √ ）、一般（√ ）、差（ ）。
影响时间投入的原因：
找工作（√ ）、自身水平（√ ）、其他原因 考试复习 。
指导教师的投入
指导教师每周指导 2 次，大约 2 小时；
指导形式：网络（√）、电话（ ）、面对面（ ）、其他 ；
指导效果： 好（√）、 较好（ ）、一般（ ）、 差（ ）。
毕业论文（设计）工作情况
是否能按任务书的“进程安排”完成工作：是（√ ）、否（ ），已完成内容占全部工作 50％ 。
你的论题是：自选（ √ ）、专业安排（ ）、跨专业（ ）。
论题是否结合专业（是）、难度（高）、工作量（大）。自己对毕业设计（论文）文件规范的学习情况：已了解（ √ ）、部分了解（）、不清楚（ ）。
条件保障
试验设备和器材是否得到保证：是（ ）、否（ √ ）。
学校提供的图书资料是否满足需要：是（ ）、一般（√ ）、否（ ）。
学校计算机上机条件：好（ ）、较好（√ ）、不好（ ）；约需 10 机时。
经费来源：学校（ ）、个人（ √ ）、尚无需要（ ）。
存在问题及
整改思路

存在问题：系统功能尚不完善，实现功能太少，界面美观度欠缺，功能设计不够健全，只实现了系统的简单功能。
整改思路：继续完善系统各功能。

学生签名： 年 月 日

指导教师签名： 年 月 日
IV

红绿灯调度算法的研究及实现

计算机科学与技术 2009110813 侯永顺 指导教师：梁碧珍

摘 要：红绿灯在交通指挥和控制中发挥着重要的作用，红绿灯调度的策略随着交通拥堵问题的涌现而不断改进，有许多优秀的调度策略出现。本文通过对计算机操作系统的研究，尝试将操作系统中复杂的作业调度算法应用到红绿灯控制交通中，从而形成一种新的红绿灯调度策略。
关键词：操作系统；作业调度算法；交通控制

The traffic light scheduling policy based on scheduling operating system job scheduling algorithm

Abstract: The traffic light plays an important role in traffic command and control, with the traffic congestion problem traffic scheduling strategies of continuous improvement emerge. This paper attempts to apply complex operating system scheduling algorithm to the control of traffic lights traffic , thus forming a traffic light new scheduling policy.
Key words: Operating system; Job scheduling algorithm; Traffic control

V

1 绪论
1.1系统研究的背景及意义
随着我国城市化的不断发展、汽车数量急剧增长，各个城市交通拥堵情况加剧，各地交通事故也频频地发生，日益恶化的交通环境已成为突出的城市问题。很多人都知道，缓解交通拥挤的最直接、最有效办法是提高路网的通信能力，从而实现高效的交通调度方案。由于受资金因素或者是土地因素的限制，无论哪个大城市，不可能无限制地修建道路。而城市交通中极为重要的部分——往成为影响整个城市交通的关键节点。高效的红绿灯调度方式不仅可以有序指挥交通，而且在很大程度上能够保障城市道路的畅通。
传统的十字路口交通控制灯，通常是事先经过交通流量的调查，运用统计的方法将两个方向红绿灯的延时预先设置好，一般红绿灯的维持和转变是定周期。而这种传统的控制灯已然不能满足如今城市发展带来的交通问题。
针对当前城市车流量大急剧增加，交通拥堵日益严重的现状，为解决城市交通拥堵问题，保证车辆高效的通行。国内外相关研究如雨后春笋，基于交通灯智能调度的研究成果很多。一定程度上对当前交通现状有所改善，但是在我国，虽然大中型城市型城市已有比较先进的调度设施，但是随着城镇化的推进，一些后劲崛起的小城市仍然沿用传统的控制等调度方式，没有合适小型城市的智能控制灯调度系统，使得小城市也饱受交通拥堵之祸。现针对一些小城市的交通现状，通过对车流的统计，变换调度优先级，根据不同交通情况引入不同的调度算法，实现交通灯指挥疏导交通的智能化。为车流疏导提供一种合理的解决办法。
本文主要论述了我们提出的基于操作系统作业调度算法形成的新的红绿灯调度方式。
1.2国内外研究现状
传统的十字路口交通控制灯，通常是事先经过交通流量的调查，运用统计的方法将两个方向红绿灯的延时预先设置好，一般红绿灯的维持和转变是定周期。而这种传统的控制灯已然不能满足如今城市发展带来的交通问题。
针对当前城市车流量大急剧增加，交通拥堵日益严重的现状，为解决城市交通拥堵问题，保证车辆高效的通行。国内外相关研究如雨后春笋，基于交通灯智
1

能调度的研究成果很多。一定程度上对当前交通现状有所改善，但是在我国，虽然大中型城市型城市已有比较先进的调度设施，但是随着城镇化的推进，一些后劲崛起的小城市仍然沿用传统的控制等调度方式，没有合适小型城市的智能控制灯调度系统，使得小城市也饱受交通拥堵之祸。现针对一些小城市的交通现状，通过对车流的统计，变换调度优先级，根据不同交通情况引入不同的调度算法，实现交通灯指挥疏导交通的智能化。为车流疏导提供一种合理的解决办法。
1.3 主要技术路线
本文主要是实现对我们提出的新的红绿灯调度方式的模拟，而交通调度有实时性的特点，调度的不可预知性。为实现本模拟系统的实时性和凸显我们提出的调度方式的智能性，我们采用基于对话框的MFC应用程序，设计的核心技术是灵活应用MFC提供的计时器资源。我们以Windows XP 操作系统、 Visual Studio C++ 6.0为开发环境，采用 MFC作为应用程序开发框架。

2 主要问题论述
2.1车道汽车流向

图2-1 六车道的十字路口示意图
规定一个车道中移动的车辆经过十字路口到另一车道为一个相位（M），那么一个上图的交叉路口会产生十二种相位：

图2-2 由南开始的相位图

图2-3 由北开始的相位图

图2-4 由东开始的相位图

图2-5 由西开始的相位图
在这十二种相位从互斥调度的角度可以分为两类，即：
第一类：N6到W1、S6到E1、W6到S1、E6到N1，这一类没有调度时方向互斥的问题，所以不需要调度，可自由通行；
第二类：N4到E3、S4到W3，W4到N3、E4到S3，E5到W2、W5到E2，N5到S2,、S5到N2。
其中在第二类中形成互斥的相位组分别是：
组一：N4到E3、S4到W3，W4到N3、E4到S3；
组二：E5到W2、W5到E2，N5到S2,、S5到N2。
经过上述分析，可以得出一次调度开放的相位有：
通行相位组一（N组）：N4到E3、S4到W3，N6到W1、S6到E1、W6到S1、E6到N1；
通行相位组二（W组）：W4到N3、E4到S3，N6到W1、S6到E1、W6到S1、E6到N1；
通行相位组三（E组）：E5到W2、W5到E2，N6到W1、S6到E1、W6到S1、E6到N1；
通行相位组四（S组）：S5到N2 、N5到S2，N6到W1、S6到E1、W6到S1、E6到N1。
通行相位组五（n组）：N4到E3、N5到S2，N6到W1、S6到E1、W6到S1、E6到N1；
通行相位组六（w组）：W4到N3、W5到E2，N6到W1、S6到E1、W6到S1、E6到N1；
通行相位组七（e组）：E4到S3、E5到W2，N6到W1、S6到E1、W6到S1、E6到N1、；
通行相位组八（s组）：S4到W3、S5到N2，N6到W1、S6到E1、W6到S1、E6到N1、N6到W1。
而这四组通行相位在时间上是互斥的，在同一时间只能容许其中一组通行，否则，可能会造成严重的交通事故。

图2-6 调度组放行示意图（通行相位组二）
2.2 单车道分级限速问题

图2-7 车流方向由南向北的三车道分级限速示意图
在这里对车流来源点路段进行分级限速，分级限速作三点主要说明：
第一：解决了车辆行车速度混乱而造成的拥堵问题和混乱秩序，同时限速便于计算车辆数，进而便于计算调度指标——优先级；
第二：在计算优先级时，多不同缓冲区赋予不同的权重，靠后的缓冲区在计算优先级时权重要比靠前的缓冲区权重要高；
第三：初始状态下缓冲区数量一定，每一个缓冲区能够容纳的车辆数量一定，一个缓冲区满，再动态开辟新的缓冲区，根据车辆拥堵情况，灵活增减缓冲区。
2.3动态优先级值的计算
2.3.1优先级计算
首先，如前面所述，四个互斥组要想被调度，必须获得最高的优先级。每一个组的优先级与该组每个车道上滞留的车辆有直接的关系。
就问题一所述，八个组分别是：N（组）、W（组）、E（组）、S（组），n（组）、w（组）、e（组）、s（组），各组中不形成互斥的相位有四组：N6到W1、S6到E1、W6到S1、E6到N1、N6到W1，这四组随时可以通行，故不用考虑调度的问题。
对剩下的相位作如下规定：
1. N4、S4，E4、W4，N5、S5，E5、W5；这八个车道是车辆来源车道；车道上车辆滞留重量用C表示，车道车辆滞留量由C和道路标识组合表示，每个车道车辆滞留量分别是CN4、CS4、CE4、CW4、CN5、CS5、CE5、CW5 ；
2. 计算机优先级时，各类权重用W表示，W和下标组合作为不同类型权重的区分，具体计算中给出解释；
3. 优先级用P表示，不同车道上的优先级由P和车道标识组合表示。
优先级计算公式：
P =Pi + ； 式（2.1）
其中Pi 车辆等待时间的延长而直接获得的优先级的值；设置这个量主要考虑到，如果某一个相位滞留车辆持续增加，时刻保持所有缓冲为满的情况，而其他车道靠前缓冲区都未满，且后续车辆又少，在此车道上的车辆将长时间得不到放行，这样造成不良调度。故在此设置Pi以避免上述情况的出现。
2.3.2具体车道优先级计算
1. 选取车道，本次选取N4；
2. 假设此十字路口每个方向车道分三级缓冲地带（三级都满后，开辟第四、五……），分别是：b1、b2、b3；
3. 权重用于衡量车辆滞留的严重度，靠后的缓冲地点应该比靠前的缓冲地带在计算优先级时有更高的权重，在这里，N4车道上三级缓冲地带计算优先级的权重分别是：Wb1、Wb2、Wb3（后续会出现Wbi） ，且Wb1 < Wb2< Wb3 ;
4. 在这里，N4车道上各个缓冲地带车辆为Cb1、Cb2、Cb3 ，
CN4 = Cb1+ Cb2+Cb3
5. 在这里，N4车道上的优先级，如式（2.2）为：
2PN4 =Pi + 式（2.2）
3 关于不同调度算法的说明
3.1 轮换调度算法
该算法的原型是，操作系统中作业调度和进程调度中共有的算法——基于时间片的轮转调度算法。根据问题一的论述，十字路口车辆放行时受空间限制而形成四组互斥放行组，早期红绿灯控制交通中，各个互斥组放行时间相同且一定。此种情况下，互斥的每个调度组被调度的优先级是一样的。
运用轮换调度算法具体操作如下：
在问题一中根据相位互斥，可以得出八组互斥的调度组，但是N组和n组、W组和w组、E组和e组、S组和s组，均含有相同的互斥相位，如果首先调度的N组，然后再立即放行n组，那么N4到E3这一相位在时间上连续两次被放行；类似其他组也是如此。如果该相位上车辆滞留很少，那么这样调度造成道路空间资源浪费；就该算法而言，也失去了调度的公平性，不利于其他车道上车流的疏导。所以在使用轮换调度时，在N、W、E、S和n、w、e、s，两组序列中任意选择一组序列作为调度的输入序列。
人工拟定四组的先后顺序，四个调度组排成一个队列，称为调度就绪队列。排在队首的先被调度，该组放行时间持续T秒，T秒结束后，该组至于调度就绪队列队尾，此时位于队首的一组如前一组一样操作。

图3-1 时间片轮转调度流程图（示例时间片大小为35秒）
轮换调度算法控制效果的好坏取决于每组时间片的大小，时间片小，单车道上拥堵的车辆少，在此段时间能够得到及时放行；但是对于拥堵车辆较多的车道，放行时间短，不同方向的红绿灯频繁变化，经过数次调度，拥堵在该车道车流中后位置的车辆部能被及时放行，不利于缓解该车道的拥堵情况。如果时间片长，经过一次或者比较少次调度后，拥堵车辆很多的车道得到疏导，但是拥堵车辆少的车道一次调度时间太长，甚至与该车道绿灯时没有或者很少有车辆通行，浪费没必要的时间，同时在这段时间内，其他车道的车辆又会逐渐增多，从而造成交通拥堵。因此，合理的时间片大小是决定该调度算法好坏的关键，如何得到合理的时间片大小，要根据具体的路口车辆通行情况的长期统计结构得到，并且随着城市的发展，这个数据要求不断更新。
3.2 基于动态优先级的调度过程
3.2.1软抢占式调度
这种调度方式要求中断所有当前正在放行的车道的调度，无条件让出通行权。具体流程如下图：

图3-2 软抢占调度流程图
流程说明，该调度策略主要是在一个相位组调度即将结束时，检测调度就绪队列中各相位组里是否有需要实时调度的任务，即，某个相位上滞留有需要急需放行的车辆（诸如：救护车、消防车、警用执勤车、其他一些工程车辆等），如果有，则此组在优先级比较中获得最高优先级，被置于调度就绪队列队首。
3.2.2硬抢占调度方式
当然上述调度存在缺陷，如，某个相位需要立即放行的车辆在其他相位组刚好被调度放行时到达，而此时被放行相位车道上滞留大量车辆，优先级久高不下，这样需要立即放行的车辆会长时间不能被放行，导致该车辆被延误，造成比较严重的后果。
针对上述情况，对上述情况，可以对软实时调度作细微改进——硬抢占式调度。具体流程如下图：

图3-3 硬抢占调度流程图
硬抢占调度方式，主要是改变了检测实时任务的时间，以及一旦检测到某个相位有实时任务时，在一定时间后，终止当前正在放行的相位，立即调度含有需要实时放行车辆的相位。
在这里不是一检测到就马上放行，而要使原先被调度的相位上的绿灯持续一段时间，主要考虑到，原先放行相位车道上有占据了十字路口的黄灯缓冲区的车辆，如果立刻调度含有需要立刻放行车辆的相位，而此相位与原先放行的相位互斥，这样容易造成交通事故。而一段时间的长短，要根据黄灯缓冲区的长度和要求车辆在该区域指定的速度决定（一般时间很短，不会延误调度）。
3.2.3常规优先级调度

图3-4 常规优先级调度的基本流程图
(1)阀值t：
阀值t 是每一次调度，被调度相位放行持续的最低时限。阀值的设定保证了每一次调度都会有一定的车辆得到通行。同时设置这个值，避免了由于优先级的细微变化而引起调度相位组频繁切换。阀值t 由具体路口车流统计得出。
而这个阀值可以分为可变和不可变：不可变阀值是，就单个十字路口而言，使用该调度体系，常规优先级调度的阀值始终是系统投入运行时设定的那个值。采用不变阀值，相对而言操作简单，系统开销会小一点，适合车流量相对稳定的路口。可变阀值是指在调度过程中，该值会根据每一次被放行车道上滞留车辆量来动态调整，如，上一次调度，车道上滞留车辆少，设定阀值为t1 相对较短，本次调度由于下班高峰期，被放行车道上滞留大量车辆，如果仍然采用前一次的阀值，t1时间过后，该相位的优先级与另一相位的优先级持平或略低，那么另一相位上的车辆被放行。而本车道上车辆滞留时间就会增加，另一车道上的后到达的车辆被放行了，而本车道上先达到的车辆仍旧滞留，这样调度明显是不合理的。所以动态改变阀值，使得滞留车辆少的车道被调度放行时获得较小的阀值，而滞留车辆多的车道被调度放行时获得较大阀值，从而提高调度效率。
(2)调度过程描述：
首先人工设定初始的调度就绪队列，队首的相位组被放行。该相位绿灯计时开始，开始计算各个相位的优先级并计时。采用固定阀值时，比较计时和阀值的大小，一旦计时大于阀值，对当前各个相位有点急排序，得出调度就绪队列，选择排在队首的相位组作为被调度相位组，对其放行。采用可变阀值是，先获得本次调度所需要的阀值，然后再如固定阀值时一样操作。
4 系统控制流程
前面完成了优先级的计算，和四种调度方式的说明。但系统运行起来，如何去选择合理的调度方式，怎样让红绿灯做出合理的变换，体现系统的智能性？在本节将做出解答。
4.1 优先级方差S²
由于只有八个优先级值，数据量小，因此采用比较简单的统计规律，获得一次调度时优先级的方差如式（4.1）：
S2= (PN4-P)2(PN5-P)2(PS4-P)2(PS5-P)2(PW4-P)2(PW5-P)2(PE4-P)2(PE5-P)2/8 式（4.1）
其中P是一组优先级的平均值P = (PN4+ PN5+ PS4 +PS5+ PW4+ PW5+ PE4+ PE5)/8
一组统计数据，方差反应了这组数据的波动情况。当八个相位的优先级基本相同时，基于优先级的调度方式作用不明显，此时退化成轮换调度方式，不仅操作上比较简单，也不会降低调度效率。而当一组优先级值波动较大时，此时选择基于优先级的调度方式效率会更高。因此在获得各组优先级之后计算出此时优先级的方差。
4.2 临界值K
在这里定义临界值的概念，这个值是定量判断一组统计数据的波动情况的量。计算得到优先级方差与临界值比较，根据比较结果选择对应的调度方式。
4.3 控制流程
首先获取各个互斥相位优先级，计算优先级方差S2,，与临界值K比较；当S2>K是说明各组之间优先级差异较大，优先级作用较为显著，选择基于合适的基于优先级调度方式；当S2<K时，各个相位上的优先级差异不明显，选择较为简单的轮转调度。流程图如下：

图4-1 控制流程图
4.4结果分析及结论
我们通过模拟传统的轮换调度获得相应的数据，实现基于优先级调度的数据，一次模拟，两种调度产生的数据如下表：
表4-1轮换调度和优先级调度放行结果统计
相位名称
传统的轮调度（次/min）
传统的轮调度（辆/min）
基于优先级的调度（次/min）
基于优先级的调度（辆/min）
N4到E3
1.285714
14.142857
6.722689
13.613445
S4到W3
1.285714
14.142857
4.705882
13.613445
W4到N3
0.857143
11.142857
5.042017
13.613445
E4到S3
1.285714
14.142857
3.025210
12.100840
W5到E2
1.285714
14.142857
2.689076
13.277312
S5到N2
1.285714
10.714286
3.193277
12.100840
N5到S2
1.285714
10714286
2.352941
13.277311
E5到W2
0.857143
11.142857
1.512605
13.613445

这里采集两类数据作对比分析，即，单位时间内单个相位被放行次数和单位时间内该相位上被放行的车辆数。从数据上看，单位时间内基于优先级的调度方式在切换调度相位上更频发，由于采用的前面提到的第一种随机数据生成策略，实际在各个相位上产生的车辆比较均衡，所以在调度的过程种优先级相对平均年龄，所以调度放行的车辆也相对平均，这与预期的调度效果是一致的，从数据上看基于优先级的调度是优于轮换调度的。
当然这只是试验数据的很小的一部分，不能作为评价整个调度系统的硬性数据，在不断的试验中，还有新的数据出现。

总 结
本文通过对操作系统进程调度和作业调度模块的研究，结合操作系统的作业调度算法，并引入存储体系中的缓存思想。为道路交通调度提供了一种比较系统的调度策略。对道路分级限速，解决拥堵乱像，为优先级的计算提供便利，使得更换高效的调度成为可能。将拥堵的严重程度作为计算优先级的主要指标，把优先级作为选择调度的唯一依据，同时充分考虑了紧急情况下的调度策略，针对不同情况提出了四种调度策略，基本上保证了一般情况，红绿灯对道路交通有条不紊的指挥控制。
当然本文也存在许多不足之处，由于受数学能力限制，不能具体给出临界值K的来源，而且对用优先级方差来衡量数据波动情况处理比较简单。本文中有一些数据需要大量统计计算适当建立数学模型才具有说服力，但是很遗憾在本文中也不能给出。在交通控制中有一些影响优先级的问题也没有考虑进来，譬如行人过马路的问题，交通事故后系统该如何处理等，这些都是有待改善的。

致 谢
大学四年学习时光已经接近尾声，在此我想对我的母校，我的父母朋友，我的老师和同学们表达我由衷的感谢。感谢我家人对我大学四年学习的默默支持；感谢我的母校百色学院给我学习的机会，感谢我系老师和同学们四年来对我的关心和帮助。平日里老师们的谆谆教诲时常在我耳边想起，是你们给了我学习知识的机会，是你们付出了辛勤努力让我得到了今天的成绩，在此，我再一次真诚地向帮助过我的老师和同学表示感谢！
在我做毕业设计的每个阶段，从选题到查阅资料，论文提纲的确定，中期论文的修改，后期论文格式调整等各个环节中梁老师都给予了我细心的指导和帮助，在此我向梁老师致以诚挚的谢意。同时，本篇论文的写作也得到了侯永顺、丽前等同学的热情帮助，感谢在整个毕业设计期间和我合作的同学，和曾经在各个方面给予我帮助的伙伴们，谢谢你们。
大学生活一晃而过，回首走过的岁月，心中倍感充实，当我写完这篇毕业论文的时候，感触良多。往后我会再接再厉，时刻牢记老师的教诲向着自己的梦想迈开强健有力的步伐，最终通向成功的彼岸。时光匆匆如流水，转眼便是大学毕业时节，春梦秋云，聚散真容易。离校日期已日趋临近，毕业论文也随之进入尾声。从开始进入课题到论文的顺利完成，一直都离不开老师、同学、朋友给我热情的帮助，在这里请再次接受我诚挚的谢意！
在未来的日子里，我会更加努力的学习和工作，不辜负父母以及老师们对我的殷切期望！

参考文献：
[1]汤子瀛.操作系统（第五版）[M].北京：清华大学出版社，2009.
[2]严蔚敏.数据结构[M]. 北京：清华大学出版，2009.
[3]谭浩强. c++面向对象程序设计教程（第三版）[M].北京：清华大学出版社，2009.
[4]侯捷.深入浅出MFC（第二版）[M].华中科技大学出版社,2001.
[5]（美）帕罗赛斯.北京博彦科技发展有限责任公司 译 .MFC Windows程序设计（第2版）[N].清华大学出版社,2007.
[6]（美）Stanley B. Lippman Barbara E.Moo Josée LaJoie 著，李师贤 等译. C++ Primer中文版[M].人民邮电出版社，2006.　
[7] (美)Walter Savitch著，周靖译.C++面向对象程序设计——基础、数据结构与编程思想[N].清华大学出版社，2004.
[8] (美)AI Stevens著，林瑶 等译.C++大学自学教程[M].电子工业出版社，2004.
[9]刘瑞新主编.Visual C++面向对象程序设计[M].机械工业出版社，2004.

百色学院本科毕业论文（设计）诚信保证书

对于毕业论文（设计）《红绿灯调度算法的研究及实现》，本人郑重承诺：其内容真实、可靠，系本人在 梁碧珍 教师的指导下独立完成；如果被查出有弄虚作假、抄袭剽窃行为，本人愿承担全部责任。

承诺者：

年 月 日

本科毕业论文（设计）

答辩提纲

系 名
数学与计算机信息工程系

专 业 名 称
计算机科学与技术

年 级
计本092班

学 号
2009110813

学 生 姓 名
侯永顺

答 辩 提 纲

论文（设计）题目
红绿灯调度算法的研究及实现
一、选择论题的目的和意义
如今，随着经济的发展，人流物流不断扩大，车流也不断的增长，特别是一些大的城市，每天都面临着庞大的车流，经常出现堵车现象，这就需要更多的交警来进行参与、指挥，耗时耗力，并不一定能够达到预期的效果，而红绿灯调度算法系统的开发相比以前全人工服务方式有着明显的优势 ，不仅减少人力物力财力，而且安全，值得推广。
现在的红绿灯调度系统是智能交通系统的一个重要部分，它可以尽快疏通交通堵塞，可以尽可能地避免因交通堵塞给人们带来的交通的不便利，而且都是机器自动化，大大减少了人力物力财力，做好一个红绿灯调度系统对一个城市的交通，城市居民的安全具有重大的意义。
二、论文（设计）的理论基础
交通控制系统、操作系统、数据结构、C++语言程序设计、MFC程序设计、数理统计等理论。
三、论文（设计）采用的主要研究方法
1.在设计规划方面：纵观社会动态根据现实的需求确定系统的研究主题，并根据需求制定出系统建设的总体规划。
2.在设计分析方面：通过研究操作系统作业调度的各种算法和流程以及结合当下交通控制的特点，提出新的交通调度算法。
3.在系统模拟实现方面：对系统进行总体结构设计、模块结构功能设计、数据流程设计、代码设计、界面设计。
4.在模拟系统实施方面：根据系统调度算法要求达到的预期效果进行系统的设计与调试，使系统能在实际操作中正常运行并为我提出的调度算法提供有效数据，用来对比分析。
5.在数据分析方面：根据控制不同变量，采用不同的调度算法，获得最终的实验数据，在根据实验数据进行对比分析。

四、论文（设计）的主要观点、价值及不足之处
1.在代码的精简和系统优化上做的不足，程序运行是会出现一些无法预知的bug，而又不能给出相应的处理方案；
2.系统在界面友好性上做的很不足，界面死板难看，部分模块的一些控件在事件响应上处理的不够干净；
3. 不能具体给出临界值K的来源，而且对用优先级方差来衡量数据波动情况处理比较简单；
4. 有一些数据需要大量统计计算适当建立数学模型才具有说服力，但是很遗憾在本文中也不能给出；
5. 在交通控制中有一些影响优先级的问题也没有考虑进来。
五、论文（设计）的内容框架
首先提出三种基于优先级的交通调度算法以及一如一种传统的交通调度方式，对这四种调度方式做了很详细的介绍。接下来，采用基于对话框的MFC程序作模拟调度为验证调度方式的有效性提过数据支持和感性认识。其中模拟系统主要实现的功能有：模拟现实道路车辆的产生；四种核心调度策略的实现；十字路口各车道车辆滞留、通行的动态显示，调度过程模拟，各类数据的存储、显示与分析；该调度算法中需要的参数的人工设置，人工预设调度方案

签 名：　　　　　　　
2012　年5月23日
注：该提纲由学生在答辩前一周填写完毕后交本系，系应于答辩前3天交答辩小组。

目 录
1. 总论 1
1.1 项目概况 1
1.2 项目建设的必要性 2