您是第 位访客

flashsim 源码分析(四): 总线上锁机制的实现

flashsim 模拟器是事件驱动型的。每一个请求对应一个事件(event对象)。event 对象会在闪存内部的各个器件之间相互传递,从而来模拟闪存处理IO请求。

前面介绍了,总线通道(bus channel)中的交叉操作)。现在结合源码来了解下,flashsim 是如何来模拟总线占用的。

首先了解下,flashsim 中处理一个事件的基本流程

(1) 首先 new 一个 ssd 对象,调用 ssd->event_arrive(event_type, logical_address, size, start_time) 来向 ssd 传入一个IO请求。

(2) ssd->event_arrive() 会根据传入的参数 new 一个 event 对象,并调用 controller.event_arrive(event) 来处理事件。

(3) controller.event_arrive() 会根据 event 对象的 event_type 属性来决定调用 ftl->read(event)ftl->write(event)ftl->trim(event) 中的哪一个。

(4) ftl 对 event 进一步处理之后,会通过调用 controller.issue(event) 将 event 对象传出。

(5) controller.issue() 会根据事件类型的不同对事件做出不同的处理。

  • 如果事件类型为 READ:那么将依次调用 ssd.bus.lock(),ssd.read(),ssd.bus.lock(),ssd.ram.write(),ssd.ram.read(),ssd.replace()。
  • 如果时间类型为 WRITE:那么将依次调用 ssd.bus.lock(),ssd.ram.write(),ssd.ram.read(),ssd.replace()。
  • 如果事件类型为 ERASE:那么将依次调用 ssd.bus.lock(),ssd.erase()。
  • 如果事件类型为 MERGE:那么将依次调用 ssd.bus.lock(),ssd.merge()。
  • 如果事件类型为 TRIM:那么直接返回 SUCCESS。

至于为什么这么调用,可以看看前面介绍的总线通道上的交叉操作

(6) controller.issue() 函数处理完成后会直接返回到最开始的 ssd->even_arrive() 函数中。同时,event 对象中的 time_taken 属性记录了该 event 所花费的时间,并将这个值返回给上层应用。

总线通道中锁机制的实现

下面重点介绍下 ssd.bus.lock() 这个函数,这个函数实现了多个事件对总线的竞争。

在 ssd.bus.lock() 函数中,会直接调用 channel.lock() 函数。其实调用 ssd.bus.lock() 就等价于调用 channel.lock()。

为了模拟真实环境下总线的竞争情况。flashsim 在 bus 对象中维护了一个 timings 列表(利用vector实现)。timings 中的每个元素都是一个 lock_times 结构体,lock_times 包含两个元素,分别是 lock_timeunlock_time,分别表示这个请求占用总线和释放总线的时刻。timings 列表中的每一个元素都对应一个占用总线的请求。

ssd.bus.lock(channel, start_time, duration, event) 传入的参数分别是,请求的 channel 的编号,开始占用总线的时间,占用总线的时间长度和相应的事件对象。 ssd.bus.lock() 会根据 channel 参数调用相应的 channel.lock(start_time, duration, event) 函数。

channel.lock() 函数内部的处理流程如下:

(1) 调用 unlock() 函数,根据当前请求的 start_time 删除 channel.timings 中已经完成的记录。unlock()函数的实现是,依次遍历 channel.timings 中的记录,删除 unlock_time <= start_time 的记录,然后将 channel.timings 列表中的记录按照 lock_time 属性升序排序。

(2) 确定当前请求开始调度的时刻。channel.timings 中维护了很多占用总线的请求,需要根据一定的准则来确定,新到来的请求什么时候开始被调度。

新的请求开始调度的时刻应该按照下面的准则来确定:

  • 如果 channel.timings 列表为空,那么,当前请求开始调度的时间自然为该请求开始的时间,即 sched_time = start_time 。

  • 如果当前请求开始的时间比 channel.timings 列表中第一个请求的开始时间还早,并且当前请求完成后,timings 中的第一个请求还没开始或者刚开始,那么当前请求的开始调度时间为该请求的开始时间,即 sched_time = start_time 。

  • 在 timings 列表中寻找一个事件,在它结束之后和下一个事件开始之间,有足够的时间来完成当前事件。即,如果当前事件开始时间 比channel.timings 列表中的第 i 请求结束的时间要早,并且第 i 个请求结束和第 i+1 个请求开始之间的时间间隔大于当前请求所需要占用总线的时长。那么当前请求开始调度的时间为第 i 个请求结束的时间,即 sched_time = timings.get(i).unlock_time 。

  • 如果上面的条件都不满足,那么当前请求会在 timings 中所有请求完成之后调用,也就是在最后一个请求的结束时刻调用,即 sched_time = timings.back().unlock_time 。

