WiMAX基站各种调度算法的比较

Comparison of Different Scheduling Algorithms for

WiMAX Base Station

Deficit Round-Robin vs. Proportional Fair vs. Weighted Deficit Round-Robin

Jani Lakkakorpi Nokia Technology Platforms Helsinki, Finland https://www.wendangku.net/doc/959076116.html,kkakorpi@https://www.wendangku.net/doc/959076116.html,

Alexander Sayenko

Nokia Research Center

Helsinki, Finland

alexander.sayenko@https://www.wendangku.net/doc/959076116.html,

Jani Moilanen

Nokia Siemens Networks

Espoo, Finland

jani.moilanen@https://www.wendangku.net/doc/959076116.html,

Abstract—In this paper, we present a performance comparison of different WiMAX base station (BS) scheduling algorithms: Deficit Round-Robin (DRR) vs. Proportional Fair (PF) vs. Weighted Deficit Round-Robin (WDRR). Our simulations show that when the radio channel conditions are taken into account (in PF and WDRR schedulers), the improvements in throughput can be considerable.

Key Words—IEEE 802.16 WiMAX, scheduling, QoS, ns-2

I.I NTRODUCTION

WiMAX is an IEEE standard (IEEE 802.16d/e) for wireless broadband access network [1, 2]. Some of the main advantages of WiMAX over other access network technologies are longer range and more sophisticated support for Quality of Service (QoS) at the MAC level. Several different types of applications and services can be used in WiMAX networks and the MAC layer is designed to support this convergence. The standard defines two basic operational modes: mesh and point-to-multipoint (PMP). In the former mode, subscriber stations (SS) can communicate to each other and to the base stations (BS). In the PMP mode, the SSs are only allowed to communicate through the BS. Thus, the provider can control the environment to ensure the QoS requirements of its customers.

There can be multiple separate connections between the BS and an SS. At the BS, all downlink (DL) connections have dedicated buffers and slots are granted per connection. In uplink (UL) direction, however, the BS grants slots per SS and not per connection. It is the SS that decides how the UL slots are used. There are five standardized QoS classes in WiMAX (IEEE 802.16e, to be exact). Three of them can be used for real-time connections. In unsolicited grant service (UGS), the BS allocates fixed-size grants periodically; UGS connections cannot send any bandwidth requests. In real-time polling service (rtPS), the BS periodically polls the SS by granting one slot for sending a bandwidth request, while the goal of extended real-time polling service (ertPS) is to combine the advantages of UGS and rtPS. In ertPS, the BS continues granting the same amount of bandwidth (by default, the size of this allocation corresponds to maximum sustained traffic rate of the connection) until the ertPS connection explicitly requests a change in polling size. Extended piggyback request field of the grant management subheader can be used for this purpose. If the bandwidth request size is zero, the BS may provide allocations for bandwidth request header only or nothing at all. In the latter case, contention request opportunities can be used. The two remaining QoS classes are intended for non-real time traffic. Non-real time polling service (nrtPS) is similar to rtPS except that connections are polled less frequently and they can use contention request opportunities. Best Effort (BE) connections are never polled but they can only receive resources through contention.

This paper studies scheduling in a WiMAX BS. For these purposes, we run several simulation scenarios and apply different scheduling algorithms. The rest of this paper is organized as follows: section 2 presents the proposed algorithms, sections 3 and 4 present our simulator and the simulation results, respectively, while section 5 concludes the paper.

II.S CHEDULING A LGORITHMS

As in the case of other wireless technologies, it is likely that the air interface [1, 2] will be the biggest system bottleneck with WiMAX, too. This is why the BS scheduler should make sure that the scarce resources are used effectively.

A.Deficit Round-Robin

Deficit-Round-Robin (DRR) is a well-known scheduling algorithm [3] originally developed for IP networks. In DRR, the deficitCounter of each active1 connection is increased by quantum when the connection has its turn. If the size of the head-of-line packet of this connection is smaller than or equal to the deficitCounter, we send the packet and decrease the deficitCounter by the size of the packet. We continue sending packets as long as the deficitCounter allows. If the deficitCounter is too small for the head-of-line packet, we move to the next connection. The deficit that is stored in the 1 Here active connection means that the connection has packets in the queue.

deficitCounter of the connection is then saved for the next round. If we were able to serve all packets of the connection, the deficitCounter is reset to zero.

In our WiMAX BS, however, we do not schedule packets but slots. In fact, in the UL direction we do not even know the size of the head-of-line packet. Thus, the basic DRR algorithm needs to be modified a bit for our purposes. In each frame, the virtual (UL bandwidth request) and real (DL) queue sizes are converted from bytes to slots. The number of required slots depends on the current modulation and coding scheme (MCS) of the connection. The quantum parameter is now given in slots. In turn, the deficitCounter of each connection is increased by quantum. Slots are granted2 until all requests have been fulfilled or we run out of slots. Several rounds per frame can be done. If a queue drains out, the deficitCounter is reset to zero. It should be noted that in our variant of DRR only those DL and UL connections that are granted the last DL and UL slots of a frame can save any deficit for the next frame; all other deficitCounters should be zero at this stage.

B.Weighted Deficit Round-Robin

Weighted Deficit Round-Robin (WDRR) is a variant of DRR, where we adjust the quantum size according to connection’s current MCS. We simply multiply the quantum by bytes per slot that the current MCS of the connection can deliver and then divide the quantum by six (bytes per slot for QPSK-1/2, our most robust MCS when OFDMa is used). For example, with 16QAM-3/4 we have three times bigger quantum than with QPSK-1/2.

WDRR might need some additional starvation-avoidance features, e.g., a coefficient that determines the final quantum sizes. This is for further study.

C.Proportional Fair

Proportional Fair (PF) scheduler [4] should in theory result in better throughput than the DRR scheduler, because the PF scheduler assigns slots first to those connections that have the best ratio of current achievable rate to averaged rate. In every frame, the scheduler serves the connections in this order; we repeat the following sequence as long as there are available slots or until there are no more requests.

First, find the connection with biggest R(t) to T(t) ratio and grant as many slots as the connection needs or maximum number of slots that can be allocated at a time (scheduling slot size, similar to quantum in DRR). R(t) is the number of bytes that can be sent in a single slot; it is determined by the current MCS of the connection.

