第6章 Overlapped I/O, 在您身后变戏法 —1

    这一章描述咋样运用 overlapped I/O(也就是 asynchronous
I/O)。某些时候 overlapped I/O 可以代替多线程的功能。不过,overlapped
I/O 加上completion ports,常被规划为多线程处理,以便在一个“受制于 I/O
的主次”(所谓 I/O bound 程序)中拿走高效用。

    译注    深层啄磨 Win32 平台(WinNT 和 Win95)的 File Systems 和
Device I/O 的书籍极少。Advanced Windows 3rd edition(Jeffrey
Richter/Microsoft Press)第 13章和第 14 章有许多贵重的始末,可供参考。
  
 截止近期自我早已花了数章篇幅告诉各位“如何”以及“为啥”要拔取线程。我将以这一章介绍一个您恐怕不想采纳多线程的场馆。许多应用程序,例如终端机模拟程序,都亟需在同一时间处理对一个之上的文本的读写操作。利用
Win32 所谓的 overlapped I/O 特性,你就足以让所有这么些 I/O
操作并行处理,并且当其他一个 I/O
完成时,你的程序会收下一个通报。其他操作系统把这多少个特性称为 nonblocking
I/O 或 asynchronous I/O。
  
 回头看看第2章和第3章,那里已经示范咋样暴发一个线程负责后台打印操作。事实上“后台打印”这种说法是错误的,大家在后台所开展的操作只可是是发生打印机所需的多少。Windows
操作系统负责以打印管理器(Printer Manager)完成打印。打印管理器会
“spooled”
这多少个准备好的数量,并且以打印机所能接受的进度,逐步地将数据喂给打印机。
    关键在于 I/O 设备是个慢速设备,不论打印机、调制解调器,甚至硬盘,与
CPU 相比较都奇慢无比。坐下来干等 I/O
的到位是一件不甚明智的工作。有时候数据的流动率卓殊惊人,把多少从你的公文服务器中以
Ethernet
速度搬走,其速度可能高达每秒一百万个字节。倘使您品味从文件服务器中读取100KB
,在用户的看法来看几乎是一下子完成。可是,要精通,你的线程执行这个命令,已经浪费了
10 个一百万次 CPU 周期。
    现在设想一下,同一个文书服务器,透过一条拨号线路,被 Remote Access
Service(Service)s(RAS)处理。于是,100KB 的数据量在 ISDN 上需要 15 秒,在
9600bps
线路上急需几乎两分钟。尽管从用户的见解来看,一个窗口在这么长的岁月尾完全没有反应,也是分外可怕的。
    那一个题材的肯定缓解方案就是,使用另一个线程来展开 I/O。但是,这就
    发生出一部分连锁题材,包括哪些在主线程中操控许四个 worker
线程、咋样设定同步机制、怎么着处理错误情形、怎样展现对话框。这个难题都将在本章出现并解决之。
    一个最简易的对答:overlapped I/O 是 Win32
的一项技艺,你能够要求操作系统为你传送数据,并且在传递完毕时通报你。这项技艺使你的顺序在I/O
举办过程中还可以够继承处理事务。事实上,操作系统内部正是以线程来形成
overlapped I/O。你可以取得线程的拥有利益,而不需付出什么样痛苦代价。
        重要!
        Windows 95 所扶助的 overlapped I/O 有些限制,只适用于 named
pipes 、mailslots 、serial I/O 、以及 socket() 或 accept()所传回来的sockets,它并不帮忙磁盘或光盘中的文件操作。本章的兼具例子只在Windows
NT 下才可以使得运转。

    这一章对于 overlapped I/O
的探究,将从最简易的应用起来,然后再衍变到最高级的利用。
        i 激发的文件 handles
        i 激发的 event 对象
        i 异步过程调用(Asynchronous Procedure Calls,APCs)
        i I/O completion ports
    其中以 I/O completion ports
特别显得重要,因为它们是绝无仅有适用于高负荷服务器(必须同时爱惜广大连续线路)的一个技艺。Completion
ports 利用部分线程,协助平衡由“I/O
请求”所引起的载荷。这样的架构特别契合用在SMP 系统(译注:帮助三个 CPU
的操作系统)中暴发所谓的 “scalable” 服务器。
    译注     所谓 scalable 系统,是指可以藉着扩大 RAM 或磁盘空间或 CPU
