UDN-企业互联网技术人气社区

板块导航

浏览  : 650
回复  : 3

[原生js] js系列:generator(实现微型OS)

[复制链接]
葡萄柚的头像 楼主
发表于 2017-2-5 10:09:38 | 显示全部楼层 |阅读模式
  相关代码在 generator_demo

  操作系统概要

  操作系统的一个主要任务是调度不同的任务(线程),操作系统通常有两种方式来触发调度,一种是通过中断(Interrupt,包括时钟中断,IO中断等),另一种是通过陷阱(Trap),通过调用某种特殊指令切换到OS,这两种情况下,CPU都会挂起当前任务,切换到OS,也是这时候可能进行任务切换。

  当OS运行多个任务时,通过Trap进行任务切换。实际上yield就可以视为trap操作,使用yield,可以将执行流切换到OS的主任务,然后可以进行任务调度。下面通过js实现一个微型的“操作系统”。

  1.定义Task(task.js)
  1. class Task{
  2.     constructor(target){
  3.         Task.taskid++;
  4.         this.tid = Task.taskid;
  5.         this.target = target;
  6.         this.sendval = null;
  7.     }
  8.     run(){
  9.         return this.target.next(this.sendval)
  10.     }   
  11. }
  12. Task.taskid = 0;
  13. function coroutine(func){
  14.     function start(...args){
  15.         let cr = func(...args)
  16.         cr.next();
  17.         return cr;
  18.     }
  19.     return start;
  20. }
  21. function* foo(){
  22.     console.log('part 1')
  23.     yield
  24.     console.log('part 2')
  25.     yield
  26. }
  27. 测试

  28. // test
  29. let t1 = new Task(foo())
  30. t1.run() // part 1
  31. t1.run() // part 2
复制代码

  Task里包裹了一个coroutine,其仅支持run操作,run每次运行到下次yield处。

  2.定义Scheduler(scheduler.js)
  1. let Task = require('./task').Task;
  2. class Scheduler{
  3.     constructor(){
  4.         this.ready = [];
  5.         this.taskmap = {};
  6.     }
  7.     new(target){
  8.         let newtask = new Task(target);
  9.         this.taskmap[newtask.tid] = newtask;
  10.         this.schedule(newtask);
  11.         return newtask.tid;
  12.     }
  13.     schedule(task){
  14.         this.ready.push(task)
  15.     }
  16.     exit(task){
  17.         console.log(`Task ${task.tid} terminated`)
  18.         delete this.taskmap[task.tid]
  19.     }
  20.     mainloop(){
  21.         while(Object.keys(this.taskmap).length>0){
  22.             let task = this.ready.shift();
  23.             let result = task.run();
  24.             if(!result.done){
  25.                 this.schedule(task)
  26.             }else{
  27.                 this.exit(task)
  28.             }
  29.         }
  30.     }
  31. }
  32. exports.Scheduler = Scheduler;
复制代码

  测试
  1. var Scheduler = require('./scheduler').Scheduler;
  2. function* foo(){
  3.         console.log("I'm foo")
  4.         yield
  5. }
  6. function* bar(){
  7.         console.log("I'm bar")
  8.         yield
  9. }

  10. let sched = new Scheduler()
  11. sched.new(foo())
  12. sched.new(bar())
  13. sched.mainloop()

  14. //运行结果
  15. I'm foo
  16. I'm bar
  17. Task1 terminated
  18. Task2 terminated
复制代码

  调度器维护了一个就绪队列ready,存储所有待运行的任务,同时维护一个taskmap,负责线程tid到线程的映射关系,以简化线程管理,new操作负责创建一个新的任务,每次创建新任务后立即将其存入就绪队列,mainloop是主任务循环,使用最简单的调度算法(轮流执行),其从就绪队列取出任务,执行到下次yield为止,假如发现任务执行完毕,则从就绪队列删除任务,否则执行完任务后将其放在就绪队列尾部,exit操作负责删除一个任务。这样就实现了一个简单调度器了,但是其不能执行任何系统调用,无法调用OS提供的服务。

  3.SystemCall(system_call.js)

  实际的操作系统,通过trap调用系统服务,本节实现系统调用。

  系统调用是一个特殊指令,用SystemCall表示。流程为task通过yield syscall将执行流切到scheduler 的mainloop,mainloop检测到task的返回值类型为SystemCall,执行syscall的handle操作,执行handle前mainloop把当前的task和sched信息存储在syscall里,以便syscall执行完系统服务后,将当天task继续放在就绪队列里供后续执行。
  1. class SystemCall{
  2.     handle(){

  3.     }
  4. }
  5. class GetTid extends SystemCall{
  6.     constructor(){
  7.         super()
  8.     }
  9.     handle(){
  10.         this.task.sendval = this.task.tid
  11.         this.sched.schedule(this.task)

  12.     }
  13. }

  14. exports.SystemCall = SystemCall;
  15. exports.GetTid = GetTid;
复制代码

  SystemCall只支持handle操作,对于GetTid其返回当前task的tid,并将当前task放回就绪队列。

  我们需要同时修改Scheduler的mainloop实现,以识别SystemCall指令。
  1. mainloop(){
  2.         while(Object.keys(this.taskmap).length>0){
  3.             let task = this.ready.shift();
  4.             let result = task.run();
  5.             //判断是否为系统调用
  6.             if(result.value instanceof SystemCall){
  7.                 let syscall = result.value;
  8.                 syscall.task = task
  9.                 syscall.sched = this
  10.                 syscall.handle()
  11.                 continue
  12.             }
  13.             if(!result.done){
  14.                 this.schedule(task)
  15.             }else{
  16.                 this.exit(task)
  17.             }
  18.         }
  19.     }