Then, update the exponentially averaged rate T for all connections (including those connections that do not have any 2 Slots are not granted immediately; here we only construct the MAP messages. data to send in this frame) N times. N is the number of slots we just allocated. If the connection was just served:

)(

*

/1

)(

*)

/1

1(

)1

(t

R

t

t

T

t

t

T

c

c

+

?

=

+. (1) Otherwise:

)(

*)

/1

1(

)1

(t

T

t

t

T

c

?

=

+. (2) Time constant t c is an adjustable parameter; it determines how long we can let a flow starve. In the case of 5 ms frame length and 500 slots per (DL or UL) subframe, t c of 10000 slots corresponds to 10000*(0.005/500) = 0.1 seconds. However, if we schedule real-time connections before BE connections, the number of DL or UL slots available for the BE class cannot be known beforehand. Thus, we should take our traffic mix into account when selecting the t c parameter. Initial value for T, T(0), can be set as the expected average rate divided by the expected average number of connections.

III.W I MAX N ETWORK S IMULATION M ODEL

The basic implementation of our WiMAX module is described in [5]. The module includes the following features: OFDM and OFDMa PHY levels (no MIMO3 support yet), transport and management connections, fragmentation (a large packet can be split between several MAC PDUs), packing (several packets and packet fragments can be put into a single PDU), ranging and bandwidth request contention periods, CDMA codes for ranging and bandwidth requests, support for the most important MAC level signaling messages and the ARQ mechanism that allows retransmitting dropped PDUs.

Additionally, the module includes several different BS schedulers and it has a simple model for link adaptation. These features are described in more detail in the following sections. A.MCS, Link Adaptation and Errors

MCS defines how many bits a connection can send in a single slot. The BS can dynamically change both the DL and UL MCS of an SS4 based on the channel conditions. In our simulator, link adaptation is modeled by a Markov chain (see Table I), where the states represent different MCSs. Transition from a state to another is possible in each frame. We have obtained the state transition probabilities from system simulations. Naturally, these results always correspond to certain simulation parameters.

The used error rate for a 100-byte MAC PDU is 10% with each MCS when ARQ is applied and 1% when ARQ is not applied. In real life, more robust MCSs would probably be used when the connection is run without ARQ. One approach would be to use separate Markov chains for these connections. With our present model, however, less robust MCSs may be used, too.

3 Multiple Input Multiple Output.

4 Different DL connections belonging to the same SS can use different MCSs.

TABLE I

B YTES PER S LOT V ALUES AND T RANSITION P ROBABILITIES OF THE L INK A DAPTATION M ARKOV

C HAIN

Transition probability to

Direction MCS Bytes/slot 64QAM-3/4 64QAM-2/3 16QAM-3/4 16QAM-1/2 QPSK-3/4 QPSK-1/2

64QAM-3/4 27 0.79486090 0.13948325 0.06565585 0.00000000 0.00000000 0.00000000 64QAM-2/3 24 0.28293998 0.38394350 0.33311652 0.00000000 0.00000000 0.00000000 16QAM-3/4 18 0.01279176 0.03352881 0.87825311 0.07542632 0.00000000 0.00000000 16QAM-1/2 12 0.00000000 0.00000000 0.02520945 0.94088229 0.03383335 0.00007491 QPSK-3/4 9 0.00000000 0.00000000 0.00000000 0.10215911 0.78974198 0.10809891 DL

QPSK-1/2 6 0.00033259 0.00005309 0.00048092 0.00127569 0.01932743 0.97853028 64QAM-3/4 27 0.68184019 0.21234867 0.08523002 0.01525424 0.00314770 0.00217918 64QAM-2/3 24

0.36491229 0.41250953 0.18550725 0.02730740 0.00503432 0.00472921 16QAM-3/4 18 0.02981995 0.06013912 0.73937498 0.13868273 0.01793856 0.01404466 16QAM-1/2 12 0.00374267 0.00865052 0.17964833 0.67039757 0.08975355 0.04780736 QPSK-3/4 9 0.00094722 0.00129166 0.01295961 0.11413933 0.50981658 0.36084560 UL

QPSK-1/2 6 0.00206103 0.00083422 0.00420929 0.01414364 0.04588231 0.93286951

B. Scheduler

The BS scheduler grants slots for the SSs according to the QoS parameters and bandwidth request sizes of the individual connections. Uplink virtual queue sizes are updated whenever slots are granted and every time a bandwidth request (that includes the real queue size) arrives. For DL connections, we use the BS queue sizes and the QoS parameters.

Our scheduler assigns slots in three stages (see Fig. 1): management connections are served first, then real-time connections, and finally non-real-time connections. Different scheduling algorithms (DRR, PF or WDRR) can be applied in the two latter stages. In DRR and WDRR, the (basic) quantum size is a configuration parameter 5; a bigger quantum size decreases the MAP overhead, because we then serve fewer connections per frame. In PF, the t c parameter controls the tradeoff between throughput and delay, while scheduling slot size is similar to quantum in DRR.

We have implemented support for three QoS classes: ertPS, rtPS and BE. ertPS and rtPS connections are served first; they are assigned slots until all ertPS and rtPS (virtual) queues are empty or until there are no slots left for this traffic. In order to avoid the starvation of BE connections, we can reserve a portion of all slots exclusively for these connections. Moreover,

connection admission control should take care that there are

always enough slots for the real-time connections 6. We could easily enhance our scheduler and provide support for UGS and nrtPS classes as illustrated in Fig. 1.

UL rtPS connections are polled regularly (frequency depends

on connection parameters), because they cannot participate in contention like the UL BE connections. UL ertPS connections are polled regularly, too, and during their active periods they are regularly granted slots based on their QoS requirements.

5

Default value for quantum and scheduling slot size is 17 slots for all connections. However, we could have different values for different stages. 6

If the connection admission control is conservative enough, it should not make a difference what scheduling algorithm we use for real-time connections – we should then be able to fulfill these requests in every frame.

Fig. 1. Multi-stage scheduler at the BS.

In order to make sure that no bandwidth is wasted; silence suppression detection at the BS is done for UL ertPS connections: whenever an UL frame is received, a connection-specific timer is launched. When this timer expires, we go into silence state, where only polling slots are granted. We do not let the ertPS connections participate in contention, because that might introduce large medium access delays. Having a sufficient amount of request opportunities, on the other hand, would make this option more feasible. The amount of request opportunities should then be adaptive [6] as we do not want to use all of our resources for contention.

BE connections are served after ertPS and rtPS connections; they are served until the BE (virtual) queues are empty or until there are no slots left. If there are still available UL slots, they

are assigned for contention. If ARQ is enabled for a connection, we apply the following connection-internal scheduling order (at the SS, too): 1) ARQ feedback messages, 2) retransmissions and 3) all other PDUs [7]. Currently we simulate only cases with a single connection

