507 lines
13 KiB
Go
507 lines
13 KiB
Go
package main
|
|
|
|
import "sort"
|
|
|
|
const (
|
|
StateReady = "R"
|
|
StateExecute = "E"
|
|
StateWait = "W"
|
|
StateFinish = "F"
|
|
)
|
|
|
|
type PCB struct {
|
|
Name string `json:"name"`
|
|
Priority int `json:"priority"`
|
|
InitPriority int `json:"initPriority"`
|
|
ArrivalTime int `json:"arrivalTime"`
|
|
NeedTime int `json:"needTime"`
|
|
UsedTime int `json:"usedTime"`
|
|
State string `json:"state"`
|
|
StartTime int `json:"startTime"`
|
|
FinishTime int `json:"finishTime"`
|
|
QueueLevel int `json:"queueLevel"`
|
|
WaitUntil int `json:"waitUntil"`
|
|
SliceUsedTime int `json:"sliceUsedTime"`
|
|
}
|
|
|
|
func (p *PCB) Clone() PCB {
|
|
return *p
|
|
}
|
|
|
|
func (p *PCB) Remaining() int {
|
|
return p.NeedTime - p.UsedTime
|
|
}
|
|
|
|
type Snapshot struct {
|
|
Time int `json:"time"`
|
|
Processes []PCB `json:"processes"`
|
|
Running string `json:"running"`
|
|
Queues [][]string `json:"queues"`
|
|
Event string `json:"event"`
|
|
}
|
|
|
|
type SimResult struct {
|
|
Snapshots []Snapshot `json:"snapshots"`
|
|
Algorithm string `json:"algorithm"`
|
|
AvgTurnaround float64 `json:"avgTurnaround"`
|
|
Deadlock bool `json:"deadlock"`
|
|
}
|
|
|
|
func NewPCB(name string, priority, arrivalTime, needTime int) *PCB {
|
|
return &PCB{
|
|
Name: name,
|
|
Priority: priority,
|
|
InitPriority: priority,
|
|
ArrivalTime: arrivalTime,
|
|
NeedTime: needTime,
|
|
UsedTime: 0,
|
|
State: StateReady,
|
|
StartTime: -1,
|
|
FinishTime: -1,
|
|
QueueLevel: 0,
|
|
WaitUntil: -1,
|
|
SliceUsedTime: 0,
|
|
}
|
|
}
|
|
|
|
func allFinished(procs []*PCB) bool {
|
|
for _, p := range procs {
|
|
if p.State != StateFinish {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func allWaitingOrFinished(procs []*PCB) bool {
|
|
for _, p := range procs {
|
|
if p.State != StateWait && p.State != StateFinish {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func anyWillWake(procs []*PCB, time int) bool {
|
|
for _, p := range procs {
|
|
if p.State == StateWait && p.WaitUntil > time {
|
|
return true
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
func collectReady(procs []*PCB, time int) []*PCB {
|
|
var ready []*PCB
|
|
for _, p := range procs {
|
|
if p.State == StateReady && p.ArrivalTime <= time {
|
|
ready = append(ready, p)
|
|
}
|
|
}
|
|
return ready
|
|
}
|
|
|
|
func findRunning(procs []*PCB) *PCB {
|
|
for _, p := range procs {
|
|
if p.State == StateExecute {
|
|
return p
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func calcAvgTurnaround(procs []*PCB) float64 {
|
|
total := 0
|
|
count := 0
|
|
for _, p := range procs {
|
|
if p.State == StateFinish && p.FinishTime > 0 {
|
|
total += p.FinishTime - p.ArrivalTime
|
|
count++
|
|
}
|
|
}
|
|
if count == 0 {
|
|
return 0
|
|
}
|
|
return float64(total) / float64(count)
|
|
}
|
|
|
|
func makeSnap(time int, procs []*PCB, running string, queues [][]string, event string) Snapshot {
|
|
var copies []PCB
|
|
for _, p := range procs {
|
|
copies = append(copies, p.Clone())
|
|
}
|
|
return Snapshot{
|
|
Time: time,
|
|
Processes: copies,
|
|
Running: running,
|
|
Queues: queues,
|
|
Event: event,
|
|
}
|
|
}
|
|
|
|
func SimulatePriorityRR(processes []*PCB, timeSlice int) SimResult {
|
|
procs := make([]*PCB, len(processes))
|
|
for i, p := range processes {
|
|
c := *p
|
|
procs[i] = &c
|
|
}
|
|
|
|
var snapshots []Snapshot
|
|
var readyQueue []*PCB
|
|
time := 0
|
|
maxTime := 0
|
|
for _, p := range procs {
|
|
end := p.ArrivalTime + p.NeedTime*2 + 10
|
|
if end > maxTime {
|
|
maxTime = end
|
|
}
|
|
}
|
|
|
|
for time <= maxTime {
|
|
for _, p := range procs {
|
|
if p.State == StateWait && p.WaitUntil <= time {
|
|
p.State = StateReady
|
|
p.WaitUntil = -1
|
|
readyQueue = append(readyQueue, p)
|
|
}
|
|
if p.ArrivalTime == time && p.State == StateReady {
|
|
found := false
|
|
for _, q := range readyQueue {
|
|
if q == p {
|
|
found = true
|
|
break
|
|
}
|
|
}
|
|
if !found {
|
|
readyQueue = append(readyQueue, p)
|
|
}
|
|
}
|
|
}
|
|
|
|
running := findRunning(procs)
|
|
|
|
if running != nil {
|
|
for _, p := range readyQueue {
|
|
if p.Priority < running.Priority {
|
|
running.State = StateReady
|
|
running.SliceUsedTime = 0
|
|
readyQueue = append(readyQueue, running)
|
|
running = nil
|
|
break
|
|
}
|
|
}
|
|
}
|
|
|
|
if running == nil {
|
|
if len(readyQueue) == 0 {
|
|
if allFinished(procs) {
|
|
snapshots = append(snapshots, makeSnap(time, procs, "", nil, "✓ 所有进程执行完毕"))
|
|
break
|
|
}
|
|
if allWaitingOrFinished(procs) {
|
|
if !anyWillWake(procs, time) {
|
|
snapshots = append(snapshots, makeSnap(time, procs, "", nil, "✗ 死锁：所有未完成进程都在等待"))
|
|
return SimResult{Snapshots: snapshots, Algorithm: "基于优先级的时间片轮转", AvgTurnaround: calcAvgTurnaround(procs), Deadlock: true}
|
|
}
|
|
snapshots = append(snapshots, makeSnap(time, procs, "", nil, "无就绪进程，等待唤醒..."))
|
|
time++
|
|
continue
|
|
}
|
|
snapshots = append(snapshots, makeSnap(time, procs, "", nil, "无就绪进程"))
|
|
time++
|
|
continue
|
|
}
|
|
|
|
sort.Slice(readyQueue, func(i, j int) bool {
|
|
if readyQueue[i].Priority != readyQueue[j].Priority {
|
|
return readyQueue[i].Priority < readyQueue[j].Priority
|
|
}
|
|
return readyQueue[i].ArrivalTime < readyQueue[j].ArrivalTime
|
|
})
|
|
|
|
selected := readyQueue[0]
|
|
readyQueue = readyQueue[1:]
|
|
selected.State = StateExecute
|
|
selected.SliceUsedTime = 0
|
|
if selected.StartTime == -1 {
|
|
selected.StartTime = time
|
|
}
|
|
running = selected
|
|
}
|
|
|
|
queueNames := buildQueueNames(readyQueue)
|
|
event := running.Name + " 执行 (优先级=" + itoa(running.Priority) + ", 剩余=" + itoa(running.Remaining()) + ")"
|
|
snapshots = append(snapshots, makeSnap(time, procs, running.Name, queueNames, event))
|
|
|
|
running.UsedTime++
|
|
running.SliceUsedTime++
|
|
|
|
if running.UsedTime >= running.NeedTime {
|
|
running.State = StateFinish
|
|
running.FinishTime = time + 1
|
|
snapshots = append(snapshots, makeSnap(time+1, procs, "", nil, running.Name+" 执行完毕 ✓"))
|
|
} else if running.SliceUsedTime >= timeSlice {
|
|
running.Priority += 3
|
|
if running.UsedTime%3 == 0 && running.UsedTime < running.NeedTime {
|
|
running.State = StateWait
|
|
running.WaitUntil = time + 2
|
|
running.SliceUsedTime = 0
|
|
snapshots = append(snapshots, makeSnap(time+1, procs, "", nil,
|
|
running.Name+" 等待I/O (优先级→"+itoa(running.Priority)+", 唤醒于t="+itoa(running.WaitUntil)+")"))
|
|
} else {
|
|
running.State = StateReady
|
|
running.SliceUsedTime = 0
|
|
readyQueue = append(readyQueue, running)
|
|
snapshots = append(snapshots, makeSnap(time+1, procs, "", buildQueueNames(readyQueue),
|
|
running.Name+" 时间片用完 (优先级→"+itoa(running.Priority)+")"))
|
|
}
|
|
} else {
|
|
queueNames2 := buildQueueNames(readyQueue)
|
|
snapshots = append(snapshots, makeSnap(time+1, procs, running.Name, queueNames2, running.Name+" 继续执行"))
|
|
}
|
|
|
|
time++
|
|
}
|
|
|
|
return SimResult{
|
|
Snapshots: snapshots,
|
|
Algorithm: "基于优先级的时间片轮转",
|
|
AvgTurnaround: calcAvgTurnaround(procs),
|
|
Deadlock: false,
|
|
}
|
|
}
|
|
|
|
func SimulateMLFQ(processes []*PCB, queueTimeSlices [3]int) SimResult {
|
|
procs := make([]*PCB, len(processes))
|
|
for i, p := range processes {
|
|
c := *p
|
|
c.QueueLevel = 0
|
|
c.SliceUsedTime = 0
|
|
procs[i] = &c
|
|
}
|
|
|
|
var snapshots []Snapshot
|
|
queues := [3][]*PCB{}
|
|
time := 0
|
|
maxTime := 0
|
|
for _, p := range procs {
|
|
end := p.ArrivalTime + p.NeedTime*3 + 20
|
|
if end > maxTime {
|
|
maxTime = end
|
|
}
|
|
}
|
|
|
|
for time <= maxTime {
|
|
for _, p := range procs {
|
|
if p.State == StateWait && p.WaitUntil <= time {
|
|
p.State = StateReady
|
|
p.WaitUntil = -1
|
|
queues[p.QueueLevel] = append(queues[p.QueueLevel], p)
|
|
}
|
|
if p.ArrivalTime == time && p.State == StateReady {
|
|
p.QueueLevel = 0
|
|
p.SliceUsedTime = 0
|
|
found := false
|
|
for _, q := range queues[0] {
|
|
if q == p {
|
|
found = true
|
|
break
|
|
}
|
|
}
|
|
if !found {
|
|
queues[0] = append(queues[0], p)
|
|
}
|
|
}
|
|
}
|
|
|
|
running := findRunning(procs)
|
|
|
|
if running != nil {
|
|
preempted := false
|
|
for q := 0; q < 3; q++ {
|
|
sort.Slice(queues[q], func(i, j int) bool {
|
|
return queues[q][i].Priority < queues[q][j].Priority
|
|
})
|
|
if len(queues[q]) > 0 && (q < running.QueueLevel || (q == running.QueueLevel && queues[q][0].Priority < running.Priority)) {
|
|
running.State = StateReady
|
|
queues[running.QueueLevel] = insertSortedByPriority(queues[running.QueueLevel], running)
|
|
running = nil
|
|
preempted = true
|
|
break
|
|
}
|
|
}
|
|
_ = preempted
|
|
}
|
|
|
|
if running == nil {
|
|
selected := selectFromMLFQ(queues)
|
|
if selected == nil {
|
|
if allFinished(procs) {
|
|
snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "✓ 所有进程执行完毕"))
|
|
break
|
|
}
|
|
if allWaitingOrFinished(procs) {
|
|
if !anyWillWake(procs, time) {
|
|
snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "✗ 死锁：所有未完成进程都在等待"))
|
|
return SimResult{Snapshots: snapshots, Algorithm: "多级反馈队列轮转", AvgTurnaround: calcAvgTurnaround(procs), Deadlock: true}
|
|
}
|
|
snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "无就绪进程，等待唤醒..."))
|
|
time++
|
|
continue
|
|
}
|
|
snapshots = append(snapshots, makeMLFQSnap(time, procs, "", queues, "无就绪进程"))
|
|
time++
|
|
continue
|
|
}
|
|
|
|
removeFromQueue(&queues, selected)
|
|
selected.State = StateExecute
|
|
if selected.StartTime == -1 {
|
|
selected.StartTime = time
|
|
}
|
|
running = selected
|
|
}
|
|
|
|
event := running.Name + " 从Q" + itoa(running.QueueLevel) + "执行 (片内已用=" + itoa(running.SliceUsedTime) + "/" + itoa(queueTimeSlices[running.QueueLevel]) + ")"
|
|
snapshots = append(snapshots, makeMLFQSnap(time, procs, running.Name, queues, event))
|
|
|
|
running.UsedTime++
|
|
running.SliceUsedTime++
|
|
qLevel := running.QueueLevel
|
|
ts := queueTimeSlices[qLevel]
|
|
|
|
if running.UsedTime >= running.NeedTime {
|
|
running.State = StateFinish
|
|
running.FinishTime = time + 1
|
|
snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues, running.Name+" 执行完毕 ✓"))
|
|
} else if running.SliceUsedTime >= ts {
|
|
shouldWait := running.UsedTime%3 == 0 && running.UsedTime < running.NeedTime
|
|
if shouldWait {
|
|
running.State = StateWait
|
|
running.WaitUntil = time + 2
|
|
running.SliceUsedTime = 0
|
|
snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues,
|
|
running.Name+" 等待I/O (唤醒于t="+itoa(running.WaitUntil)+")"))
|
|
} else if qLevel < 2 {
|
|
running.QueueLevel = qLevel + 1
|
|
running.State = StateReady
|
|
running.SliceUsedTime = 0
|
|
queues[qLevel+1] = append(queues[qLevel+1], running)
|
|
snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues,
|
|
running.Name+" 降级→Q"+itoa(qLevel+1)))
|
|
} else {
|
|
running.State = StateReady
|
|
running.SliceUsedTime = 0
|
|
queues[2] = append(queues[2], running)
|
|
snapshots = append(snapshots, makeMLFQSnap(time+1, procs, "", queues,
|
|
running.Name+" 重新加入Q2"))
|
|
}
|
|
} else {
|
|
snapshots = append(snapshots, makeMLFQSnap(time+1, procs, running.Name, queues, running.Name+" 继续执行"))
|
|
}
|
|
|
|
time++
|
|
}
|
|
|
|
return SimResult{
|
|
Snapshots: snapshots,
|
|
Algorithm: "多级反馈队列轮转",
|
|
AvgTurnaround: calcAvgTurnaround(procs),
|
|
Deadlock: false,
|
|
}
|
|
}
|
|
|
|
func selectFromMLFQ(queues [3][]*PCB) *PCB {
|
|
for q := 0; q < 3; q++ {
|
|
sort.Slice(queues[q], func(i, j int) bool {
|
|
if queues[q][i].Priority != queues[q][j].Priority {
|
|
return queues[q][i].Priority < queues[q][j].Priority
|
|
}
|
|
return queues[q][i].ArrivalTime < queues[q][j].ArrivalTime
|
|
})
|
|
if len(queues[q]) > 0 {
|
|
return queues[q][0]
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func removeFromQueue(queues *[3][]*PCB, target *PCB) {
|
|
for q := 0; q < 3; q++ {
|
|
for i, p := range queues[q] {
|
|
if p == target {
|
|
queues[q] = append(queues[q][:i], queues[q][i+1:]...)
|
|
return
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
func insertSortedByPriority(queue []*PCB, p *PCB) []*PCB {
|
|
queue = append(queue, p)
|
|
sort.Slice(queue, func(i, j int) bool {
|
|
if queue[i].Priority != queue[j].Priority {
|
|
return queue[i].Priority < queue[j].Priority
|
|
}
|
|
return queue[i].ArrivalTime < queue[j].ArrivalTime
|
|
})
|
|
return queue
|
|
}
|
|
|
|
func buildQueueNames(queue []*PCB) [][]string {
|
|
var names []string
|
|
for _, p := range queue {
|
|
names = append(names, p.Name)
|
|
}
|
|
if names == nil {
|
|
names = []string{}
|
|
}
|
|
return [][]string{names}
|
|
}
|
|
|
|
func buildMLFQQueueNames(queues [3][]*PCB) [][]string {
|
|
var qs [][]string
|
|
for q := 0; q < 3; q++ {
|
|
var names []string
|
|
for _, p := range queues[q] {
|
|
names = append(names, p.Name)
|
|
}
|
|
if names == nil {
|
|
names = []string{}
|
|
}
|
|
qs = append(qs, names)
|
|
}
|
|
return qs
|
|
}
|
|
|
|
func makeMLFQSnap(time int, procs []*PCB, running string, queues [3][]*PCB, event string) Snapshot {
|
|
return makeSnap(time, procs, running, buildMLFQQueueNames(queues), event)
|
|
}
|
|
|
|
func itoa(n int) string {
|
|
if n == 0 {
|
|
return "0"
|
|
}
|
|
neg := false
|
|
if n < 0 {
|
|
neg = true
|
|
n = -n
|
|
}
|
|
s := ""
|
|
for n > 0 {
|
|
s = string(rune('0'+n%10)) + s
|
|
n /= 10
|
|
}
|
|
if neg {
|
|
s = "-" + s
|
|
}
|
|
return s
|
|
}
|
|
|
|
func minInt(a, b int) int {
|
|
if a < b {
|
|
return a
|
|
}
|
|
return b
|
|
}
|