A scalable logical coordinates framework for routing in wireless sensor networks

A Scalable Logical Coordinates Framework for Routing

in Wireless Sensor Networks?

Qing Cao and Tarek Abdelzaher

Department of Computer Science,University of Virginia,Charlottesville,V A22904

e-mail:{qingcao,zaher}@https://www.wendangku.net/doc/d19458038.html,

Abstract

Routing is one of the key challenges in sensor networks that directly affects the information throughput and energy expenditure.Geographic routing is the most scalable rout-ing scheme for statically placed nodes in that it uses only a constant amount of per-node state regardless of network size.The location information needed for this scheme,how-ever,is not easy to compute accurately using current lo-calization algorithms.In this paper,we propose a novel logical coordinate framework that encodes connectivity in-formation for routing purposes without the bene?t of geo-graphic knowledge,while retaining the constant-state ad-vantage of geographic routing.In addition to ef?ciency in the absence of geographic knowledge,our scheme has two important advantages:(i)it improves robustness in the pres-ence of voids compared to other logical coordinate frame-works,and(ii)it allows inferring bounds on route hop count from the logical coordinates of the source and destination nodes,which makes it a candidate for use in soft real-time systems.The scheme is evaluated in simulation demonstrat-ing the advantages of the new protocol.

1.Introduction

Recent technology has made exciting progress in large-scale sensor networks,which opens the door for myriads of civil,meteorological and military https://www.wendangku.net/doc/d19458038.html,rge-scale sensor networks can be deployed to carry out vari-ous tasks without the need for human intervention.Ef?cient data dissemination among different parts of the network is crucial for overall application performance.Such dissemi-nation hinges on the design and implementation of ef?cient routing protocols.

Current routing protocols for sensor networks(and more generally for ad hoc wireless networks)broadly fall into ?The work reported in this paper was supported in part by the National Science Foundation grants EHS-0208769and ITR EIA-0205327, DARPA grant F33615-01-C-1905,and MURI grant N00014-01-1-0576.two categories;address based[13,20,14]and content based[25,4].The former category requires an explicit des-tination address.The latter implicitly de?nes a set of desti-nations by their attributes and delivers the data to all match-ing destinations.It is likely that future sensor networks need both types of routing protocols.Content-based routing may be used as an ef?cient multicast mechanism that discovers a set of destinations matching given criteria(and returns their addresses to the sender if needed).Address-based routing can then be used to unicast data individually to particular destinations in the content-based groups as dictated by ap-plication logic.In this paper,we focus on the latter type and assume that when the address-based routing is needed,the addresses of the destinations have been obtained in advance, presumably through some content based mechanisms.

With the exception of geographic routing schemes[9,1, 14,15,8](where nodes are addressed by their location), address-based routing schemes are typically not scalable in that their routing state grows as some function of either the network size or the number of active destinations.In con-trast,geographic routing needs a constant amount of state that is only related to the node’s immediate neighborhood. Unfortunately,it also needs location information.While a plethora of localization services have been proposed to esti-mate node locations using a small number of GPS-enabled anchors[23,18,3,16],accurate localization services re-main hard to implement.It has been shown that errors in node location information lead to routing failures[11]. This dif?culty motivates the development of scalable rout-ing protocols(i.e.,those that maintain a constant amount of state)that do not rely on geographic knowledge.This pa-per presents logical coordinate routing,which belongs to this category.

The main idea of our scheme is for each node to main-tain hop counts to a small number of landmarks.This hop count vector is the logical coordinate of the node.The dif-ference vector between two node vectors represents the dis-tance between them.The routing scheme forwards packets in the direction that minimizes the magnitude of the remain-ing difference https://www.wendangku.net/doc/d19458038.html,pared with current routing pro-

tocols,this simple scheme has several advantages.First,it translates the routing problem into a different logical do-main in which the state kept on each node is constant(only immediate neighbor coordinates).Moreover,it can encode a con?gurable amount of topological information that de-pends on the number of chosen landmarks,which we call con?gurable dimensionality,from which we observe sev-eral positive implications.Most importantly,since the log-ical coordinate dimensions can be arbitrarily enriched by increasing the number of landmarks,logical vectors con-tain inherent redundancy,which signi?cantly improves ro-bustness with respect to node failures and physical voids. Selecting an appropriate number of landmarks at suitable locations makes it possible to eliminate voids in the log-ical coordinate space despite their existence in the physi-cal https://www.wendangku.net/doc/d19458038.html,pared to location-based approaches,the log-ical coordinates directly encode connectivity relationships among nodes,rather than physical proximity.Hence,they re?ect and abstract the more relevant topological informa-tion in a simple and ef?cient manner.In this paper,we call routing in the new coordinate space logical coordinate rout-ing(LCR).Finally,the logical coordinates of each node can be used to bound the actual hop distance between two ar-bitrary nodes.As a result,they can be leveraged to predict the delivery delay between nodes,which is of use in soft real-time sensor networks such as EnviroTrack[7]and Mo-bicast[12].

Recently,other ef?cient routing protocols emerged that are geographical location independent[21,17].Compared with them,our protocol is the?rst one to use con?gurable logical dimensionality,and directly encode a bound on hop count.Besides,simulation-based comparisons show that our protocol demonstrates a considerable performance im-provement in delivery ratio,especially in the presence of voids.

In the rest of this paper,we present an exploration of the new logical coordinate framework and its possible ap-plications.The paper is organized as follows.Section2de-scribes our assumptions,the design of the logical space and its properties.The design of a speci?c simple-forwarding based routing protocol is presented in Section3.Section 4describes our experiments and an in-depth analysis of the data collected.We review related work in Section5and con-clude in Section6.

2.Design of the Logical Coordinates

In this section,we present the assumptions,principles and properties of the logical coordinate framework.

2.1.Assumptions

We assume that the nodes are placed on a plane.(This assumption regarding physical space is not to be confused with the con?gurable dimensionality in the logical coordi-nate space).Planar placement is usually an adequate char-acterization of many real applications.Second,we consider the position of individual nodes to be relatively static.The static model generally characterizes typical sensor networks well enough.In practice,we may recompute the logical co-ordinates of each node periodically to account for possible displacement due to wind and other environmental factors. Third,we assume that the approximate placement of land-marks is controllable.For example,they can be purposely placed at the boundaries of the region.We will demonstrate later that the location of the landmarks has considerable im-pact on the ef?ciency of logical coordinates.At last,we as-sume that the communication links between nodes are bi-directional.Although this may not be true in reality,it can be easily achieved by selecting only those links which are bi-directional for communication.

In our framework,nodes need not know their location.It is important to clarify that this paper does not argue against use of localization services.In fact,approximate knowledge of location is essential for many sensor network applica-tions,such as target tracking.However,unlike target track-ing where location errors of individual target-tracking nodes can be reduced by averaging across multiple observers,in geographic routing individual node locations play a key role in forwarding decisions.Hence,location information must be accurate not only after aggregation and trajectory?tting, but also at the individual node level.The paper therefore as-serts that it is bene?cial not to have to rely on the availabil-ity of such accurate location information for the bene?t of routing services.

2.2.The Logical Coordinate Space

The idea of the logical coordinate approach is partly in-spired by the classical distance vector concept in conven-tional networks in that the key structure in our framework is based on measuring hop counts between nodes.The key difference is that instead of encoding the hop count between any two nodes,we encode hop distance to a few reference points(landmarks)only.As we show later,it is advanta-geous to place the landmarks as sparsely as possible.

After the landmarks are chosen,the logical coordinate framework is constructed as follows.First,each landmark broadcasts a beacon that is forwarded once to all nodes along with a hop count parameter.The hop count is initial-ized to zero at the landmark and incremented at each hop. Each node that receives the beacon records the shortest dis-tance,in hops,from itself to the corresponding landmark.If multiple beacons from the same landmark are received via different routes,the lowest count is recorded.When mul-tiple landmarks are chosen,every node in the sensor net-work is expected to receive beacons from all landmarks. Each node consequently records the hop counts between it-

self and each of the landmarks.We call the vector formed by these hop numbers the logical coordinate vector .The di-mensionality of this vector corresponds to the number of landmarks.For example,if we choose four landmarks,we build a four-dimensional logical coordinate space.To pre-serve a consistent order of elements in all logical coordinate vectors,these vectors can be sorted,for example,by unique landmark identity,statically assigned at compile time and carried along in the aforementioned beacons.