per SS. IV. P ERFORMANCE E VALUATION

We use a modified version of the ns-2 simulator [8]. The WiMAX related modifications have been described in the preceding section. Six simulations are run in each simulated case

in order to obtain 95% confidence intervals. Simulation time is always 200 seconds. One-way core network delay between a server and the BS is set to 31 ms. The only bottleneck in our system is the WiMAX air interface (see Fig. 2). The most important WiMAX network parameters are listed in Table II. We simulate the following traffic mix: 5 VoIP connections, 5 video streaming connections (DL only); 10, 14, 18, 22, 26 or 30 web browsing connections and 5, 7, 9, 11, 13 or 15 file downloading connections per BS. All user traffic is given BE treatment except for VoIP traffic that is given rtPS treatment. Our G.723.1 VoIP traffic source is a simple On-Off Markov model, where both On and Off period lengths are exponentially distributed with mean lengths of 1.2 s and 0.8 s, correspondingly. 24 bytes of payload is sent every 30 ms during active periods. Altogether, RTP, UDP and IP add 40 bytes of overhead, which results in a total packet size of 64 bytes. Packet header compression (from 40 bytes to 4 bytes) is applied at the BS and the SS.

TABLE II

S IMULATION P ARAMETERS Parameter Value PHY OFDMa Duplexing mode TDD Frame length 5 ms

Bandwidth 10 MHz

FFT size 1024

Cyclic prefix length 1/8

TTG (Transmit-receive Transition Gap) 296 PS

RTG (Receive-transmit Transition Gap) 168 PS DL/UL permutation zone FUSC/PUSC DL/UL ratio 35/12 DL-MAP/UL-MAP fixed overhead 13 bytes / 8 bytes Number of ranging opportunities 1 Ranging backoff start/end 0/15 Number of request opportunities 3 Request backoff start/end 3/15 CDMA codes for ranging and bw requests 64/192 Maximum MAC PDU size 100 bytes

Fragmentation/Packing Yes/Yes ARQ For all but VoIP connections ARQ feedback types All ARQ block size / window size 16 bytes / 1024 ARQ block rearrangement

No

Fig. 2.

Simulation topology.

The variable bit rate video traffic source is simulated according to [9]. The following parameters are used: mean rate of 125 kbps, maximum rate of 250 kbps and 1500-byte packets. UDP is used as a transport protocol and IPv4 adds 20 bytes of overhead, which results in a payload size of 1472 bytes.

Our web browsing traffic source is simplified from [10]; it is necessary to limit the variability of page sizes as the TCP goodput depends on that, too. We have a main page and 30 inline items per page, all items have a size of 4.91 kB, which results in a total page size of 152 kB (this is based on our measurements). Page reading time is uniformly distributed between 1 and 5 seconds and four NewReno TCP [11] connections are utilized. The same HTTP traffic model is used for modeling file downloading, but in that case only a single 250 kB file is downloaded. Time between two downloads is uniformly distributed between 1 and 5 seconds. A single NewReno TCP connection is utilized.

Fig. 3–11 illustrate the main results of our simulations. Both PF and WDRR perform very well (in terms of MAC throughput and TCP goodput) against DRR. This is in line with the results of

[12]. Especially the good performance of WDRR is a nice surprise as this scheme should be easier to implement (and less computationally complex) than PF. The fact that PF scheduler can leave a connection without any resources for quite a long period of time (if t c is large enough) may be a problem if ARQ timers are set to expire too soon. Moreover, sudden variations in round-trip time (RTT) might launch TCP retransmissions, and that could possibly lead into degraded TCP goodput.

WDRR outperforms PF with lower traffic loads, because the

PF algorithm needs to have enough connections in order to achieve better relative throughput gain. When there are more connections, it is more likely that the PF algorithm always picks a connection with a good MCS.

When large t c values are used in the PF scheduler, the price we have to pay for better TCP goodput is increased delay. However, Fig. 12–20 illustrate that Active Queue Management (AQM) at the BS (see [13] for details) can be used to dramatically reduce the queuing delays without sacrificing the goodput.

V. C ONCLUSIONS

In this paper, we have presented a performance comparison of different schedulers for WiMAX BS. Our simulations show that PF scheduler is clearly a better choice for BE traffic than DRR scheduler. However, more studies are still needed on, e.g., the impact of different ARQ timer values.

WDRR is an interesting alternative to PF as it is somewhat simpler in implementation. As WDRR seems to outperform PF when the number of connections is low, it could be feasible to combine PF and WDRR so that there would be a certain threshold (e.g., the number of users or connections) after which the scheduling algorithm would change from WDRR to PF.

For VoIP and other real-time traffic, DRR is still the best choice. It is not acceptable to let VoIP connections starve every now and then (when the most robust MCSs are used) just because that would lead into better MAC throughput. In fact, with PF scheduling, VoIP delay could grow intolerable if the number of VoIP connections is significant.

A CKNOWLEDGMENT

The authors would like to thank everyone involved in the ns-2 simulator development at the Telecommunication laboratory of University of Jyv?skyl?.

R EFERENCES

[1]Air interface for fixed broadband wireless access systems. IEEE Standard

802.16, Jun. 2004.

[2]Air interface for fixed broadband wireless access systems – amendment for

physical and medium access control layers for combined fixed and mobile operation in licensed bands. IEEE Standard 802.16e, Dec. 2005.

[3]M. Shreedhar and G. Varghese, “Efficient fair queueing using Deficit

Round-Robin,” IEEE/ACM Transactions on Networking, vol. 4, pp. 375-385, Jun. 1996.

[4] A. Jalali, R. Padovani, and R. Pankaj, “Data Throughput of CDMA-HDR:

A High Efficiency-High Data Rate Personal Communication Wireless

System,” Proceedings of the IEEE VTC2000-Spring, Tokyo, Japan, May 2000.