个数而晋级应用程序效率的一种系统。

1722 最优乘车

 

1997年NOI全国比赛

 时间限制: 1
s

 空间限制: 128000
KB

 题目等级 : 大师
Master

题解

 

 

 

问题叙述 Description

 
  H城是一个旅游胜地,每年都有广大的人前来旅游。为便于游客,巴士集团在各种旅游景点及商旅,客栈等地都安装了巴士站并开展了有些单程巴上路线。每条单程巴士路线从某个巴士站出发,依次途经若干个巴士站,最终到达极限巴士站。

    一名客人近期到H城国旅,他很想去S公园游玩,但即使从他到处的餐馆没有一块巴士可以从来抵达S公园,则他可能要先乘某伙同巴士坐几站,再下来换乘同一站台的另一路巴士, 这样换乘五遍后到达S公园。

    现在用整数1,2,…N 给H城的有着的巴士站编号,约定这名客人所在食堂的巴士站编号为1…S公园巴士站的号码为N。

    写一个主次,帮助这名客人找寻一个最优乘车方案,使他在从酒馆乘车到S公园的过程中转发的次数最少。

输入描述 Input Description

   
输入文件是INPUT.TXT。文件的率先行有四个数字M和N(1<=M<=100 1<N<=500),表示开通了M条单程巴士路线,总共有N个车站。从第二行到第M发行依次给出了第1条到第M条巴士路线的音信。其中第i+1行给出的是第i条巴士路线的信息,从左至右按运行顺序依次给出了该路线上的装有站号相邻六个站号之间用一个空格隔开。

出口描述 Output Description

   
输出文件是OUTPUT.TXT,文件只有一行。如若无法乘巴士从旅舍到达S公园,则输出”N0″,否则输出你的次第所找到的起码换车次数,换车次数为0表示不需换车即可抵达。

样例输入 萨姆ple Input

3 7

6 7

4 7 3 6

2 1 3 5

样例输出 Sample Output

2

数量范围及提醒 Data Size & Hint

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int a[101][101];
 6 int map[101][101];
 7 int cd[101];
 8 int inf=0x7fffffff;
 9 int main()
10 {
11     
12     for(int i=0;i<=101;i++)
13     for(int j=0;j<=101;j++)
14     map[i][j]=inf;
15     //memset(map,0x7f,sizeof(map));
16     //for(int i=1;i<=)
17     int n,m;
18     //scanf("%d%d",&m,&n);
19     cin>>m>>n;
20     char p;
21     for(int i=1;i<=m;i++)
22     {
23         int now=1;
24         char p;
25         while(1)
26         {
27             int bc=0;//储存结果
28             p=getchar();
29             while(p>='0'&&p<='9')
30             {
31                 bc=bc*10+p-'0';
32                 p=getchar();
33             }
34             if(bc!=0)
35             {
36                 a[i][now]=bc;
37                 now++;
38             }
39             
40             if(p==' ')
41             continue;
42             if(p=='\n')
43             {
44                 if(a[i][now-1]==0)
45                 continue;
46                 cd[i]=now;
47                 now=1;
48                 break;
49             }
50         }
51         cd[i]--;
52     }
53     for(int k=1;k<=m;k++)
54     {
55         for(int i=1;i<=cd[k];i++)
56         {
57             for(int j=1;j<=cd[k];j++)
58             {
59                 if(i==j)
60                 map[a[k][i]][a[k][j]]=0;
61                 else
62                 map[a[k][i]][a[k][j]]=1;
63             }
64         }
65     }
66     for(int k=1;k<=n;k++)
67     {
68         for(int i=1;i<=n;i++)
69         {
70             for(int j=1;j<=n;j++)
71             {
72                 if(map[i][k]!=inf&&map[k][j]!=inf)
73                 if(map[i][j]>map[i][k]+map[k][j])
74                 {
75                     map[i][j]=map[i][k]+map[k][j];
76                 }
77             }
78         }
79     }
80     if(map[1][m]==inf)
81     {
82         cout<<"NO";
83     }
84     else
85     {
86         cout<<map[1][n]-1;
87     }
88     return 0;
89 }