After each node records its own logical coordinate vec-tor,the initial establishment of the logical coordinate space is complete.An example of a logical space with four land-marks (denoted by ?lled black circles)is shown in Figure 1.In this example,24nodes are deployed.Since four land-marks are chosen,the logical coordinate space is four di-mensional.The four landmarks have coordinates (0,5,3,8),(5,0,8,3),(8,3,5,0)and (3,8,0,5),respectively.Note that we have transformed the target space from a physical plane to four (partially redundant)logical dimensions.Further,the coordinates of landmarks have the distinctive trait that they have one zero element in exactly one dimension;namely,the dimension corresponding to the local landmark.Other nodes have non-zero (positive)coordinates in all dimen-sions.

Node Deployment Example Landmark

Common Node

Figure 1.Logical Coordinates Construction Example

2.3.Space Maintenance

The formation of the logical coordinates must be re-silient with respect to two kinds of inconsistencies.First,beacon message loss that results in missing coordinates.We call this problem null coordinates .In the neighbor beacon exchange,a node that ?nds out that it has null coordinates compared with its neighbors tries to correct each null coor-

dinate by incrementing the lowest of the corresponding co-ordinates of its neighbors by one (hop)to update its own co-ordinate vector.

The second type of inconsistency is where neighboring nodes differ by more than one in some coordinate.This should never occur in an ideal world because neighbors are only one hop away.However,it could be observed in the presence of message loss.In the neighbor beacon ex-change stage,if a node ?nds out that one of its neighbors has a coordinate value that differs by more than one com-pared with its own (for the same landmark),then the node with the higher-valued coordinate locally decrements it to remove the inconsistency.If a logical coordinate is updated on some node,it will beacon this update to refresh its neigh-bors.Although this refreshing has the potential to be prop-agated,in practice,we ?nd that the scope of updates in the neighbor exchange stage is highly limited,and the update process converges very fast.

2.4.Properties and Concepts

Now we present useful concepts of the logical coordi-nate framework,which are the fundamentals of the design of our new protocol.

2.4.1.The Neighborhood Property The most ba-sic property maintained by the logical coordinate space as described above is the following:

Property 1.In a correct logical coordinate space,the cor-responding coordinates for the same landmark between any two nodes which are mutual neighbors differ by at most 1.Proof.This property follows directly from the neighbor-hood maintenance protocol discussed above.

2.4.2.Bounded Hop Count From the perspective of soft real-time applications,a very useful property of the proto-col is that the hop count along the actual routing path be-tween a source and a destination can be estimated solely from the logical coordinates of the source and destination,as follows.

Property 2.For any two nodes V (V 1,...,V n )and W (W 1,...,W n ),the hop count of the shortest path between them is lower-bounded by MAX (|V 1?W 1|,...,|V n ?W n |)and upper-bounded by i |V i ?W i |.

Proof.This follows directly from Property 1,since for any single hop,the coordinate in each dimension can change by at most one.

In practice we found that the lower bound is especially useful.The actual hop count was usually found to be ex-actly the lower bound.Hence,this optimistic bound can be used to estimate delay in soft real-time load balanced sensor networks where deadline misses can be tolerated.For those

cases that are higher than the lower bound,the marginal off-set in the hop count is usually low enough compared with the overall hop number.We will validate this claim thor-oughly in the experiments.

2.4.

3.The Distance Concept We use vector distance,de-?ned below,as the logical distance between nodes.Thus, for logical coordinate vectors V and W with coordinate ele-ments V i and W i,respectively,the distance D between them is de?ned as:

D=

n

i=1

(V i?W i)2(1)

As shown,we use the length of the difference vector (V1?W1,V2?W2,...,V n?W n)as the distance metric be-tween nodes.Observe that the length computed above has no physical geometric interpretation,since the logical di-mensions are not orthogonal.However,compared to phys-ical distance,this metric re?ects more accurately the topo-logical distance between two nodes in the sensor network graph.If two nodes are connected by fewer hops,the logi-cal distance between them tends to be smaller.

3.The Logical Coordinate Routing Protocol

In the previous section,we outlined the logical coor-dinate framework and its properties.We now apply these properties to the design of the LCR protocol.

3.1.Basic Protocol Design

In our routing protocol,the node with the least logi-cal distance to the destination is chosen as the next relay. Since each node knows the logical coordinates of its neigh-bors,this comparison can be done locally.In most cases, greedy forwarding alone guarantees a high ratio of success-ful packet delivery.We refer to this scheme as the baseline design.We further augment the LCR protocol with tech-niques for loop avoidance and(logical)void avoidance,de-scribed in the following two subsections respectively,in or-der to address these less common routing anomalies.

3.2.Loop Avoidance

One possible cause of delivery failure in LCR is the pres-ence of multiple nodes that have the same distance to the destination.This may lead to unexpected loops.This situa-tion rarely arises in location-based routing since two nodes rarely share exactly the same distance to a destination.How-ever,the presence of same distance nodes is more common in logical coordinates due to the coarser granularity of co-ordinate values.Figure2a shows an example.As shown, although each node chooses the best node it knows in its neighbor table,a packet is forwarded back to its starting point(node9).One intuitive solution is to record all nodes that the packet has visited in the packet header.However, the packet sizes in sensor networks are usually only tens of bytes,implying it is infeasible to record all nodes the packet has been routed to.We solve this problem by making a tradeoff,recording only a?nite moving history of the de-livery path in the packet.The length of moving history rep-resents a tradeoff between the memory capacity needed for better loop avoidance and the corresponding control over-head.

One loop avoidance example is shown in Figure2b.Ob-serve that for purposes of loop avoidance,nodes in the recorded history can be identi?ed by short internal identi-?ers(chosen at compile time)known only to themselves and their neighbors,as opposed to their full-length logical

coordinates.

Message Start

Destination

Node 20(7,2,2)

Distance 29

Node 16(5,3,5)

Distance 14

Node 15(4,4,6)

Distance 34

Node 8(3,5,4)

Distance 29

Node 6(3,4,5)

Distance 29

Part a

Message Start

Destination

Node 20(7,2,2)

Distance 29

Node 8(3,5,4)

Figure2.Loop Avoidance using Moving His-

tory Recording

Due to the limited size of the moving history record and the large number of nodes in a sensor network,it is still pos-sible that loops may exist.For this purposes,a time-to-live ?eld is added to the packet header,such that packets are dropped when this?eld reaches a threshold.

3.3.Void Avoidance

Another related problem is that some nodes may have no neighbor that is logically closer to the destination,such as node6in the aforementioned example.Clearly this implies that the packet has met a logical void.Our logical coordi-nate framework,by construction,is much less susceptible to such dead-ends than geographic coordinates.This is be-cause our logical space morphs around physical voids,elim-inating local minima.Nevertheless,situations exist when a local minimum arises in the logical space(for example upon

node failures).When one node?nds that it has no neigh-bor that is closer to the destination than itself,it will choose the best upstream node(i.e.,the closest neighbor to the des-tination).The purpose of this action is to try to deliver the packet to a new node where a new downstream path might exist to the destination.In order to bound upstream forward-ing,we use a parameter called tolerance counter stored in the packet header.Initialized to zero at the start node,this parameter increases by one whenever the packet is deliv-ered to an upstream node.The packet is dropped if this counter exceeds a prede?ned threshold,MaxT olerance. Observe that since we also keep a moving path history in the packet,the memory of the last few hops helps the packet avoid being delivered back to the local minimum.Also note that the void avoidance mechanism can increase worst-case hop count between source and destination(stated by the bounded hop-count property in Section2.4.2)by at most MaxT olerance.

Of course,the void avoidance approach is,by nature, heuristic,and does not guarantee packet delivery.However, our simulation results validate its effectiveness compared with other routing algorithms.

3.4.Dynamic Issues:Node Failure,Sleep,and Re-

placement

The main source of dynamic changes in topology is the failure or replacement of old nodes,or topological changes introduced by power management.When new nodes are put into the network,they contact nearby neighbors to retrieve their logical coordinate vectors.The new nodes then con-struct their own LCVs in the same manner as described in Section2.3,and use the constructed LCVs for future routing purposes.Observe that in most power management schemes such new nodes are generally awakened to replace those that go to sleep,leveraging redundancy that exists in the sensor network[5,24].The new nodes will tend to assume the same logical coordinates as those of the departed ones due to physical proximity.Thus,only localized adjustments need to be made in the logical coordinate grid.

