sched.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630
  1. /* CFS-lite scheduler core: per-CPU state, a weighted run queue, a sorted sleep
  2. * list and the timer entry.
  3. *
  4. * Weight is an integer 1..SCHED_WEIGHT_MAX. Each ready process has a 64-bit
  5. * virtual runtime advanced by (elapsed ticks * stride) while it runs, where
  6. * stride = SCHED_WEIGHT_SCALE / weight. The smallest vruntime gets the CPU,
  7. * so the long-term share is proportional to the weight. A 10 ms slice bounds
  8. * latency; a wake-up gets clamped to the current minimum vruntime so an
  9. * interactive process is scheduled promptly without accumulating unbounded
  10. * credit.
  11. *
  12. * The run queue is a single global list for now. That is also the shape an
  13. * SMP version wants: one queue protected by a lock, with per-CPU current.
  14. */
  15. #include "sched.h"
  16. #include "io.h"
  17. #include "paging.h"
  18. #include "process.h"
  19. #include "syscall.h"
  20. #include "timer.h"
  21. #include "tss.h"
  22. /* 2^20 / weight, so weight 8 advances 131072 per tick and weight 16 half
  23. * that. The product fits comfortably in the 64-bit vruntime. */
  24. #define SCHED_WEIGHT_SCALE (1u << 20)
  25. struct cpu cpus[MAX_CPUS];
  26. unsigned int cpu_count;
  27. unsigned int cpu_gs_ready;
  28. static struct process *runq_head, *runq_tail;
  29. static struct process *sleep_head, *sleep_tail;
  30. static unsigned int wakeups;
  31. /* switch.S reads these two facts directly: current at %gs:0 and esp at
  32. * offset 0 of the process. Keep them true. */
  33. _Static_assert(__builtin_offsetof(struct cpu, current) == 0,
  34. "switch.S reads current from %gs:0");
  35. _Static_assert(__builtin_offsetof(struct process, esp) == 0,
  36. "switch.S saves the interrupted esp at offset 0");
  37. static inline unsigned int irq_save_disable(void)
  38. {
  39. unsigned int flags;
  40. __asm__ volatile ("pushfl; popl %0; cli" : "=r"(flags));
  41. return flags;
  42. }
  43. static inline void irq_restore(unsigned int flags)
  44. {
  45. __asm__ volatile ("pushl %0; popfl" : : "r"(flags));
  46. }
  47. static inline unsigned long long weight_stride(unsigned int weight)
  48. {
  49. if (weight < 1)
  50. weight = 1;
  51. if (weight > SCHED_WEIGHT_MAX)
  52. weight = SCHED_WEIGHT_MAX;
  53. return (unsigned long long)(SCHED_WEIGHT_SCALE / weight);
  54. }
  55. /* ---- run queue (interrupts off) ---- */
  56. static void runq_add_locked(struct process *p)
  57. {
  58. if (p->on_runq)
  59. return;
  60. p->on_runq = 1;
  61. p->run_prev = runq_tail;
  62. p->run_next = 0;
  63. if (runq_tail)
  64. runq_tail->run_next = p;
  65. else
  66. runq_head = p;
  67. runq_tail = p;
  68. }
  69. static void runq_del_locked(struct process *p)
  70. {
  71. if (!p->on_runq)
  72. return;
  73. if (p->run_prev)
  74. p->run_prev->run_next = p->run_next;
  75. else
  76. runq_head = p->run_next;
  77. if (p->run_next)
  78. p->run_next->run_prev = p->run_prev;
  79. else
  80. runq_tail = p->run_prev;
  81. p->on_runq = 0;
  82. p->run_next = p->run_prev = 0;
  83. }
  84. static void sleepq_add_locked(struct process *p)
  85. {
  86. struct process *it = sleep_head, *prev = 0;
  87. while (it && (int)(it->wake_ms - p->wake_ms) <= 0) {
  88. prev = it;
  89. it = it->sleep_next;
  90. }
  91. p->sleep_prev = prev;
  92. p->sleep_next = it;
  93. if (prev)
  94. prev->sleep_next = p;
  95. else
  96. sleep_head = p;
  97. if (it)
  98. it->sleep_prev = p;
  99. else
  100. sleep_tail = p;
  101. }
  102. static void sleepq_del_locked(struct process *p)
  103. {
  104. if (p->sleep_prev)
  105. p->sleep_prev->sleep_next = p->sleep_next;
  106. else if (sleep_head == p)
  107. sleep_head = p->sleep_next;
  108. if (p->sleep_next)
  109. p->sleep_next->sleep_prev = p->sleep_prev;
  110. else if (sleep_tail == p)
  111. sleep_tail = p->sleep_prev;
  112. p->sleep_next = p->sleep_prev = 0;
  113. }
  114. void wait_queue_init(struct wait_queue *wq)
  115. {
  116. wq->head = wq->tail = 0;
  117. }
  118. static void waitq_add_locked(struct wait_queue *wq, struct process *p)
  119. {
  120. p->waiting_on = wq;
  121. p->wait_next = 0;
  122. p->wait_prev = wq->tail;
  123. if (wq->tail)
  124. wq->tail->wait_next = p;
  125. else
  126. wq->head = p;
  127. wq->tail = p;
  128. }
  129. static void waitq_del_locked(struct process *p)
  130. {
  131. struct wait_queue *wq = p->waiting_on;
  132. if (!wq)
  133. return;
  134. if (p->wait_prev)
  135. p->wait_prev->wait_next = p->wait_next;
  136. else
  137. wq->head = p->wait_next;
  138. if (p->wait_next)
  139. p->wait_next->wait_prev = p->wait_prev;
  140. else
  141. wq->tail = p->wait_prev;
  142. p->wait_next = p->wait_prev = 0;
  143. p->waiting_on = 0;
  144. }
  145. /* Current minimum vruntime among READY processes. If nothing is ready, use
  146. * the running process's vruntime so a freshly woken process does not receive
  147. * an enormous credit relative to a CPU-bound one. */
  148. static unsigned long long min_vruntime_locked(void)
  149. {
  150. struct process *p;
  151. unsigned long long min = 0;
  152. int found = 0;
  153. for (p = runq_head; p; p = p->run_next) {
  154. if (!found || p->vruntime < min) {
  155. min = p->vruntime;
  156. found = 1;
  157. }
  158. }
  159. if (found)
  160. return min;
  161. p = current_proc();
  162. return (p && p != this_cpu()->idle) ? p->vruntime : 0;
  163. }
  164. static void account_locked(struct process *p)
  165. {
  166. unsigned int elapsed;
  167. if (!p || p == this_cpu()->idle || p->state != PROC_RUNNING)
  168. return;
  169. elapsed = get_ticks_ms() - p->slice_start;
  170. if (elapsed) {
  171. p->vruntime += (unsigned long long)elapsed * p->stride;
  172. p->slice_start = get_ticks_ms();
  173. }
  174. }
  175. /* Clamp a woken process to the current minimum and make it runnable. */
  176. static void wake_locked(struct process *p)
  177. {
  178. struct process *cur = current_proc();
  179. struct cpu *c = this_cpu();
  180. if (!p || p->state == PROC_DEAD || p->state == PROC_UNUSED)
  181. return;
  182. if (p->waiting_on)
  183. waitq_del_locked(p);
  184. if (p->state == PROC_SLEEPING)
  185. sleepq_del_locked(p);
  186. p->state = PROC_READY;
  187. if (p->vruntime < min_vruntime_locked())
  188. p->vruntime = min_vruntime_locked();
  189. runq_add_locked(p);
  190. wakeups++;
  191. if (cur && (cur == c->idle ||
  192. p->weight >= cur->weight))
  193. c->need_resched = 1;
  194. }
  195. void sched_add_ready(struct process *p)
  196. {
  197. if (!p->weight) {
  198. p->weight = SCHED_WEIGHT_DEFAULT;
  199. p->stride = weight_stride(p->weight);
  200. p->vruntime = min_vruntime_locked();
  201. }
  202. p->state = PROC_READY;
  203. runq_add_locked(p);
  204. }
  205. void sched_unlink(struct process *p)
  206. {
  207. runq_del_locked(p);
  208. if (p->waiting_on)
  209. waitq_del_locked(p);
  210. if (p->state == PROC_SLEEPING)
  211. sleepq_del_locked(p);
  212. }
  213. void sched_set_weight_locked(struct process *p, unsigned int weight)
  214. {
  215. if (!p)
  216. return;
  217. if (weight < 1)
  218. weight = 1;
  219. if (weight > SCHED_WEIGHT_MAX)
  220. weight = SCHED_WEIGHT_MAX;
  221. if (p->state == PROC_RUNNING)
  222. account_locked(p);
  223. p->weight = weight;
  224. p->stride = weight_stride(weight);
  225. }
  226. /* Add the current process to a wait queue. The caller holds interrupts off
  227. * and must restore the flags and call sched_yield() itself. */
  228. void sched_block_on_locked(struct wait_queue *wq)
  229. {
  230. struct process *p = current_proc();
  231. if (!p)
  232. return;
  233. runq_del_locked(p);
  234. waitq_add_locked(wq, p);
  235. p->state = PROC_BLOCKED;
  236. p->on_runq = 0;
  237. }
  238. void sched_block_on(struct wait_queue *wq)
  239. {
  240. unsigned int flags;
  241. if (this_cpu()->preempt_count)
  242. return;
  243. flags = irq_save_disable();
  244. sched_block_on_locked(wq);
  245. irq_restore(flags);
  246. sched_yield();
  247. }
  248. /* Block on a wait queue with a deadline. Either a waiter wake or the sleep
  249. * list expiry removes the process from both queues. */
  250. void sched_block_timeout(struct wait_queue *wq, unsigned int ms)
  251. {
  252. struct process *p = current_proc();
  253. unsigned int flags;
  254. if (!p)
  255. return;
  256. if (ms == 0) {
  257. sched_block_on(wq);
  258. return;
  259. }
  260. if (this_cpu()->preempt_count)
  261. return;
  262. flags = irq_save_disable();
  263. p->wake_ms = get_ticks_ms() + ms;
  264. p->state = PROC_SLEEPING;
  265. runq_del_locked(p);
  266. waitq_add_locked(wq, p);
  267. sleepq_add_locked(p);
  268. irq_restore(flags);
  269. sched_yield();
  270. }
  271. static void wake_one_locked(struct wait_queue *wq)
  272. {
  273. struct process *p = wq->head;
  274. if (!p)
  275. return;
  276. waitq_del_locked(p);
  277. if (p->state == PROC_BLOCKED || p->state == PROC_SLEEPING)
  278. wake_locked(p);
  279. }
  280. void wait_wake_one(struct wait_queue *wq)
  281. {
  282. unsigned int flags = irq_save_disable();
  283. wake_one_locked(wq);
  284. irq_restore(flags);
  285. }
  286. void wait_wake_all(struct wait_queue *wq)
  287. {
  288. unsigned int flags = irq_save_disable();
  289. while (wq->head)
  290. wake_one_locked(wq);
  291. irq_restore(flags);
  292. }
  293. void sched_init(void)
  294. {
  295. unsigned int i;
  296. cpu_count = 1;
  297. runq_head = runq_tail = 0;
  298. sleep_head = sleep_tail = 0;
  299. wakeups = 0;
  300. for (i = 0; i < MAX_CPUS; i++) {
  301. cpus[i].current = 0;
  302. cpus[i].idle = 0;
  303. cpus[i].id = i;
  304. cpus[i].lapic_id = 0;
  305. cpus[i].need_resched = 0;
  306. cpus[i].preempt_count = 0;
  307. cpus[i].idle_ticks = 0;
  308. cpus[i].switches = 0;
  309. }
  310. }
  311. static void sched_switch_to(struct process *next)
  312. {
  313. struct cpu *c = this_cpu();
  314. unsigned int cr3 = paging_current_cr3();
  315. if (next->cr3 && next->cr3 != cr3) {
  316. __asm__ volatile ("movl %0, %%cr3"
  317. :
  318. : "r"(next->cr3)
  319. : "memory");
  320. }
  321. if (c->tss && next->kstack_top)
  322. c->tss->esp0 = next->kstack_top;
  323. }
  324. /* Pick the READY process with the smallest vruntime that may run on this
  325. * CPU. Ties go to the lower pid for determinism. */
  326. static struct process *pick_locked(void)
  327. {
  328. struct process *p, *best = 0;
  329. unsigned int mask = 1u << this_cpu()->id;
  330. for (p = runq_head; p; p = p->run_next) {
  331. if (!(p->affinity & mask))
  332. continue;
  333. if (!best || p->vruntime < best->vruntime ||
  334. (p->vruntime == best->vruntime && p->pid < best->pid))
  335. best = p;
  336. }
  337. return best;
  338. }
  339. static void wake_sleepers_locked(void)
  340. {
  341. unsigned int now = get_ticks_ms();
  342. while (sleep_head && (int)(sleep_head->wake_ms - now) <= 0) {
  343. struct process *p = sleep_head;
  344. sleepq_del_locked(p);
  345. p->state = PROC_READY;
  346. p->wake_ms = 0;
  347. wake_locked(p);
  348. }
  349. }
  350. /*
  351. * CFS-lite schedule. Called from the PIT stub (after ESP has been saved) or
  352. * from the int 0x81 gate, always with interrupts disabled.
  353. */
  354. void schedule(void)
  355. {
  356. struct cpu *c = this_cpu();
  357. struct process *cur = c->current;
  358. struct process *next;
  359. if (cur && cur != c->idle) {
  360. if (cur->state == PROC_RUNNING) {
  361. account_locked(cur);
  362. cur->state = PROC_READY;
  363. runq_add_locked(cur);
  364. } else if (cur->state == PROC_READY) {
  365. /* Woken between setting BLOCKED/SLEEPING and entering
  366. * the gate: already on the run queue. */
  367. } else if (cur->state == PROC_DEAD) {
  368. /* Keep the PCB alive until the kworker can free it, but
  369. * unpublish it immediately. */
  370. process_zombie_add(cur);
  371. }
  372. }
  373. next = pick_locked();
  374. if (!next) {
  375. next = c->idle;
  376. if (!next) {
  377. for (;;)
  378. __asm__ volatile ("cli; hlt");
  379. }
  380. }
  381. if (next != cur) {
  382. if (cur)
  383. cur->on_cpu = PROC_NO_CPU;
  384. c->switches++;
  385. }
  386. runq_del_locked(next);
  387. next->state = PROC_RUNNING;
  388. next->on_cpu = c->id;
  389. next->last_cpu = c->id;
  390. next->slice_start = get_ticks_ms();
  391. c->current = next;
  392. c->need_resched = 0;
  393. sched_switch_to(next);
  394. }
  395. void sched_yield(void)
  396. {
  397. struct cpu *c = this_cpu();
  398. /* Blocking helpers must not be used inside a preempt-disabled section.
  399. * If one is, record the request instead of switching with the count
  400. * still owned by the old process. */
  401. if (c->preempt_count) {
  402. c->need_resched = 1;
  403. return;
  404. }
  405. __asm__ volatile ("int $0x81" ::: "memory");
  406. }
  407. void sched_sleep_ms(unsigned int ms)
  408. {
  409. struct process *p = current_proc();
  410. unsigned int flags;
  411. if (!p)
  412. return;
  413. if (ms == 0) {
  414. sched_yield();
  415. return;
  416. }
  417. if (this_cpu()->preempt_count)
  418. return; /* sleeping inside a non-preemptible section is invalid */
  419. flags = irq_save_disable();
  420. p->wake_ms = get_ticks_ms() + ms;
  421. p->state = PROC_SLEEPING;
  422. runq_del_locked(p);
  423. sleepq_add_locked(p);
  424. irq_restore(flags);
  425. sched_yield();
  426. }
  427. /* Called from the PIT after ticks has been incremented. Returns 1 when the
  428. * assembly should call schedule(). */
  429. int sched_tick_bsp(void)
  430. {
  431. struct cpu *c = this_cpu();
  432. struct process *p = c->current;
  433. if (p) {
  434. p->cpu_ticks++;
  435. if (p == c->idle)
  436. c->idle_ticks++;
  437. }
  438. wake_sleepers_locked();
  439. if (c->preempt_count) {
  440. if (p && p != c->idle && p->state == PROC_RUNNING &&
  441. (unsigned int)(get_ticks_ms() - p->slice_start) >=
  442. SCHED_SLICE_TICKS)
  443. c->need_resched = 1;
  444. return 0;
  445. }
  446. if (!p)
  447. return 0;
  448. if (p == c->idle) {
  449. if (runq_head) {
  450. c->need_resched = 1;
  451. return 1;
  452. }
  453. return 0;
  454. }
  455. if (p->state != PROC_RUNNING) {
  456. c->need_resched = 1;
  457. return 1;
  458. }
  459. if ((unsigned int)(get_ticks_ms() - p->slice_start) >= SCHED_SLICE_TICKS)
  460. c->need_resched = 1;
  461. return c->need_resched ? 1 : 0;
  462. }
  463. void preempt_disable(void)
  464. {
  465. this_cpu()->preempt_count++;
  466. }
  467. void preempt_enable(void)
  468. {
  469. struct cpu *c = this_cpu();
  470. if (c->preempt_count)
  471. c->preempt_count--;
  472. }
  473. int sched_snapshot(struct sys_schedinfo *out)
  474. {
  475. unsigned int flags, i;
  476. struct process *p;
  477. if (!out)
  478. return -1;
  479. flags = irq_save_disable();
  480. out->ncpus = cpu_count;
  481. out->runnable = 0;
  482. for (p = runq_head; p; p = p->run_next)
  483. out->runnable++;
  484. out->sleeping = 0;
  485. for (p = sleep_head; p; p = p->sleep_next)
  486. out->sleeping++;
  487. out->blocked = 0;
  488. for (i = 0; i < PROC_MAX; i++) {
  489. p = procs[i];
  490. if (p && p->state == PROC_BLOCKED)
  491. out->blocked++;
  492. }
  493. out->zombies = process_zombie_count();
  494. out->switches = cpus[0].switches;
  495. out->wakeups = wakeups;
  496. out->idle_ticks = cpus[0].idle_ticks;
  497. out->slice_ticks = SCHED_SLICE_TICKS;
  498. irq_restore(flags);
  499. return 0;
  500. }
  501. static void sched_put_dec(unsigned int n)
  502. {
  503. char buf[12];
  504. unsigned int i = sizeof(buf) - 1;
  505. buf[i] = '\0';
  506. if (n == 0) {
  507. io_putchar('0');
  508. return;
  509. }
  510. while (n && i > 0) {
  511. buf[--i] = (char)('0' + (n % 10));
  512. n /= 10;
  513. }
  514. io_putstr(buf + i);
  515. }
  516. void sched_print(void)
  517. {
  518. struct sys_schedinfo s;
  519. unsigned int uptime, idle_pm, up_s, idle_s, idle_frac;
  520. if (sched_snapshot(&s) != 0)
  521. return;
  522. uptime = get_ticks_ms();
  523. /* Avoid 64-bit division: scale to seconds first. ticks wraps at ~49
  524. * days, so idle_s * 1000 stays within 32 bits for the useful range. */
  525. up_s = uptime / 1000u;
  526. if (up_s == 0) {
  527. idle_pm = (s.idle_ticks >= uptime) ? 1000 : 0;
  528. } else {
  529. idle_s = s.idle_ticks / 1000u;
  530. idle_frac = s.idle_ticks % 1000u;
  531. idle_pm = (idle_s * 1000u) / up_s;
  532. idle_pm += (idle_frac * 1000u / up_s) / 1000u;
  533. if (idle_pm > 1000u)
  534. idle_pm = 1000u;
  535. }
  536. io_putstr("sched: cfs, ");
  537. sched_put_dec(s.ncpus);
  538. io_putstr(" cpu, ");
  539. sched_put_dec(s.slice_ticks);
  540. io_putstr(" ms slice\nrunq ");
  541. sched_put_dec(s.runnable);
  542. io_putstr(" sleep ");
  543. sched_put_dec(s.sleeping);
  544. io_putstr(" block ");
  545. sched_put_dec(s.blocked);
  546. io_putstr(" zombie ");
  547. sched_put_dec(s.zombies);
  548. io_putstr("\nswitches ");
  549. sched_put_dec(s.switches);
  550. io_putstr(" wakeups ");
  551. sched_put_dec(s.wakeups);
  552. io_putstr(" idle ");
  553. sched_put_dec(idle_pm / 10);
  554. io_putchar('.');
  555. io_putchar((char)('0' + idle_pm % 10));
  556. io_putstr("%\n");
  557. }