我试图了解如果所有请求都提供到达时间，CSCAN 算法将如何工作。我可以在网上找到许多资源和教程来解释该算法，仅包含包含扇区 ID 的请求列表，但是，我想了解当还提供按到达时间升序排序的到达时间时，如何处理请求。我想写一个c程序，有以下要求：
输入将采用以下格式，第一个数字代表要服务的扇区，第二个数字代表到达时间（按到达时间升序排序）：
7394 61
1217 63
3898 70
4254 74
8951 75
4764 86
5517 95
6765 100
151 108
5637 121
4245 125
8742 130
1703 138
879 140
磁盘总大小可以为 10000（0-9999 扇区）。 预期答案是：行驶距离为 16765，时间为 3414。 顺便说一句，环绕距离（从磁盘末尾 9999 到 0）被视为 1，而不是磁盘大小。
我尝试了几种不同的方法，例如计算每个请求的时间并将其与迄今为止到达的请求进行比较，但所有这些方法最终都得到了错误的结果。我认为，由于列表已经提供，并且计划要求并没有明确说明是否有单独的时间来跟踪到达时间，所以我会为第一个到达的请求提供服务，然后计算时间（按要求行驶的距离为 5）并与看看那时哪些请求已经到达，但这会引起一些混乱，因为我无法真正思考这个算法。我一定没有实施正确的逻辑，如果有人能详细解释这一点，我将不胜感激。以下是我尝试实施的内容：
// begin is 0, requests is an array of the request struct that has the sector id and arrival time
// there's also a direction variable keeping track of the current direction but i didn't use it
void cscan(int begin) {
int movement = 0;
double time = 0;
int head = begin;
int serviced[50] = {0}; // Track whether a request has been serviced
int servicedRequests = 0; // Count of serviced requests
// Sort the requests in ascending order of sectorIDs
for (int i = 0; i < numRequests - 1; i++) {
for (int j = i + 1; j < numRequests; j++) {
if (requests[i].sectorID > requests[j].sectorID) {
Request temp = requests[i];
requests[i] = requests[j];
requests[j] = temp;
}
}
}
// Sweep from head to DISK_SIZE - 1
for (int i = 0; i < numRequests; i++) {
if (!serviced[i] && requests[i].sectorID >= head && requests[i].arrivalTime <= time) {
int distanceMoved = abs(requests[i].sectorID - head);
movement += distanceMoved;
time += distanceMoved / 5.0;
// Update head position, mark request as serviced
head = requests[i].sectorID;
serviced[i] = 1;
servicedRequests++;
}
}
// Wrap-around to 0
if (head != DISK_SIZE - 1) {
int distanceToEnd = DISK_SIZE - 1 - head;
movement += distanceToEnd; // Move to the end of the disk
time += distanceToEnd / 5.0; // Travel time to the end
time += 10.0; // Add wrap-around penalty
head = 0; // Wrap to the start of the disk
}
// Sweep from 0 to DISK_SIZE - 1 again for unserviced requests
for (int i = 0; i < numRequests; i++) {
if (!serviced[i] && requests[i].arrivalTime <= time) {
int distanceMoved = abs(requests[i].sectorID - head);
movement += distanceMoved;
time += distanceMoved / 5.0;
// Update head position, mark request as serviced
head = requests[i].sectorID;
serviced[i] = 1;
servicedRequests++;
}
}
//print the distance moved and time
}
这给了我行驶距离 18950 和时间 3800 的答案，这显然不符合要求。
我已经用C++实现了这个算法：当头部完成一个移动时，它会选择最快完成的下一个请求。
这是代码：
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
struct sRequest
{
int sector;
int arrival;
};
struct sEvent
{
enum class eEventType {
arrival,
completion
};
eEventType type;
sRequest request;
int time;
sEvent( const sRequest& r )
: request( r ), time( r.arrival ),
type( eEventType::arrival)
{}
sEvent( const sRequest& r, int t )
: request( r ), time( t ), type( eEventType::completion)
{}
};
struct sHead {
bool busy;
int sector;
bool asc;
};
class eventComp
{
public:
bool operator() (const sEvent& lhs, const sEvent& rhs) const
{
return (lhs.time>rhs.time);
}
};
std::vector<sRequest> theRequests;
std::vector<sRequest> theRequestsWaiting;
std::priority_queue<sEvent,std::vector<sEvent>, eventComp> theEventQueue;
sHead theHead;
int theSimTime;
int totalDistance;
void readfile(const std::string &fname)
{
// The input will be of the following format with the first number representing the sector to be serviced
// and the second representing the arrival time (sorted by arrival time asc):
std::ifstream ifs(fname);
if (!ifs.is_open())
throw std::runtime_error(
"Cannot open " + fname);
sRequest R;
ifs >> R.sector;
ifs >> R.arrival;
while (!ifs.fail())
{
theRequests.push_back(R);
ifs >> R.sector;
ifs >> R.arrival;
}
}
sRequest& chooseFastestRequest( int& bestTime )
{
sRequest& ret = theRequestsWaiting[0];
bestTime = INT_MAX;
for( auto& tr : theRequestsWaiting )
{
int timeRequired = abs( tr.sector - theHead.sector ) / 5;
bool isAsc = ( theHead.sector > tr.sector );
if( isAsc != theHead.asc )
timeRequired += 10;
if( timeRequired < bestTime ) {
bestTime = timeRequired;
ret = tr;
}
}
return ret;
}
void startRequest()
{
int timeRequired;
auto& r = chooseFastestRequest( timeRequired );
theEventQueue.push( sEvent(r,theSimTime+timeRequired));
theRequestsWaiting.erase( theRequestsWaiting.begin());
theHead.busy = true;
theHead.asc = ( r.sector >= theHead.sector );
totalDistance += abs( r.sector - theHead.sector );
std::cout << "Head moving from " << theHead.sector <<" to "<< r.sector << "\n";
}
void Simulate()
{
// load request arrivals into event queue
for( auto & r : theRequests )
theEventQueue.push(r);
theSimTime = 0;
totalDistance = 0;
while( theEventQueue.size() )
{
auto& e = theEventQueue.top();
theSimTime = e.time;
switch( e.type ) {
case sEvent::eEventType::arrival:
std::cout << e.request.sector << " sector request arrived at " << theSimTime << "\n";
theRequestsWaiting.push_back( e.request );
if( ! theHead.busy)
startRequest();
break;
case sEvent::eEventType::completion:
std::cout << e.request.sector << " sector completed at " << theSimTime << "\n";
theHead.sector = e.request.sector;
theHead.busy = false;
if( theRequestsWaiting.size() )
startRequest();
break;
}
theEventQueue.pop();
}
std::cout << "time " << theSimTime << ", distance " << totalDistance;
}
main()
{
readfile("../dat/test1.txt");
Simulate();
return 0;
}
输出是
7394 sector request arrived at 61
Head moving from 0 to 7394
1217 sector request arrived at 63
3898 sector request arrived at 70
4254 sector request arrived at 74
8951 sector request arrived at 75
4764 sector request arrived at 86
5517 sector request arrived at 95
6765 sector request arrived at 100
151 sector request arrived at 108
5637 sector request arrived at 121
4245 sector request arrived at 125
8742 sector request arrived at 130
1703 sector request arrived at 138
879 sector request arrived at 140
7394 sector completed at 1539
Head moving from 7394 to 3898
6765 sector completed at 1664
Head moving from 6765 to 4254
6765 sector completed at 1664
Head moving from 6765 to 8951
6765 sector completed at 1664
Head moving from 6765 to 4764
6765 sector completed at 1674
Head moving from 6765 to 5517
6765 sector completed at 1674
Head moving from 6765 to 6765
6765 sector completed at 1674
Head moving from 6765 to 151
6765 sector completed at 1684
Head moving from 6765 to 5637
5637 sector completed at 1919
Head moving from 5637 to 4245
5637 sector completed at 1919
Head moving from 5637 to 8742
4245 sector completed at 2207
Head moving from 4245 to 1703
1703 sector completed at 2715
Head moving from 1703 to 879
1703 sector completed at 2715
Head moving from 1703 to 879
879 sector completed at 2889
time 2889, distance 35265
此应用程序的完整 VSCODE 项目位于 https://github.com/JamesBremner/so79242119