Similarly,when nodes fail,generally other nodes do not need to adjust their logical coordinates.The inherent redun-dancy in the construction of logical coordinates makes them tolerant to a certain percentage of node failures.Greedy al-gorithms will generally remain successful in?nding a logi-cal route to the destination.If local minima are reached,the void avoidance mechanism introduced in Section3.3will resolve the problem.

4.Performance Evaluation

In this section,we present the performance evaluation re-sults of LCR.We start by presenting the simulation setup,followed by a description of the experiments and results. The simulation environment is GloMoSim,a discrete event simulator developed by UCLA.GloMoSim simulates at the packet level,thus allowing us to gather accurate data on a variety of aspects.

The simulation setting is constructed with respect to the settings used in previous similar routing research projects, such as[2]and[14].There are three settings,each contains a sparse scenario and a dense scenario,denoted by A and B, respectively.

In the following simulations,we choose DSR,GF and GPSR as comparison candidates.We don’t compare against DSDV and AODV considering that the work in[2]has demonstrated the performance superiority of DSR com-pared to these two protocols in ad-hoc environment.We also include a delivery performance comparison between LCR and the virtual coordinate approach proposed by[21] in Section4.2.1.

Scenario Sparse(A)Dense(B)Region

Scenario130501500m?300m

Scenario21202003000m?600m

Scenario3721201250m?1250m

Table1.Simulation Setting

We use a reliable MAC protocol in order to isolate de-livery failures due to the routing layer from those due to the MAC layer.A reliable MAC-layer is currently available for MICA II motes[22](our target implementation platform) since the recent release of TinyOS1.1[10].The evaluation is focused on comparing the ability of routing protocols to exploit topological connectivity information.Performance is measured in data packet delivery ratio,path hop counts, and number of routing protocol packet transmissions.These metrics tend to be independent of MAC layer details(other than reliability).Thus,while we choose802.11in the MAC layer,results presented in this section could be generalized to any reliable MAC protocol.We assume that individual nodes have a communication range of250m.Each packet sent in the network has a TTL of64.

Our evaluation contains two parts.The?rst part explores optimal parameter settings of our protocol and justi?es de-sign decisions.In the second part,we evaluate the routing protocol performance.

4.1.Evaluation of Design Choices

Different design choices in LCR can signi?cantly in?u-ence its performance.In this section,we give a quantita-tive evaluation of their effects.The evaluation below is for

an underloaded network.Effects of congestion are investi-

gated in future work.

4.1.1.The Impact of Distance Metrics As mentioned

earlier,our distance metric does not have a physical in-

terpretation because the coordinates are not orthogonal.

Hence,it is important to evaluate its performance.In this section,we compare the packet delivery ratio of routing

based on this distance metric compared to that based on

other distance metric candidates.In particular,we compare against the common metric of manhattan distance,which

simply adds up the absolute differences in coordinate val-ues in all dimensions.

Four landmarks are positioned on the boundary of the

area.Zero tolerance for upstream packets is assumed(i.e. MaxT olerance=0).No loop-avoidance measures are adopted.We select all pairs of nodes that can reach each

other and let them send one packet to each other.The packet delivery ratio is plotted for two greedy routing policies:one that minimizes the difference vector length(DV Length)as described in this paper,and one that minimizes manhattan distance.All scenarios tested are dense(set A)scenarios.

Figure3.Impact of Distance De?nition

Figure3shows the simulation results.We observe that the difference vector length approach performs signi?cantly better than the manhattan distance approach.We also notice that LCR successfully delivers almost all packets even with-out the tolerance and loop-avoidance optimizations in dense scenarios,which re?ects the inherent delivery properties of the logical coordinates framework.