(3) 确定当前请求开始调度的时刻后,就可以根据开始调度时刻和占用的时间长度 new 一个 lock_times 对象,并将其添加到当前 channel 的 timings 列表中。

(4) 通过调用 event.incr_ bus_wait_time() 和 event.incr_time_taken() 增加相应的 event 对象的 bus_wait_time 和 time_taken 属性的值。这两个属性分别表示该 event 在总线上排队等待的时间和该 event 到目前为止所消耗的时间。在总线上等待的时间 = 调度开始的时间-请求开始的时间。在总线上消耗的时间 = 等待时间 + 占用总线的时间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
enum status Channel::lock(double start_time, double duration, Event &event)
{
assert(num_connected <= max_connections);
assert(ctrl_delay >= 0.0);
assert(data_delay >= 0.0);
assert(start_time >= 0.0);
assert(duration >= 0.0);
// 删除当前 channel 中已经完成的锁记录(timings)
// 实现:依次遍历 channel.timings 中的记录,删除 unlock_time <= start_time 的记录,
// 然后将 channel.timings 中的记录按照 lock_time 属性升序排序。
unlock(start_time);
// BUS_CHANNEL_FREE_FLAG 初始化为 -1,
// sched_time 表示当前事件开始调度的时刻
double sched_time = BUS_CHANNEL_FREE_FLAG;
// 如果 channel.timings 列表为空,那么当前事件的调度时间即为该事件的开始时间
if(timings.size() == 0)
sched_time = start_time;
// 如果 channel.timings 列表不为空,根据timings,为当前事件确定一个合理的调度时刻
else
{
// 如果当前请求开始的时间比 channel.timings 列表中第一个请求的开始时间还早,
// 并且当前请求完成后,timings 中的第一个请求还没开始或者刚开始,
// 那么当前请求的开始调度时间为该请求的开始时间
if((*it).lock_time > start_time && (*it).lock_time - start_time >= duration)
sched_time = start_time;
if(sched_time == BUS_CHANNEL_FREE_FLAG)
{
for(; it < timings.end(); it++)
{
if (it + 1 != timings.end())
{
// 在两个相邻的事件之间有足够的时间来完成当前请求
if((*it).unlock_time >= start_time && (*(it+1)).lock_time - (*it).unlock_time >= duration)
{
sched_time = (*it).unlock_time;
break;
}
}
}
}
// 如果上面仍然没有找到合适的调度时间,那么当前事件在 timings 列表中所有
// 事件都完成之后调度(也就是 channel.timings 中最后一个事件的 uncock 时间)
if(sched_time == BUS_CHANNEL_FREE_FLAG)
sched_time = timings.back().unlock_time;
}
// 将新的调度信息添加到 channel.timings 中
lock_times lt;
lt.lock_time = sched_time;
lt.unlock_time = sched_time + duration;
timings.push_back(lt);
// 更新 channel.timings 列表中最后一个事件的完成事件
if (lt.unlock_time > ready_at)
ready_at = lt.unlock_time;
// 更新当前事件的所消耗的时间。
event.incr_bus_wait_time(sched_time - start_time);
event.incr_time_taken(sched_time - start_time + duration);
//printf("%f\n",event.incr_bus_wait_time(sched_time - start_time));
//printf("%f\n",event.incr_time_taken(sched_time - start_time + duration));
return SUCCESS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Channel::unlock(double start_time)
{
// 删除该 channel 上已经完成的记录。
std::vector<lock_times>::iterator it;
for ( it = timings.begin(); it < timings.end();)
{
if((*it).unlock_time <= start_time) // 完成时间小于当前时间的记录都表示完成了
timings.erase(it);
else
{
it++;
}
}
// 重新排序
std::sort(timings.begin(), timings.end(), &timings_sorter);
}