-
Notifications
You must be signed in to change notification settings - Fork 16
Expand file tree
/
Copy pathroadmap.html
More file actions
2074 lines (1526 loc) · 163 KB
/
roadmap.html
File metadata and controls
2074 lines (1526 loc) · 163 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7" lang="en"> <![endif]-->
<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8" lang="en"> <![endif]-->
<!--[if IE 8]> <html class="no-js lt-ie9" lang="en"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en"> <!--<![endif]-->
<head>
<meta charset="UTF-8">
<!-- Remove this line if you use the .htaccess -->
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<meta name="viewport" content="width=device-width">
<meta name="description" content="Build a simple operating system">
<title>Roadmap // eXperimental Operating System</title>
<link rel="shortcut icon" type="image/png" href="favicon.png">
<!--<link href='http://fonts.googleapis.com/css?family=Open+Sans:400italic,400,700' rel='stylesheet' type='text/css'>-->
<link rel="stylesheet" href="css/style.css">
<!--[if lt IE 9]>
<script src="http://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
</head>
<body>
<!-- Prompt IE 7 users to install Chrome Frame -->
<!--[if lt IE 8]><p class=chromeframe>Your browser is <em>ancient!</em> <a href="http://browsehappy.com/">Upgrade to a different browser</a> or <a href="http://www.google.com/chromeframe/?redirect=true">install Google Chrome Frame</a> to experience this site.</p><![endif]-->
<div class="container">
<header id="navtop">
<a href="index.html" class="logo fleft">
<img src="img/logo.png" alt="Designa Studio">
</a>
<nav class="fright">
<ul><li><a href="index.html" >Home</a></li>
<li><a href="about.html">About</a></li>
<li><a href="documentation.html" >Documentation</a></li>
<li><a href="downloads.html">Downloads</a></li>
<li><a href="roadmap.html" class="navactive">Roadmap</a></li></ul>
</ul>
</nav>
</header>
<div class="services-page main grid-wrap">
<header class="grid col-full">
<hr>
<p class="fleft">Roadmap</p>
</header>
<aside class="grid col-one-quarter mq2-col-full">
<menu>
<ol style="list-style-type:decimal">
<li><a href="#navstage1" class="sec">Setting up the System</a></li>
<li><a href="#navstage2" class="sec">Understanding the Filesystem</a></li>
<li><a href="#navstage3" class="sec">Starting the machine</a></li>
<li><a href="#navstage4" class="sec">Running a user program</a></li>
<li><a href="#navstage5" class="sec">Interrupts</a></li>
<li><a href="#navstage6" class="sec">Getting started with Multiprogramming</a></li>
<li><a href="#navstage7" class="sec">Creating Files</a></li>
<li><a href="#navstage8" class="sec">Playing with Files</a></li>
<li><a href="#navstage9" class="sec"> Process System Calls</a></li>
<li><a href="#navstage10" class="sec">Exception Handling and Demand Paging</a></li>
<li><a href="#navstage11" class="sec">Enhancements to XOS</a></li>
</ol>
</menu>
</aside>
<section class="grid col-three-quarters mq2-col-full">
<div class="grid-wrap">
<article id="navstage1" class="grid col-full">
<h2>Using the Roadmap </h2>
<p> This roadmap is divided into stages. Each stage is to be done in the sequential order. Incrementally you will build XOS according to its specification. Links are provided throughout the document for further reference. There are two kinds of links, <a href="#" class="imp">important links</a> and <a href="#">informative links</a>. You must visit the <a href="#" class="imp">Important links</a> the read the immediate section to which the link points to, in order to proceed with the roadmap. <a href="#">Informative links</a> may be clicked if you want more information at a particular point. However this information may not be necessary at that point. You can proceed with the roadmap without visiting these links also. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<!--- **************************** STAGE 1 *************************************************** -->
<article id="navstage1" class="grid col-full">
<h2>Stage 1: Setting up the System </h2>
<p> Follow the instructions in the <a href="usage-spec.html#navsetup" class="imp">setting up</a> section of the usage documentation to setup the system. This roadmap assumes that the entire package is extracted to $HOME/myxos. If the setting up of the system is done correctly the following directories will be created.
</p>
<ul>
<li><b> $HOME/myxos/apl </b><br/>
This directory contains the <a href="apl-spec.html">APL</a> (Application Programmers Language) compiler required to compile user programs to XSM machine instructions. Try out APL compiler using the instructions given <a href="usage-spec.html#navapl">here</a>.
<ul>
<li> $HOME/myxos/apl/samples - Contains sample APL programs for your reference. </li>
<li> $HOME/myxos/apl/apl_progs - This is an empty directory. The user programs that you write in APL must be saved in this directory.</li>
</ul>
</li>
<li><b> $HOME/myxos/spl </b> <br/>
This directory contains the <a href="spl-spec.html">SPL</a> (System Programmers Language) Compiler required to compile system programs (i.e. operating system routines) to XSM machine instructions. Instructions on how to use SPL compiler is given <a href="usage-spec.html#navspl">here</a>.
<ul>
<li> $HOME/myxos/spl/samples - Contains sample SPL programs for your reference.</li>
<li> $HOME/myxos/spl/spl_progs - This directory is an empty directory. The operating system routines that you code using SPL is to be saved here. </li>
</ul>
</li>
<li><b> $HOME/myxos/xfs-interface </b><br/>
This directory contains an interface through which files from your UNIX machine can be loaded into the File System of XSM (<a href="xfs-spec.html">XFS</a> or eXperimental File System). The interface also provides options for formatting the disk, listing the files loaded into the disk, removing files from the disk, copying continuous blocks from the disk to a UNIX file and displaying a file in the XFS disk. Usage instructions and examples can be found <a href="usage-spec.html#navxfs" > here</a>. </li>
<li><b> $HOME/myxos/xsm </b><br/>
This directory contains the machine simulator (<a href="xsm-spec.html">XSM</a> or eXperimental String Machine). Usage instructions and examples can be found <a href="usage-spec.html#navxsm"> here</a>. </li>
<li><b> $HOME/myxos/doc </b><br/>
This directory contains the complete specification for <a href="xos-spec.html">XOS</a> (eXperimental Operating System), <a href="xsm-spec.html">XSM</a> (eXperimental String Machine), <a href="xfs-spec.html">XFS</a> (eXperimental File System), <a href="apl-spec.html">APL</a> (Application Programmers Language) and <a hre="spl-spec.html">SPL</a>(System Programmers Language) and <a href="usage-spec.html">Usage Documentation</a> </li>
</ul>
<p><h6>Assignment</h6> Read and understand the <a href="xfs-spec.html">Filesystem (XFS) Specification</a>.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<!--- **************************** STAGE 2 *************************************************** -->
<article id="navstage2" class="grid col-full">
<h2>Stage 2: Understanding the Filesystem </h2>
<p><a href="xfs-spec.html">eXperimental Filesystem (XFS)</a> is a simulated file system. A UNIX file named "disk.xfs" simulates a hard disk for the machine simulator (XSM). Building XOS begins with understanding the underlying <a href="xfs-spec.html">Filesystem (XFS)</a> and its <a href="usage-spec.html#navxfs">interface</a>. In this stage, you will create an UNIX file and load it to the XFS disk using the XFS-Interface</p>
<ol>
<li> Run the XFS Interface
<div class="syntax">
<pre>cd $HOME/myxos/xfs-interface
./xfs-interface</pre>
</div>
This will take you to the <a href="usage-spec.html#navxfs">xfs-interface</a> prompt.
</li>
<li> Start by formatting the disk in the XFS interface using <b>fdisk</b> command. Type the following commands in the xfs-interface prompt
<div class="syntax">
<pre># fdisk
# exit</pre>
</div>
You will be back in the UNIX shell and a file named <b>disk.xfs</b> is created in the location <b>$HOME/myxos/xfs-interface/</b>. This UNIX file simulates the hard disk for the machine simulator. The disk is formatted as XFS or eXperimental File System. See <a href="xfs-spec.html#navintro"> XFS Specification </a>
</li>
<li>
<p>The <a href="xfs-spec.html#navdfl" class="imp">Disk Free List</a> in XFS is a data structure which keeps track of used and unused blocks in the disk. An unused block is indicated by 0 and a used block is indicated by 1. Check the contents of the Disk Free List after formatting the disk. Use the <b>df</b> command to view the Disk Free List (Disk Free List is stored in disk block number 20). The output will be as follows:</p>
<pre>
0 - 1
1 - 1
2 - 1
3 - 1
4 - 1
5 - 1
6 - 1
7 - 1
8 - 1
9 - 1
10 - 1
11 - 1
12 - 1
13 - 1
14 - 1
15 - 1
16 - 1
17 - 1
18 - 1
19 - 1
20 - 1
21 - 1
22 - 1
23 - 1
24 - 0
25 - 0
.
.
No of Free Blocks = 488
Total No of Blocks = 512
</pre><br/>
<p> The first 24 blocks (blocks 0 to 23) are reserved for disk structures, OS routines and INIT program. See <a href="xfs-spec.html">Disk Organization</a>. Hence it is marked as 1 (used) and the remaining entries for blocks 24 to 511 are 0 (unused).
.</pre>
</li></p>
<li><p> Create a file in your UNIX machine with sample data. <br/>
A sample data file is given below
<pre>There is a place where the sidewalk ends
And before the street begins,
And there the grass grows soft and white,
And there the sun burns crimson bright,
And there the moon-bird rests from his flight
To cool in the peppermint wind.</pre>
Save the file as <b>$HOME/myxos/sample.dat</b>
</li></p>
<li> <p>Load this data file ($HOME/myxos/sample.dat) to the XFS disk from your UNIX machine. This can be done by the following commands
<div class="syntax">
<pre>cd $HOME/myxos/xfs-interface
./xfs-interface
</pre>
</div>
This will take you to the xfs-interface prompt. Type the following commands in the xfs-interface prompt.
<div class="syntax">
<pre># load --data $HOME/myxos/sample.dat</pre>
</div>
This will load the file to the XFS disk. A FAT entry will be created for this file. <a href="xfs-spec.html#navfat">FAT</a> or File Allocation Table contains information such as the file name, file size and the block number of <a href="xfs-spec.html#navfile">basic block</a>. The basic block corresponding to a file will contain locations of the file blocks. Read about <a href="xfs-spec.html#navfile" class="imp">XFS (eXperimental File System)</a> before proceeding in the roadmap.
</li> </p>
<li> Find out the FAT entry corresponding to the loaded file. Use the <b>copy</b> command to copy FAT entries (FAT is stored in disk block number 19) to a UNIX file (say <i>$HOME/myxos/fat_block.txt</i>).
<div class="syntax">
<pre># copy 19 19 $HOME/myxos/fat_block.txt
# exit</pre>
</div>
</li>
<li> Check the <a href="xos-spec.html#navfiles_fat">FAT entry</a> by viewing the <tt>fat_block.txt</tt> file from UNIX machine and find the block number of basic block of the loaded data file. Example of first three lines of <tt>fat_block.txt</tt> indicating the filename, file size and basic block for this loaded file.
</li>
<pre>sample.dat
512
24</pre>
<li>
Get the basic block number (24 in the above example). Copy the basic block of the file using xfs-interface to a UNIX file (say $HOME/myxos/basic_block.txt) using <b>copy</b> command, to get the data blocks used by this file. Invoke the XFS interface and use the following command.
<div class ="syntax">
<pre> # copy 24 24 $HOME/myxos/basic_block.txt</pre>
</div>
(<b>NOTE</b>: In this example block number 24 is the basic block of the loaded file)
The first few lines of the file <tt>$HOME/myxos/basic_block.txt</tt> is shown below.
<pre>25
-1
-1
.
.</pre>
This indicates that the only data block of this file is block number 25. Remaining -1 entries, indicates that the remaining entries are invalid. There is only one data block for this file at block number 25. </li><br/>
<li> <p>Now check the contents of the disk free list. 2 more entries will be marked as used. One is the basic block for this file (block number 24) and the other will be data block for the file (block number 25). (See <a href="xfs-spec.html#navfile" class="imp">Files</a> in XFS) The contents of this disk free list will be as follows</p>
<pre>
0 - 1
1 - 1
2 - 1
3 - 1
4 - 1
5 - 1
6 - 1
7 - 1
8 - 1
9 - 1
10 - 1
11 - 1
12 - 1
13 - 1
14 - 1
15 - 1
16 - 1
17 - 1
18 - 1
19 - 1
20 - 1
21 - 1
22 - 1
23 - 1
24 - 1
25 - 1
26 - 0
27 - 0
28 - 0
.
.
No of Free Blocks = 486
Total no of Blocks = 512</pre><br/>
</li>
<li> Copy the data blocks from the XFS disk and display it as a UNIX file <tt>$HOME/myxos/data.txt</tt>.
<div class ="syntax">
<pre> # copy 25 25 $HOME/myxos/data.txt</pre>
</div>
You will get back the contents of the file <tt>$HOME/myxos/sample.txt</tt> in <tt>$HOME/myxos/data.txt</tt>. However in <tt>$HOME/myxos/data.txt</tt>, each word is displayed in a line. A word in XFS is 16 characters long. Sample <tt>data.txt</tt> file is shown below.
<pre>There is a plac
e where the sid
ewalk ends
And before the
street begins,
And there the g
rass grows soft
and white,
And there the s
un burns crimso
n bright,
And there the m
oon-bird rests
from his flight
To cool in the
peppermint wind</pre>
</li>
</ol>
<p><h6>Assignment</h6> Read and understand the <a href="xsm-spec.html">Machine(XSM) Specification</a>.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<!--- **************************** STAGE 3 *************************************************** -->
<article id="navstage3" class="grid col-full">
<h2>Stage 3: Starting the machine </h2>
<p>When the XSM machine is started up, the <a href="xsm-spec.html#navrom"> ROM Code </a> is executed. ROM Code resides in page 0 of the memory. It is hard coded into the machine i.e the ROM code at physical address 0 (to 511) is "already there" when machine starts up. The ROM code is called the "bootstrap" loader in OS literature. ROM code does the following operations :
<ol>
<li>Loads block 0 of disk to page 1 of memory (physical address 512).</li>
<li>After loading the block to memory, it sets IP (Instruction Pointer) to 512 so that the next instruction to be executed is fetched from location 512 (page 1 in memory starts from location 512).</li>
</ol></p>
<p>So if you write a program in SPL, compile it using SPL compiler and load the compiled code to block 0 of disk using XFS Interface, your program will be executed by the machine. This program which is loaded to block 0 of disk is supposed to be the <a href="xos-spec.html#navsysroutines_osstartup">OS Startup Code</a>. As described above, this OS Startup Code is loaded from disk block 0 to memory page 1 by the ROM Code on machine startup. (<b>WARNING</b>:The following links are for more information. Don't get lost in these links. If you don't understand, come back and proceed with the roadmap, <a href="xos-spec.html#navmemorg">Memory Organization</a>, <a href="xfs-spec.html#navdiskorg">Disk Organization</a>).</p>
<p/>The OS designer must design and program the "OS Startup Code", compile it using the SPL compiler to generate executable program and copy this program to block 0 of the disk (using xfs interface). Once that is done, this code is loaded into page 1 of memory during boot up by the ROM code. Now this OS Startup code will start executing.</p>
<p>In this stage, we will write a system program to<b> print odd numbers from 1 to n</b> and run it as the OS Startup Code in the machine. The steps to do this are explained in detail below. </p>
<ol>
<li><p>Create the program to print odd numbers from 1 to n using SPL. (SPL Specification need not be read now. It is given in <a href="spl-spec.html"> SPL Documentation </a>) See examples of SPL programs in <tt>$HOME/myxos/spl/samples</tt>. <b>NOTE: It is advised that the system programmer use only the Kernel registers S0 - S15 while writing SPL programs </b> as Program registers R0 - R7 are used by user programs. </p>
SPL Code to print odd numbers from 1 to n (taken as input)
<div class="syntax">
<pre>
alias counter S0;
alias n S1;
print "Enter n:";
read n;
counter = 0;
while(counter <= n) do
if(counter%2 != 0) then
print counter;
endif;
counter = counter + 1;
endwhile; </pre>
</div>
<p>
An SPL program uses the system registers directly instead of variables. For convenience, you can alias the registers with appropriate identifiers. See <a href="spl-spec.html#navalias" class="imp">aliasing</a> in SPL. In the above program S0 is aliased as <i>counter</i> and S1 is aliased as <i>n</i>. The value of <i>n</i> or S1 is taken as input from the user.
</li>
</p>
<li>Save this file as <tt>$HOME/myxos/spl/spl_progs/oddnos.spl</tt>. Compile this SPL program using the commands
<div class="syntax">
<tt> cd $HOME/myxos/spl </tt><br/>
<tt> ./spl --os $HOME/myxos/spl/spl_progs/oddnos.spl </tt> </div>
</li>
<li> Load the file generated by the SPL compiler ( <tt>$HOME/myxos/spl/spl_progs/os_startup.xsm</tt> ) as the OS startup code to <tt>disk.xfs</tt> using the XFS Interface. Invoke the XFS interface and use the following command to load the OS Startup Code
<div class="syntax"># load --os $HOME/myxos/spl/spl_progs/os_startup.xsm<br/># exit
</div>
</li>
<p>Note that the <tt>--os</tt> option loads the file to Block 0 of the XFS disk </p>
<li> Run the machine using the command
<div class="syntax">
<pre>cd $HOME/myxos/xsm
./xsm</pre>
</div>
<p></p>
</li>
</ol>
The machine will halt after printing all odd numbers from 1 to n
<pre><tt>
Enter n:
10
1
3
5
7
9
Machine is halting
</tt></pre>
<p> You may also write a few SPL programs on your own and run it on the machine to get familiarized with SPL syntax. Try using the instructions like <a href="spl-spec.html#navbreakpointstmt"><i>breakpoint</i></a> which translates to <a href="xsm-spec.html#navinstr_brkp">BRKP</a> machine instruction. This instruction is useful for debugging. Refer <a href="usage-spec.html#navxsm">XSM Debugger</a></p>
<p><h6>Assignment</h6> Read and understand the <a href="runtime.html">Runtime environment </a>.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<!--**************************** STAGE 4 *******************************)-->
<article id="navstage4" class="grid col-full">
<h2>Stage 4: Running a user program </h2>
<p> User programs or application programs are programmed using APL or Application Programmer's Language. In stage 3, you wrote a system program and executed it. In this stage you will write a user program. (APL Specification need not be read now. It is given in <a href="apl-spec.html"> APL Documentation </a>)</p>
<p>
A user program is different from a system program. It is to be noted that a system program is executed in kernel mode (See <a href="xsm-spec.html#navmodes" class="imp">Privilege modes</a>). The machine starts its execution in kernel mode. In kernel mode both privileged and unprivileged <a href="xsm-spec.html#navinstr">instructions</a> can be executed. <b> All memory addresses are physical addresses in kernel mode </b>.</p>
<p> A user program should be run in user mode. In user mode only unprivileged instructions can be executed. <b>All memory addresses are logical in user mode </b>. In user mode, <b> the machine translates logical addresses to physical addresses using the <a href="xsm-spec.html#navaddr" class="imp">address translation</a> scheme of the machine </b>. The OS Startup code must load the user program to be executed from the disk to the memory and set up the page tables before switching to the user mode, so that the address translation scheme works correctly.
</p>
<p>
Before the start of execution of the user program, the mode of execution must be changed from kernel mode to user mode. The value of Instruction Pointer must be set to the starting logical address of the code of the user program (Since all addresses are logical addresses in user mode, program starts executing from logical address 0). Its important that you MUST read about <a href="runtime.html" class="imp">Runtime environment</a> before proceeding with the roadmap. Both switching to user mode and setting of the IP are achieved by using <a href="spl-spec.html#naviretstmt"> ireturn</a> instruction. The ireturn instruction in SPL translates to the machine instruction <a href="xsm-spec.html#navinstr_iret">IRET</a>. </p>
<p>In this stage, a user program is written in APL. It is then compiled and loaded to the disk as the <a href="xos-spec.html#navpromgmt_init">INIT</a> program. The first user program which is executed is called the INIT program. INIT program is stored in blocks 21-23 of the XFS disk. It does not have a FAT entry or a basic block. You will also write an OS Startup Code to load your INIT program from the disk to the memory and execute it. Note that the OS Startup code is a system program which runs in kernel mode. Hence it must be written in SPL. (SPL Specification need not be read now. It is given <a href="spl-spec.html"> in SPL Documentation </a>)</p>
<p>( <b>NOTE:</b> In SPL, you can write privileged instructions and access machine registers and the entire memory directly using physical addresses. The OS routines which run in kernel mode is written in SPL. SPL compiles to the instruction set available in Kernel Mode. On the other hand, APL is used write user programs. APL is a high level programming language. It compiles to instructions available in the User mode. An APL program has a limited view of the machine and uses logical addressing. Read about <a href="runtime.html" class="imp">Runtime environment</a> to understand the logical address space viewed by a user program. APL is used to test out the functioning of the OS routines that you write in SPL.)</p>
<ol>
<li> Write a program in APL to print all prime numbers lesser than a number taken as input. See <a href="apl-spec.html#navexamples">Examples</a> of APL programs. In the roadmap, the path of the file is assumed to be <tt>$HOME/myxos/apl/apl_progs/prime.apl</tt>. This program will be the INIT program in this stage. </li><br/>
<li> Compile your APL program using the command
<div class="syntax">
<tt> cd $HOME/myxos/apl </tt><br/>
<tt> ./apl $HOME/myxos/apl/apl_progs/prime.apl </tt>
</div>
The output file generated is $HOME/myxos/apl/apl_progs/prime.xsm
</li>
<br/>
<li> Load this file to <b>disk.xfs</b> as <b>INIT program</b> using XFS interface.
<div class="syntax">
# load --init $HOME/myxos/apl/apl_progs/prime.xsm
</div></li>
<li> When the program finishes execution of the user program, the machine must halt. To do this, create an SPL program with just a <b>halt;</b> instruction. Here, we have assumed its path to be <b>$HOME/myxos/spl/spl_progs/haltprog.spl</b>. </li>
Compile this program using --int=7 flag as shown.
<div class="syntax">
cd $HOME/myxos/spl <br/>
./spl --int=7 $HOME/myxos/spl/spl_progs/haltprog.spl <br/>
</div>
Now a file named <tt>int7.xsm</tt> is created in <tt>$HOME/myxos/spl/spl_progs/</tt>. <br/><br/>
Load this file to the XFS Disk (disk.xfs) using XFS interface as Interrupt 7 routine.
<div class="syntax"># load --int=7 $HOME/myxos/spl/spl_progs/int7.xsm</div>
Interrupt 7 routine is responsible for halting the machine upon completion of running user program. Interrupt 7 Routine is invoked at the end of every user program. APL compiler adds the <tt>INT 7</tt> instruction at the end of every compiled user program. This is to be loaded into the memory by the OS Startup Code. You will learn about <a href="xos-spec.html#navsysroutines_interrupt">interrupts</a> in later stages.
</li><br/><br/>
<li> It must be ensured that the machine will terminate on <a href="xsm-spec.html#navexcep">exceptions</a>. Upon encountering an exception, the machine invokes the <a href="xos-spec.html#navsysroutines_exhandler">exception handler</a> routine. In this stage, simply halt on exceptions. Compile the SPL program used in the previous step (<tt>HOME/myxos/spl/spl_progs/haltprog.spl</tt>) using <tt>--exhandler</tt> flag
<div class="syntax">
cd $HOME/myxos/spl <br/>
./spl --exhandler $HOME/myxos/spl/spl_progs/haltprog.spl <br/>
</div>
Now a file named <tt>exhandler.xsm</tt> is created in <tt>$HOME/myxos/spl/spl_progs/</tt>. <br/><br/>
Load this file to the XFS Disk (disk.xfs) using XFS interface as Exception Handler
<div class="syntax"># load --exhandler $HOME/myxos/spl/spl_progs/exhandler.xsm</div>.
This is to be loaded into the memory by the OS Startup Code. You will learn in detail about <a href="xos-spec.html#navsysroutines_exhandler">exception handler</a> in later stages.
</ol>
<h6>OS Startup Code</h6>
<ol>
Interrupt 7 Routine, Exception Handler routine and the program to print primes must be loaded from the XFS disk to the memory by the OS Startup Code. The OS Startup Code executes in kernel mode and hence must be written in <a href="spl-spec.html">SPL</a>, compiled and loaded to the disk as done in stage 3. The new OS Startup Code must do the following tasks. </br><br/>
<li> <p>Load Exception Handler from disk blocks 1 and 2 to memory pages 7 and 8 respectively. Load Interrupt 7 Routine from disk blocks 17 and 18 to memory page 23 and 24 using <a href="spl-spec.html#navlsstmt" >load</a> instruction. These programs are responsible for halting the machine on exceptions and upon finishing execution of the process respectively.
<div class="syntax">
load (page_number, block_number);
</div>
</li>
(<b>NOTE</b>:The following links are instructive. However don't get lost in these links. If you don't understand, come back and proceed with the roadmap, <a href="xos-spec.html#navmemorg">Memory Organization</a>, <a href="xfs-spec.html#navdiskorg">Disk Organization</a>).</p>
<li><p>The program to print primes will be loaded as the INIT program. Since the INIT program is the first user program that is executed, you may assign a PID (Process Identifier) value 0.</p>
<p>
The first structure to setup is the Process Control Block for the INIT process. ( See <a href="xos-spec.html#navpromgmt_pcb">PCB</a> ). The <a href="xos-spec.html#navpromgmt_readylist">Ready List</a> starts from memory address 1536. In general, the starting address of the PCB of a process is computed using the formula <pre>1536 + (PID x 32)</pre>
Each PCB is of size 32 words. Hence, PID x 32 will give the index of the PCB within the Ready List of PCBs. Adding 1536, which is the starting address of the Ready List, will give the physical address of the PCB. While writing SPL programs, you may use the <a href="spl-spec.html#navconst">predefined constant</a> <tt>READY_LIST</tt> instead of the value 1536 . PID of INIT process is set to 0, and hence its PCB's starting address is 1536.
The first word in the PCB stores the PID of the corresponding process. Set the 1st word of the PCB with the value 0 (which is the PID for INIT Process)
<div class="syntax">
[READY_LIST + 0] = 0; // Sets the entry for PID as 0
</div>
<li>Load the <b>INIT program</b> (program to print primes) from the disk to the memory. In the memory, user programs are stored in pages 25-63. Since INIT is the first process, we will allocate the first 3 pages (pages 25-27) for code. Every running process will require a stack. (Understanding the <a href="runtime.html" class="imp">Runtime Environment</a> is a MUST at this point). Memory page 28 can be allocated for the stack. (See <a href="xos-spec.html#navpromgmt_prostruct">Process Structure</a>) . The blocks 21-23 from disk is to be loaded to the memory pages 25-27. ( See <a href="xos-spec.html#navmemorg">Memory Organization</a> and <a href="xfs-spec.html#navdiskorg">Disk Organization )</a></li>
<div class="syntax">
load(25,21); // Load 1st page of code from disk to memory<br/>
load(26,22); // Load 2nd page of code from disk to memory<br/>
load(27,23); // Load 3rd page of code from disk to memory<br/>
</div>
<li> Page Table for INIT must be set up for address translation scheme to work correctly. This is because INIT is a user process and addresses generated are logical. Machine translates these logical addresses to physical addresses by looking up the page table for INIT. (Understanding <a href="xsm-spec.html#navaddr" class="imp">Address Translation</a> is a MUST at this point). The PTBR or Page Table Base Register stores the starting address of the page table of a process. The page table for each process has 8 words. The list of all page tables start at memory address 1024.(See <a href="xos-spec.html#navmemorg" >Memory Organization</a>). SPL has a predefined constant <tt>PAGE_TABLE</tt> which stores the value 1024. Hence PID x 8 will give the index of the page table of the particular process within the list of page tables. Adding 1024 to this value gives the physical address of the page table of this process. This physical address is stored in PTBR. Thus, PTBR of a process is calculated using the formula <pre> 1024 + (PID x 8) </pre>
Since PID of INIT is 0, PTBR value of INIT is set as 1024.
<div class="syntax">PTBR = 1024; </div>
<p></p>
<b>PTLR</b> (Page Table Length Register) stores the number of entries in the page table of a process.In XOS the page table of every process will have 4 entries (See <a href="runtime.html">Runtime Environment</a>). Thus, PTLR is set to 4.<br/>
<div class="syntax">PTLR = 4; </div>
Every process consists of four pages. Three pages are for storing code and one page for the stack (See <a href="xos-spec.html#navpromgmt_prostruct">Process Structure</a>). </li><br/>
<p>Each page table entry contains 2 words. There are 4 such entries in the page table of a process. The first word of each entry indicates the physical page number corresponding to a logical page number. The 2nd word of each entry contains auxiliary information (You MUST read about <a href="xos-spec.html#navpromgmt_pagetbl" class="imp">Per-process Page table</a> before proceeding). </p>
<p>Set up entries for memory pages 25 to 27 (3 pages for code) as well as one entry for memory page 28 (1 page for stack) in the page table for the INIT process. Set the first word of each entry to corresponding physical page number (25 to 28) and set the second word (Auxiliary information) as <b>"01"</b> (Not referenced and Valid). (<b>NOTE:</b> Auxiliary information must be always set as a string enclosed within quotes(") as otherwise, the preceding 0 will get truncated.) </p>
<p>The valid bit is set to 1 (indicating that the first word of this entry is a valid physical page number) because the actual page is loaded into the memory. This will not be done in demand paging, which will be done in Stage 10 (See <a href="xsm-spec.html#navaddr" class="imp">Address Translation</a>). The reference bit is set to 0, as the page is not referenced now. It is set to 1 by the machine, when an access to the page is made when the process executes.</p>
Setting up the entries of page table can be done in the following way
<div class="syntax">
[PTBR + 0] = 25; // Physical Page Number for Logical Page 0<br/>
[PTBR + 1] = "01"; // Auxiliary Information for Logical Page 0<br/>
. <br/>
. <br/>
. <br/>
[PTBR + 6] = 28; // Physical Page Number for Logical Page 3 (Stack) <br/>
[PTBR + 7] = "01"; // Auxiliary Information for Logical Page 3 (Stack)<br/>
</div>
</li>
<li> Once all structures are set up, <tt>STATE</tt> field in the PCB of INIT process is set to 2 (running). (See <a href="xos-spec.html#navpromgmt_pcb">PCB</a> for more information about process states). When there are more than one process in memory, the running process is identified by looking at the STATE field in the Ready List of PCBs.
<div class="syntax">
[READY_LIST + 1] = 2; // Sets the entry for STATE as Running
</div>
<p> The remaining entries of the PCB need not be set by the OS startup code. You will learn about these in subsequent stages. </p>
</li> <br/>
<li>
<p> Next we need to set the stack pointer (<b>SP</b>) register. Each program in memory has an associated runtime stack. A runtime stack holds the local variables and function parameters while a process is running (See <a href="runtime.html" class="imp" >Runtime environment</a>). The Stack Pointer or <b>SP</b> points to the top of this stack.</p>
<p>The stack of every process in XOS starts at logical address 3 x 512 (= 1536) which corresponds to logical page number 3 ( logical page numbering of a process starts from 0). It can grow upto logical address 4 x 512 - 1 (= 2047). If stack grows beyond this value, machine triggers an exception (See <a href="xsm-spec.html#navexcep">Exceptions</a>). </p>
<p> Before OS Startup Code transfers control to the user program, the value of <b>SP</b> must be set to its starting logical address ( 3 * 512 = 1536). Every user program runs in user mode. In user mode, all addresses are logical addresses. Since SP is used by the user program, its address should be a logical address. </p>
<div class="syntax">SP = 3 * 512; </div>
</li>
<li>
<p> The OS Startup Code transfers control of execution to the user program using an <a href="xsm-spec.html#navinstr_iret" target=""><tt>IRET</tt></a> instruction. An IRET performs the following operations
<ol style="list-style-type:lower-roman">
<li> The privilege mode is changed from KERNEL to USER mode. </li>
<li> The value in the top of the user stack (pointed to by SP) is stored in IP or Instruction Pointer. The IP register contains the logical address of the next instruction to be executed in user mode. IP cannot be changed explicitly by the programmer using any instruction other than branching instructions, subroutine instructions, <tt>IRET</tt> and <tt>INT</tt> instructions (See <a href="xsm-spec.html#navinstr">instructions</a>).
</li> <li> Decrement the value of SP by 1 </li>
</ol>
<p> For an <tt>IRET</tt> instruction to function properly, the value at the top of the stack should be the logical address of the next instruction. This value gets stored in IP.</p>
<p> The code pages of every program in memory starts from logical address 0. (See <a href="runtime.html" class="imp" >Runtime environment</a>). Hence <b>IP</b> or instruction pointer needs to be set to 0 before a process starts executing. As IP cannot be set explicitly, put the value 0 to the top of the stack, and <tt>IRET</tt> instruction will implicitly set the IP to this value. Since the OS Startup Code runs in KERNEL mode, the physical address of SP must be used to access the top of the stack. Stack of INIT process is allocated physical page number 28. Its corresponding physical address is 28 * 512. Hence, the following instruction will put 0 in the top of the stack.
<div class="syntax">
[28 * 512] = 0; // Set up the IP value for INIT in the stack
</div>
See <a href="xsm-spec.html#navmodes">privilege modes</a> and <a href="xsm-spec.html#navaddr">address translation</a> for detailed information.
</li>
<br/>
<li> Use the <b>ireturn</b> instruction to transfer control to user program. <b>ireturn</b> translates to <tt><a href="xsm-spec.html#navinstr_iret" target=""><tt>IRET</tt></a></tt> machine instruction </li>
<div class="syntax">
ireturn;
</div>
</ol>
<h6>Making things work !</h6><br/>
<p> You have already written, compiled and loaded your user program to <b>disk.xfs</b>. You have also loaded Interrupt 7 Routine and Exception Handler to <b>disk.xfs</b>. </p>
<p> After finishing writing OS Startup Code in SPL, save it as <b>$HOME/myxos/spl/spl_progs/os_startup.spl</b>. You should compile this file using SPL compiler with --os flag as shown.</p>
<div class="syntax"><pre> cd $HOME/myxos/spl
./spl --os $HOME/myxos/spl/spl_progs/os_startup.spl</pre>
</div>
<p>This will generate a file <b>$HOME/myxos/spl/spl_progs/os_startup.xsm</b>. Load this file as the OS startup code to <tt>disk.xfs</tt> using the XFS Interface. Invoke the XFS interface and use the following command to load the OS Startup Code. </p>
<div class="syntax"># load --os $HOME/myxos/spl/spl_progs/os_startup.xsm<br/># exit
</div>
<p> Run the machine by disabling the timer. The machine has a timer which interrupts the execution at specific intervals while running a user program. It passes the control to timer interrupt routine. We will be dealing with the timer in stage 5 (Interrupts). Until then we will run the machine with the timer disabled. The <i>--timer=0</i> flag is used to disable the timer (See <A href="/usage-spec.html#navxsm">Usage Instructions</a>). </p>
<div class="syntax">cd $HOME/myxos/xsm/<br/> ./xsm --timer=0</div>
If the timer is not disabled, the machine will get stuck when a timer interrupt occurs. This is because the control gets passed to the Timer Interrupt Routine which has no valid code loaded in the memory.
<br/><br/>
The output will be similar to the one given below,
<pre>Enter n:
10
2
3
5
7
Machine is halting</pre>
<h6>Using the Debugger :</h6>
<p> The DEBUG mode of the machine can be quite useful for understanding the switch between kernel and user mode. Try adding two breakpoint instructions in the OS Startup code - one before setting the value of <b>SP</b> and one just before the <b>ireturn</b> instruction. Add a breakpoint instruction at the beginning of the APL program which is loaded as INIT. When the machine is run with the --debug flag, check the value of SP and IP at each breakpoint instruction. At the first breakpoint the value of SP will be 0 as it is not yet set. To move to the next breakpoint, type 'c' or 'continue' and press Enter. At the second breakpoint the value of SP will be 1536 ( = 3*512) like it was set. The value of IP in both these breakpoints will be physical addresses as no address translation takes place in kernel mode. Then try the 'step' or 's' command to execute the next instruction. Single step utill the 'IRET' instruction is executed. To run the last used command in the debug environment press Enter. The last command 'step' will be executed. After the execution of the IRET instruction, the value of SP will be 1535. This is a logical address and will get translated by the machine as it is in user mode. The value of IP will be 0, as the user program starts executing from logical address 0. To move to the next breakpoint use the 'continue' command. The SP value will be more than 1535 as some space is allocated in the stack for variables used in the APL program.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<!-- ************************ STAGE 5***************** ************************** !-->
<article id="navstage5" class="grid col-full">
<h2>Stage 5: Interrupt Routines </h2>
<p> When an interrupt occurs while the XSM simulator is running, it transfers control to specific memory locations corresponding to the interrupt. Interrupts can be invoked either by software (through INT instruction) or by hardware. In XSM, the only hardware interrupt is the timer interrupt, which is triggered in fixed intervals of instructions. (In real machines, a timer interrupt is triggered in fixed intervals of time using a timer device). There are seven software interrupts in XSM, invoked using machine instructions <tt>INT 1</tt> to <tt>INT 7</tt>. </p>
<p>Interrupts can only be triggered or invoked in user mode. In Kernel mode interrupts are disabled. Upon encountering an interrupt, the machine transfers control to specific locations in memory and changes from user mode to kernel mode. These memory locations contains Interrupt Routines. Since interrupt routines are executed in kernel mode, use SPL to write them. User programs can access operating system services by invoking software interrupts. Memory pages 9 and 10 contains the Timer Interrupt Routine. Memory page (11 and 12) to (23 and 24) contain Interrupt Routines 1 to 7 (See <a href="xos-spec.html#navmemorg">Memory Organization</a>). Each interrupt routine has 2 pages in memory. These are invoked using <tt>INT 1</tt> to <tt>INT 7</tt> machine instructions respectively. </p>
<p>(<b>NOTE:</b> The interrupt instructions <tt>INT 1</tt> to <tt>INT 7</tt> can be invoked from an APL program using system call interfaces. You will be implementing system calls in the subsequent stages. If you are curious, jump ahead and read about <A href="xos-spec.html#navsyscalls">System Calls</a> )</p>
<p>
In this stage you'll be implementing a sample timer interrupt and a software interrupt. See <a href ="xsm-spec.html#navintrrupt">Interrupts</a> for more details.
</p>
<h5>Implementing Software Interrupt</h5>
<p> Upon encountering the machine instruction <b>INT</b> in a user program, the machine transfers control to the corresponding interrupt routine. The interrupt routines reside in pages 11 to 24 of the memory (See <a href="xos-spec.html#navmemorg">Memory Organization</a>). </p>
<p>
In this stage you'll do a test implementation of Interrupt 1 Routine. Your task is to display <tt>"In INT 1"</tt> when <b>INT 1</b> instruction is encountered. To do this, you will need to write Interrupt 1 Routine to display the message <tt>"In INT 1"</tt>. This program must be loaded to memory by the OS Startup Code. Now, when invoking an <tt>INT 1</tt> instruction in a user program, the machine transfers control to Interrupt 1 Routine. Interrupt 1 Routine prints <tt>"In INT 1"</tt> on the screen and transfers control back to the user program. Follow these steps to get this done,</p>
<ol>
<li> <p>Create an SPL program to print <tt>"In INT 1"</tt>. Use an <tt>ireturn;</tt> instruction in the end. The sample SPL program is given below</p>
<div class="syntax">
print "In INT 1";<br/>
ireturn; </div>
<p>
This is your Interrupt 1 routine. This program will be executed when a user program invokes the <tt>INT 1</tt> instruction. After printing <tt>"In INT 1"</tt> the <tt>ireturn;</tt> instruction is executed. The <tt>ireturn</tt> instruction (which the SPL compiler translates to the <tt><a href="xsm-spec.html#navinstr_iret" target=""><tt>IRET</tt></a></tt> machine instruction) is responsible for transferring the control back to the user program which invoked the <tt>INT 1</tt> instruction.
</li></p>
<li> Save this file in your UNIX machine as <b>$HOME/myxos/spl/spl_progs/sample_int.spl</b> </li>
<li> Compile this program using SPL compiler with the flag <tt>--int=1</tt>. This flag is used because this program is to be loaded as the Interrupt 1 routine.
<div class="syntax">
cd $HOME/myxos/spl<br/>
./spl --int=1 $HOME/myxos/spl/spl_progs/sample_int.spl
</div>
<p>The output file generated will be <b>$HOME/myxos/spl/spl_progs/int1.xsm</b>. Open the file and see how the translated code looks like. You will see the following machine code</li>
<div class="syntax">
START <br/>
MOV T0, "In INT 1" <br/>
OUT T0 <br/>
IRET <br/>
HALT
</div>
</p>
<p>T0 to T3 are registers used by the SPL compiler to translate SPL code to machine instructions. This information is not relevant when you design and implement the OS in SPL. (See <a href="xsm-spec.html#navregset">Register Set</a> in XSM if you are interested to know more )</p>
<li> Load this file to the XFS disk as interrupt 1 using xfs-interface. </li>
<div class="syntax">
# load --int=1 $HOME/myxos/spl/spl_progs/int1.xsm <br/>
# exit
</div>
<li> Create a user program to invoke INT 1. For simplicity, write the program using XSM Machine instructions directly, instead of using APL (See <a href="xsm-spec.html#navinstr">Instructions</a> in XSM). This program prints <tt>"Before INT"</tt>, invokes Interrupt 1 Routine using <tt>INT 1</tt> instruction, and prints <tt>"After INT"</tt> after returning from the Interrupt routine. The <tt>INT 7</tt> instruction before the <tt>END</tt> instruction is used to halt the machine after executing the user program. You've previously implemented the Interrupt 7 Routine with <tt>HALT</tt> instruction.
<div class="syntax">
START <br/>
MOV R0, "Before INT" <br/>
OUT R0 <br/>
INT 1 <br/>
MOV R0, "After INT" <br/>
OUT R0<br/>
INT 7 <br />
END
</div>
</li>
<li> Load it directly to the XFS disk as <a href="xfs-spec.html#navinit">INIT program</a>. This program is already in XSM machine code, and hence it need not be compiled.
</li>
<li> Modify the OS Startup Code used in the previous stage to load the <b>Interrupt 1 Routine</b> from disk blocks 5 and 6 (See <a href="xfs-spec.html#navdiskorg">Disk Organization</a>) to memory pages 11 and 12 (See <a href="xos-spec.html#navmemorg">Memory Organization</a>). To do this, add the following line before the <tt>ireturn;</tt> instruction of the OS startup code.
<div class="syntax"> // Load Interrupt 1 Routine from disk to memory <br/>load (11, 5);<br/> load (12, 6);</div>
</li>
<li> Compile the OS Startup Code using SPL compiler.
<div class="syntax">cd $HOME/myxos/spl<br/>
./spl --os $HOME/myxos/spl/spl_progs/os_startup.spl</div>
<li> Load the compiled output file $HOME/myxos/spl/spl_progs/os_startup.xsm to the XFS disk using XFS interface</li>
<li> Run the machine by disabling the timer.
<div class="syntax"> cd $HOME/myxos/xsm <br/>./xsm --timer=0 </div>
You'll get the following output on the screen.
<pre><tt>
Before INT
In INT 1
After INT
Machine is halting
</tt></pre>
</li>
</ol>
<br/>
<h5>Implementing Timer Interrupt</h5>
<p> The XSM simulator has a timer which invokes the timer interrupt routine after specific number of instructions . (Note that, in real machines, a timer interrupt is triggered in fixed intervals of time using a timer device). The <a href="xsm-spec.html#navtimer">Timer Interrupt Routine</a> resides in pages 9 and 10 in the memory (see <a href="xos-spec.html#navmemorg">Memory Organization</a>). </p>
<p>Your task is to display <tt>"TIMER"</tt> every time a timer interrupt is triggered. Create a timer interrupt routine, which prints <tt>"TIMER"</tt>. The Timer Interrupt Routine is loaded to memory by the OS Startup Code. A sample program to print numbers up to 20 is compiled using APL compiler and used as INIT program. The Machine is run without disabling the timer. When a timer interrupt occurs, the control is passed to the timer interrupt routine. This routine prints <tt>"TIMER"</tt> and returns to the user program. </p>
<p>(<b>NOTE:</b> Timer Interrupt is triggered at fixed intervals of instructions. The interval can be specified when the XSM simulator is started - see <a href="usage-spec.html#navxsm">Usage</a> of XSM. Default interval for timer interrupt is 10 instructions)
</p>
<p>
Detailed instructions to get this done are given below.</p>
<ol>
<li> Create an SPL program to print "TIMER". The sample SPL program is given below
<div class="syntax">
print "TIMER";<br/>
ireturn;
</div>
</li>
<li> Save this file in your UNIX machine as <b>$HOME/myxos/spl/spl_progs/sample_timer.spl</b> </li>
<li> Compile this program using SPL compiler with the flag --int=timer.
<div class="syntax">
cd $HOME/myxos/spl<br/>
./spl --int=timer $HOME/myxos/spl/spl_progs/sample_timer.spl
</div>
<p>The output file generated will be in <b>$HOME/myxos/spl/spl_progs/timer.xsm</b>
</li></p>
<li> Load this file to XFS disk as Timer Interrupt Routine using XFS Interface.</li>
<li> Compile the sample program to print numbers upto 20 using APL compiler. The sample program is available at <b>$HOME/myxos/apl/samples/printnum.apl</b>. Load the compiled output as the INIT program to XFS disk. </li>
<li> Modify the OS Startup Code to load the <b>Timer Interrupt Routine</b> from disk blocks 3 and 4 (See <a href="xfs-spec.html#navdiskorg">Disk Organization</a>) to memory pages 9 and 10 (see <a href="xos-spec.html#navmemorg">Memory Organization</a>). Add the following line to OS startup code before the <tt>ireturn;</tt> instruction.
<div class="syntax">load (9, 3);<br/>load (10, 4);<br/></div>
</li>
<li> Compile the new OS Startup Code using SPL Compiler, and load it to the XFS disk using XFS Interface.</li>
<li> <p>Now, run the machine <b>without</b> disabling the timer, to see the timer interrupt routine in action. To enable the timer, omit the <tt>--timer</tt> flag. You can specify the interval of instructions after which the timer interrupt is triggered by specifying a <tt>value</tt> in the <tt>--timer=<value></value></tt>. The default <tt>value</tt> is 10 instructions.</p>
<div class="syntax">cd $HOME/myxos/xsm <br/> ./xsm </div>
You'll get the following output on the screen
<pre><tt>1
2
TIMER
3
4
5
6
7
TIMER
8
9
10
11
12
TIMER
13
14
15
16
17
TIMER
18
19
20
Machine is halting
</tt></pre>
</li>
</ol>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<!--*********************************STAGE 6 ******************************** -->
<article id="navstage6" class="grid col-full">
<h2>Stage 6: Getting started with Multiprogramming</h2>
<p>Multiprogramming refers to running more than one process simultaneously. Each process has a limited view of the entire machine. (Read <a href="runtime.html#navmachineview" class="imp">Runtime Environment</a> for more details). An OS capable of multiprogramming like XOS can provide this view to more than one process concurrently. In this stage, you will learn how to run two processes concurrently on the machine.</p>
<p> In XSM, when a timer interrupt is triggered, the control is passed to the timer interrupt routine. In the previous stage you made the timer interrupt to display <tt>"TIMER"</tt> at fixed intervals. <b> However, the actual function of timer interrupt routine is to schedule processes in memory.</b> </p>
<p>The timer interrupt routine should save the context of the current process in its Process Control Block (<a href="xos-spec.html#navpromgmt_pcb">PCB</a>). Context of a process refers to the program registers (R0 - R7), SP, BP, IP, PTBR and PTLR of the process. It should then schedule and dispatch a new process to be run on the machine. This means that another process will be picked from the ready list of PCBs. The context of this process is obtained from its PCB and copied into machine registers. The control of execution is then transferred to the instruction pointed to by the IP of this process. In this stage you will run two programs concurrently on the machine. You should run XSM simulator without disabling the timer. <br/>
</p>
<p>OS Startup Code must be modified to load two programs into the memory and start the execution of one program. The timer interrupt routine when invoked, saves the context of the currently running process and schedules the other process for execution. </p>
<p>Detailed instructions are given below.</p>
<h6>Creating User Programs</h6>
<ol>
<li> Write an APL program to print all odd numbers from 1 to 20 and save it as <b>$HOME/myxos/apl/apl_progs/odd.apl</b> </li>
<li> Compile this program using APL compiler and load the <b>$HOME/myxos/apl/apl_progs/odd.xsm</b> file generated to the disk using XFS Interface as INIT program. Try to read and understand the assembly code generated by APL. </li>
<div class="syntax"># load --init $HOME/myxos/apl/apl_progs/odd.xsm </div>
<li> Write another APL program to print all even numbers from 1 to 20 and save it as <b>$HOME/myxos/apl/apl_progs/even.apl</b> </li>
<li> Compile this program using APL compiler and load the <b>$HOME/myxos/apl/apl_progs/even.xsm</b> file generated to the disk using XFS Interface as an executable file. </li>
<div class="syntax"># load --exec $HOME/myxos/apl/apl_progs/even.xsm </div>
<li> Use the XFS interface to find the data blocks to which this file is loaded as done in Stage 2. In this roadmap, we assume that the basic block of the file is in block 24 and it has a single data block with block number 25. Note that this may not be the actual scenario if you have other files loaded in the disk. </li>
</ol>
<br/>
<h6>Modify the OS Startup Code</h6> <br/>
<p>The OS startup code of the previous stage loads only the INIT process and sets its process structures. In this stage, the OS Startup Code has to be modified to load the second process and set up PCB and page table of this process as well. (<b>NOTE:</b> For the subsequent stages, the OS Startup Code of the previous stage, will be used. Hence, before modifying the OS Startup Code, take a copy of it so that it can be used later).
</p>
<p>Before the <tt>ireturn</tt> statement in the OS Startup Code, it should load and set up the process structures for the second process.</p>
<ol>
<li><p>The PID (Process Identifier) for the second process may be set to 1. This is because, the INIT process has been assigned PID value 0. Hence you must set the PID field of the second process as 1. As noted in Stage 4, the starting address of PCB for any running process is calculated using the formula: </p>
<p>1536 + (PID x 32) </tt></p>
The value 1536 is stored in the the predefined SPL constant <tt>READY_LIST</tt>.
<div class="syntax">
[READY_LIST + 32] = 1; // Sets the entry for PID as 1<br/>
</div>
</li>
<li> Load the code blocks of the second program from disk to memory (In this roadmap, we have assumed that the file has only one code block which is stored in block 25. See Step 5 of the previous section. Note that, you must use the XFS interface to find the actual block numbers in your disk. There can be a maximum of 3 code blocks for any executable file). Note that the pages allocated for user processes start from page number 25 onwards and pages 25 to 28 have already been allocated for the INIT process. So the second, process can be allocated pages after 28. For convenience we have used page 29 in the memory to load the code block for our program. (See <a href="xos-spec.html#navmemorg">Memory Organization</a>). Page 29 will contain the code corresponding to this program and page 30 will be used as the stack (See <a href="xos-spec.html#navpromgmt_prostruct">Process Structure</a>).
<div class="syntax">
load(29,25 );
</div>
</li>
<li><p>Page Table for this process must be setup. The starting address of the page table of a process is calculated using the formula discussed in stage 4. </p>
<tt>1024 + PID * 8</tt>
<p><br/>
The register S0 is aliased as <tt>PTBR_Process1</tt> and assigned this value as shown below. See <a href="spl-spec,html#navalias">Aliasing</a> in SPL Specification.</p>
<div class="syntax">
alias PTBR_Process1 S0;<br/>
PTBR_Process1 = 1024 + 1 * 8;
</div>
</li>
<li><p>Setup page table entries for memory page 29 (If only 1 pages is used for code) as well as one entry for memory page 30 (1 page is used for stack) as shown below. First word of each entry is the physical page number and the 2nd word is the auxiliary information (See <a href="xsm-spec.html#navaddr">Address Translation</a>).
<div class="syntax">
// Setting up page table for 2nd process<br/><br/>
[PTBR_Process1 + 0] = 29; // Physical Page Number for Logical Page 0<br/>
[PTBR_Process1 + 1] = "01"; // Not referenced and Valid<br/>
[PTBR_Process1 + 2] = -1; // Invalid Page Number for Logical Page 1<br/>
[PTBR_Process1 + 3] = "00"; // Not referenced and Not Valid<br/>
. <br/>
. <br/>
. <br/>
[PTBR_Process1 + 6] = 30; // Physical Page Number for Logical Page 3 <br/>
[PTBR_Process1 + 7] = "01"; // Not referenced and Valid<br/>
</div>
</p></li>
<li> For the second process all the entries in the <a href="xos-spec.html#navpromgmt_pcb">PCB</a> must be setup. This is because the timer interrupt routine loads the context of this process from its <a href="xos-spec.html#navpromgmt_pcb">PCB</a>. The context of the process refers to all the registers and open files associated with a process.
<ul>
<li>STATE field is set to 1 (ready)
<div class="syntax">
[READY_LIST + 33] = 1; // STATE is READY
</div></li>
<li>PTBR field of the PCB is set to <tt>PTBR_Process1</tt>. PTLR field is set to 4 since the maximum number of entries in a page table of the process is 4 (See <a href="xos-spec.html#navpromgmt_prostruct">Process Structure</a>).
<div class="syntax">
[READY_LIST + 37] = PTBR_Process1; // PTBR <br/>
[READY_LIST + 38] = 4; // PTLR
</div></li>
<li> SP and BP fields in the PCB are set to the starting logical address of the process stack. The stack of any process starts at logical page number 3, which corresponds to logical address 3 * 512. (For understanding the use of SP and BP, read and understand <a href="runtime.html#navfncalls" class="imp">Runtime Environment</a> of a process).
<div class="syntax">
[READY_LIST + 34] = 3 * 512; // Sets the entry for BP in the PCB<br/>
[READY_LIST + 35] = 3 * 512; // Sets the entry for SP in the PCB
</div>
</li>
<li> Code area of the process starts from logical address 0, so IP field is set to zero.
<div class="syntax">
[READY_LIST + 36] = 0; // Sets the entry for IP to logical address 0 in the PCB
</div>
</li>
The rest of the entries of the PCB may not be set now. You will deal with them in subsequent stages.
</ul>
</li> <br/>
<li> Before switching to user mode, the timer interrupt routine must be loaded to memory. Add the instruction to load the timer interrupt routine from disk blocks 3 and 4 to memory pages 9 and 10. See <a href="xos-spec.html#navmemorg">Memory Organization</a> and <a href="xfs-spec.html#navdiskorg">Disk Organization </a>. You have already modified the os startup code to load the timer interrupt routine in the previous stage. So this is not to be done again.
<div class="syntax">
load(9,3);<br/>load(10,4);
</div>
</li>
</ol>
</li>
<br/>
<h6>Timer Interrupt Routine</h6> <br/>
<p> Next task to be done in this stage, is to program the Timer Interrupt in SPL, compile it and load it to the disk. The Timer Interrupt routine is the XOS <b>scheduler</b>. The scheduler is responsible for scheduling out the currently running process and allocate the CPU for a ready process. Scheduling out involves freeing the machine registers used by the process and saving it. Then the registers corresponding to the new process is loaded to machine registers. After scheduling, the control is transferred to the new process. The detailed set of actions that the timer interrupt routine must perform follows:
<ol>
<li> Find the PID or Process Identifier of the currently running process. In XOS, PID is calculated from the value of the <tt>PTBR</tt> using the formula <b><tt> (PTBR - 1024) / 8</tt></b>. This is because, the Per-Process Page tables are stored in memory from address 1024 onwards and each page table is of size 8 words. The PTBR value gives the starting address of the page table of the current process. Hence this calculation will give the Process ID for the currently running process (Note that this calculation is specific to XOS. In other operating systems Process ID may not be computable from the value of PTBR). <div class="syntax"><pre>alias currentPID S0;
currentPID = (PTBR - 1024) / 8;</pre>
</div> </li>
<li><p>Find the location of the <a href="xos-spec.html#navpromgmt_pcb">PCB</a> of the current process using the formula 1536 + 32 * currentPID, as discussed previously</li>
<div class="syntax"><pre>alias currentPCB S1;
currentPCB = READY_LIST + 32 * currentPID;</pre>
</div> </li>
</p>
<li><p>Set the STATE field of the current PCB to 1 (Ready). This is because, when the timer interrupt routine schedules another process for execution, this process will be ready and waiting for the CPU. </li></p>
<div class="syntax">
[ currentPCB + 1 ] = 1; // Set STATE to READY<br/>
</div>
<li>The Timer Interrupt Routine must store back the current registers to the PCB of the current process. It can then assign the registers with the values corresponding to the next scheduled process.
<ul>
<li> Set BP and SP fields in the PCB with values in registers <tt>BP</tt> and <tt>SP - 1</tt>. When an interrupt occurs, the value of IP is stored automatically on the top of the stack and SP is incremented. Hence SP - 1 is the correct value of SP of this process ignoring the <tt>IP</tt> pushed by the interrupt at the top of the stack.
<div class="syntax">
[ currentPCB + 2 ] = BP;<br/>
[ currentPCB + 3 ] = SP - 1; <br/>
</div>
(<b>WARNING</b>: Understand carefully why SP - 1 is stored in the PCB. Do not follow it blindly.)
</li>
<li> <p>Next, you need to set the IP field in the PCB. When a timer interrupt occurs, the IP value gets stored in the stack. The timer interrupt routine should fetch this value from the stack and save it in the PCB of the current process before switching over to the next process. </p>
<p>The timer interrupt routine is in KERNEL mode. Before this timer interrupt routine was invoked, a user process was running in USER mode. The top of the stack of this process is pointed to by the <tt>SP</tt>. The value of SP is the logical address of the top of the stack of that user process. But since the timer is in kernel mode, you will need to work with physical addresses. Hence, you will need to find the physical address corresponding to this SP value. </p>
<p>
Physical page number corresponding to a logical address is obtained from the page table. <tt><i>logical address / 512</i></tt> gives the logical page number. Since each page table entry has 2 words, multiply the logical page number by 2 to find the index of the page table entry corresponding to the logical page number. Adding PTBR to this will give the location of the page table entry corresponding to the given logical address. <b><pre>Location of page table entry = PTBR + 2 x (<i>Logical Address</i> / 512) </pre></b>The value stored in the first word in the page table entry corresponds to the physical page number. </p>
<b><pre>Physical Page Number = [ Location of page table entry + 0 ] </pre></b>
<p> Offset into the page is calculated as </p>
<pre><b>offset = logical_address % 512</b></pre>
<p> The physical address is computed by multiplying the physical page number by page size (=512) and adding the offset. </p>
<pre><b>Physical Address = Physical Page Number x 512 + offset </pre></b></p>
<p> <b>NOTE</b>: In user mode, logical addresses are translated to physical address by the machine using its <a href="xsm-spec.html#navaddr">address translation</a> scheme. However, in kernel mode, you will need to manually translate any logical address to physical address using the procedure described above.</p>
<p> The above calculations is summarized into the following instructions for getting the physical address of SP,
<div class="syntax">alias physicalSP S2;</br>
physicalSP = ([PTBR + 2 * (SP / 512)] * 512) + (SP % 512);
</div>
</p>
<p>
(<b>WARNING</b>: Understand carefully how physicalSP is obtained from SP. Do not follow the formula blindly.)</p><p>
IP of the current process is on the top of the stack. Having obtained the physical address of SP, you can fetch this IP value from the stack and save it in the IP field of <a href="xos-spec.html#navpromgmt_pcb">PCB</a>. This can be done using the following instruction.</p>
<div class="syntax">[ currentPCB + 4 ] = [ physicalSP ]; // Save IP of current process in the PCB from the stack</div>
</li>
<li>Set PTBR and PTLR fields of the PCB with the values in <tt>PTBR</tt> and <tt>PTLR</tt>
<div class="syntax">
[ currentPCB + 5 ] = PTBR;<br/>
[ currentPCB + 6 ] = PTLR ; <br/>
</div>
</li>
<li>Save the registers <tt>R0</tt> to <tt>R7</tt> in the respective fields of the PCB. When a new process is executed, the machine registers are allocated for that process. The current values of registers must be backed up in the PCB so that it is not lost when a new process is executed.
<div class="syntax">
[ currentPCB + 7 ] = R0; <br/>
.<br/>
.<br/>
[ currentPCB + 14 ] = R7;<br/>
</div>
</li>
</ul>
</li>
<li> Now, the next process to be scheduled for execution is to be selected. To do this, scan the <a href="xos-spec.html#navpromgmt_readylist">Ready List of PCBs</a> in a circular manner starting from the next PCB to check for the process with STATE value 1 (Ready) in its PCB. This scheduling algorithm is known as <b>Round-Robin</b> scheduling. Every process gets equal share of the CPU time (for other scheduling algorithms, refer Silberschatz, Galvin, Gagne: Operating System Concepts). Store the address of the PCB of the newly found process in a register. In this roadmap we have assumed this register's alias to be <tt>newPCB</tt>.</li>
<li> The register values of the newly found process were stored in its PCB when it was scheduled out at an earlier point in time. Now these values needs to be fetched from the PCB and loaded back into the machine registers, so that execution will resume from where it was scheduled out. Load the fields except IP from this PCB to the corresponding registers. Note that IP value cannot be modified directly (See <a href="xsm-spec.html#navinstr">XSM Instructions</a>). </li>
<li><p> IP value is set by the <b>ireturn;</b> instruction as explained in Stage 4. For this to work correctly, you need to fetch the value from the IP field in the PCB and store it in the top of the stack of the new process. To store a value on the stack, allocate a space on the top of the stack by incrementing SP. Next, the IP value from the PCB must be stored on the stack. But since, the timer interrupt routine is in kernel mode, the physical address of SP must be calculated as explained before. Once the physical address of SP is calculated, IP value can be stored on the stack. The <tt>ireturn</tt> will take this value from the stack and store it in the IP register.
</p>
<div class="syntax">
SP = SP + 1; <br/>
alias newphysicalSP S2; <br/>
newphysicalSP = ([PTBR + 2 * (SP / 512)] * 512) + (SP % 512); <br/>
[ newphysicalSP ] = [ newPCB + 4 ]; // Stores IP field value of PCB on the stack <br/>
</div>
<li> Set the STATE field of the new PCB to 2 (Running). </li>
<li> Now you can transfer control to the new process, using <b>ireturn</b> instruction. This changes the execution mode from KERNEL mode to USER mode </li>
</ul>
</li>
</ol>
<h6> Making things work!</h6>
<ol>
<li> Compile the OS Startup Code and Timer interrupt Routine using the SPL Compiler. </li>
<li> Load the compiled output .xsm files corresponding to OS Startup code and timer interrupt routine to the XFS disk using XFS interface. </li>