4.1.2.The Impact of Landmark Choice Another impor-tant aspect of the design of LCR is how to choose the land-marks wisely.In this experiment,we investigate the effect of landmark placement and the effect of the number of land-marks on routing performance.The simulation shows six different landmark con?gurations that differ in landmark positions and count as depicted in Figure4.Random land-mark placement(labeled random)is compared to uniform placement at the network circumference(labeled corner for different numbers of landmarks and different node densi-ties.Again,we assume zero MaxT olerance.Considering that packets must contain the destination’s logical coordi-nates,and that the size of the packet header is limited,we cannot choose too many landmarks.Fortunately,we notice that performance improvement reaches diminishing returns with as few as four landmarks.At this point,the routing ser-vice?nds almost all routes available.Considering that,in these experiments,we do not use tolerance and loop avoid-ance measures,these results are quite encouraging and serve as a lower bound for actual performance when such mea-sures are invoked.

Figure4.Impact of Landmark Choice

4.2.Routing Protocol Performance Evaluation 4.2.1.Packet Delivery Ratio Figure5shows the packet delivery ratio under different scenario settings.We ensure that the network is not partitioned.Traf?c is generated by the simpli?ed scenario in which each pair of nodes alter-nately exchange packets over the whole simulation period. We deliberately choose the period to be long enough to avoid the effect of congestion.Precise location information is assumed to be available for GPSR and greedy GF.The delivery success ratio is evaluated by recording how many packets each node receives during the whole period.It is no surprise that under such assumptions,DSR achieves a 100%delivery ratio in all settings.We don’t draw the DSR line for legibility.Theoretically,GPSR should also achieve a100%delivery ratio.In reality,its actual performance is slightly lower because the TTL of a single packet is set to64.In some cases,GPSR packets start their traversing process,resulting in much longer(suboptimal)paths caus-ing the TTL to expire.Some packets are therefore dropped. LCR performs comparably well to GPSR and signi?cantly better than greedy GF.This performance is measured when no localization error exists.

https://www.wendangku.net/doc/d19458038.html,parison of Delivery Ratio Previous work,such as[11],has demonstrated that greedy GF suffers a substantial performance degrada-tion when the localization service can not provide accurate location information.We show in Figure6that a simi-lar degradation is seen with GPSR.As shown in this graph, the performance of GPSR is severely affected when the lo-calization error exceeds40%of the individual node com-munication radius.In fact,even when nodes are dense, if the localization error is as large as the communica-tion range,the performance of GPSR is still severely under-mined.On the other hand,the performance of LCR is not affected by localization errors,thus making it more prefer-able in scenarios where accurate location information is not available.

Figure6.Delivery Ratio of GPSR Under Loca-

tion Error

Recent previous work also proposed similar network co-ordinate encoding services that do not require geographical location.It is thus very interesting to provide direct compar-ison between LCR and the previously proposed services. In this paper,we compare LCR to the virtual coordinates approach mentioned in[21].To provide a precise and fair comparison,we use their scenario setting.We also use the published results in[21]regarding geographical locations and virtual coordinates.The setting contains two different densities,one node per12.5square units and one node per 19.5square units,respectively.There are four network size settings,from50to3200nodes.The nodes are uniformly deployed.Figure7shows the comparison results between LCR and the virtual coordinate approach.In LCR,we do not use loop avoidance and void avoidance measures,since it is conceivable that both of these optimizations can be ap-plied to either routing framework.By doing this,we pro-vide a fair comparison of the inherent packet delivery prop-erties of both network coordinate encoding

schemes.

https://www.wendangku.net/doc/d19458038.html,parison of Logical Coordinate

Routing Schemes

As shown in Figure7,when the density is high,there is little performance difference between the three types of greedy routing approaches.On the other hand,when the density is low,we observe a considerable advantage to LCR.

4.2.2.Routing Path Length Figure8shows a compari-son of the packet delivery path length distribution of three routing protocols,DSR,LCR and GPSR(with different lo-calization errors expressed as a percentage of the commu-nication radius).The data presented are concerned with the distribution of the number of hops beyond the shortest hop count.For example,1means that the route found by the pro-tocol in question is one hop longer than the best route.We use scenario1with50nodes deployed.The data are the re-sults of ten randomized simulation rounds.For GPSR,we also consider the presence of localization errors and the cor-responding results are plotted accordingly.Only those pack-ets that are successfully delivered are included in the analy-sis.

When no localization error exists,GPSR performs the best.However,when the localization error is40%of the

Figure8.Packet Path Length Beyond the Best

Route

communication range,the performance of GPSR is de-graded and it becomes inferior to LCR.

DSR and LCR are both localization-error free,but the performance of DSR in terms of packet length is degraded by its proactive caching schemes,which causes packets to be aggressively sent along sub-optimal routes.As a result, it has a longer packet path than both LCR and GPSR.

Packet path optimality is closely related to power con-sumption.In sensor networks,one of the main sources of power consumption is the transmission of packets.As a re-sult,Figure8indirectly indicates the power-ef?ciency of a particular routing scheme.If no localization errors exist, GPSR should be the most energy-ef?cient.However,when localization error is taken into account,LCR is better.We recognize that MAC-layer effects,such as message retrans-missions,have a marked in?uence on power consumption. However,we do not investigate these effects because they are MAC-speci?c and are not an inherent property of our protocol.

4.2.3.Path Hop Prediction and Real Time Applications We now study the accuracy of hop prediction promised by Property2.An estimate of path length is particularly use-ful for soft real time applications.We show that prediction according to the lower bound computed from the logical co-ordinates of the source and the destination is particularly ac-curate in practice.

We simulate six scenarios each for?fty rounds with dif-ferent deployments.For each pair of nodes,the prediction and the actual hop number are compared.Figure9shows the distribution of the correct prediction ratio(i.e.,what fraction of the time the lower bound is equal to the actual path length).As shown,under all six situations,the lower bound prediction is correct at least70%of the time.Fur-thermore,for nearly all cases where prediction is wrong, the actual path length is only one hop longer than the lower bound.Observe that the lower bound is trivially correct if the source or destination is one of the landmarks since one of the coordinates would then explicitly measure the hop distance to that landmark.

Figure9.The Prediction of Hop Count

4.2.4.Routing Protocol Overhead Figure10shows a comparison of the routing protocol overhead of three rout-ing protocols,measured by the number of protocol pack-ets sent during the total simulation period.We still use sce-nario1with50nodes deployed.We gradually increase the number of data sources to monitor the protocol overhead. The packet transmissions are initiated from different nodes. We only test non-partitioned network scenarios and assume each node sends only one packet.DSR is a reactive rout-ing protocol,which means its protocol traf?c increases with the number of transmissions.We also notice that due the ag-gressive caching,the increase in transmitted packets has a diminishing effect on the increase of routing overhead.

Both LCR and GPSR send out beacons periodically with no respect to the number of data transmissions.Conse-quently,both LCR and GPSR send out roughly a constant number of protocol control packets.LCR utilizes a one-time?ooding process to broadcast the location beaconing packets.As a result,LCR requires a higher routing proto-col overhead than GPSR.

4.2.

5.Void Avoidance We evaluate in this section the per-formance of different routing protocols in the presence of void areas.We also generalize the results to the discussion of the robustness of LCR,especially in the face of node failures.We simulate the presence of voids and the failure of nodes by reducing active node density,since both voids and node failures essentially decrease the number of usable nodes.We use scenario3in this experiment.We reduce the average number of neighbors per node from twenty to six in steps of one and we keep the network unpartitioned.In order to make comparisons between different routing pro-tocols under realistic scenarios,we also include the perfor-

DSR LCR GF GPSR Principle ID Based Logical Coordinates Location Based Location Based Protocol Overhead Large Small Small Small Delivery Ratio Theoretically Perfect High Moderate-High Theoretically Perfect Route Optimality Good Better Best when not degraded Best when not degraded Degradation No No Yes Yes

V oid Avoidance Excellent Excellent Moderate Excellent

Table2.Routing Protocol Performance Overview

Figure10.Routing Protocol Overhead mance of GPSR under localization errors.The results of this experiment are shown in Figure11.

Figure11.Delivery Ratio under Different

Node Density

In these experiments,DSR realizes a100%delivery ra-tio,and thus is not plotted.We set the TTL of individ-ual packets to64.For this reason,some GPSR packets are dropped due to the suboptimal perimeter traversing process. Greedy GF has no mechanism for dealing with voids.Its performance therefore degrades rapidly.The performance of GPSR under localization errors also degrades consider-ably at higher errors.In contrast,LCR reliably delivers the great majority of packets even in the presence of voids in sparser networks.

4.2.6.Performance Evaluation Summary Based on the experimental results above,we conclude that every proto-col has its desirable features.Although DSR and GPSR are two schemes that both theoretically guarantee a100%de-livery ratio,they have drawbacks in sensor networks.The route discovery process makes DSR less suitable in terms of packet overhead,while GPSR can be severely degraded by localization inaccuracy.The design of LCR avoids these problems.Like DSR,it is not affected by localization errors thus guaranteeing a better delivery ratio than greedy GF and degraded GPSR.Its protocol overhead,however,is low and it exhibits exceptional ability to avoid voids in the network. Table2summarizes the different characteristics of the rout-ing protocols studied in this paper and serves as a guide for future protocol design in wireless sensor networks.

5.Related Work

Previous literature on ad hoc routing contains many valu-able protocols,each with varying assumptions and applica-bility.Two trends of address-based routing draw our atten-tion.The?rst type makes routing choices based on real ge-ographical locations[9,1,14,19,6,8].The second type, proposed relatively recently,tries to explore the possibility of routing without geographical information,but with cer-tain types of substitutes through various network encoding approaches[21,17].For geographic routing,one potential problem is the performance degradation introduced by loca-tion inaccuracy.Since it is usually not economical to install one GPS receiver on each node,localization services must be leveraged[23,3,18,16,11].However,these services in-troduce location inaccuracy,which is known to have seri-ous consequences on the performance of routing protocols (Section4.2.1).Although such inaccuracies might be alle-viated by introducing more complex localization services, the additional complexity either requires more costly hard-ware or introduces more overhead in the network.

It is therefore natural to search for location free routing paradigms for sensor networks that preserve the simplicity

and ef?ciency of location-based schemes.Protocols in[21] and[17]are of this type.

A preliminary comparison of delivery ratio between LCR and[21]has shown that LCR has a higher deliv-ery ratio,especially in sparse scenarios.We also point out that our protocol requires only a one hop neighbor ta-ble to achieve satisfactory performance,while both[21] and[17]require that at least two hop neighbor informa-tion is https://www.wendangku.net/doc/d19458038.html,st but not least,our protocol distin-guishes itself by its inherent suitability for soft real-time ap-plications.We hope by leveraging these properties of LCR, it becomes more natural to use in emerging sensor net-works.

6.Conclusions and Future Work

In this paper,we presented a simple logical coor-dinate framework,together with a scalable(i.e.,con-stant state)routing protocol,LCR,that uses logical co-ordinates in lieu of geographic information.Being location-independent,LCR has the distinct advantage of in-dependence from localization errors.It is attractive for soft real time applications in that bounds on the hop count be-tween any pair of nodes can be estimated from the source and destination coordinates.Moreover,its logical dis-tance metrics have the potential of masking the existence of physical voids and irregularities.We performed ex-tensive simulation experiments to compare LCR with other logical coordinate frameworks,observing a per-formance advantage in the treatment of voids.Based on these results,we conclude that our protocol per-forms very well in realistic wireless sensor networks where voids abound,accurate localization is unavail-able or costly,and state must be minimal due to resource constraints.

References

[1]P.Bose,P.Morin,I.Stojmenovic,and J.Urrutia.Routing

with guaranteed delivery in ad hoc wireless networks.Wire-less Networks,7(6):609–616,2001.

[2]J.Broch, D. A.Maltz, D. B.Johnson,Y.-C.Hu,and

J.Jetcheva.A performance comparison of multi-hop wire-less ad hoc network routing protocols.In Proceedings of Mo-biCom,1998.

[3]N.Bulusu,J.Heidemann,and D.Estrin.Gps-less low cost

outdoor localization for very small devices,2000.

[4] A.Carzaniga,D.Rosenblum,and A.Wolf.Content-based

addressing and routing:A general model and its application, 2000.

[5] A.Cerpa and D.Estrin.Ascent:Adaptive self-con?guring

sensor networks topologies.In Proceedings of the IEEE In-focom,2002.

[6]S.B.et al.A distance routing effect algorithm for mobility

(dream).In Proceedings of MobiCom,1998.

[7]T.A.et al.Envirotrack:Towards an environmental com-

puting paradigm for distributed sensor networks.In In-ternational Conference on Distributed Computing Systems (ICDCS),2004.

[8] A.Z.Fabian Kuhn,Roger Wattenhofer.Worst-case optimal

and average-case ef?cient geometric ad-hoc routing.In Pro-ceedings of MobiHoc,2003.

[9]G.Finn.Routing and addressing problems in large

metropolitan-scale internetworks.In Technical Report,vol-ume ISI/https://www.wendangku.net/doc/d19458038.html,C/ISI,March1987.

[10]W.for TinyOS.https://www.wendangku.net/doc/d19458038.html,/tos/.

[11]T.He,C.Huang,B.Blum,J.Stankovic,and T.Abdelza-

her.Range-free localization schemes in large scale sensor networks.In Proceedings of MobiCom,2003.

[12]Q.Huang,C.Lu,and G.-C.Roman.Spatiotemporal multi-

cast in sensor networks.In First ACM Conference on Em-bedded Networked Sensor Systems(SenSys’03),2003. [13] D.B.Johnson and D.A.Maltz.Dynamic source routing

in ad hoc wireless networks.In Mobile Computing,volume 353.Kluwer Academic Publishers,1996.

[14] B.Karp and H.T.Kung.GPSR:greedy perimeter stateless

routing for wireless networks.In Proceedings of Mobicom, 2000.

[15]Y.-B.Ko and N.H.Vaidya.Location-aided routing(lar)in

mobile ad hoc networks.In Proceedings of MobiCom,Octo-ber1998.

[16]https://www.wendangku.net/doc/d19458038.html,anizing a global coordinate system from local

information on an amorphous computer.In A.I.Memo1666, MIT https://www.wendangku.net/doc/d19458038.html,boratory,1999.

[17]J.Newsome and D.Song.Gem:Graph embedding for rout-

ing and datacentric storage in sensor networks without ge-ographic information.In Proceedings of the SenSys2003, 2003.

[18] D.Niculescu and B.Nath.Dv based positioning in ad hoc

networks.In Journal of Telecommunication Systems,2003.

[19] D.Niculescu and B.Nath.Trajectory based forwarding and

its applications.In Proceedings of Mobicom,2003.

[20] C.Perkins and E.M.Royer.Ad-hoc on demand distance vec-

tor routing.In WMCSA’99,February1999.

[21] A.Rao,C.Papadimitriou,S.Shenker,and I.Stoica.Geo-

graphic routing without location information.In Proceed-ings of Mobicom,2003.

[22]T.M.sensor node data speci?cations.

https://www.wendangku.net/doc/d19458038.html,/products.

[23]Y.Shang,W.Ruml,Y.Zhang,and M.P.J.Fromherz.Local-

ization from mere connectivity.In Proceedings of Mobihoc, pages201–212.ACM Press,2003.

[24]T.Yan,T.He,and J.A.Stankovic.Differentiated surveil-

lance for sensor networks.In Proceedings of ACM SenSys, 2003.

[25]H.Zhou and S.Singh.Content based multicast(cbm)in

ad hoc networks.In Proceedings of MobiHoc,pages51–60, 2000.

操作系统实验五虚拟存储器管理

操作系统实验 实验五虚拟存储器管理 学号1115102015 姓名方茹 班级11 电子A 华侨大学电子工程系

实验五虚拟存储器管理 实验目的 1、理解虚拟存储器概念。 2、掌握分页式存储管理地址转换盒缺页中断。 实验内容与基本要求 1、模拟分页式存储管理中硬件的地址转换和产生缺页中断。 分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说 明哪些页已在主存，哪些页尚未装入主存。作业执行 时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转 换机构按页号查页表，若该页对应标志为“ 1”，则表示该页 已在主存，这时根据关系式“绝对地址 =块号×块长 +单元号”计算出欲访问的主 存单元地址。如果块长为 2 的幂次，则可把块号作为高地址部分，把单元号作为低 地址部分，两者拼接而成绝对地址。若访问的页对 应标志为“ 0”，则表示该页不在主存，这时硬件发“缺页中断”信号， 有操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后 再重新执行这条指令。设计一个“地址转换”程序来模拟硬件的地址转 换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执 行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主 存时，则输出“ * 该页页号”，表示产生了一次缺页中断。 2、用先进先出页面调度算法处理缺页中断。 FIFO 页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时， 把开始的 m 个页面装入主存，则数组的元素可定为m 个。 实验报告内容 1、分页式存储管理和先进先出页面调度算法原理。 分页式存储管理的基本思想是把内存空间分成大小相等、位置固定

计算机组成原理模拟习题库 (16)

《计算机组成原理》模拟试卷十六 一.填空题（每空1分，共20分） 1.计算机系统是一个由硬件、软件组成的多级层次结构。它通常由 A.______、 B.______、 C.______、汇编语言级、高级语言级组成。每一级上都能进行 D.______。 2.为了运算器的高速性，采用了A.______进位、B.______乘除法、C.______等并行 技术措施。 3.奔腾CPU中，L2级cache的内容是A.______的子集，而B.______的内容又是 C.______的子集。 4.RISC指令系统的最大特点是 A.______、B.______固定、C.______种类少、只有 D.______指令访问存储器。 5.当代流行的标准总线追求与A.______、B.______、C.______无关的开发标准。 6.SCSI是处于A.______和B.______之间的并行I/O接口，可允许连接C.______台不 同类型的高速外围设备。 二. 选择题（每题1分，共20分） 1.邮局把信件进行自动分拣，使用的计算机技术是______。 A. 机器翻译 B. 自然语言理解 C. 机器证明 D. 模式识别 2.下列数中最大数为______。 A. （101001）2 B. （52）8 C. （13）16 D. （101001）BCD 3.某机字长16位，定点表示，尾数15位，数符1位，则定点法原码整数表示的最大 正数为______ A. （215-1）10 B. -（215-1）10 C. （1-2-15）10 D. -（1-2-15）10 4.算术/逻辑运算单元74181ALU可完成______。 A.16种算术运算和16种逻辑运算功能 B.16种算术运算和8种逻辑运算功能 C.8种算术运算和16种逻辑运算功能 D.8种算术运算和8种逻辑运算功能 5.某计算机字长16位，其存储容量为2MB，若按半字编址，它的寻址范围是______。 A. 8M B. 4M C. 2M D. 1M 6.磁盘存储器的等待时间通常是指______。 A. 磁盘旋转半周所需的时间 B. 磁盘转2/3周所需时间 C. 磁盘转1/3周所需时间 D. 磁盘转一周所需时间 7.下列有关存储器的描述中，不正确的是______。 A.多体交叉存储器主要解决扩充容量问题 B.访问存储器的请求是由CPU发出的 C.cache与主存统一编址，即主存空间的某一部分属于cache D.cache的功能全由硬件实现 8.常用的虚拟存储器系统由______两级存储器组成，其中辅存是大量的磁表面存储

四川大学 操作系统上机实验 实验五 Windows虚拟存储器管理

实验报告 实验名称：Windows虚拟存储器管理 实验时间：2013年5月27日 实验人员：____郑笑凡___（姓名）__1143041243__（学号）____2011____（年级） 实验目的：1、了解Windows 2000/XP的内存管理机制，掌握页式虚拟存储技术。 2、理解内存分配原理，特别是以页面为单位的虚拟内存分配方法。 3、学会使用Windows 2000/XP下内存管理的基本API函数 实验环境：windows xp 实验步骤： 1、下载virtumem.cpp； 2、建立工程，将virtumen.cpp加入； 3、编译工程，观察结果，确信六种状态都出现至少一次，必要时可改程 序，方便观察结果； 4、看懂程序，按要求另写一段小程序； 5、编译，执行，观察结果。 6，总结。 实验陈述： 1、基础知识： pagefile.sys文件的位置在：__安装的系统盘根目录下____________________________________此文件的作用：____实现物理内存的扩展__________________________________________________ 改变此文件大小的方法:右击”我的电脑”,依次选择”属性”—“高级”—“性能选项”— “更改”_______________________________________ 虚拟地址空间中的页面分为：提交页面，保留页面，空闲页面 页面的操作可以分为：保留、提交、回收、释放、加锁 2、编程准备. 页面属性是在结构体MEMORY_BASIC_INFORMATION_的字段AllocationProtect 和字段中Protect体现出来的。 简述VirtualFree,VirtualPtotect,VirtualLock,VirtualUnlock,VirtualQuery的作用：_ VirtualFree：__释放虚存___________________________________________________ VirtualPtotect：_保留虚存_________________________________________________ VirtualLock：___加锁虚存_________________________________________________ VirtualUnlock：_解锁虚存________________________________________________ VirtualQuery：____查询虚存_______________________________________________ 3、编程 1）将virtumem.cpp加入工程，编译，执行。 是否能编译成功？是 请描述运行结果：

OS实验指导四——虚拟存储器管理

OS实验指导四——虚拟存储器管理

————————————————————————————————作者：————————————————————————————————日期： 2

《操作系统》实验指导四 开课实验室：A207、A209 2015/11/23 、2015/11/24 实验类型设计 实验项目（四）虚拟存储器管理实验 实验学时 4 一、实验目的 设计一个请求页式存储管理方案，并编写模拟程序实现。 二、设备与环境 1. 硬件设备：PC机一台 2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发 环境，如C \C++\Java 等编程语言环境。 三、实验要求 1) 上机前认真复习页面置换算法，熟悉FIFO算法和LRU页面分配和置换算法的过程； 2) 上机时独立编程、调试程序； 3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行 结果截图）。 四、实验内容 1、问题描述： 设计程序模拟FIFO和LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，并计算每种算法缺页次数和缺页率。 2、程序具体要求如下： 编写程序用来模拟虚拟页式存储管理中的页面置换 要求： 1)快表页面固定为4块 2)从键盘输入N个页面号 3)输出每次物理块中的页面号和缺页次数，缺页率 4)实现算法选择