[5] A. Sayenko, O. Alanen, J. Karhula and T. H?m?l?inen,” Ensuring the QoS

Requirements in 802.16 Scheduling,” Proceedings of IEEE/ACM MSWiM 2006, Torremolinos, Spain, Oct. 2006.

[6] A. Sayenko, O. Alanen and T. H?m?l?inen, “Adaptive Contention

Resolution Parameters for the IEEE 802.16 Networks,” Proceedings of Qshine 2007, Vancouver, Canada, Aug. 2007.

[7] A. Sayenko, V. Tykhomyrov, H. Martikainen and O. Alanen,

“Performance Analysis of the 802.16 ARQ Mechanism,” Proceedings of IEEE/ACM MSWiM 2007, Chania, Greece, Oct. 2007.

[8]UCB/LBNL/VINT, “Network Simulator – ns (version 2),” Jun. 2007.

https://www.wendangku.net/doc/959076116.html,/nsnam/ns/index.html

[9] B. Maglaris, D. Anastassiou, P. Sen, G. Karlsson and J. Robbins,

“Performance Models of Statistical Multiplexing in Packet Video

Communications,” IEEE Transactions on Communications, vol. 36, pp.

834-844, Jul. 1988.

[10]M. Molina, P. Castelli and G. Foddis, “Web Traffic Modeling Exploiting

TCP Connections’ Temporal Clustering through HTML-REDUCE,” IEEE Network, vol. 12, pp. 46-55, May-Jun. 2000.

[11]S. Floyd and T. Henderson, “The NewReno Modification to TCP’s Fast

Recovery Algorithm,” RFC 2582, Apr. 1999.

[12]Chingyao Huang, Hung-Hui Juan, Meng-Shiang Lin and Chung-Ju Chang,

“Radio Resource Management of Heterogeneous Services in Mobile WiMAX systems,” IEEE Wireless Communications, vol.14, pp.20-26, Feb.

2007.

[13]J. Lakkakorpi, A. Sayenko, J. Karhula, O. Alanen and J. Moilanen, “Active

Queue Management for Reducing Downlink Delays in WiMAX,”

Proceedings of IEEE VTC2007-Fall, Baltimore, MD, USA, Oct. 2007.

with/without DL AQM. AQM. AQM.

模拟一种处理机调度算法讲解

课程设计报告 设计名称：模拟实现一种处理机调度算法 学生姓名： xxx 专业：计算机科学与技术 班别： xxxxxxxx 学号： xxxxxx 指导老师： xxxxx 日期： 2014 年 6 月 20 日

初始条件： 1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。 2．实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1．模拟进程调度，能够处理以下的情形： ⑴能够选择不同的调度算法（要求中给出的调度算法）； ⑵能够输入进程的基本信息，如进程名、优先级、到达 时间和运行时间等； ⑶根据选择的调度算法显示进程调度队列； ⑷根据选择的调度算法计算平均周转时间和平均带权周 转时间。 2．设计报告内容应说明： ⑴需求分析； ⑵功能设计（数据结构及模块说明）； ⑶开发平台及源程序的主要部分； ⑷测试用例，运行结果与运行情况分析； ⑸自我评价与总结： i）你认为你完成的设计哪些地方做得比较好或比较出 色； ii）什么地方做得不太好，以后如何改正；

iii）从本设计得到的收获（在编写，调试，执行过程中 的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方 法）； 进程调度模拟设计——先来先服务、优先级法1、背景： 当计算机系统是多道程序设计系统时，通常会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法成为调度算法。 进程调度的核心问题是采用什么样的算法把处理机分配给进程，好的算法将提高资源利用率，减少处理机的空闲时间，避免有些作业长期得不到相应的情况发生等，从而设计出受欢迎的操作系统。较常见的几种进程调度算法有：先来先服务调度算法；短作业优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先算法和多级反馈队列调度算法等。 2.1设计目的 无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机

处理器调度习题