复制代码

  测试
  1. let Scheduler = require('./scheduler').Scheduler
  2. let GetTid = require('./system_call').GetTid
  3. function* foo(){
  4.     let mytid = yield new GetTid()
  5.     for(let i=0;i<1;i++){
  6.         console.log(`I'm foo ${mytid}`)
  7.         yield
  8.     }
  9. }
  10. function* bar(){
  11.     let mytid = yield new GetTid()
  12.     for(let i=0;i<2;i++){
  13.         console.log(`I'm bar ${mytid}`)
  14.         yield
  15.     }
  16. }

  17. let sched = new Scheduler()
  18. sched.new(foo())
  19. sched.new(bar())
  20. sched.mainloop()

  21. //结果
  22. I'm foo 1
  23. I'm bar 2
  24. Task 1 terminated
  25. I'm bar 2
  26. Task 2 terminated
复制代码

  这样通过GetTid系统调用,foo和bar获取了当前task的tid值。

  4.Task Management

  接下来添加任务管理功能,包括创建task,杀死task,等待task。这些功能都通过系统调用方式提供。

  NewTask和KillTask的实现比较简单
  1. class NewTask extends SystemCall{
  2.     constructor(target){
  3.         super()
  4.         this.target = target
  5.     }
  6.     handle(){
  7.         let tid = this.sched.new(this.target)
  8.         this.task.sendval = tid
  9.         this.sched.schedule(this.task)
  10.     }
  11. }
  12. class KillTask extends SystemCall{
  13.     constructor(tid){
  14.         super()
  15.         this.tid = tid
  16.     }
  17.     handle(){
  18.         let task = this.sched.taskmap[this.tid]
  19.         if(task){
  20.             task.target.return()
  21.             this.task.sendval = true
  22.         }else{
  23.             this.task.sendval = false
  24.         }
  25.         this.sched.schedule(this.task)
  26.     }
  27. }
复制代码

  NewTask就是简单的通过scheduler的new操作创建一个task,而KillTask则是通过传入tid,从taskmap中查找到task,并发送结束信号给task(通过coroutine的return操作)。

  而WaitTask的实现则较为复杂,等待的task不再放入ready队列中,而是放到wait队列中,除非等待的任务执行完毕,否则自己其不参加调度。因此需要在Scheduler中加入wait队列。

  Scheduler修改如下
  1. exit(task){
  2.         console.log(`Task ${task.tid} terminated`)
  3.         delete this.taskmap[task.tid]
  4.         // 唤醒所有等待该任务的其他任务
  5.         let tasks = this.exit_waiting[task.tid] || []
  6.         delete this.exit_waiting[task.tid]
  7.         for(let task of tasks){
  8.             this.schedule(task)
  9.         }
  10. }
  11. waitforexit(task,waittid){
  12.         if(waittid in this.taskmap){
  13.             this.exit_waiting[waittid] || (this.exit_waiting[waittid] = []).push(task)
  14.             return true
  15.         }else{
  16.             return false
  17.         }
  18.     }
复制代码

  每当有任务exit时,都要检查是否有其他任务等待此任务,若有则唤醒所有等待该任务的任务,waitforexit操作将等待的任务放入对应tid的等待队列中。

  WaitTask实现如下
  1. class WaitTask extends SystemCall{
  2.     constructor(tid){
  3.         super()
  4.         this.tid = tid
  5.     }
  6.     handle(){
  7.         let result = this.sched.waitforexit(this.task,this.tid)
  8.         this.task.sendval = result
  9.         // 如果等待一个不存在的任务,那么直接返回,无需等待
  10.         if(!result){
  11.             this.sched.schedule(this.task)
  12.         }
  13.     }
  14. }
复制代码

  WaitTask逻辑很简单,调用scheduler的waitforexit操作,假如发现等待的任务不存在,则不用继续等待,仍然将自己放入ready队列中,否则则进行等待,不进入ready队列。

  测试
  1. let Scheduler = require('./scheduler').Scheduler
  2. let GetTid = require('./system_call').GetTid
  3. let NewTask = require('./system_call').NewTask
  4. let KillTask = require('./system_call').KillTask
  5. let WaitTask = require('./system_call').WaitTask


  6. function* foo(){
  7.     let mytid = yield new GetTid()
  8.     for(let i=0;i<1;i++){
  9.         console.log(`I'm foo ${mytid}`)
  10.         yield
  11.     }
  12. }
  13. function* bar(){
  14.     let mytid = yield new GetTid()
  15.     for(let i=0;i<2;i++){
  16.         console.log(`I'm bar ${mytid}`)
  17.         yield
  18.     }
  19. }

  20. // test KillTask && NewTask
  21. function* sometask(){
  22.     let mytid = yield new GetTid()
  23.     console.log(`I'm sometask ${mytid}`)
  24.     let t1 = yield new NewTask(bar())
  25.     console.log(`Before killing `)
  26.     yield new KillTask(t1)
  27. }
  28. let sched = new Scheduler()
  29. sched.new(sometask())
  30. sched.mainloop()

  31. // test WaitTask
  32. function* main(){
  33.     let child = yield new  NewTask(foo())
  34.     console.log(`Waiting for child`)
  35.     yield new WaitTask(child)
  36.     console.log('child done')
  37. }

  38. sched = new Scheduler()
  39. sched.new(main())
  40. sched.mainloop()
复制代码

  至此我们实现了一个微型的OS。

相关帖子

发表于 2017-2-5 10:10:09 | 显示全部楼层
还是挺有借鉴意义的
使用道具 举报

回复

发表于 2017-2-5 10:10:09 | 显示全部楼层
OMG!介是啥东东
使用道具 举报

回复

发表于 2017-2-5 10:10:09 | 显示全部楼层
总觉得哪里有点问题啊
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部