利用操作系统进程调度算法分析城市拥堵问题

韩沐轩，徐艳

（成都锦城学院 计算机与软件学院，四川成都，611731）

1 研究背景与意义

现在的城市交通存在以下一些问题：一、城市交通的基础设施不够完善。二、城市交通的设计不合理。三、城市交通的管理缺乏有效的机制。城市的交通问题将会影响一个城市的各个方面比如：拥堵的交通将会增加人们通勤的时间从而影响一个城市的经济发展、堵车也会浪费更多的资源并且产生更多的有害气体污染空气、同时面对一些紧急事情的处理上也会因为交通的拥堵可能造成一些严重的损失。计算机的操作系统和城市的交通系统在很多方面都十分的相似，因此我们可以通过计算机操作系统来帮助我们分析并解决城市的交通拥堵问题。所以，通过计算机操作系统的知识来解决交通拥堵对于中国城市未来的发展具有十分深远的意义。

2 城市老城区道路拥堵问题

老城区的规划和建造时间较早，然而随着城市的发展和汽车保有量的不断增加，这导致了老城区交通道路早已不能满足如今的道路需要。因此，对老城区的交通道路进行相应的重新修建或者适当的改造，这将会大大提高生活在附近居民的生活质量以及出现的便利性。同时，在一些人文气息浓厚的老城区通过交通条件的改善也会使其更加具有吸引力，从而带动城市的旅游业和经济的发展[1]。

2.1 城市老城区道路拥堵的解决办法

这时我们可以从操作系统原理中引入多线程的概念来帮助解决问题。一个程序可以有多个线程同时进行工作，这里的程序可以比作从老城区的A点到B点这个过程，而多线程可以比作从A点到B点的道路可以同时通过多辆汽车。然后通过下面的程序可以帮助我们更加直观的了解多线程在解决老城区道路拥堵时起到的重要作用，我们设置a代表的是同方向汽车的数量，m代表车辆通过所需时间，用循环来实现得到每个车道通过所需时间，x代表为车道数，当x越大时m的值就越小。

综上所述我们可以得出结论就是当汽车的总量相同时车道数越多所需通过的时间越短。因此，老城区的交通拥堵问题可以通过扩建道路来进行缓解。

3 高速公路事故拥堵问题

高速公路时常会因为雨雪天气导致的道路的摩擦阻力减小等环境因素，驾驶人员的安全意识淡薄、没有遵守交通规则、驾驶水平较差或者存在疲劳驾驶等人为因素，汽车的轮胎使用时间过长导致的摩擦力变小或者制动的机械结构损坏等汽车因素，从而导致发生严重的交通事故，进而导致产生了高速公路的交通拥堵现象[2]。

3.1 针对高速公路事故拥堵的解决办法

我国高速公路的建设标准一般都是单向两车道以上，然而高速公路发生的事故一般都会涉及两个车道及以上，这会导致高速公路单方向可通行的车道可能只有一个，但是因为高速公路事故导致拥堵的车辆会有两三个车道，当交通警察抵达事故地点对后续车辆进行疏通时应该怎么样安排不同车道的疏通顺序才能使大家的拥堵时间变少呢？操作系统中的进程调度算法将会帮助交通警察更加高效的疏通道路。

首先，我们需要引入的算法有：先来先服务算法（FCFS）、短作业优先算法（SJF/SPF）、时间片轮转算法（RR）。

先来先服务算法（FCFS）：按照进程进入就绪队列的先后时间来进行排队，先来的先执行后来的后执行，优点是简单，缺点是对于后面进入的进程不公平、而且使用这个算法有很大的不确定性，因为你并不能缺点是短进程先来还是长进程先来，而且通常会导致平均周期很长。

短作业优先算法（SJF/SPF）：当有多个进程在就绪队列中排队时，其中短进程优先执行并且当有更短的进程进入就绪队列后会发生抢占让更短的进程优先执行。在平均周期上会比先来先服务算法更短，然而这个也有缺点就是对短进程公平而对长进程不公平，在某些长进程的重要性上大于短进程时就会降低工作效率。

时间片轮转算法（RR）：规定一个固定的时间片例如1秒，当就绪队列的第一个进程运行1秒之后就会排在队列的最后一个，然后就是第二个进程运行1秒后排在之前第一个进程的后面，这样一直重复循环。时间片轮转算法的优点就是对不管是长进程还是短进程都是公平的，但是对于该算法最大的缺点就是对时间片的设定上面，时间片过短会导致调度程序剥夺处理器的次数增加而让系统的开销增大，时间片过长会导致时间片轮转算法变成效率较低的先来先服务算法[3]。

3.1.1 不同算法疏通道路的分析与比较

我们假定一个高速同向是三车道，因为前方发生了事故导致有两个车道无法正常使用，现在有A、B、C三个个车道的车辆等待通行，其中A车道车辆到达事故地点时间为12：00通过需花费3分钟，B车道车辆到达事故地点时间为12：02通过需花费6分钟，C车道车辆到达事故地点时间为12：04通过需花费4分钟，这时候交通警察该什么顺序疏通三个车道的车辆从而使得大家的平均等待时间最短。以下代码是通过C语言实现三种调度算法在该问题的运用：

（1）先来先服务（FCFS）程序：

