kern
view src/sched.c @ 68:0a205396e1a0
- added a generic red-black tree data structure
- added a VM map as an red-black tree of vm_pages in the process structure
- constructed the vm map of the memory passed by the kernel initially to the first process.
| author | John Tsiombikas <nuclear@mutantstargoat.com> |
|---|---|
| date | Mon, 10 Oct 2011 04:16:01 +0300 |
| parents | 0be4615594df |
| children | 3941e82b07f2 |
line source
1 #include <stdio.h>
2 #include <assert.h>
3 #include "sched.h"
4 #include "proc.h"
5 #include "intr.h"
6 #include "asmops.h"
7 #include "config.h"
9 #define EMPTY(q) ((q)->head == 0)
11 struct proc_list {
12 struct process *head, *tail;
13 };
15 static void idle_proc(void);
16 static void ins_back(struct proc_list *list, struct process *proc);
17 static void ins_front(struct proc_list *list, struct process *proc);
18 static void remove(struct proc_list *list, struct process *proc);
19 static int hash_addr(void *addr);
21 static struct proc_list runq;
22 static struct proc_list zombieq;
24 #define HTBL_SIZE 101
25 static struct proc_list wait_htable[HTBL_SIZE];
28 void schedule(void)
29 {
30 disable_intr();
32 if(EMPTY(&runq)) {
33 if(!get_current_proc()) {
34 /* we're already in the idle process, don't reenter it
35 * or you'll fill up the stack very quickly.
36 */
37 return;
38 }
40 idle_proc();
41 return;
42 }
44 /* if the current process exhausted its timeslice,
45 * move it to the back of the queue.
46 */
47 if(runq.head->ticks_left <= 0) {
48 if(runq.head->next) {
49 struct process *proc = runq.head;
50 remove(&runq, proc);
51 ins_back(&runq, proc);
52 }
54 /* start a new timeslice */
55 runq.head->ticks_left = TIMESLICE_TICKS;
56 }
58 /* always enter context_switch with interrupts disabled */
59 context_switch(runq.head->id);
60 }
62 void add_proc(int pid)
63 {
64 int istate;
65 struct process *proc;
67 istate = get_intr_state();
68 disable_intr();
70 proc = get_process(pid);
72 ins_back(&runq, proc);
73 proc->state = STATE_RUNNABLE;
75 set_intr_state(istate);
76 }
78 /* block the process until we get a wakeup call for address ev */
79 void wait(void *wait_addr)
80 {
81 struct process *p;
82 int hash_idx;
84 disable_intr();
86 p = get_current_proc();
87 assert(p);
89 /* remove it from the runqueue ... */
90 remove(&runq, p);
92 /* and place it in the wait hash table based on sleep_addr */
93 hash_idx = hash_addr(wait_addr);
94 ins_back(wait_htable + hash_idx, p);
96 p->state = STATE_BLOCKED;
97 p->wait_addr = wait_addr;
99 /* call the scheduler to give time to another process */
100 schedule();
101 }
103 /* wake up all the processes sleeping on this address */
104 void wakeup(void *wait_addr)
105 {
106 int hash_idx;
107 struct process *iter;
108 struct proc_list *list;
110 hash_idx = hash_addr(wait_addr);
111 list = wait_htable + hash_idx;
113 iter = list->head;
114 while(iter) {
115 if(iter->wait_addr == wait_addr) {
116 /* found one, remove it, and make it runnable */
117 struct process *p = iter;
118 iter = iter->next;
120 remove(list, p);
121 p->state = STATE_RUNNABLE;
122 ins_back(&runq, p);
123 } else {
124 iter = iter->next;
125 }
126 }
127 }
129 static void idle_proc(void)
130 {
131 /* make sure we send any pending EOIs if needed.
132 * end_of_irq will actually check if it's needed first.
133 */
134 struct intr_frame *ifrm = get_intr_frame();
135 end_of_irq(INTR_TO_IRQ(ifrm->inum));
137 set_current_pid(0);
139 printf("idle loop is running\n");
141 /* make sure interrupts are enabled before halting */
142 while(EMPTY(&runq)) {
143 enable_intr();
144 halt_cpu();
145 disable_intr();
146 }
147 }
150 /* list operations */
151 static void ins_back(struct proc_list *list, struct process *proc)
152 {
153 if(EMPTY(list)) {
154 list->head = proc;
155 } else {
156 list->tail->next = proc;
157 }
159 proc->next = 0;
160 proc->prev = list->tail;
161 list->tail = proc;
162 }
164 static void ins_front(struct proc_list *list, struct process *proc)
165 {
166 if(EMPTY(list)) {
167 list->tail = proc;
168 } else {
169 list->head->prev = proc;
170 }
172 proc->next = list->head;
173 proc->prev = 0;
174 list->head = proc;
175 }
177 static void remove(struct proc_list *list, struct process *proc)
178 {
179 if(proc->prev) {
180 proc->prev->next = proc->next;
181 }
182 if(proc->next) {
183 proc->next->prev = proc->prev;
184 }
185 if(list->head == proc) {
186 list->head = proc->next;
187 }
188 if(list->tail == proc) {
189 list->tail = proc->prev;
190 }
191 }
193 static int hash_addr(void *addr)
194 {
195 return (uint32_t)addr % HTBL_SIZE;
196 }