3、程序流程图 3、源程序参考： （1）FIFO 算法部分 #include "stdio.h" #define n 12 #define m 4 void main() { int ym[n],i,j,q,mem[m]={0},table[m][n]; char flag,f[n]; printf("请输入页面访问序列\n "); for(i =0;i

习题--存储系统

第3章存储系统 一．判断题 1．计算机的主存是由RAM和ROM两种半导体存储器组成的。 2．CPU可以直接访问主存，而不能直接访问辅存。 3．外（辅）存比主存的存储容量大、存取速度快。 4．动态RAM和静态RAM都是易失性半导体存储器。 5．Cache的功能全部由硬件实现。 6．引入虚拟存储器的目的是为了加快辅存的存取速度。 7．多体交叉存储器主要是为了解决扩充容量的问题。 8．Cache和虚拟存储器的存储管理策略都利用了程序的局部性原理。 9．多级存储体系由Cache、主存和辅存构成。 10．在虚拟存储器中，当程序正在执行时，由编译器完成地址映射。 二．选择题 1．主（内）存用来存放。 A．程序 B．数据 C．微程序 D．程序和数据 2．下列存储器中，速度最慢的是。 A．半导体存储器 B．光盘存储器 C．磁带存储器 D．硬盘存储器 3．某一SRAM芯片，容量为16K×1位，则其地址线有。 A．14根 B．16K根 C．16根 D．32根 4．下列部件（设备）中，存取速度最快的是。 A．光盘存储器 B．CPU的寄存器 C．软盘存储器 D．硬盘存储器 5．在主存和CPU之间增加Cache的目的是。 A．扩大主存的容量 B．增加CPU中通用寄存器的数量 C．解决CPU和主存之间的速度匹配 D．代替CPU中的寄存器工作 6．计算机的存储器采用分级存储体系的目的是。 A．便于读写数据 B．减小机箱的体积 C．便于系统升级 D．解决存储容量、价格与存取速度间的矛盾 7．相联存储器是按进行寻址的存储器。 A．地址指定方式 B．堆栈存取方式 C．内容指定方式 D．地址指定与堆栈存取方式结合 8．某SRAM芯片，其容量为1K×8位，加上电源端和接地端后，该芯片的引出线的最少数目应为。 A．23 B．25 C．50 D．20 9．常用的虚拟存储器由两级存储器组成，其中辅存是大容量的磁表面存储器。 A．主存—辅存 B．快存—主存 C．快存—辅存 D．通用寄存器—主存 10．在Cache的地址映射中，若主存中的任意一块均可映射到Cache内的任意一快的位置上，则这种方法称为。 A．全相联映射 B．直接映射 C．组相联映射 D．混合映射 三．填空题