void FCFS(vector &pcb，int &n)

{Input(pcb，n);

TimeBubbleSort(pcb，n);

float tursum=0.0;

float Time=0;//运行总时间

for(int i=0;i

{if(i==0)

{pcb[0].fintime=pcb[0].sertime;

Time=pcb[0].fintime;}

Else

{if(pcb[i].arrtime>Time){//如果前一个进程运行完成下一个进程没有到达Time=pcb[i].arrtime;}

pcb[i].fintime=pcb[i].sertime+Time;//更新一下程序运行的总时间

Time=pcb[i].fintime;}

pcb[i].turtime=pcb[i].fintime-pcb[i].arrtime;

tursum+=pcb[i].turtime;}

Output(pcb,n,tursum);

}

（2）短进程优先算法（SJF）：

void SJF(vector &pcb,int n)

{Input(pcb,n);

//先按照到达时间排序

TimeBubbleSort(pcb,n);

float Time=0;

bool flaghave=false;

float tursum=0.0;

//一次运行一个进程

//第一个进程一定先运行

pcb[0].fintim=pcb[0].sertime;

pcb[0].flagrun=true;

pcb[0].turtime=pcb[0].fintime-pcb[0].arrtime;

Time=pcb[0].fintime;

tursum+=pcb[0].turtime;

for(int i=1;i

{flaghave=false;

//找出当前数组中还没有运行的第一个pcb

//不会存在全部运行过的情况,因为上面的for循环是n-1次,所以肯定刚好把下标从1～n-1的访问完

int Minser=0;

for(int index=1;index

{if(!pcb[index].flagrun)

{Minser=index;break;}

}

//找到之后,从第一个节点开始向后访问,判断有没有到达时间小于Time的有:再找出服务时间最小的

for(int j=1;j

{if((pcb[j].arrtime

{flaghave=true;

if(pcb[j].sertime

Minser=;}

}

//没有:当前进程就是到达时间最小的,直接运行它,Minser不用变

if(!flaghave){Time=pcb[Minser].arrtime;}

//计算当前进程的各个时间

pcb[Minser].fintime=Time+pcb[Minser].sertime;

pcb[Minser].turtime=pcb[Minser].fintimepcb[Minser].arrtime;

pcb[Minser].flagrun=true;

Time=pcb[Miner].fintime;

tursum+=pcb[Minser].turtime;

}

Output(pcb,n,tursum);

}

时间片轮转算法（RR）：

void RR(vector &pcb,int n,int time)

{Input(pcb,n);

//先按到达时间排序

Time_BubbleSort(pcb,n);

queuepq;

//第一个一定先运行

//先将pcb[0]push进去

pcb[0].flagpush=true;

pq.push(pcb[0]);

int q=time;//时间片

float Time=0;//程序的运行时间

bool flagall=false;//是否全部入队

while((!pq.empty())||(!flagall))

{--q;++Time;

//如果有进程到达入队

//如果已经全部入过队了就不用判断了省时间

if(!flagall)

{for(int i=1;i

{if((pcb[i].arrtime==Time)&&(!pcb[i].flagpush))

{pcb[i].flagpush=true;pq.push(pcb[i]);

if(pq.size()==n)

flagall=true;break;

}

}

//判断是否所有的进程都进入了队列作用是当有一个进程执行完但是后面有进程没有到达时要一直++Time

for(inti=0;i

{if(pcb[i].flagpush=false)

flagall=false;

}

}

//队列不为空就去访问队列为空有两种情况:1.所有进程运行完了2.当前进程运行完了,但是下一个没有到达,这个不用管,会继续while循环

if(!pq.empty())

{//自身的完成时间+1

++pq.front().run_time;

//如果运行完了队首出队换下一个运行

if(pq.front().run_time==pq.front().sertime)

{pq.front().fintime=Time;

For(int i=0;i

{if(pcb[i].name==pq.front().name)

{pcb[i]=pq.front();break;}

}

pq.pop();

q=time;}

else{//没有运行完后面还有别的进程挂到队尾运行的下一个进程

if(!pq.empty()&&pq.size()>1)

{if(q==0)

{q=time;pq.push(pq.front());pq.pop();}

}

}

}

//一个进程运行完但是另一个没有进来时间片会轮完所以要更新

if(q==0)

q=time;

}

float tursum=0;

//计算后面每一个的各个时间

for(int i=0;i

{pcb[i].turtime=pcb[i].fintime-pcb[i].arrtime;

tursum+=pcb[i].turtime;

}

Output(pcb,n,tursum);

}

代码运行结果如下图1所示：

因此我们可以得出了一个更深层的结论，每个算法其实都有自己的优点和缺点，在某些适合该算法的情况下效率最高，但是在实际使用中通常都是几个算法相互结合起来使用以达到最高的效率。

图1 三种算法的结果

4 结语

我们是真的可以利用操作系统中的一些原理问题进行分析，然后将其拆分使之可以灵活地运用在如何去解决城市或者城市与城市之间的交通拥堵问题。当然单单使用合适的方法并不能解决拥堵问题，同时我们也需要增大驾驶人员考取驾照的难度使其能够减少因驾驶不当而造成的交通拥堵，城市规划部门的合理规划和长远规划更是十分重要。