Mercurial > hg > Game > CbCTaskManager
changeset 0:5b089096921f
first commit.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 18 Dec 2009 21:57:05 +0900 |
parents | |
children | aef83aed7a07 |
files | DataSegment.cc List.c List.h Task.cbc Task.h TaskManager.cbc TaskManager.h TaskQueue.c TaskScheduler.cbc TaskScheduler.h memo.txt test/list/Makefile test/list/testlist.c test/scheduler/Makefile test/scheduler/test_sched.cbc |
diffstat | 15 files changed, 926 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/DataSegment.cc Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,109 @@ +/* user defined */ +DataSegment tree { + DataSegment tree first; + DataSegment tree second; + int v; +}; +/* replace above to below. */ +typedef int32_t DS_offset; +struct tree { + /* system defined. */ + struct { + int allocated_size; + int size; + DS_offset parent; + } + /* user defined. */ + DS_offset first; + DS_offset second; + void *v; +} + +tree a = new tree(); +newDS(type) { + data = malloc(defaultsize); + data->allocated_size = defaultsize; + data->size = sizeof(type); + data->parent = 0; + return data; +} + +a->first = othertree; // 完全にコピーされる +// 次のように扱われる +copyDS(DS a, field fld, DS othertree) { + DS top; + top = a; + while (top->parent!=0) { + top = top + top->parent; + } + + DS newspace; + //if (top->allocated_size < top->size + othertree->size) realloc(); + newspace = top + top->size; + top->size += othertree->size; + + memcpy(newspace, othertree, othertree->size); + a->fld = newspace - a; + newspace->parent = a - newspace; +} + +*(a->first); + *(a + a->first); + +//deleteはできない + + + + +#if 0 + +class DS_offset { + uint32_t offset; +} +/* */ +class DataSegmentBase { + int allocated_size; + int size; + DS_offset parent; +}; + +DataSegment tree { + DataSegment tree first; + DataSegment tree second; + int v; +}; +class tree : DataSegmentBase { + DS_offset first; + DS_offset second; + int v; +}; + +DataSegmentBase::operator new() { +} +DS_offset::operator =(DataSegmentBase ) { +} +#endif + +/* + * ------------------------------------- + * | Sfsv|first|second| | + * ------------------------------------- + * + */ +void +main() { + DataSegment tree a = new DataSegment tree; + a->first = null; + a->second = null; + a->v = "aiueo"; + + DataSegment tree top = new DataSegment tree; + a->first = a; + //a->first = new DataSegment tree; + + a->first->first = new DataSegment tree; +} + + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/List.c Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,81 @@ +#include<stdlib.h> + +#include"List.h" + +List * +_listAddFirst(List* top, void *data) +{ + List *newlist; + if (!top) { + newlist = malloc(sizeof(struct _List)); + newlist->data = data; + newlist->next = newlist; + newlist->prev = newlist; + return newlist; + } + List *last = top->prev; + + newlist = malloc(sizeof(struct _List)); + newlist->data = data; + newlist->next = top; + newlist->prev = last; + + top->prev = newlist; + last->next = newlist; + return newlist; +} + +List * +_listRemove(List *top, void *data) +{ + List *t; + if (top->data==data) { + if (top->next==top) { + free(top); + return NULL; + } + List *newtop = top->next; + top->next->prev = top->prev; + top->prev->next = top->next; + free(top); + return newtop; + } + for (t=top->next; t!=top; t=t->next) { + if (t->data==data) { + t->next->prev = t->prev; + t->prev->next = t->next; + free(t); + return top; + } + } + return top; +} + +void * +_listGetnthData(List *top, int n) +{ + List *t; + + for (t=top; n>0; n--) { + t = t->next; + if (t==top) return NULL; + } + + return t->data; +} + +void +_listApply(List *top, ApplyFn fn, void *arg) { + List *t = top; + do { + fn(t->data, arg); + t = t->next; + } while ( t!=top ); +} + + + + + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/List.h Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,17 @@ +#ifndef _LIST_H +#define _LIST_H + +typedef struct _List { + void *data; + struct _List *next; + struct _List *prev; +} List; + +List * _listAddFirst(List*, void *); +List * _listRemove(List *, void *); +void * _listGetnthData(List *, int); + +typedef int (*ApplyFn)(void*,void*); +void _listApply(List *, ApplyFn, void *); + +#endif /* !_LIST_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Task.cbc Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,107 @@ + + +typedef __code (*Scheduler)(); +typedef __code (*Taskrun)(Scheduler, void*, void*); + +typedef struct _Task { + Taskrun run; + + TaskList waiter; // List of tasks waiting for me :-P + TaskList waitee; // List of tasks keep me waiting :-( +} Task; + + +typedef struct _TaskList { + Task *task; + struct _TaskList *next; + struct _TaskList *prev; +} TaskList; + +/* + * use this function like below. + * list = listAddFirst(list, task); + */ +TaskList * +listAddFirst(TaskList* top, Task *task) +{ + if (!top) { + newlist = malloc(sizeof(struct _TaskList)); + newlist->task = task; + newlist->next = newlist; + newlist->prev = newlist; + return newlist; + } + TaskList *last = top->prev; + + newlist = malloc(sizeof(struct _TaskList)); + newlist->task = task; + newlist->next = top; + newlist->prev = last; + + top->prev = newlist; + last->next = newlist; + return newlist; +} + +TaskList * +listAddLast(TaskList* top, Task *task) +{ + /* + if (!top) { + newlist = malloc(sizeof(struct _TaskList)); + newlist->task = task; + newlist->next = newlist; + newlist->prev = newlist; + return newlist; + } + TaskList *last = top->prev; + + newlist = malloc(sizeof(struct _TaskList)); + newlist->task = task; + newlist->next = top; + newlist->prev = last; + + top->prev = newlist; + last->next = newlist; + return newlist; + */ +} + +TaskList * +listRemove(TaskList *top, Task *task) +{ + TaskList *t; + if (top->task==task) { + if (top->next==top) { + free(top); + return NULL; + } + TaskList *newtop = top->next; + top->next->prev = top->prev; + top->prev->next = top->next; + free(top); + return newtop; + } + for (t=top->next; t!=top; t=t->next) { + if (t->task==task) { + t->next->prev = t->prev; + t->prev->next = t->next; + free(t); + return top; + } + } + return top; +} + +typedef int (*ApplyFn)(Task*,void*); + +listApply(TaskList *top, ApplyFn fn, void *arg) { + t = top; + do { + fn(t->task, arg); + t = t->next; + } while ( t!=top ); +} + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Task.h Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,16 @@ +#ifndef _TASK_H +#define _TASK_H + +typedef __code (*Taskrun)(__code(*)(void*,void*,void*), void*, void*); +typedef __code (*Scheduler)(__code(*)(void*,void*,void*), void*, void*); +//typedef __code (*Scheduler)(Taskrun, void*, void*); +//typedef __code (*Taskrun)(Scheduler, void*, void*); +#define END (NULL) + +enum cpu { + ANY = 0, + MAIN, + SUB, +}; + +#endif /* _TASK_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/TaskManager.cbc Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,95 @@ +#include "TaskManager.h" + +TaskQueue waitingQueue; +TaskQueue activeQueue; + +/* + * TaskManager's main loop. + * + * while (1) { + * checkFinishedTask(); // to scheduler. + * wait2active(); + * while (actQisnotempty) { + * task = pollFirst(actQ); + * executeTask(task); // to scheduler. + * } + * } + */ +__code TManagerStart() +/* active, waitngタスクリストを整理 */ +{ + list = activeQueue; + goto executeTasklist(list); +} + +__code executeTasklist() +/* */ +{ + if (0 < activeQueue->length) { + goto TManagerLoop(); + } + task = pollFirst(activeQueue); + + /* + * rbuff, wbuffの用意 + */ + goto task->run(TManagerReturnEntry, rbuff, wbuff); + /* Taskへ */ +} + +__code TManagerReturnEntry() +/* Taskから戻ってくるコードセグメント */ +{ + /* + * 依存していたtaskに通知? + */ + goto executeTasklist(list->cdr); +} + +__code TManagerLoop() +{ + /* + * waitingTaskからactiveTaskへ + */ + + goto TManagerStart(); +} + + +__code sched() +{ + TaskList *t = waiter; + Task *t; + for (; t!=;); +} + + +/* belows is Interfaces for Users. */ +/* it may be replace to code segment. but how? */ + +Task *newTask(int task_id) +{ + static int id=0; // 今は使ってない… 使う? + task = allocate(sizeof(Task)); + + task->taskclass = taskclasses[task_id]; + task->id = id; + task->waiter = NULL; + task->waitee = NULL; + + return task; +} + +void setData(Task *task, void *rbuff, size_t rs, void *wbuff, size_t ws) +{ + task->rbuff = rbuff; + task->wbuff = wbuff; + task->rsize = rsize; + task->wsize = wsize; +} + +void spawn(Task *task) +{ +} + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/TaskManager.h Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,46 @@ +#ifndef _TASKMANAGER_H +#define _TASKMANAGER_H +#include <stdlib.h> +#include "List.h" + +typedef List TaskList; +// inline functionのがいいか + + +typedef __code (*Taskrun)(__code(*)(void*,void*,void*), void*, void*); +typedef __code (*Scheduler)(__code(*)(void*,void*,void*), void*, void*); +//typedef __code (*Scheduler)(Taskrun, void*, void*); +//typedef __code (*Taskrun)(Scheduler, void*, void*); +#define END (NULL) + +enum cpu { + ANY = 0, + MAIN, + SUB, +}; + +/* C++CeriumでのTaskObjectにあたる */ +typedef struct _taskclass { + Taskrun run; + char *name; + enum cpu cputype; +} TaskClass; + +/* C++CeriumでのHTaskにあたる */ +typedef struct _Task { + TaskClass taskclass; + unsigned int id; // is it needed? + + void *rbuff; + void *wbuff; + size_t rsize; + size_t wsize; + + TaskList waiter; // List of tasks waiting for me :-P + TaskList waitee; // List of tasks keep me waiting :-( +} Task; + +extern int max_taskclass; /* defined by USERs. */ +extern TaskClass taskclasses[]; /* defined by USERs. */ + +#endif /* !_TASKMANAGER_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/TaskQueue.c Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,92 @@ +#include"TaskList.h" + +typedef struct _TaskQueue { + TaskList *head; + TaskList *tail; + int length; +} TaskQueue; + +TaskQueue * +newTaskQueue() +{ + TaskQueue *queue; + /* TODO: mallocはあとで独自実装に書き直し! */ + malloc(sizeof(struct _TaskQueue)); + queue->head = NULL; + queue->tail = NULL; + queue->length = 0; + return queue; +} + +void +queueAddFirst(TaskQueue *queue, Task *) +{ + TaskList *oldhead = queue->head; + TaskList *newlist; + newlist = malloc(sizeof(struct _TaskList)); + + if (oldhead) { + oldhead->prev = newlist; + } + newlist->next = oldhead; + newlist->prev = NULL; + queue->head = newlist; + queue->length++; + return ; +} + +void +queueAddLast(TaskQueue *queue, Task *task) +{ + TaskList *oldtail = queue->tail; + TaskList *newlist; + newlist = malloc(sizeof(struct _TaskList)); + + if (oldtail) { + oldtail->next = newlist; + } + newlist->next = NULL; + newlist->prev = oldtail; + queue->tail = newlist; + queue->length++; + return ; +} + +Task * +queuePollFirst(TaskQueue *queue) +{ + TaskList *first = queue->head; + TaskList *second; + Task *task; + if (!first) return NULL; + + second = first->next; + task = first->task; + free(first); + + second->prev = NULL; + queue->head = second; + queue->length--; + return task; +} + +Task * +queuePollLast(TaskQueue *queue) +{ + TaskList *first = queue->tail; + TaskList *second; + Task *task; + if (!first) return NULL; + + second = first->prev; + task = first->task; + free(first); + + second->next = NULL; + queue->tail = second; + queue->length--; + return task; +} + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/TaskScheduler.cbc Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,86 @@ +//#include "Task.h" +#include <stdint.h> +#include <stdlib.h> +#include "TaskScheduler.h" +#include "List.h" + + +typedef List SchedTaskList; +#define addSchedTask(a,b) (SchedTaskList*)_listAddFirst((List*)(a),(void*)(b)) +#define removeTask(a,b) (SchedTaskList*)_listRemove((List*)(a),(void*)(b)) +// inline functionのがいいか + +typedef struct _segment { + ID id; // task identifier; + Taskrun nextcode; + void *rbuff; + void *wbuff; +} SchedTask; + +typedef struct _scheduler { + /* it may be Singleton. */ + + SchedTask *running; + SchedTaskList *runnable; + +} TaskScheduler; + +__code schedEntry(Taskrun nextcode, void *rbuff, void *wbuff); + +static TaskScheduler *schedule; + +extern void *allocate(size_t); +__code +initScheduler(__code (*ret)(void *), void *arg) +{ + schedule = allocate(sizeof(TaskScheduler)); + schedule->runnable = NULL; + schedule->running = NULL; + goto ret(arg); +} + +__code +addCode(ID id, Taskrun code0, void *rbuff, void *wbuff) +{ + SchedTask *newcs; + newcs = allocate(sizeof(SchedTask)); + newcs->nextcode = code0; + newcs->rbuff = rbuff; //taskの遷移で引数が変化しないならいならい + newcs->wbuff = wbuff; + + schedule->runnable = addSchedTask(schedule->runnable, newcs); + + goto selectCode(); +} + +__code +selectCode() +{ + SchedTask *task; + task = _listGetnthData(schedule->runnable, 0); + schedule->running = task; + + goto task->nextcode((void*)schedEntry, task->rbuff, task->wbuff); +} + +__code +schedEntry(Taskrun nextcode, void *rbuff, void *wbuff) +{ + /* nextcode==NULLならTaskは終わったと判断 */ + /* scheduled */ + if ( nextcode==NULL ) { + ID id = schedule->running->id; + schedule->runnable = + removeTask(schedule->runnable, schedule->running); + free(schedule->running); + schedule->running = NULL; + goto exitCode(id); + } else { + schedule->running->nextcode = nextcode; + schedule->running->rbuff = rbuff; + schedule->running->wbuff = wbuff; + goto checkNewCode(); + } +} + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/TaskScheduler.h Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,11 @@ +#ifndef _TASKSCHEDULER_H +#define _TASKSCHEDULER_H +#include <stdint.h> +#include "Task.h" +typedef uint32_t ID; + +__code initScheduler(__code (*)(void *), void *); +__code addCode(ID, Taskrun, void *, void *); +__code selectCode(); + +#endif /* _TASKSCHEDULER_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/memo.txt Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,47 @@ + +Task + o 一つ一つの仕事を表す + o それぞれが別のTaskに対して依存関係を持っている + o 一つのTaskは複数のコードセグメントの連なり + o コードセグメント毎にスケジューラに処理を渡したい + o gotoのリフレクションは今はマクロで? + * ユーザーインターフェイス + o wait_for (using set_depend of TM) + o set_cpu (optional) + o spawn + +TaskManager + o 実行環境によらないおなじ処理 + o Taskの依存関係をもとに実行に移す + o 実際の実行はSchedulerに任せる + o activeTaskQとwaitingTaskQをもつ + o SchedulerからTaskの終了通知を受け取る + o 通知を受けたらそのTaskに依存しているTaskの依存を解消 + o 依存がなくなったタスクはactiveTaskQに移される + o 実行中のTaskがなく, activeTaskQが0なら終了? + * ユーザーインターフェイス + o malloc + o create_task + o ?set_depend (used by wait_for of Task) + o spawn_task (used by spawn of Task) + +Scheduler + o TaskManagerに指示されたTaskを実際に実行する + o CPU管理 + o 実行環境毎にコードがちがう + (pthread用、Cell用、クラスタ用、Fifo..) + o 一度に指示されたものを実行する必要はない + o Taskが終了したらTaskManagerに通知する + * TaskManagerのためのインターフェイス + o initialize + o executeTask(Task *) + o checkFInishedTask + o numTask + o numCPU + +MailManager + o Schedulerとおなじく環境依存 + o TaskManagerに終了通知を行う + + +ユーザはTaskのコードセグメントを定義すればいい
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/list/Makefile Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,12 @@ +CC = gcc + +INCLUDE = -I../../ +CFLAGS = -g -O0 $(INCLUDE) + + +.c.o: + $(CC) -c $(CFLAGS) -o $@ $< + +testlist: testlist.o ../../List.o + $(CC) -o $@ $^ +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/list/testlist.c Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,58 @@ +#include<stdio.h> +#include<string.h> + +#include"List.h" + +void printList(List *list); + +int +main(int argc, char **argv) +{ + char buff[BUFSIZ]; + List *list=NULL; + + while (fgets(buff, BUFSIZ, stdin)!=NULL) { + int size = strlen(buff); + char *newstr; + + if (buff[size-1]=='\n') { + buff[size-1]='\0'; + size--; + } + if (strncmp(buff, "d:", 2)==0) { + int count; + char *s; + count = atoi(buff+2); + s = _listGetnthData(list, count); + if (s) { + printf("%s\n", s); + list = _listRemove(list, s); + } + } else { + newstr = strdup(buff); + list = _listAddFirst(list, newstr); + } + + printList(list); + } + +} + + +int printOne(void *data,void *arg) +{ + char *s = data; + printf("%s > ", s); + return 1; +} +void +printList(List *list) +{ + _listApply(list, printOne, NULL); + printf("\n"); +} + + + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/scheduler/Makefile Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,24 @@ +#CC = gcc +CbCC = ~/WorkSpace/Mercurial/build_cbc44/INSTALL_DIR/bin/gcc +CC = $(CbCC) + +INCLUDE = -I../../ +CFLAGS = -Wall -g -O0 $(INCLUDE) + +.SUFFIXES: .cbc .c .o + +all: test_sched + +.c.o: + $(CC) -c $(CFLAGS) -o $@ $< +.cbc.o: + $(CbCC) -c $(CFLAGS) -o $@ $^ + +test_sched: test_sched.o ../../List.o ../../TaskScheduler.o + $(CC) -o $@ $^ + +clean: + rm -f *.o test_sched + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/scheduler/test_sched.cbc Fri Dec 18 21:57:05 2009 +0900 @@ -0,0 +1,125 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "Task.h" +#include "TaskScheduler.h" + +#define __DEBUG(f, args...) \ + fprintf(stderr, "in %s: "f, __FUNCTION__, ## args) + +__code task1 (Scheduler scheduler, void *rbuff, void *wbuff); +__code task2 (Scheduler scheduler, void *rbuff, void *wbuff); +int main (int argc, char **argv); +__code startcode (void *arg); +__code checkNewCode (); +__code exitCode (); + +void * allocate (size_t size); + +#define NUM 3 +__code +task0(Scheduler scheduler, void *rbuff, void *wbuff) +{ + int i,j; + double *in = rbuff; + double *out = wbuff; + double a[NUM][NUM] = { + { 1.0, 0.0, 0.0 }, + { 0.0, 1.0, 0.0 }, + { 0.0, 0.0, 1.0 }, + }; + for (i=0; i<NUM; i++) { + out[i] = 0.0; + for (j=0; j<NUM; j++) { + out[i] += a[i][j] * in[j]; + } + } + __DEBUG("\n"); + goto task1(scheduler, rbuff, wbuff); +} +__code +task1(Scheduler scheduler, void *rbuff, void *wbuff) +{ + int i,j; + double *in = rbuff; + double *out = wbuff; + double a[NUM][NUM] = { + { 1.0, 0.0, 0.0 }, + { 0.0, 1.0, 0.0 }, + { 0.0, 0.0, 1.0 }, + }; + for (i=0; i<NUM; i++) { + out[i] = 0.0; + for (j=0; j<NUM; j++) { + out[i] += a[i][j] * in[j]; + } + } + __DEBUG("\n"); + goto task2(scheduler, rbuff, wbuff); +} +__code +task2(Scheduler scheduler, void *rbuff, void *wbuff) +{ + int i,j; + double *in = rbuff; + double *out = wbuff; + double a[NUM][NUM] = { + { 1.0, 0.0, 0.0 }, + { 0.0, 1.0, 0.0 }, + { 0.0, 0.0, 1.0 }, + }; + for (i=0; i<NUM; i++) { + out[i] = 0.0; + for (j=0; j<NUM; j++) { + out[i] += a[i][j] * in[j]; + } + } + __DEBUG("\n"); + goto scheduler(END, rbuff, wbuff); +} + + +int +main(int argc, char **argv) +{ + __DEBUG("\n"); + goto initScheduler(startcode, NULL); + + return 0; +} + +__code startcode(void *arg) { + double *rbuff, *wbuff; + rbuff = malloc(sizeof(double)*NUM); + wbuff = malloc(sizeof(double)*NUM); + + goto addCode(0, task1, rbuff, wbuff); +} + +__code +checkNewCode() +{ + __DEBUG("\n"); + goto selectCode(); +} + +__code +exitCode() +{ + __DEBUG("exit\n"); + exit(0); +} + +void * +allocate(size_t size) +{ + void *rtn = malloc (size); + if (!rtn) { + perror("malloc"); + exit(1); + } + return rtn; +} + + +