操作系统作业(虚拟存储器与磁盘缓存)

操作系统作业操作系统——虚拟存储器与磁盘缓存1 1.问题描述 虚拟存储器技术牺牲了内存访问速度，换取了可用内存容量的增加；磁盘高速缓存以内存容量的牺牲换取了I/O性能的提升。一个以时间换空间，一个以空间换时间，这两种看似矛盾的技术为什么可以并存？ 2.解答 在操作系统中，各种存储器管理方式都有一个共同点，就是他们都要求将一个作业全部装入内存后方能运行，所以就会出现有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部装入内存，致使该作业无法运行或者出现有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数的作业装入内存让他们先运行，而将其他大量的作业留在外存上等待，而这种情况的原因都是由于内存容量不够大，所以要增加内存容量，要是从物理上增加内存容量，成本太大。而虚拟内存则是在逻辑上扩充了内存容量. 在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。 虚拟内存在计算机中的作用很大，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。这样,在有效缓解了内存紧张的同时,也控制了成本. 而在文件系统中，对文件的访问速度至关重要，为了提高对文件的访问速度，可以提高磁盘的I/O的速度，能够将文件中的数据快速地从磁盘传送到内存中，或者相反。但是目前，磁盘的I/O的速度远低于内存的访问速度，所以采用磁盘高速缓存技术硬盘上集成了高速缓存的芯片（内存），来提高硬盘的运行速度。 磁盘高速缓存是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘

虚拟存储器管理 页面置换算法模拟实验

淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级：软件*** 学号：20**1228** 姓名：****

一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实 页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页 的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号， 取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定

存储管理实验报告

实验三、存储管理 一、实验目的： ? 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。 在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验理解在分页式存储管理中怎样实现虚拟存储器。 在本实验中，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 二、实验题目： 设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 对分区的管理法可以是下面三种算法之一：（任选一种算法实现） 首次适应算法 循环首次适应算法 最佳适应算法 三．实验源程序文件名:cunchuguanli.c

执行文件名:cunchuguanli.exe 四、实验分析： 1)本实验采用可变分区管理，使用首次适应算法实现主存的分配和回收 1、可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并 且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 为了说明那些分区是空闲的，可以用来装入新作业，必须有一张空闲说明表 ? 空闲区说明表格式如下：? 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址，长度指出空闲区的大小。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业完成后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。 2、当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。 有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分

存储器 练习题答案

一、选择题 1、存储器和CPU之间增加Cache的目的是( )。 A. 增加内存容量 B. 提高内存的可靠性 C. 解决CPU与内存之间速度问题 D.增加内存容量，同时加快存取速度 2、常用的虚拟存储系统由（）两级存储器组成，其中辅存是大容量的磁表面存储器。 A 主存-辅存 B 快存-主存 C 快存-辅存 D 通用寄存器-主存 3、双端口存储器所以能高速进行读/ 写，是因为采用（）。A．高速芯片B．两套相互独立的读写电路 C．流水技术D．新型器件 4、在下列几种存储器中，CPU可直接访问的是（）。 A. 主存储器 B. 磁盘 C. 磁带 D. 光盘 5、SRAM芯片，存储容量为64K×16位，该芯片的地址线和数据线数目为（）。 A．64，16 B．16，16 C．64，8 D．16，64。 6、采用虚拟存储器的主要目的是（）。 A．扩大主存储器的存储空间，并能进行自动管理和调度B．提高主存储器的存取速度 C．提高外存储器的存取速度 D．扩大外存储器的存储空间

7、双端口存储器在（）情况下会发生读/写冲突。 A. 左端口与右端口的地址码不同 B. 左、右端口的地址码相同 C. 左、右端口的数据码相同 D. 左、右端口的数据码不同 8、计算机系统中的存储器系统是指（）。 A RAM存储器 B ROM存储器 C 主存储器D主存储器和外存储器 9、某计算机字长32位，其存储容量为4MB，若按半字编址，它的寻址范围是（）。 A 0~4MB-1 B 0~2MB-1 C 0~2M-1 D 0~1M-1 10、某一SRAM芯片，采用地址线与数据线分离的方式，其容量为512×8位，除电源和接地端外，该芯片引出线的最小数目应是（）。 A 23 B 25 C 50 D 19 11、以下四种类型的半导体存储器中，以传输同样多的字为比较条件，则读出数据传输率最高的是（）。 A DRAM B SRAM C FLASH ROM D EPROM 12、计算机的存储器采用分级存储体系的目的是（）。A．便于读写数据B．减小机箱的体积