处理器调度 选择题 当CPU执行操作系统代码时，则处理机处于( )。 A．执行态 B．目态 C．管态 D．就绪态 ( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 A．系统调用 B．操作系统 C．内核 D．特权指令 操作系统提供给程序员的接口是( )。 A．进程 B．系统调用 C．库函数 D．B和C 用户程序向系统提出使用外设的请求方式是( )。 A．作业申请 B．原语 C．系统调用 D．I／O指令 当作业正常完成进入完成状态时，操作系统( )。 A．将输出该作业的结果并删除内存中的作业 B．将收回该作业的所占资源并输出结果 C．将收回该作业的所占资源及输出结果，并删除该作业 D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 B．作业是比进程低一级的概念。 C．一个作业至少由一个进程组成。 D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 作业从后备作业到被调度程序选中的时间称为( )。 周转时间B．响应时间C．等待调度时间D．运行时间 设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 A．T1+T2+T3 B．1／3(T1+T2+T3) C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 从作业提交给系统到作业完成的时间间隔称为作业的( )。 A．中断时间 B．等待时间 C．周转时间 D．响应时间 设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 A．1 h B．5 h C．2．5 h D．8 h FCFS调度算法有利于( )。 A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 下列哪种说法不是SJ(P)F调度算法的缺点( )。 A．对于长作业(进程)不利 B．未考虑作业(进程)的紧迫程度 C．不能有效降低作业(进程)的平均等待时间 D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 A．先来先服务调度算法B．短进程优先调度算法 C．优先权调度算法D．高响应比优先调度算法 在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。

操作系统实验一处理机调度算法的实现

实验报告 学院（系）名称：计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级3班实验项目实验一：处理机调度算法的实现 课程名称操作系统课程代码0668036 实验时间2011 年11月17日第3、4节 2011 年11月21日第7、8节 2011 年11月24日第3、4节 实验地点软件实验室7-216 批改意见成绩 教师签字： 实验内容： 1．设定系统中有五个进程，每一个进程用一个进程控制块表示。 2．输入每个进程的“优先数”和“要求运行时间”。 3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。 4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。 5．若某进程运行时间为零，则将其状态置为“结束”,且退出队列。 6．运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。 实验要求： 1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果； 4．为增加程序可读性，在程序中进行适当注释说明； 5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强； 7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。

【实验过程记录（源程序、测试用例、测试结果及心得体会等）】 程序运行代码如下： #include #include #include struct PCB{//定义进程控制块PCB，包括进程的名字，优先运行数，运行时间char name[20]; int pri; int time; struct PCB * next; }*k; struct LinkQueue{//链式队列节点类型定义 PCB * front; PCB * rear; }; LinkQueue InitQueue(){//链式队列初始化 LinkQueue Q; PCB * p; p=(PCB*)malloc(sizeof(PCB));//申请头结点存储空间 if(p){ Q.front=Q.rear=p; Q.front->next=NULL;//头结点指针域置空 return Q; }else{ printf("初始化队列失败，程序运行终止！\n");//初始化失败 exit(0); } } LinkQueue sort(LinkQueue Q,PCB * p){//定义将进程按给定的优先数从大到小连成就绪队列的函数 PCB *temp1; PCB *temp2; if(Q.rear==Q.front){ Q.front->next=p; Q.rear=p; }else{ temp1=Q.front; temp2=temp1->next; while(temp2->pri>=p->pri && temp2->next!=NULL){ temp1=temp2; temp2=temp1->next; }if(temp2->next==NULL && temp2->pri>=p->pri){ temp2->next=p; Q.rear=p;

操作系统处理器调度算法C++程序

一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include #include using namespace std; int main() { int n,a[100],b[100]; double s[100],m[100],T=0,W=0; cout<<"请输入作业数:"<>n; cout<<"请分别输入各作业到达系统的时间:"<>b[i]; } cout<<"请分别输入各作业所运行的时间:"<>a[i];s[0]=0; s[i+1]=s[i]+a[i]; m[i+1]=(s[i+1]-b[i])/a[i]; T=T+s[i+1]-b[i]; W=W+m[i+1]; }

TCP拥塞控制算法性能比较-Read

TCP拥塞控制算法性能比较 一、NS2仿真 1.仿真实验的网络结构图 如图所示0、1、2为源节点，3为路由器，4为目的节点。源节点0、1、2为TCP代理节点，频宽为8Mbps，传递延迟时间为0.1ms，仿真时使用FTP流量。路由器的队列管理机制使用DropTail，频宽为0.8Mbps，传递延迟为100ms。在这个实验中建立3条TCP数据流，0和4、1和4、2和4。在OTCL编码中，代理节点的协议代理分别设置为TCP/Reno、TCP/Newreno、TCP/Sack1和tcp/Vegas，来模拟这四种算法。 二、模拟结果与算法分析比较 1、模拟拥塞控制四种算法的cwnd变换图：

2、TCP拥塞控制的四个阶段 这是TCP拥塞控制的核心，也体现了TCP拥塞控制的基本思想，它分为启动阶段，拥塞避免，快速重传和快速恢复阶段。 (1) 启动阶段 当连接刚建立或在发生一次超时的情况下，进入慢启动阶段。 一个新的TCP连接建立后，cwnd被初始化为1，源端只被允许发送一个报文段。当发出的报文收到接受端的ACK确认后，cwnd加1，即增加一个报文段发送。在这个阶段中，cwnd随RTT呈指数增长。 采用慢启动方法，可以防止TCP在启动一个新的连接时发送过多的数据而造成数据丢失和网络拥塞，同时，由于cwnd实际上以指数规律增长也就避免了单纯的AIMD算法造成的吞吐量增加过慢的问题。 cwnd的无限增长必将引起网络拥塞，于是引入一个状态变量：慢启动阈值ssthresh。 当cwndssthresh是，则采用拥塞避免算法，减缓cwnd的增长速度。 (2) 拥塞避免阶段

TCP拥塞控制算法比较

TCP拥塞控制算法比较 TCP发展到现在已经形成了TCP Tahoe、TCP Reno、TCP NewReno、SACK、Vegas等不同版本，这些算法各有利弊。 Tahoe算法是TCP的早期版本。它的核心思想是：让cwnd以指数增长方式迅速逼近可 用信道容量，然后慢慢接近均衡。它包括了3个基本的拥塞控制算法：慢启动、拥塞避免、快速重传。Tahoe的缺点体现在快速重传后转向慢启动算法，这样不能有效的利用网络带宽并且还引入较大的延时。 Reno算法是针对Tahoe算法的不足而做的改进。改进主要有两方面：一是对于收到连 续3个重复的ACK确认，算法不经过慢启动，而直接进入拥塞避免阶段；二是增加了快速重传和快速恢复机制。Reno算法以其简单、有效和鲁棒性成为TCP源算法的主流，被广泛的 采用。但它不能有效的处理多个报文分组从同一发送窗口中丢失的情况。 NewReno对Reno中快速恢复算法进行了补充，它考虑了一个发送窗口内多个报文分组 同时丢失的情况。Reno算法中，发送方收到一个不重复的应答后就退出快速恢复，而NewReno 中，只有当所有的报文分组都被应答后才退出快速恢复状态。NewReno的实现只要修改TCP 发送端的实现代码，实现简单。 SACK算法也针对一个窗口内多个报文分组丢失的情况而对Reno算法进行改进：SACK 定义了一个变量pipe来表示出现在路由器上报文分组的估计数量，接收方TCP发送SACK 分组来通知发送方的接收状况，这样源端就能准确的知道哪些报文分组被正确的传到接收端，从而避免不必要的重传，提高网络吞吐量。但SACK算法的实现需要修改TCP发送端和接收端的实现代码，增加了TCP的复杂性，因此不易大规模的应用。 Vegas与上述的算法不同，它是以RTT的变化作为拥塞信号，调节源端的发送速率。通过监测RTT的变化来改变cwnd的大小。由于Vegas采用RTT的改变来判断网络的可用带宽，能较好的预测网络带宽的使用情况，其公平性、效率都较好。但是，由于Vegas与其它算法在竞争带宽方面存在不公平现象，因此未能在因特网中普遍采用，还需要继续改进。

操作系统原理第四章 处理机调度习题

第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则

操作系统处理机调度算法的实现c语言源代码

处理机调度算法的实现 处理机调度算法的实现 1．设定系统中有五个进程，每一个进程用一个进程控制块表示。 2．输入每个进程的“优先数”和“要求运行时间”， 3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。 4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。 5．若要求运行时间为零，则将其状态置为“结束”,且退出队列。 6．运行所设计程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。 #include #include struct PCB { char name[10]; int priority,time; struct PCB *next; }*k; struct LinkQueue { PCB * front; PCB * rear; }; //队列初始化 LinkQueue init(){ LinkQueue Q; PCB * p; p=(PCB *)malloc(sizeof(PCB)); if(p) { Q.front=Q.rear=p; Q.front->next=NULL; return Q; }else{ printf("队列初始化失败，程序运行终止! \n"); exit(0); } } //插入新进程，使优先数从大到小排列 LinkQueue sort(LinkQueue Q,PCB *p) { PCB * temp1;

PCB * temp2; if(Q.rear==Q.front) { Q.front->next=p; Q.rear=p; } else { temp1=Q.front; temp2=temp1->next; while(temp2->priority>=p->priority && temp2->next!=NULL) { temp1=temp2; temp2=temp1->next; } if(temp2->next==NULL && temp2->priority>=p->priority) { temp2->next=p; Q.rear=p; } else { p->next=temp1->next; temp1->next=p; } } return Q; } LinkQueue input(LinkQueue Q) /* 建立进程控制块函数*/ { int i; for(i=1;i<=5;i++) { printf("\n 进程号No.%d:\n",i); k=(PCB *)malloc(sizeof(PCB)); printf("\n 输入进程名:"); scanf("%s",k->name); printf("\n 输入进程优先数:"); scanf("%d",&k->priority); printf("\n 输入进程运行时间:"); scanf("%d",&k->time); printf("\n"); k->next=NULL; Q=sort(Q,k); /* 调用sort函数*/ } return Q; } LinkQueue running(LinkQueue Q) /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ { if(k->time==0) {

处理器调度习题教学内容

处理器调度习题

处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法

操作系统-课程设计报告-处理机调度程序

: 操作系统 课程设计报告 @ 学校：广州大学 学院：计算机科学与教育软件学院 班级：计算机127班 课题：处理机调度程序 任课老师：陶文正、陈文彬 姓名：黄俊鹏 { 学号：11

班内序号：27 成绩： 日期：2015年1月6日 一、设计目的 在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。 二、设计要求 1）进程调度算法包括：时间片轮转法，短作业优先算法，动态优先级算法。2）可选择进程数量 3）本程序包括三种算法，用C语言实现，执行时在主界面选择算法（可用函数实现）（进程数，运行时间，优先数由随机函数产生）执行，显示结果。 三、设计思路及算法思想 1.· 2.界面菜单选项 一级菜单提供2个选项： ①自动生成进程数量 ②手动输入所需进程数量 一级菜单选择完毕后进入二级菜单： ①重新生成进程 ②时间片轮转法 《 ③短作业优先算法 ④动态优先级算法 ⑤退出程序 3.调度算法

程序所用PCB结构体 ! 需要用到的进程结构体如上图所示 1)时间片轮转法 主要是设置一个当前时间变量，curTime和时间片roundTime。 遍历进程组的时候，每运行一个进程，就把curTime += roundTime。进程已运行时间加roundTime 2)短作业优先算法 遍历进程组，找到未运行完成并且运行时间最短的进程，让它一次运行完成，如此往复，直到所有进程都运行完成为止。 3)— 4)动态优先级算法 做法跟短作业优先算法类似，此处主要是比较进程的优先数，优先级高者，先执行。直到全部执行完毕。当一个进程运行完毕后，适当增减其余进程的优先数，以达到动态调成优先级的效果。 4.程序流程图

