Scheduler.h 4.68 KB
Newer Older
Martin Karsten's avatar
Martin Karsten committed
1
/******************************************************************************
Martin Karsten's avatar
Martin Karsten committed
2
    Copyright (C) Martin Karsten 2015-2021
Martin Karsten's avatar
Martin Karsten committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
******************************************************************************/
Martin Karsten's avatar
Martin Karsten committed
17
18
#ifndef _Scheduler_h_
#define _Scheduler_h_ 1
Martin Karsten's avatar
Martin Karsten committed
19

Martin Karsten's avatar
Martin Karsten committed
20
#include "runtime/BaseProcessor.h"
Martin Karsten's avatar
Martin Karsten committed
21

22
#if TESTING_LOADBALANCING
Martin Karsten's avatar
Martin Karsten committed
23

24
class IdleManager {
25
26
  volatile ssize_t         fredCounter;
  WorkerLock               procLock;
27
  ProcessorList            waitingProcs;
28
  FredQueue<FredReadyLink> waitingFreds;
Martin Karsten's avatar
Martin Karsten committed
29

Martin Karsten's avatar
Martin Karsten committed
30
  FredStats::IdleManagerStats* stats;
Martin Karsten's avatar
Martin Karsten committed
31

32
  Fred* block(BaseProcessor& proc) {
Martin Karsten's avatar
Martin Karsten committed
33
    procLock.acquire();
34
    if (waitingFreds.empty()) {
35
36
      proc.setHalting(true, _friend<IdleManager>());
      waitingProcs.push_front(proc);
Martin Karsten's avatar
Martin Karsten committed
37
      procLock.release();
38
      return proc.suspend(_friend<IdleManager>());
Martin Karsten's avatar
Martin Karsten committed
39
    } else {
40
      Fred* nextFred = waitingFreds.pop();
Martin Karsten's avatar
Martin Karsten committed
41
      procLock.release();
42
      return nextFred;
Martin Karsten's avatar
Martin Karsten committed
43
44
45
    }
  }

46
  void unblock(Fred& fred) {
Martin Karsten's avatar
Martin Karsten committed
47
48
    procLock.acquire();
    if (waitingProcs.empty()) {
49
      waitingFreds.push(fred);
Martin Karsten's avatar
Martin Karsten committed
50
51
      procLock.release();
    } else {
52
53
54
55
56
57
58
      BaseProcessor* nextProc = fred.getProcessor(_friend<IdleManager>());
      if (nextProc->isHalting(_friend<IdleManager>())) {
        waitingProcs.remove(*nextProc);
      } else {
        nextProc = waitingProcs.pop_front();
      }
      nextProc->setHalting(false, _friend<IdleManager>());
Martin Karsten's avatar
Martin Karsten committed
59
      procLock.release();
60
      nextProc->resume(&fred, _friend<IdleManager>());
Martin Karsten's avatar
Martin Karsten committed
61
62
63
64
    }
  }

public:
Martin Karsten's avatar
Martin Karsten committed
65
  IdleManager(cptr_t parent) : fredCounter(0) { stats = new FredStats::IdleManagerStats(this, parent); }
Martin Karsten's avatar
Martin Karsten committed
66

67
68
69
70
  void reset(cptr_t parent, _friend<EventScope>) {
    new (stats) FredStats::IdleManagerStats(this, parent);
  }

71
72
73
  bool tryGetReadyFred() {
    ssize_t c = fredCounter;
    return (c > 0) && __atomic_compare_exchange_n(&fredCounter, &c, c-1, false, __ATOMIC_RELAXED, __ATOMIC_RELAXED);
Martin Karsten's avatar
Martin Karsten committed
74
75
  }

76
  Fred* getReadyFred(BaseProcessor& proc) {
77
    ssize_t fredCount = __atomic_fetch_sub(&fredCounter, 1, __ATOMIC_RELAXED);
78
    if (fredCount > 0) {
79
      stats->ready.count(fredCount);     // number of freds ready
80
81
      return nullptr;
    } else {
Martin Karsten's avatar
Martin Karsten committed
82
      stats->blocked.count(1-fredCount); // number of procs waiting including this one
83
84
      return block(proc);
    }
Martin Karsten's avatar
Martin Karsten committed
85
86
  }

87
88
89
  bool addReadyFred(Fred& f) {
    if (__atomic_add_fetch(&fredCounter, 1, __ATOMIC_RELAXED) > 0) return false;
    unblock(f);
Martin Karsten's avatar
Martin Karsten committed
90
91
92
93
94
95
    return true;
  }
};