南京中医药大学虚拟存储器管理实验

实验三虚拟存储管理 实验性质：验证 建议学时：3 实验目的： 存储管理的主要功能之一是合理的分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换方法。 预习内容： 阅读教材《计算机操作系统》第四章，掌握存储器管理相关概念和原理。 实验内容： （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： ①50%的指令是顺序执行的； ②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分。 具体的实施方法是： ①在[0,319]的指令地址之间随机选取一起点m； ②顺序执行一条指令，即执行地址为m+1的指令； ③在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’； ④顺序执行一条指令，其地址为m’+1； ⑤在后地址[m’+2,319]中随机选取一条指令并执行； ⑥重复上述步骤，直至执行320次指令。 （2）将指令序列变换成页地址流。 设：①页面大小为1K； ②用户内存容量为10块到32块； ③用户虚存容量为32K； 在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条~第9条指令为第0页（对应的虚存地址为[0，9]）； 第10条~第19条指令为第1页（对应的虚存地址为[10，19]）； …… 第310条~第319条指令为第31页（对应的虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。 （3）计算并输出下述各种算法在不同的内存容量下的缺页率。 ①先进先出的算法（FIFO）； ②最近最少使用算法（LRU）； ③最佳淘汰法（OPT）：先淘汰最不常用的页地址； ④最少访问页面算法（LFU）。 缺页率=（页面失效次数）/（页地址流长度）= 缺页中断次数/ 320 在本实验中，页地址流的长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

虚拟存储器管理实验报告

淮海工学院计算机科学系实验报告书 课程名：《操作系统》 题目：虚拟存储器管理 页面置换算法模拟实验 班级： 学号： 姓名：

一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前

计算机操作系统第五章-虚拟存储器分解

第五章虚拟存储器 第一节虚拟存储器的基本概念 一、虚拟存储器的引入 在前面介绍的各种存储管理方式中，用户作业一旦被装入内存，就会一直驻留其中，直到进程运行结束(驻留性)。有些存储管理方式还存在一次性。因此，用户作业要最终运行完毕，系统必须给它提供不短于作业长度的存储空间。于是就出现了两种问题： ?长作业无法运行 ?大量作业无法同时运行 程序运行的局部性原理：在一段时间内一个程序的执行往往呈现出高度的局部性。 前期讨论：P112-113；局部性还表现在两方面： (1) 一条指令被执行，则不久以后该指令很可能再次执行；某个数据被访问，则不久以后该数据附近的数据很可能被访问。产生这类局部性的典型原因，是由于在程序中存在着大量的循环操作。 (2) 程序在一段时间内所访问的地址，可能集中在一定的范围之内。若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元很可能被使用。其典型情况便是程序的顺序执行、数组的处理等。 局部性原理是在存储分配时克服驻留性、实现虚拟存储的依据。 二、虚拟存储器的定义 定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。其访问速度接近于内存，而其容量和每位的成

本却又接近于外存。 特性：虚拟存储器 连续性离散性 一次性多次性 驻留性交换性 虚拟性 对用户而言，它访问特性和内存一样；它以CPU时间和外存空间换取宝贵内存空间，是操作系统中的一种资源转换技术。 容量： ?一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址宽度为32位，则程序可以寻址范围是0～232-1 ，即虚存容量可达4GB。 ?虚拟存储器的容量与主存的实际大小没有直接的关系，而是在主存与辅存的容量之和的范围内。 三、虚拟存储技术 基本原理：P115 把内存与外存有机地结合起来使用，从而得到一个容量很大的“内

第7章虚拟存储器管理

第7章虚拟存储器管理 一、选择 1．虚拟存储器的最大容量是由决定的。 A．内、外存容量之和B．计算机系统的地址结构 C．作业的相对地址空间D．作业的绝对地址空间2．采用先进先出页面淘汰算法的系统中，一进程在内存占3块（开始为空），页面访问序列为1、2、3、4、1、2、5、1、2、3、4、5、6。运行时会产生次缺页中断。 1 2 3 4 1 2 5 1 2 3 4 5 6 1 2 3 4 1 2 5 3 4 6 1 2 3 4 1 2 5 3 4 1 2 3 4 1 2 5 3 1 2 3 4 5 6 7 8 9 10 1 2 3 4 1 2 5 A．7 B．8 C．9 D．10 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．分配给作业的内存块数 二、问答 1．一个虚拟地址结构用24个二进制位表示。其中12个二进制位表示页面尺寸。试问这种虚拟地址空间总共多少页？每页的尺寸是多少？ 解：24-12=12，有212个页。每页有212个字节。 2．什么叫虚拟存储器？怎样确定虚拟存储器的容量？ 3．为什么请求分页式存储管理能够向用户提供虚拟存储器？ 4．试述缺页中断与一般中断的区别。

实验四 虚拟存储器管理实验

实验四虚拟存储器管理实验 ◆实验名称：存储器管理实验 ◆仪器、设备：计算机 ◆参考资料：操作系统实验指导书 ◆实验目的： 设计一个请求页式存储管理方案，并编写模拟程序实现。 ◆实验内容： 编写程序用来模拟虚拟页式存储管理中的页面置换 要求： 1.快表页面固定为4块 2.从键盘输入N个页面号 3.输出每次物理块中的页面号和缺页次数，缺页率 ◆实验原理、数据（程序）记录： #define PAGES 4 /* 物理块数*/ #define N 16 /*最多输入的页面号*/ int pages[PAGES][2]; /*page[i][0]保存页面号，page[i][1]保存页面存留时间*/ int queue[N]; /*页面号数组*/ void initialise(void) /*------------初始化：快表和页面号数组++++++++++++++*/ { int i; for(i=0;i

实验四 虚拟存储器管理

实验四虚拟存储器管理 一、实验目的 1、为了更好的配合《操作系统》有关虚拟存储器管理章节的教学。 2、加深和巩固学生对于请求页式存储管理的了解和掌握。 3、提高学生的上机和编程过程中处理具体问题的能力。 二、实验内容 请求页式存储管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。 1．通过随机数产生一个指令序列，共320条指令。 指令的地址按下述原则生成： a.50%的指令是顺序执行的。 b.25%的指令是均匀分布在前地址部分。 c.25%的指令是均匀分布在后地址部分。 具体的实施方法是： a.在[0,319]指令地址之间随机选取一起点； b.顺序执行一条指令，即执行地址为m+1的指令； c.在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’； d.顺序执行一条指令，其地址为m’； e.在后地址[m’+2，319]中随机选取一条指令并执行； f.重复上述步骤a~e，直到执行320次指令。 2．将指令序列变换成为页地址流 设： a.页面大小为1K； b.用户内存容量为4到32页； c.用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条~第9条指令为第0页，对应虚存地址为[0，9]；