七种IP拥塞控制算法需改进

七种IP拥塞控制算法需改进 DDoS攻击引起的网络拥塞，是由恶意主机控制大量傀儡机所造成的，并非传统意义上的端到端拥塞，所以只能在路由器上进行控制，即基于IP拥塞控制来实现的。而目前主流的七种IP拥塞控制算法都需要在改进后，才能有效地应用于防范DDoS攻击。 分布式拒绝服务DDoS（Distributed Denial of Service）攻击被认为是目前Internet所面临的最大威胁之一。 目前有一些常用的DDoS攻击防护机制和方法包括: 通过修改配置和协议预防攻击、反向查找攻击源头、攻击检测和过滤、分布式攻击检测和过滤(主机端/路由器端)等。 DDoS攻击与网络拥塞 网络产生拥塞的根本原因在于用户提供给网络的负载超过了网络的存储和处理能力，表现为无效数据包增加、报文时延增加与丢失、服务质量降低等。如果此时不能采取有效的检测和控制手段，就会导致拥塞逐渐加重，甚至造成系统崩溃，在一般情况下形成网络拥塞的三个直接原因是: ●路由器存储空间不足。几个输入数据流需要同一个

输出端口，如果入口速率之和大于出口速率，就会在这个端口上建立队列。如果没有足够的存储空间，数据包就会被丢弃，对突发数据流更是如此。增加存储空间在表面上似乎能解决这个矛盾，但根据Nagel的研究，如果路由器有无限存储量时，拥塞只会变得更坏。 ●带宽容量相对不足。直观地说，当数据总的输入带宽大于输出带宽时，在网络低速链路处就会形成带宽瓶颈，网络就会发生拥塞，相关证明可参考香农信息理论。 ●处理器处理能力较弱。如果路由器的CPU在执行排队缓存、更新路由表等操作时，处理速度跟不上高速链路，会产生拥塞。同理，低速链路对高速处理器也会产生拥塞。 以上是早期Internet网络发生拥塞的三个主要原因。对此，TCP拥塞控制给出了较好的解决方案。在实际应用中，如果所有的端用户均遵守或兼容TCP拥塞控制机制，网络的拥塞能得到很好的控制。但是，当DDoS攻击造成网络拥塞时，TCP基于窗口的拥塞控制机制对此无法加以解决。原因是攻击带来的拥塞是由大量恶意主机发送数据所造成的，这些主机不但不会完成TCP拥塞控制机制所规定的配合工作，甚至本身就可能包含了伪造源地址、加大数据发送量、增加连接数等攻击方式。在此情况下，对DDoS攻击所造成的网络拥塞就必须在路由器上进行处理，这只能是基于IP拥塞控制来实现的。

常见拥塞的优化方法(DOC)

常见小区拥塞的优化方法

内容简介 在本文中，主要从出现TCH信道拥塞可能的原因入手，提出一些解决TCH 信道拥塞的方法和思路，以供大家参考。 文档更新、审核记录 目录

