1. MESI状态转换基础模拟
任务目标
实现一个MESI缓存一致性协议状态机模拟器，输入缓存行当前状态与总线操作，输出转换后的状态及是否产生总线事务。覆盖四种状态（Modified、Exclusive、Shared、Invalid）在本地读/写、远程读/写操作下的全部合法转换路径。
核心实现
class MESIStateMachine {
constructor() {
// 状态编码: M=Modified, E=Exclusive, S=Shared, I=Invalid
// 操作编码: LR=Local Read, LW=Local Write, RR=Remote Read, RW=Remote Write
this.transitions = {
'I': {
'LR': { next: 'E', busAction: 'BusRd' }, // 本地读未命中，发BusRd
'LW': { next: 'M', busAction: 'BusRdX' }, // 本地写未命中，发BusRdX
'RR': { next: 'I', busAction: null }, // 远程读未命中，无动作
'RW': { next: 'I', busAction: null } // 远程写未命中，无动作
},
'E': {
'LR': { next: 'E', busAction: null }, // 本地读命中，无动作
'LW': { next: 'M', busAction: null }, // 本地写命中，升级为M
'RR': { next: 'S', busAction: null }, // 远程读，降级为S
'RW': { next: 'I', busAction: null } // 远程写，失效
},
'S': {
'LR': { next: 'S', busAction: null }, // 本地读命中
'LW': { next: 'M', busAction: 'BusRdX' }, // 本地写，需通知其他核失效
'RR': { next: 'S', busAction: null }, // 远程读，保持共享
'RW': { next: 'I', busAction: null } // 远程写，失效
},
'M': {
'LR': { next: 'M', busAction: null }, // 本地读命中
'LW': { next: 'M', busAction: null }, // 本地写命中
'RR': { next: 'S', busAction: 'BusRd' }, // 远程读，需写回内存
'RW': { next: 'I', busAction: 'BusRdX' } // 远程写，需写回内存
}
};
}
/**
* 执行状态转换
* @param {string} currentState - 当前状态: 'M'|'E'|'S'|'I'
* @param {string} operation - 操作: 'LR'|'LW'|'RR'|'RW'
* @returns {{nextState: string, busAction: string|null, valid: boolean}}
*/
transition(currentState, operation) {
const stateTrans = this.transitions[currentState];
if (!stateTrans) {
return { nextState: null, busAction: null, valid: false };
}
const trans = stateTrans[operation];
if (!trans) {
return { nextState: null, busAction: null, valid: false };
}
return {
nextState: trans.next,
busAction: trans.busAction,
valid: true
};
}
/**
* 获取所有合法转换路径（用于验证）
* @returns {Array<{from: string, op: string, to: string, bus: string|null}>}
*/
getAllTransitions() {
const result = [];
const states = ['M', 'E', 'S', 'I'];
const ops = ['LR', 'LW', 'RR', 'RW'];
for (const s of states) {
for (const op of ops) {
const r = this.transition(s, op);
if (r.valid) {
result.push({ from: s, op, to: r.nextState, bus: r.busAction });
}
}
}
return result;
}
}
// ========== 最小验证入口 ==========
function runVerification() {
const fsm = new MESIStateMachine();
const testCases = [
// [当前状态, 操作, 期望下一状态, 期望总线动作]
['I', 'LR', 'E', 'BusRd'],
['I', 'LW', 'M', 'BusRdX'],
['E', 'LW', 'M', null],
['E', 'RR', 'S', null],
['S', 'LW', 'M', 'BusRdX'],
['M', 'RR', 'S', 'BusRd'],
['M', 'RW', 'I', 'BusRdX'],
['S', 'RW', 'I', null]
];
let allPassed = true;
console.log('=== MESI状态机验证 ===');
for (const [state, op, expNext, expBus] of testCases) {
const result = fsm.transition(state, op);
const nextOk = result.nextState === expNext;
const busOk = result.busAction === expBus;
const ok = nextOk && busOk;
if (!ok) allPassed = false;
console.log(
`${state} --${op}--> ${result.nextState} | 总线: ${result.busAction ?? '无'} | ` +
`${ok ? '✓' : '✗ 期望: ' + expNext + ', ' + (expBus ?? '无')}`
);
}
// 检查非法转换
const invalidCases = [
['M', 'LR'], // 合法，不应出现在非法列表
['I', 'RR'], // 合法
];
// 验证所有16种组合均合法（MESI完整协议无非法组合）
const allTrans = fsm.getAllTransitions();
console.log(`\n合法转换总数: ${allTrans.length}/16`);
if (allTrans.length !== 16) {
console.log('✗ 应有16条合法转换');
allPassed = false;
} else {
console.log('✓ 全部16条转换路径完整');
}
return allPassed;
}
// 执行验证
runVerification();运行方式
- 将代码保存为
mesi_simulator.js - 使用Node.js运行：
node mesi_simulator.js
验证方法与通过条件
运行后观察控制台输出：
- 8条测试用例全部标记
✓，且每条转换的下一状态与总线动作均与注释中的期望值一致 - 输出
合法转换总数: 16/16，表示MESI协议四种状态×四种操作的全部转换路径均已覆盖 - 最终无
✗标记即验证通过
状态转换总览
图中省略了自环转换（如M状态LR/LW保持M、S状态LR/RR保持S、E状态LR保持E、I状态RR/RW保持I），完整转换逻辑以代码为准。总线动作仅在需要跨核通信时产生：BusRd表示请求读取数据，BusRdX表示请求独占写入权。