#else

96
class IdleManager {
Martin Karsten's avatar
Martin Karsten committed
97
public:
98
  IdleManager(cptr_t) {}
99
  void reset(cptr_t, _friend<EventScope>) {}
100
};
Martin Karsten's avatar
Martin Karsten committed
101
102
103

#endif

104
class Scheduler {
Martin Karsten's avatar
Martin Karsten committed
105
protected:
Martin Karsten's avatar
Martin Karsten committed
106
107
108
109
  WorkerLock     ringLock;
  size_t         ringCount;
  BaseProcessor* placeProc;
  BaseProcessor  stagingProc;
Martin Karsten's avatar
Martin Karsten committed
110
111

public:
112
113
  IdleManager idleManager;
  Scheduler() : ringCount(0), placeProc(nullptr), stagingProc(*this, "Staging    "), idleManager(this) {}
Martin Karsten's avatar
Martin Karsten committed
114
  ~Scheduler() {
Martin Karsten's avatar
Martin Karsten committed
115
    ScopedLock<WorkerLock> sl(ringLock);
Martin Karsten's avatar
Martin Karsten committed
116
    RASSERT(!ringCount, ringCount);
Martin Karsten's avatar
Martin Karsten committed
117
118
119
  }

  void addProcessor(BaseProcessor& proc) {
Martin Karsten's avatar
Martin Karsten committed
120
    ScopedLock<WorkerLock> sl(ringLock);
Martin Karsten's avatar
Martin Karsten committed
121
    if (placeProc == nullptr) {
122
      ProcessorRingGlobal::close(proc);
Martin Karsten's avatar
Martin Karsten committed
123
124
      placeProc = &proc;
    } else {
125
      ProcessorRingGlobal::insert_after(*placeProc, proc);
Martin Karsten's avatar
Martin Karsten committed
126
    }
127
    ProcessorRingLocal::close(proc);
Martin Karsten's avatar
Martin Karsten committed
128
129
130
131
    ringCount += 1;
  }

  void removeProcessor(BaseProcessor& proc) {
Martin Karsten's avatar
Martin Karsten committed
132
    ScopedLock<WorkerLock> sl(ringLock);
Martin Karsten's avatar
Martin Karsten committed
133
    RASSERT0(placeProc);
Martin Karsten's avatar
Martin Karsten committed
134
    // move placeProc, if necessary
135
    if (placeProc == &proc) placeProc = ProcessorRingGlobal::next(*placeProc);
Martin Karsten's avatar
Martin Karsten committed
136
137
    // ring empty?
    if (placeProc == &proc) placeProc = nullptr;
138
139
    ProcessorRingGlobal::remove(proc);
    ProcessorRingLocal::remove(proc);
Martin Karsten's avatar
Martin Karsten committed
140
141
142
    ringCount -= 1;
  }

143
  BaseProcessor& placement(_friend<Fred>, bool staging = false) {
Martin Karsten's avatar
Martin Karsten committed
144
#if TESTING_LOADBALANCING
145
    if (staging) return stagingProc;
146
147
#else
    (void)staging;
Martin Karsten's avatar
Martin Karsten committed
148
#endif
Martin Karsten's avatar
Martin Karsten committed
149
    RASSERT0(placeProc);
150
    // ring insert is traversal-safe, so could use separate 'placeLock' here
Martin Karsten's avatar
Martin Karsten committed
151
    ScopedLock<WorkerLock> sl(ringLock);
152
    placeProc = ProcessorRingGlobal::next(*placeProc);
Martin Karsten's avatar
Martin Karsten committed
153
154
155
156
    return *placeProc;
  }

#if TESTING_LOADBALANCING
157
  Fred* stage()  {
Martin Karsten's avatar
Martin Karsten committed
158
    return stagingProc.tryDequeue(_friend<Scheduler>());
Martin Karsten's avatar
Martin Karsten committed
159
160
161
162
  }
#endif
};

Martin Karsten's avatar
Martin Karsten committed
163
#endif /* _Scheduler_h_ */