一.存在均衡话务的可能 (5) 二.存在硬件问题的可能 (15) 三.存在需要扩容的可能； (16) 四.存在TCH和SD资源分配问题 (16)

前言 我们在谈到网络拥塞时，常常是指信令信道拥塞以及话务信道拥塞。其中话务信道拥塞也就是我们常说的TCH信道拥塞，发生在用户在申请网络服务信令交互之后，一般进行用户的真正话音要由TCH 信道承载，TCH信道的分配也称指配过程。出现TCH信道拥塞是说：在指配过程中，如果网络没有可用的TCH信道来分给手机，则系统计一次TCH分配失败。在本文中，主要从出现TCH信道拥塞可能的原因入手，提出一些解决TCH信道拥塞的方法和思路，以供大家参考。

一. 存在均衡话务的可能 存在覆盖均衡的可能是指：通过实际现场对出现拥塞的小区及其邻区的覆盖范围测试，或者在OMC上对出现拥塞的小区及其邻区做切换统计观察后，统计它们的TA大小分布，分析得出本小区的实际覆盖范围过大，而周边没有拥塞现象的小区覆盖过小，而没有充分吸收拥塞小区的话务量。此处的有话务均衡的可能是指：出现拥塞的小区其TCH拥塞率较高，但是，其SDCCH却不存在拥塞的情况，也即该小区在TCH与SDCCH资源的配置方面做得不合理。 若出现TCH信道拥塞，分析得出基站的覆盖与周边基站的覆盖没有合理地进行控制，或者TCH的拥塞率与SDCCH的拥塞率不均衡，则可以采用以下的方法进行处理：采用多种方法调整本基站与周边基站的覆盖范围；均衡拥塞基站与周边基站的话务量；对TCH与SDCCH不均衡的情况予以调整。 （1）调整本基站和邻区的发射功率等参数来收缩基站覆盖在基站拥塞情况不均衡的情况下，例如：本小区很忙，而相邻的小区却很闲，则通过调整本小区的发射功率等参数等可以有效收缩本小区的覆盖范围，同时适当调整邻区的参数来提高其覆盖，吸收话务。 相关的调整有： 1、调整基站的发射功率。BSPWRB是基站在BCCH信道上的发

按优先数调度算法实现处理机调度C++程序代码

#include using namespace std; struct PCB { char Name; //进程名 float Time; //要求运行时间 int Level; //优先数 bool state; //状态,1表就绪 PCB *next; //指针 }; void Init(PCB *head) { int num; PCB *s,*p; cout<<"请输入进程数"; cin>>num; for(int i=0;i >s->Name>>s->Time>>s->Level; if(s->Time>0) { s->state =1; while(p->next) { if(s->Level >p->next->Level )break; p=p->next ; } s->next=p->next; p->next=s; } else { s->state =0; cout<<"此进程要求运行时间时间不符合要求，不添加入进程列表"; } } } int Run(PCB *head) {

PCB *cur,*p; p=head; cur=p->next; p->next =cur->next; cur->Level--; cur->Time--; cout<<"此次执行的进程信息（执行后）:进程名"; cout<Name<<"剩余时间"<Time<<"优先数"<Level; if(cur->Time<=0) { cout<<"状态为完成态"<next) { if(cur->Level >p->next->Level )break; p=p->next ; } cur->next=p->next; p->next=cur; } cout<<"此次执行后的进程列表序列为："; p=head; while(p->next) { cout<next->Name<<" "; p=p->next ; } cout<

处理机调度算法实验报告

实验二处理机调度算法 （1）处理机调度的目的是什么？ 为提高内存利用率和系统吞吐量。 将那些暂时不能运行的进程调至外存，当内存不紧张时，将那些具备运行条件的就绪进程重新调入内存。 合理快速的处理计算机软件硬件资源，分配处理机，用以提高处理机的利用率及改善系统性能（吞吐量，响应时间）。 （2）处理机调度的算法有哪些，各自的优缺点是什么？ ①先来先服务算法：有利于长作业（进程），不利于短作业（进程）； ②短作业优先调度算法：有利于短作业（短进程），不利于长作业（长进程）； ③高优先权调度算法：静态缺点：可能导致低优先权进程长期得不到调度甚至饿死； 动态：优先权随进程等待时间增加或执行而变 ④高响应比优先调度算法 ⑤基于时间片轮转调度算法：时间片太小，会频繁发生中断，系统开销增大 时间片太大，响应进程慢。 ⑥多级反馈队列调度算法：具有较好的性能，能很好满足各类型用户的需求。 1．内存中作业运行的序列：A、B、D、C 2．A进入内存的时刻1，结束的时刻5 B进入内存的时刻5，结束的时刻8 D进入内存的时刻8，结束的时刻10 C进入内存的时刻10，结束的时刻15 3．平均周转时间：6 1．内存中作业运行的序列：B、C、A、D 2．B进入内存的时刻3，结束的时刻6 C进入内存的时刻6，结束的时刻11 A进入内存的时刻11，结束的时刻15 D进入内存的时刻15，结束的时刻17 3．平均周转时间：8.75

（4）画出处理机调度算法的程序流程图；

