CMPE322 AN OPERATING SYSTEM SCHEDULER IMPLEMENTATION Project Series 1 Solved

AN      OPERATING  SYSTEM  SCHEDULER  IMPLEMENTATION       


CMPE322          project series   is          a          set       of         projects            that      teaches how      to         construct          an        operating            system, named  BUnix   (written in         institutional      colors   of         Boğaziçi            University         J         ),          from     scratch. In         the            first      project, we        learn    how      to         manage processes         (tasks)  in         an        operating          system for        a          single   CPU            (with    a          single   core).   For       this       purpose,           we        expect  from     you      to         implement        a          round   robin            scheduler         in         C          language.          

Round           Robin Algorithm    
Round  robin    algorithm         is          a          scheduling        algorithm         in         which   the       CPU      can       be        interrupted       by            the       operating          system while    it          executes           a          process and      is          forced  to         switch  to         the       execution            of         another process in         the       ready    queue.  The      interruption      occurs  after     the       process consumes         its        assigned            time     called   “time    slot”.    Then,    the       scheduler         sends   this       process to         the       end      of         the       ready    queue   and            executes           the       process at         the       head     of         this       queue.  For       example,          assume that      the       time     slot       is            100      milliseconds      in         BUnix   and      the       operating          system has       to         schedule           the       following          processes            using    round   robin    algorithm.         You      should  have     noticed that      the       “total   execution         time”    of         a          process is            not       a          given    parameter;       it          depends           on        the       execution         of         the       program           code     which   is            explained         in         the       next     section. 

PROCESS            NAME   
ARRIVAL           TIME    (ms)     
TOTAL  EXECUTION       TIME    (ms)     
P1        
0          
210      
P2        
50        
120      
P3        
120      
240      
P4        
450      
30        
Table    1          –          Example           for        BUnix   Operating         System with     four      processes          The      actions we            are       expect  from     your     scheduler         are:      

Time    
The      Scheduler         Action  
The      Ready   Queue  
0          
Execute            P1        
                                    
P1            
 
50        
Add      P2        to         the       end      of         the            queue   
                                    
P1            
P2           
 
100      
P1        consumes         its        time     slot;      reschedule            it          and      execute P2        
                                    
P2            
P1           
 
120      
Add      P3        to         the       end      of         the            queue   
                                    
P2            
P1           
P3           
 
200      
P2        consumes         its        time     slot;      reschedule            it          and      execute P1        
                                    
P1            
P3           
P2           
 
300      
P1        consumes         its        time     slot;      reschedule            it          and      execute P3        
                                    
P3            
P2           
P1           
 
400      
P3        consumes         its        time     slot;      reschedule            and      execute P2        
                                    
P2            
P1           
P3           
 
420      
P2        is          finished;           remove it          from     the            queue   and      execute P1        
                                    
P1            
P3            
 
430      
P1        is          finished;           remove it          from     the            queue   and      execute P3        
                                    
P3            
 
450      
Add      P4        to         the       end      of         the            queue   
                                    
P3            
P4            
 
530      
P3        consumes         its        time     slot;      reschedule            and      execute P4        
                                    
P4            
P3            
 
560      
P4        is          finished;           remove it          from     the            queue   and      execute P3        
                                    
P3            
 
600      
P3        is          finished 
            
 Table    2          –          Round  robin    scheduler          

The    Process         Structure     and     the      Code  Files   
As         you      learned in         the       lectures,           a          process contains           the       program           code     and      its        current            activity (context).          Normally,         a          program           code     is          a          binary   file,      which   contains           the       instructions            that      are       executable        by        the       CPU.     However,          for        the       sake     of         simplicity,         we        will       use       text            files      (*.code)            that      represent         the       executable        code     of         the       processes         in         this       project. The            structure          of         the       text      file       is          shown  in         Table    3.         Each     row      of         the       text      file       represents            an        instruction        in         which   the       first      column presents           the       name    of         this       instruction        and      the            second column is          the       execution         time     required           by        the       CPU      to         complete          this       instruction.       

 

INSTRUCTION   NAME   
INSTRUCTION   EXECUTION       TIME    (ms)            
instruction_1    
20        
instruction_2    
50        
instruction_3    
50        
instruction_4    
20        
instruction_5    
30        
.           

.           

.           
.           

.           

.           
Exit       
10        
Table    3          –          A          Text      Based   Program           Code     File       Example           
Each     of         the       rows     is          an        atomic  operation,        which   means  if          the       CPU      starts    to         execute this            instruction,       it          cannot  be        interrupted       to         schedule           another process until     the       execution         of         that            instruction        is          completed.                   Assume that      the       “time    slot”     is          100      ms        in         BUnix   and      we        start            executing          the       process with     the       program           code     in         Table    3.         The      scheduler         should  stop     the            process after     “instruction_3” (execution        time     120ms),            add      this       process to         the       end      of         ready    queue,  and            start     executing          the       first      process in         the       queue.  Finally, you      might   have     noticed that      the       last       instruction            name    is          “exit”   which   means  that      this       process should  be        finalized           and      it          should  be        removed           from            the       system after     the       exit      instruction        is          executed.                     