第10条~第19条指令为第1页，对应虚存地址为[10，19] . . 第310条~第319条指令为第31页，对应虚存地址为[310，319]。 按以上方式，用户指令可组成32页。 3、输出下述各种算法在不同内存容量下的命中率。 a.先进先出的算法； b.最近最少访问算法； c.最近最不经常使用算法。 其中：命中率=1-页面失效次数/页地址流长度 页地址流长度为320，页面失效次数为每次访问相同指令时，该指令所对应的页不在内存的次数。 三、实验要求 实验课时4学时。要求画出利用各种算法置换时的置换图，并可以分析说明。编程可分 为几个部分完成：指令的分页，算法的选择，算法的实现，命中率的输出。编写程序前可先 阅读Linux源代码页面换入： static int do_swap_page(struct mm_struct * mm, struct vm_area_struct * vma,unsigned long address, pte_t * page_table,swp_entry_t entry,int write_access) { struct page *page = lookup_swap_cache(entry); pte-t pte; if (!pgae){ lock_kernel( ); swapin_readahead(entry); page = read_swap_cache(entry); unlock_kernel( ); if (!page) return -1;

实验三 虚拟存储器管理

实验三虚拟存储器管理 一、实验目的 为了使大的进程(其地址空间超过主存可用空间)或多个进程的地址空间之和超过实际主存空间时，仍能运行，引入了虚拟存储器的概念。使进程的一部分地址空间在主存，另一部分在辅存，由操作系统实现多级存储器的自动管理，实现主存空间的自动覆盖。模拟请求分页虚拟存储器管理技术中的硬件地址变换、缺页中断以及页式置换算法，处理缺页中断。 通过本实验，使学生对请求分页存储管理的概念有一个清楚的理解。 二、实验内容 1、模拟请求分页存储管理中的硬件地址变换的过程 (1)请求分页虚拟存储器管理技术是把进程地址空间的全部信息存放在磁盘对换区上。当进程被选中运行时，先把进程的开始几页装入主存并启动运行。为此在为进程建立页表时，应说明哪些页已在主存，哪些页不在主存。页表的格式如表1 所示。 在表1中 ①"标志位"表示对应页是否已经装入主存的标志: "0"表示对应页未装入主存;"1"表示对应页已装入主存。 ②"主存块号"表示该页对应的主存块号。 ③"修改位"指示该页进主存后是否修改过的标志。 ④"外存地址"表示该页所在的外存地址。 设计一个主存分块表，假定分配给进程的主存块数为M，且该进程开始的M页已装入主存。 (2)进程执行时，指令中的逻辑地址指出指令或操作数的地址中的页号和页内地址。硬件地址转换机构按页号查页表。 ①若该页的有效位为"1" ，表示该页已在主存，从而找到该页对应的主存块号。根据如下的关系式，计算出欲访问的主存地址: 绝对地址=块号×块的长度+页内地址 由于页的大小为2 的整次幕，所以只要将块号与页内地址相拼接，放入主存地址寄存器，形成绝对地址。不去模拟指令的执行，而是输出被转换的地址即可。 ②若该页的有效位为"0" ，对应的页不在主存，由硬件产生缺页中断，转操作系统处理。这里不去设计缺页处理程序，仅输出"*该页号的页不在主存，产生缺页中断"即可，以表示产生了一次缺页中断。 假定主存的每块长度为128个字节。现有一个具有8页的进程，系统为它分配了4 个主存块(即m=4)。其中第0~3页已经装入主存。该进程的页表如表2 所示，进程执行的指令序列如表3 所示，地址变换算法流程如图1所示。

第五章虚拟存储器附答案

第五章虚拟存储器 一、单项选择题 1.虚拟存储器的最大容量＿＿＿。 *A. 为内外存容量之和 B. 由计算机的地址结构决定（（（实际容量 C. 是任意的 D. 由作业的地址空间决定 虚拟存储器是利用程序的局部性原理，一个作业在运行之前，没有必要全部装入内存，而只 将当前要运行那部分页面或段装入便可以运行，其他部分放在外部存储器内，需要时再从外 存调入内存中运行，首先它的容量必然受到外存容量的限制，其次寻址空间要受到计算机地 址总线宽度限制。最大容量（逻辑容量）收内外存容量之和决定，实际容量受地址结构决定。2．在虚拟存储系统中，若进程在内存中占 3 块（开始时为空），采用先进先出页面淘汰 算法，当执行访问页号序列为 1﹑ 2﹑ 3﹑ 4﹑ 1﹑2﹑ 5﹑ 1﹑ 2﹑ 3﹑4﹑ 5﹑ 6 时，将 产生＿＿＿次缺页中断。（开始为空，内存中无页面， 3 块物理块一开始会发生三次缺页。） A.7 B.8 C.9 3. 实现虚拟存储器的目的是＿＿＿ A. 实现存储保护 B. 实现程序浮动 D. 10 . C. 扩充辅存容 量 D. 扩充主存容量 4.作业在执行中发生了缺页中断, 经操作系统处理后 , 应让其执行＿＿＿指令 . （书本 158 页，（ 2）最后一句话） A. 被中断的前一条 B. 被中断 的 C. 被中断的后一 条 D. 启动时的第一条 5．在请求分页存储管理中，若采用FIFO 页面淘汰算法，则当分配的页面数增加时， 断的次数 ________。( 在最后一题做完后再作答)答案错误选择： D 缺页中 A．减少B. 增 加 C. 无影响 D. 可能增加也可能减少 6.虚拟存储管理系统的基础是程序的________理论 . A. 局部性 B. 全局 性 C. 动态 性 D. 虚拟性 7. 下述 _______页面淘汰算法会产生Belad y 现象 . A. 先进先出* B. 最近最少使 用 C. 最近不经常使 用 D. 最佳 所谓 Belady 现象是指：在分页式虚拟存储器管理中，发生缺页时的置换算法采用 FIFO（先 进先出）算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面 数增多但缺页率反而提高的异常现象。 二. 填空题 1.假设某程序的页面访问序列为1. 2. 3. 4. 5. 2. 3. 1. 2. 3. 4. 5. 1. 2. 3. 4 且开始执行时主 存中 没有页面，则在分配给该程序的物理块数是3 且采用 FIFO 方式时缺页次数是 ____13____; 在分配给程序的物理块数是 4 且采用 FIFO 方式时，缺页次数是 ___14______; 在分配给程序

计算机组成原理期末考试习题及答案

《计算机组成原理》练习题 一、单项选择题 1．CPU响应中断的时间是__C____。 A．中断源提出请求； B．取指周期结束； C．执行周期结束； D．间址周期结束。 2．下列说法中___C___是正确的。 A．加法指令的执行周期一定要访存； B．加法指令的执行周期一定不访存； C．指令的地址码给出存储器地址的加法指令，在执行周期一定访存； D．指令的地址码给出存储器地址的加法指令，在执行周期不一定访存。 3．垂直型微指令的特点是__C____。 A．微指令格式垂直表示； B．控制信号经过编码产生； C．采用微操作码； D．采用微指令码。 4．基址寻址方式中，操作数的有效地址是___A___。 A．基址寄存器内容加上形式地址（位移量）； B．程序计数器内容加上形式地址； C．变址寄存器内容加上形式地址； D．寄存器内容加上形式地址。 5．常用的虚拟存储器寻址系统由___A___两级存储器组成。 A．主存－辅存；B．Cache－主存； C．Cache－辅存；D．主存—硬盘。 6．DMA访问主存时，让CPU处于等待状态，等DMA的一批数据访问结束后，CPU再恢复工作，这种情况称作___A___。 A．停止CPU访问主存；B．周期挪用； C．DMA与CPU交替访问；D．DMA。 7．在运算器中不包含____D__。 A．状态寄存器；B．数据总线； C．ALU；D．地址寄存器。 8．计算机操作的最小单位时间是__A____。 A．时钟周期；B．指令周期； C．CPU周期；D．中断周期。 9．用以指定待执行指令所在地址的是__C____。 A．指令寄存器；B．数据计数器； C．程序计数器；D．累加器。 10．下列描述中___B___是正确的。 A．控制器能理解、解释并执行所有的指令及存储结果； B．一台计算机包括输入、输出、控制、存储及算逻运算五个单元； C．所有的数据运算都在CPU的控制器中完成； D．以上答案都正确。 11．总线通信中的同步控制是___B___。 A．只适合于CPU控制的方式； B．由统一时序控制的方式； C．只适合于外围设备控制的方式； D．只适合于主存。

操作系统-实验六虚拟存储器实验报告

计算机与信息工程学院实验报告 一、实验内容 实验一：模拟分页式存储管理中硬件的地址转换和产生缺页中断。 [提示] （1）分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页 其中，标志----用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。 主存块号----用来表示已经装入主存的页所占的块号。 在磁盘上的位置----用来指出作业副本的每一页被存放在磁盘上的位置。 （2）作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式： 绝对地址=块号×块长+单元号 计算出欲访问的主存单元地址。如果块长为2的幂次，则可把块号作为高地址部分， 把单元号作为低地址部分，两者拼接而成绝对地址。若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，有操作系统按该页在磁盘上 的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

（3）设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“* 该页页号”，表示产生了一次缺页中断。 该模拟程序的算法 （4）假定主存的每块长度为128个字节；现有一个共七页的作业，其中第0页至第3页已经装入主存，其余三页尚未装入主存；该作业的页表为： （5）运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中的操作。 实验二：用先进先出（FIFO）页面调度算法处理缺页中断。 [提示]： （1）在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。调出和装入后都要修改页表页表中对应页的标志。 （2）FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。例如： P[0]，P[1]，….，P[m-1] 其中每一个P[i]（i=0，1，….，m-1）表示一个在主存中的页面号。它们的初值为：P[0]:=0，P[1]:=1，….，P[m-1]:=m-1 用一指针k指示当要装入新页时，应淘汰的页在数组中的位置，k的初值为“0”。 当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行： P[k]:=要装入页的页号 k:=(k+1) mod m 再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。