（5）补全参考程序； void process(int currentTmp, int nextTmp) { int j; int s=nextTmp-currentTmp; while(memoryNum>0 && s>=memory[0].needtime){ totalTime=totalTime+memory[0].needtime; s=s-memory[0].needtime; printf("线程%c的开始时间是:%d,结束时间 是:%f\n",memory[0].id,memory[0].cputime,totalTime+1); allTime+=totalTime+1; memoryNum--; for(j = 1; j<=memoryNum; j++) memory[j-1] = memory[j]; if(waitNum>0 && s>0){ memory[memoryNum] = wait[0]; memoryNum++; waitNum--; for(j = 1; j<=waitNum; j++) wait[j-1] = wait[j]; sort(memory,memoryNum, 'P'); } } if(memoryNum>0 && spriority)>((p+1)->priority)){ mao=*p;

3.6 拥塞控制原理

【自学笔记】 3.6拥塞控制原理 1 拥塞原因与开销 情况1:两个发送方和一个具有无穷大缓存的路由器 拥塞网络的一种开销，即当分组到达速率接近链路容量时，分组将经历较长的排队时延。 情况2:两个发送方和一个具有有限缓存的路由器 拥塞网络的另外一种开销，即发送方必须执行重传以补偿因为缓存溢出而丢弃(丢失)的分组。 发送方在遇到大时延时所进行的不必要重传，导致路由器需要利用其链路带宽来转发不必要的分组。 情况3:四个发送方、具有有限缓存的多台路由器和多跳路径 拥塞的另一种开梢，即当一个分组沿一条路径被丢弃时每个上游路由器用于转发该分组而使用的传输容量最终被浪费掉了。 2拥塞控制方法 实际中所采用的两种主要拥塞控制方法，可根据网络层是否为传输层拥塞控制提供了帮助来区分。 ·端到端拥塞控制。在端到端拥塞控制方法中，网络层没有为传输层拥塞控制提供显式支持。即使在网络中存在拥塞，端系统也必须通过对网络行为的观察(如分组丢失与时延) 来推断拥塞的发生。 TCP必须通过端到端的方法处理拥塞控制，因为lP层不会向端系统提供有关网络拥塞的反馈信息。TCP报文段的丢失(通过超时或3次冗余确认而得知)被认为是网络拥塞的一个迹象，TCP会相应地减小其发送窗口长度。 ?网络辅助的拥塞控制。在网络辅助的拥塞控制中，网络层设备件(即路由器)向发送方提供关于网络中拥塞状态的显式反馈信息。这种反馈可以通过数据报中的某个字段来指示链路中的拥塞情况。这种方法在早期的IBM SNA和ATM等体系结构中采用。 对于网络辅助的拥塞控制，拥塞信息从网络反馈到发送方通常有两种方式，直接反馈信息可以由网络路由器发给发送方。另一种形式是，路由器标记或更新从发送方流向接收方的分组中的某个字段来指示拥塞的产生(可以理解为对经过一个拥塞路由器的数据报做记号)。一旦接收方收到这个有拥塞标记的分组，就会通知发送方网络发生了拥塞。

计算机操作系统-处理机调度实验报告

中南大学 实验名称：处理机调度 课程名称：计算机操作系统 学生姓名盛希玲 学号 05 学院信息科学与工程学院 专业班级电子信息工程0602 完成时间 2008年10月12日

目录 一实验内容........................... 错误!未定义书签。二实验目的........................... 错误!未定义书签。三实验题目........................... 错误!未定义书签。四基本思想........................... 错误!未定义书签。五算法分析........................... 错误!未定义书签。六流程图............................. 错误!未定义书签。七算法描述........................... 错误!未定义书签。八运行输出结果....................... 错误!未定义书签。

一实验内容 选择一个调度算法，实现处理机调度。 二实验目的 多道系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现处理机调度，以加深了解处理机调度的工作。 三实验题目 设计一个按优先权调度和时间片轮转算法实现处理机调度的程序。 四基本思想 先选择时间片的个数和每个时间片需要的时间，正在运行的进程每运行一秒其优先权数目加一，即其优先权减小。每个时间片运行结束后，选择进入时间片进程优先权数目最小的进程，开始下一个时间片的运行。如果有进程运行结束，则离开，再在就绪队列中选择优先权数目最小的进程进入。在运行期间，如果有新的进程来到，按优先权大小放入就绪队列中。 五算法分析 定义一个结构体，此包含了PCB的信息： struct PCB { char PID[5]; /*进程名*/ int needtime; /*要求运行的时间*/ int cputime; /*已运行时间*/ int priority; /*优先权(越小越高)*/ int starttime; /*进入就绪队列的时间*/ int overtime; /*运行完成的时间*/ int state; /*状态:1就绪2运行3完成*/ struct PCB *next; }; 子函数struct PCB *create(int num,int n)用来建立一个按优先级大小排列的就绪进程链表和一个按时间先后循序排列的将进入就绪进程的链表。

操作系统原理-第四章处理机调度习题

第四章处理机调度 一. 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 **[i,j]=Allocation[i,j]+Need[i,j] **[i,j]= Allocation[i,j]+ Max[i,j] **[i,j]= Available[i,j]+Need[i,j] **[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。 A.先来先服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.长作业优先调度算法

拥塞控制算法

TCP拥塞控制算法 为了防止网络的拥塞现象，TCP提出了一系列的拥塞控制机制。最初由V. Jacobson在1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow start)”和“拥塞避免(Congestion avoidance)”组成，后来TCP Reno版本中又针对性的加入了“快速重传(Fast retransmit)”、“快速恢复(Fast Recovery)”算法，再后来在TCP NewReno中又对“快速恢复”算法进行了改进，近些年又出现了选择性应答( selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。 TCP的拥塞控制主要原理依赖于一个拥塞窗口(cwnd)来控制，在之前我们还讨论过TCP还有一个对端通告的接收窗口(rwnd)用于流量控制。窗口值的大小就代表能够发送出去的但还没有收到ACK的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也有越可能使得网络出现拥塞，如果窗口值为1，那么就简化为一个停等协议，每发送一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。TCP的拥塞控制算法就是要在这两者之间权衡，选取最好的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。 由于需要考虑拥塞控制和流量控制两个方面的内容，因此TCP的真正的发送窗口=min(rwnd, cwnd)。但是rwnd是由对端确定的，网络环境对其没有影响，所以在考虑拥塞的时候我们一般不考虑rwnd的值，我们暂时只讨论如何确定cwnd值的大小。关于cwnd的单位，在TCP中是以字节来做单位的，我们假设TCP 每次传输都是按照MSS大小来发送数据的，因此你可以认为cwnd按照数据包个数来做单位也可以理解，所以有时我们说cwnd增加1也就是相当于字节数增加1个MSS大小。 慢启动：最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说，当新建连接时，cwnd初始化为1个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发送数据，每当有一个报文段被确认，cwnd就增加1个MSS大小。这样cwnd的值就随着网络往返时间(Round Trip Time,RTT)呈指数级增长，事实上，慢启动的速度一点也不慢，只是它的起点比较低一点而已。我们可以简单计算下： 开始 ---> cwnd = 1 经过1个RTT后 ---> cwnd = 2*1 = 2 经过2个RTT后 ---> cwnd = 2*2= 4 经过3个RTT后 ---> cwnd = 4*2 = 8 如果带宽为W，那么经过RTT*log2W时间就可以占满带宽。 拥塞避免：从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带宽资源，但是