In         addition            to         the       program           code,    we        need    to         store    the       current activity (context)          of         a            process to         reschedule        this       process and      continue           to         execute it          with     the       CPU.     Normally,         the            current activity of         a          process contains           different           elements          such     as         the       registers           in         the       CPU            and      stack    of         the       process.            In         BUnix,  we        just       need    to         store    the       line       number of         the       last            executed          instruction        before  sending this       process to         the       ready    queue.              

Don’t    get       confused          by        the       names  of         the       instructions.     These   are       not       real      machine           codes   and      YOU            WILL     NOT     REALLY EXECUTE.          The      only      important         thing    is          that      you      have     to         calculate           the            execution         times    of         these    instructions      correctly.          So,       you      can       stop     a          process,            send     it          back            to         the       ready    queue,  and      run       another process at         the       right     time.    

                       

                        

The    Process         Definition    File     
 The      process definition          file       (definition.ini)   is          a          text      file       that      provides           the       initial    information      of         the            processes         in         the       system. The      following          table    shows   the       structure          of         this       file.      

Process Name   
Program           Code    File            
Arrival  Time     (ms)     
P1        
1.code  
0          
P2        
3.code  
20        
P3        
1.code  
130      
P4        
1.code  
170      
.           

.           

.           
.           

.           

.           
.           

.           

.           
Table    4          –          The       Process Definition         File       Structure          
Each     row      represents        a          process in         the       system. You      should  have     noticed that      process names  are       unique, but       more            than     one      process may      be        assigned           to         the       same    program           code.                

The    Scheduler    Code  
This      component       is          a          C          code     that      parses  the       process definition          file       and      schedules         these    processes            using    the       round   robin    algorithm.         The      design  should  have     at         least     the       following          parts:   

•       The       parsing of         the       “process           definition          file”      and      the       programming    code     files.     

•       The       process data     structure,         which   includes            at         least     the       programming    code     address (or        the       filename) and      the       last       executed          line       information.     

•       A          FIFO     queue   to         implement        the       ready    queue.  

•       A          round   robin    scheduler         that      maintains         the       queue.                          

•       An        output  mechanism       that      generates         a          file       to         show    the       ready    queue   whenever         it          is changed           by        the       algorithm.         The      output  file       should  have     the       format  that      is          shown  in         Table    5. 

[TIME]::HEAD-[Ready    Queue]-TAIL     
100::HEAD—TAIL          

200::HEAD-P1-P2-TAIL   

340::HEAD-P2-P3-P1-TAIL          

450::HEAD-P3-P1-P2-TAIL          

590::HEAD-P1-P2-P4-P3-TAIL     

630::HEAD-P2-P4-P3-TAIL          

790::HEAD-P4-P3-P2-TAIL          

930::HEAD-P3-P2-P4-TAIL          

970::HEAD-P2-P4-TAIL   

1090::HEAD-P4-P2-TAIL 

1130::HEAD-P2-TAIL      

1230::HEAD-P2-TAIL      

1240::HEAD—TAIL        
Table    5          –          The       Output File       Format 

                        

Development         Platform      
 You      have     to         implement        your     design  in         the       Linux    Platform           with     GCC/G++          Compiler.         We       strongly            advise   you      to         install   Ubuntu which   has       pre-installed     GCC/G++          compiling         tools.    We       will       test      your     code            in         this       platform           and      if          your     compiled          code     is          not       compatible       with     the       test      platform.            You      might   be        invited  for        a          demo,  if          necessary.        

Provided      Files   
The following          files      are       given    together           with     the       project: 

•       The process definition          file       (number           of         processes         and      their     arrival   times    will       be        modified           to      test      your     code).   

•       Four           program           code     files      (number           of         instructions,     their     names  and      their     execution         times    will      be        modified           to         test      your     code.    Only     exception         is          the       last       instruction        name    is      always  “exit”   and      its        execution         time     is          10        milliseconds).    

•       The expected          output  file.      

•       Note:          The      length  of         the       time     slot       is          a          constant           value    in         BUnix   operating          system (100      milliseconds).    

Project          Requirements        
•       Your     project should  have     generated         the       expected          output  file       for        modified           process definition          file       and program           code     files.                 (80%)   

•       The       source  code     documentation. The      documentation depends           on        your     design  style     but       at         least     having comments        that      explain your     code     is          strongly            advised.            (20%)   

Submission Policy            
•       You       have     to         submit  your     source  code     and      your     documentation (if         it          is          not       only      comments        in your     source  code)    to         the       Moodle as         a          zip        file.      

•       The       name    of         the       zip        file       should  be        in         [STUDENT_ID].zip          format  (such    as         2015800054.zip).