-
Notifications
You must be signed in to change notification settings - Fork 16
/
Copy pathxos-spec.html
685 lines (540 loc) · 43 KB
/
xos-spec.html
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
<!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 opearting system">
<title>XOS // Documentation // 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" class="navactive">Documentation</a></li>
<li><a href="downloads.html">Downloads</a></li>
<li><a href="roadmap.html">Roadmap</a></li></ul>
</ul>
</nav>
</header>
<div class="services-page main grid-wrap">
<header class="grid col-full">
<hr>
<p class="fleft">Operating System (XOS)</p>
<br/><br/>
<a href="https://github.com/xosnitc/xosdoc/blob/master/xos/xos.pdf?raw=true" class="button"> Download as PDF </a>
</header>
<aside class="grid col-one-quarter mq2-col-full">
<menu>
<ul>
<li><a href="#navintro" class="sec" >Introduction</a></li>
<li><a href="#navmemorg" class="sec">Memory Organization</a></li>
<li><a href="#navpromgmt" class="sec">Process Management</a></li>
<li><a href="#navpromgmt_intro" class="subsec">Introduction</a></li>
<li><a href="#navpromgmt_prostruct" class="subsec">Process Structure</a></li>
<li><a href="#navpromgmt_pcb" class="subsec">Process Control Block (PCB)</a></li>
<li><a href="#navpromgmt_readylist" class="subsec">Ready List</a></li>
<li><a href="#navpromgmt_pagetbl" class="subsec">The Per-Process Page Tables</a></li>
<li><a href="#navpromgmt_multiprog" class="subsec">Multiprogramming</a></li>
<li><a href="#navpromgmt_init" class="subsec">INIT and User Processes</a></li>
<li><a href="#navmemmgmt" class="sec" >Memory Management</a></li>
<li><a href="#navmemmgmt_intro" class="subsec" >Introduction</a></li>
<li><a href="#navmemmgmt_paging" class="subsec" >Paging</a></li>
<li><a href="#navmemmgmt_mfl" class="subsec" >Memory Free List</a></li>
<li><a href="#navmemmgmt_vm" class="subsec" >Virtual Memory</a></li>
<li><a href="#navfiles" class="sec" >Files</a></li>
<li><a href="#navfiles_fat" class="subsec" >File Allocation Table (FAT)</a></li>
<li><a href="#navfiles_dfl" class="subsec" >Disk Free List</a></li>
<li><a href="#navfiles_swoft" class="subsec" >System Wide Open File Table</a></li>
<li><a href="#navfiles_scratchpad" class="subsec" >Scratchpad</a></li>
<li><a href="#navsyscalls" class="sec" >System Calls</a></li>
<li><a href="#navsyscalls_intro" class="subsec" >Introduction</a></li>
<li><a href="#navsyscalls_file" class="subsec" >File System Calls</a></li>
<li><a href="#navsyscalls_process" class="subsec" >Process System Calls</a></li>
<li><a href="#navsysroutines" class="sec" >System Routines</a></li>
<li><a href="#navsysroutines_osstartup" class="subsec" >OS Startup Code</a></li>
<li><a href="#navsysroutines_exhandler" class="subsec" >Exception Handler</a></li>
<li><a href="#navsysroutines_timer" class="subsec" >Timer Interrupt Routine</a></li>
<li><a href="#navsysroutines_interrupt" class="subsec" >Interrupt Routines</a></li>
</ul>
</menu>
</aside>
<section class="grid col-three-quarters mq2-col-full">
<div class="grid-wrap">
<article id="navintro" class="grid col-full">
<h2>Introduction</h2>
<p>
XOS (eXperimental Operating System) is an experimental operating system which is designed to be run on the XSM (eXperimental String Machine) architecture which is a simulated machine hardware. XOS is intended as an instructional tool to help students learn various aspects about operating systems.
</p>
<p>
XOS is programmed using a custom language, SPL (System Programmer's Language) which compiles to XSM compatible code. (Refer <a href="spl-spec.html" target="_blank" >SPL Specification</a>) Application programs for XSM are written in APL (Application Programmer's Language). (Refer <a href="apl-spec.html" target="_blank" >APL Specification</a>)
</p>
<p>
The programs, data and operating system code is stored on a disk which has an XFS (eXperimental File System) in it. (Refer <a href="xfs-spec.html" target="_blank" >XFS Specification</a>)
</p>
The various functionalities of XOS include
<ul>
<li> <b>Process Management</b>, includes scheduling and dispatching processes to the CPU. XOS is capable of multiprogramming (the ability to run more than one process simultaneously). (Refer <a href="#navpromgmt" >Process Management</a>)
</li>
<li> <b>Memory Management</b>, involves allocating memory for processes, demand paging (loading memory pages from the disk as and when required). (Refer <a href="#navmemmgmt" >Memory Management</a>) </li>
<li> <b>System Calls</b>. XOS provides various system calls for the user processes to execute certain kernel level operations. (Refer <a href="#navsyscalls" >System Calls</a> ) </li>
</ul>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navmemorg" class="grid col-full">
<h2>Memory Organization</h2>
<p>The operating system organizes memory as given below</p>
<table class="doctable">
<tr> <th>Page No</th> <th>Contents</th> <th>Word Address</th> <th> # of Words</th></tr>
<tr> <td>0</td> <td>ROM Code</td> <td>0 - 511</td> <td> 512 </td></tr>
<tr> <td>1</td> <td>OS Startup Code*/Scratchpad</td> <td>512 - 1023</td><td> 512 </td> </tr>
<tr> <td rowspan="4" style="vertical-align:middle">2</td> <td>Per-process page tables <td>1024 - 1279</td> <td>256</td> </tr>
<tr> <td>Memory Free List</td> <td>1280 - 1343</td> <td>64</td> </tr>
<tr> <td>System-wide open file table</td><td>1344 - 1471</td> <td>128</td> </tr>
<tr> <td>Unallocated</td> <td>1472 - 1535</td> <td>64</td> </tr>
<tr> <td >3</td> <td rowspan="2" style="vertical-align:middle">Ready list of PCBs <td rowspan="2" style="vertical-align:middle">1536 - 2559</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>4</td> </tr>
<tr> <td>5</td> <td>File Allocation Table</td> <td>2560 - 3071</td> <td>512</td> </tr>
<tr> <td>6</td> <td>Disk Free List</td> <td>3072 - 3583</td> <td>512</td> </tr>
<tr> <td >7</td> <td rowspan="2" style="vertical-align:middle">Exception Handler <td rowspan="2" style="vertical-align:middle">3584 - 4607</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>8</td> </tr>
<tr> <td >9</td> <td rowspan="2" style="vertical-align:middle">Timer Interrupt Routine <td rowspan="2" style="vertical-align:middle">4608 - 5631</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>10</td> </tr>
<tr> <td >11</td> <td rowspan="2" style="vertical-align:middle">Interrupt 1 Routine <td rowspan="2" style="vertical-align:middle">5632 - 6655</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>12</td> </tr>
<tr> <td >13</td> <td rowspan="2" style="vertical-align:middle">Interrupt 2 Routine <td rowspan="2" style="vertical-align:middle">6656 - 7679</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>14</td> </tr>
<tr> <td >15</td> <td rowspan="2" style="vertical-align:middle">Interrupt 3 Routine <td rowspan="2" style="vertical-align:middle">7680 - 8703</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>16</td> </tr>
<tr> <td >17</td> <td rowspan="2" style="vertical-align:middle">Interrupt 4 Routine <td rowspan="2" style="vertical-align:middle">8704 - 9727</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>18</td> </tr>
<tr> <td >19</td> <td rowspan="2" style="vertical-align:middle">Interrupt 5 Routine <td rowspan="2" style="vertical-align:middle">9728 - 10751</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>20</td> </tr>
<tr> <td >21</td> <td rowspan="2" style="vertical-align:middle">Interrupt 6 Routine <td rowspan="2" style="vertical-align:middle">10752 - 11775</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>22</td> </tr>
<tr> <td >23</td> <td rowspan="2" style="vertical-align:middle">Interrupt 7 Routine <td rowspan="2" style="vertical-align:middle">11776 - 12799</td> <td rowspan="2" style="vertical-align:middle">1024</td> </tr>
<tr> <td>24</td> </tr>
<tr > <td>25</td> <td rowspan="2" style="vertical-align:middle">INIT and User Programs <td rowspan="2" style="vertical-align:middle">12800 - 32767</td> <td rowspan="2" style="vertical-align:middle">19968</td> </tr>
<tr> <td>... 63</td></tr>
</table>
<p>* Page Number 1 (OS Startup Code) will be used as scratchpad after bootup
<ul>
<li> <a href="#navsysroutines_osstartup" >OS Startup Code</a> loads the INIT process to memory and sets up data structures like FAT, Disk Free List, and Memory Free List. It also loads the Interrupt Routines and Exception handler from the disk to the memory.</li>
<li> <a href="#navpromgmt_pagetbl" >The Per-Process Page Tables</a>. used for address translation of logical addresses to physical address. </li>
<li><a href="#navmemmgmt_mfl">Memory Free List</a> is a list of free memory locations in the memory. </li>
<li><a href="#navfiles_swoft" >System Wide Open File Table</a> contains a details of files which are opened by the processes. </li>
<li><a href="#navpromgmt_readylist" >Ready List</a> of <a href="#navpromgmt_pcb" >Process Control Blocks (PCB)</a>, is a list of Process Control Blocks, which indicates the ready and terminated processes.</li>
<li><a href="#navfiles_fat" >Memory copy of File Allocation Table (FAT)</a> contains details about files stored on the disk. See <a href="xfs-spec.html#navfat">FAT in XFS</a></li>
<li> <a href="#navfiles_dfl" >Memory copy of Disk Free List</a> contains details about used and used blocks in the disk. See <a href="xfs-spec.html#navdfl">Disk Free List in XFS</a> </li>
<li><a href="#navsysroutines_exhandler" >Exception Handler</a> contains the kernel code to be executed during various exceptions. </li>
<li> <a href="#navsysroutines_timer" >Timer Interrupt Routine</a> contains the kernel code to be executed during a timer interrupt. </li>
<li> <a href="#navsysroutines_interrupt" >Interrupt Routines</a> contains kernel code to be executed during interrupts (1 to 7). </li>
<li> <a href="#navpromgmt_init" >INIT and User Processes</a> is the memory space allocated for user programs in execution. </li>
</ul>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt" class="grid col-full">
<h2>Process Management</h2>
</article>
<article id="navpromgmt_intro" class="grid col-full">
<h4>Introduction</h4>
<p>Any program in its execution is called a <b>process</b>. Processes will be loaded into memory before they start their execution. Each process occupies at most 4 pages in of the memory. The processor generates logical addresses with respect to a process during execution, which is translated to the physical address. This translation is done by the machine using page tables, Refer <a href="xsm-spec.html#navaddr" target="blank"> Address Translation (XSM Specification)</a></p>
<p>The XSM architecture supports demand paging and so the machine does not fix the number of processes that can be run on it. However XOS has limited the number of process running simultaneously to 32, due to limitations in number of <a href="#navpromgmt_pcb" >PCB</a>s in the Ready List and the number of <a href="#navpromgmt_pagetbl" >Per-Process Page Tables</a>.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt_prostruct" class="grid col-full">
<h4>Process Structure</h4>
A process in the memory has the following structure.
<ul>
<li><b>Code Area</b>: These are pages of the memory that contain the executable code loaded from the disk.</li>
<li><b>Stack</b>: This is the user stack used for program execution. The variables and data used during execution of program is stored in the stack. It grows in the direction of increasing word address. The location of the stack is fixed at the 4th page of the process.</li>
</ul>
The structure of a process is as shown:<br/>
<img src="doc/prostruct.png"/>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt_pcb" class="grid col-full">
<h4>Process Control Block (PCB)</h4>
It contains data pertaining to the current state of the process. The size of the PCB is 32 words.
<br/> Structure of a PCB is given below<br /><br/>
<table class="doctable"><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7-14</th><th>15-30</th><th>31</th></tr>
<tr><td><tt>PID</tt></td><td><tt>STATE</tt></td><td><tt>BP</tt></td><td><tt>SP</tt></td><td><tt>IP</tt></td><td><tt>PTBR</tt></td><td><tt>PTLR</tt></td><td><tt>R0 - R7</tt></td><td><tt>Per-Process <br/>Open File Table</tt></td><td><tt>...Free...</tt></td></tr>
</table>
<br/>
<h5>Process Identifier (<tt>PID</tt>) </h5>
The process identifier is a number from 0 to 31, which identifies the processes in memory.
</br></br>
<h5>Process State (<tt>STATE</tt>)</h5>
The process state corresponding to a process, indicated by STATE in the PCB stores the state of that process in the memory. A process can be in one of the following states.
<ul>
<li>0 for terminated or free, i.e. process has completed execution or the PCB slot is free.</li>
<li>1 for ready, i.e. process is waiting for the CPU to start execution.</li>
<li>2 for running, i.e. the process is currently running in the CPU</li>
</ul>
<h5>Registers</h5>
<ul>
<li><tt>IP</tt>: The word address of the currently executing instruction is stored in the IP (Instruction Pointer) register. The value of this instruction cannot be changed explicitly by any instruction. </li>
<li><tt>BP</tt>: The base address of the user stack is stored in the BP (Base Pointer) register.</li>
<li><tt>SP</tt>: The address of the stack top is stored in the SP (Stack Pointer)</li>
<li><tt>PTBR</tt>: The physical address of the Per-Process Page Table of the process is stored in the PTBR (Page Table Base Register).</li>
<li><tt>PTLR</tt>: The length of the Per-Process Page Table (No. of entries) is stored in the PTLR (Page Table Length Register). It is fixed as 4 for every process in XOS.</li>
</ul>
<p>Each process has its own set of values for the various registers. Words 7 – 14 in
the PCB stores the values of the program registers associated with the process .</p>
<h5>Per-Process Open File Table </h5>
The Per-Process Open File Table contains details of files opened by the corresponding process. Every entry in this table occupies 2 words. A maximum of 8 files can be opened by a process at a time, i.e. up to 8 entries in the PCB. It is stored in the PCB from words 15 to 30. Its structure is given below
</br>
</br>
<table class="doctable" style="width:50%">
<tr><td>Pointer to system-wide </br> open file table entry</td><td><tt>LSEEK</tt> position</td> </tr>
</table> <br/>
For an invalid entry, the value of pointer to system wide open file table is set to -1.
<ul>
<li>The OS maintains a system wide open file table which contains details of all the files that are opened by processes (Refer <a href="#navfiles_swoft" >System Wide Open File Table</a>). The entry in the Per-Process File Table points to the System-wide Open File Table entry corresponding to the file.</li>
<li>
It also stores the LSEEK position for the file, which indicates the word in
the file to which the process currently points to for read/write operations.
</li>
</ul>
</article>
<br/><br/> <br/>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt_readylist" class="grid col-full">
<h4>Ready List</h4>
<p>The list of PCBs stored in the memory is used as a Ready List by the operating system to schedule processes to CPU. The STATE in the PCB indicates whether a process is ready for execution or not. A new process in memory is scheduled for execution by circularly traversing through the list of PCBs stored in memory and selecting the first Ready process after the PCB of the currently running process in the list.</p>
<p>
A maximum of 32 PCBs can be stored in the memory, and hence the maximum number of processes that can be run simultaneously is limited to 32. The PCB list is stored in pages 3 and 4 in the memory (words 1536 – 2559)
</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt_pagetbl" class="grid col-full">
<h4>The Per-Process Page Tables</h4>
<p>Every process in XOS has a Per-Process Page Table. A total of 32 PCBs and 32 Page Tables are available. This limits the number of processes that can be run to 32. The structure of a Per-process Page Table entry is shown below</p>
<table class="doctable" style="width:50%">
<tr><td>Physical Page Number</td><td> Auxiliary Information</td> </tr>
</table>
</br>
<p>
The Per-Process Page Table stores the physical page number corresponding to each logical page associated with the process. The logical page number can vary from 0 to 3 for each process. Therefore, each process has 4 entries in the page table. Per-Process Page Tables are stored in Page 2, words 1024 – 1279 in the memory ( 256 words = 32 processes × 4 entries per process )
</p>
<p>
When a process is loaded, the actual pages are not loaded into memory. In <b>demand paging</b>, the actual pages are loaded only when the pages are accessed for the first time . Once all pages are loaded, the first word of each entry contains the physical page number where the data specified by the logical address resides in the memory.
<p> The second word contains <b>auxiliary information</b>. The first two bits of auxiliary information are reserved as reference (R) bit and valid/invalid (V) bit. The remaining bits are not used by XOS, but can be used for future enhancements. The details of bits in Auxiliary information is given below. <br/></p>
<img src="doc/auxinfo.png" />
<ul>
<li> <i>Reference Bit (R)</i>: Initially, this bit is set to 0 (unreferenced) by the machine. On a page access, this bit is set to 1 by the machine. This bit is used for page replacement by the OS. (Refer <a href="#navmemmgmt_paging">Paging</a> and <a href="#navmemmgmt_vm">Virtual Memory</a>)
<li> <i>Valid/Invalid Bit (V):</i> This bit indicates whether the entry of the page table is valid or invalid. The Valid/Invalid bit has value 1 if the first word of this entry corresponds to a valid physical page number. It has value 0 if the entry is invalid. The first word of an invalid Per-process page table entry is either -1 (indicates that there is no physical page corresponding to the logical address) or a disk block number (the physical page corresponding to the logical address resides in this disk block and needs to be loaded to memory). The Valid/Invalid bit is set by the OS. If memory access is made to a page whose page table entry is invalid, the machine transfers control to the <a href="#navsysroutines_exhandler">Exception Handler</a> routine, which is responsible for loading the correct physical page. </li>
</li>
</ul>
</p>
<p> An example of page table is given below </p>
<table class="doctable" style="width:50%">
<tr> <th>Physical Page Number</th> <th> Auxiliary information <br/>(reference and valid bit)</th> </tr>
<tr> <td>36 </td> <td> 01</td> </tr>
<tr> <td>311</td> <td> 00</td> </tr>
<tr> <td>-1</td> <td> 00</td> </tr>
<tr> <td>490</td> <td> 00</td> </tr>
</table>
In the above example:
<ul>
<li> Reference bit of every entry is set as 0, indicating unreferenced</li>
<li> The 1st entry is a valid page in memory as the valid bit is 1.</li>
<li> The 2nd entry is invalid (valid bit is 0) and the disk block no corresponding to that entry is stored (311).</li>
<li> The 3rd entry is invalid. There is no physical page associated with this logical address. </li>
<li> The 4th entry is invalid and the disk block no stored is 490. This corresponds to a page in the swap area.</li>
</ul>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt_multiprog" class="grid col-full">
<h4>Multiprogramming</h4>
<p>The operating system allows multiple processes to be run on the machine and manages the system resources among these processes. This process of simultaneous execution of multiple processes is known as multiprogramming.
</p>
<p>
To support multiprogramming in the system, the kernel makes use of the scheduler which is present in the Timer Interrupt Routine in pages 9 and 10 of the memory.
</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navpromgmt_init" class="grid col-full">
<h4><tt>INIT</tt> and other user programs</h4>
The INIT process is the first user program that is loaded by the OS after start up. The INIT and other user processes uses the memory pages 25 to 63 for execution.
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<br/><br/>
<article id="navmemmgmt" class="grid col-full">
<h2>Memory Management</h2>
</article>
<article id="navmemmgmt_intro" class="grid col-full">
<h4>Introduction</h4>
<p>XSM uses a paging mechanism for address translation (Refer <a href="xsm-spec.html#navaddr" target="blank"> Address Translation in XSM Specification </a>). XOS supports virtual memory, i.e. it supports execution of processes that are not completely in memory. It follows pure demand paging strategy for memory management. Pages are allocated as and when required during execution.
</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navmemmgmt_paging" class="grid col-full">
<h4>Paging</h4>
<p>Paging is the memory management scheme that permits the physical address space of a process to be non-contiguous. Each process has its own page table (Refer <a href="#navpromgmt_pagetbl" >The Per-Process Page Tables</a>), which is used for paging.
</p>
<p>The Per-Process Page Table contains information relating to the actual location in the memory. Each valid entry of a page table contains the page number in the memory where the data specified by the logical address resides. The address of Page Table of the currently executing process is stored in PTBR and length of the page table is set to 4 in PTLR of the machine.
</br>
The structure of an entry in the page table is given <a href="#navpromgmt_pagetbl"> here </a>.
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navmemmgmt_mfl" class="grid col-full">
<h4>Memory Free List</h4>
<p>The free list of the memory consists of 64 entries. Each entry is of size one word. Thus, the total size of the free list is thus 64 words. It is present in words 1280 to 1343 in memory. (words 256 to 319 of Page ) of the memory. Each entry of the free list contains a value of either 0 or 1 indicating whether the corresponding page in the memory is free or not respectively. When a page is shared by more than one process, the entry stores the number of processes that share the page. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navmemmgmt_vm" class="grid col-full">
<h4>Virtual Memory</h4>
<p>XOS allows virtual memory management, i.e. running processes without having all the pages in memory. It makes use of a backing store or swap in the disk to replace pages from the memory and allocate the emptied memory to another process. This increases the total number of processes that can be run simultaneously on the OS.</p>
<p>
When a process starts executing, no memory pages are allocated for it. Initially its per-process page tables are set with the block numbers of the disk blocks which contain the data blocks of the program. For each page table entry, the Auxiliary Information are intialized to 0 (invalid) and 0 (unreferenced). When a page is referenced for the first time, it triggers a page fault exception (since valid bit is set as 0). The Exception Handler Routine is responsible for loading the required page from the disk to the memory. This strategy of loading pages when accessed for the first time, is known as <b>Pure Demand Paging</b>. </p>
<p>
On encountering a page fault exception, the Exception Handler Routine loads the required page from the disk to a free page in the memory. If no free page is available in the memory, a page replacement technique is used to select a victim page. The page replacement technique used in XOS is a second chance algorithm (Refer Silberschatz, Galvin, Gagne: Operating System Concepts) which uses the reference bits in the auxiliary information. The victim page is swapped out to to the disk (swap area) to accommodate the required page.</p>
</article>
</br></br>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navfiles" class="grid col-full">
<h2>Files</h2>
<p>The operating system requires accessing the file system (XFS) while loading programs, and reading data from the files. The operating system maintains a memory copy of the file system data structures like FAT (File Allocation Table) and Disk Free List. It is loaded from the disk to the memory during operating system boot. </p>
<p>
Apart from the file system data structures XOS maintains details about files opened by all processes in the System-wide Open File Table. XOS uses a scratchpad to access files in the memory which will be explained further in this chapter. </p>
</article>
</br>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navfiles_fat" class="grid col-full">
<h4>File Allocation Table</h4>
<p> <i>File allocation table (FAT)</i> is a table that has an entry for each file present in the disk. FAT is stored in disk block 19 in the XFS disk. FAT is loaded into page number 5 of the memory when the OS starts. </p>
<p>The structure of FAT entry is given below</p>
<table class="doctable" >
<tr><th>0</th><th>1</th><th>2</th><th>3 - 7</th></tr>
<tr><td>File Name</td><td>File Size</td><td>Block# of Basic Block</td><td>...Unused...</td>
</table>
<br/>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navfiles_dfl" class="grid col-full">
<h4>Disk Free List</h4>
<p> The Disk Free List is a data structure used for keeping track of unused blocks in the disk. The memory copy of Disk Free List is stored in the <i>page number</i> 6. It is stored in <i>block number</i> 20 in the disk.
</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navfiles_swoft" class="grid col-full">
<h4>System-Wide Open File Table </h4>
<p>This data structure maintains details about all open files in the system. It is located from words 1344 to 1471 of the memory (in Page 2). System Wide Open File Table consists of a maximum of 64 entries. Therefore, there can be at most 64 open files in the system at any time. Each entry of the System Wide Open File Table occupies 2 words.
</p>
<table class="doctable" style="width:50%">
<tr><td>FAT Index </td> <td>File Open Count</td></tr>
</table>
<ul>
<li> <b>FAT index</b>: It stores the index of the corresponding file in the FAT. An invalid entry is denoted by -1. </li>
<li> <b>File Open Count</b>: File Open Count is the number of open instances of the file. When this becomes zero, the entry for the file is invalidated in the System Wide Open File Table.</li>
</ul>
<p> The Per-Process Open File Table in the PCB of each process stores information about files opened by the corresponding process. Each entry in the Per-Process Open File Table has the index to the file’s entry in the System-wide Open File Table.</p>
</article>
<br/><br/> <br/>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navfiles_scratchpad" class="grid col-full">
<h4>Scratchpad</h4>
<p>There is a specific page of the memory which is reserved to store temporary data. This page is known as the Scratchpad. The scratchpad is required since any block of the disk cannot be accessed directly by a process. It has to be present in the memory for access. Hence, any disk block that has to be read or written into is first brought into the scratchpad. It is then read or modified and written back into the disk.</p>
<p> The page number 1 of the memory is used as the scratchpad. Once the OS has booted up there is no need for the OS startup code. So this page can be reused as the scratchpad.</p>
</article>
</br></br>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsyscalls" class="grid col-full">
<h2>System Calls</h2>
</article>
<article id="navsyscalls_intro" class="grid col-full">
<h4>Introduction</h4>
<p>System calls are interfaces through which a process communicates with the OS. Each system call has a unique name associated with it (Open, Read, Fork, etc). Each of these names maps to a unique system call number. Each system call in turn causes a software interrupt to occur. Note that multiple system calls can be mapped to the same interrupt.</p>
<p> All the arguments to the system call are pushed into the user stack of the process which invokes the system call. The system call number is pushed as the last argument. (Refer <a href="apl-spec.html#navsyscalls" target="_blank" >System Calls</a> in APL Specification) </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsyscalls_file" class="grid col-full">
<h4>File System Calls</h4>
<p>File system calls are used by a process when it has to create, delete or manipulate Data files that reside on the disk (file system). There are seven file system calls. An interrupt is associated with each system call. All the necessary arguments for a system call are available in the user stack with the system call number as the last argument. </p>
<p><b>NOTE:</b> Filenames must not exceed 10 characters </p>
<b>Create</b></br>
<i>APL Syntax </i>: <tt>int Create(fileName)</tt> <br/>
<i>System Call No. </i>: 1 <br/>
<p>This system call is used to create a new file in the file system whose name is specified in the argument. The return value of the <tt>Create()</tt> system call is 0 if it is a success, and -1 otherwise. If the file already exists, the system call returns 0 (success). It invokes Interrupt 1 Routine. </p>
<b>Open</b></br>
<i>APL Syntax </i>: <tt>int Open(fileName)</tt> <br/>
<i>System Call No. </i>: 2 <br/>
<p>This system call is used to open an existing file whose name is specified in the argument. It calls Interrupt 2 Routine. The return value of the <tt>Open()</tt> system call is an integer value called FileDescriptor, which is the index of the corresponding file’s entry in the Per-Process Open File Table. </p>
<b>Close</b></br>
<i>APL Syntax </i>: <tt>int Close(fileDescriptor)</tt> <br/>
<i>System Call No. </i>: 3 <br/>
<p>This system call is used to close an open instance of a file. fileDescriptor is the integer value returned by the corresponding <tt>Open()</tt> system call. The return value of the <tt>Close()</tt> system call is 0 if it is a success, and -1 otherwise. It invokes Interrupt 2 Routine. </p>
<b>Delete</b></br>
<i>APL Syntax </i>: <tt>int Delete(fileName)</tt> <br/>
<i>System Call No. </i>: 4 <br/>
<p>This system call is used to delete the file from the file system whose name is specified in the argument. The return value of the <tt>Delete()</tt> system call is 0 if it is a success, and -1 otherwise. It invokes Interrupt 1 Routine.</p>
<b>Write</b></br>
<i>APL Syntax </i>: <tt>int Write(fileDescriptor, wordToWrite)</tt> <br/>
<i>System Call No. </i>: 5<br/>
<p>This system call is used to write one word at the current seek position, into an open file (identified by <tt>fileDescriptor</tt>) from a string/integer variable (identified by <tt>wordToWrite</tt>). The return value of the <tt>Write()</tt> system call is 0 if it is a success or -1 otherwise. It invokes Interrupt 4 Routine. </p>
<b>Seek</b></br>
<i>APL Syntax </i>: <tt>int Seek(fileDescriptor, newLseek)</tt> <br/>
<i>System Call No. </i>: 6 <br/>
<p>This system call is used to change the current value of the seek position in the per-process open file table entry of a file to the <tt>newLseek</tt> value. The return value of the <tt>Seek()</tt> system call is 0 if it is a success, and -1 otherwise. It invokes Interrupt 3 Routine. </p>
<b>Read</b></br>
<i>APL Syntax </i>: <tt>int Read(fileDescriptor, wordRead)</tt> <br/>
<i>System Call No. </i>: 7 <br/>
<p>This system call is used to read one word at the current seek position, from an open file (identified by <tt>fileDescriptor</tt>) and store the word to a string/integer variable (identified by <tt>wordRead</tt>). The return value of the <tt>Read()</tt> system call is 0 if it is a success or -1 otherwise. It invokes Interrupt 3 Routine. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsyscalls_process" class="grid col-full">
<h4>Process System Calls</h4>
<p>Process system calls are used by a process when it has to duplicate itself, execute a new process in its place or when it has to terminate itself. There are three process system calls. An interrupt is associated with each system call. All the necessary arguments for a system call are available in the user stack with the system call number as the last argument. </p>
<b>Fork</b></br>
<i>APL Syntax </i>: <tt>int Fork()</tt> <br/>
<i>System Call No. </i>: 8 <br/>
<p>This system call is used to replicate the process which invoked it. The new process which is created is known as the child and the process which invoked this system call is known as its parent. The return value of the <tt>Fork()</tt> system call to the parent process is the PID (process identifier) of the child process and -2 for the child process. It invokes Interrupt 5 Routine </p>
<b>Exec</b></br>
<i>APL Syntax </i>: <tt>int Exec(filename)</tt> <br/>
<i>System Call No. </i>: 9 <br/>
<p>This system call is used to load the program, whose name is specified in the argument, in the memory space of the current process and start its execution. The return value of the <tt>Exec()</tt> system call is -1 if it failed. It invokes Interrupt 6 Routine.</p>
<b>Exit</b></br>
<i>APL Syntax </i>: <tt>Exit()</tt> <br/>
<i>System Call No. </i>: 10 <br/>
<p>This system call is used to terminate the execution of the process which invoked it and removes it from the memory . It schedules the next ready process and starts executing it. When there is no other ready process to run, it halts the machine. It invokes Interrupt 7 Routine.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsysroutines" class="grid col-full">
<h2>System Routines</h2>
<p>The Operating System apart from its various data structures and interfaces it provides to the user processes, has certain routines to execute while start up and during interrupts. These routines are included as the Operating System Routines. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsysroutines_osstartup" class="grid col-full">
<h4>OS Startup Code</h4>
<p>The OS Startup Code resides in the page 1 in the memory. When the machine boots up, the <a href="xsm-spec.html#navrom">ROM Code</a> loads the OS Startup Code from block 0 in the disk to page 1 in the memory. The OS Startup code initializes all data structures required for the OS, loads the FAT and Disk Free List from file system into the memory and starts execution of the <tt>INIT</tt> process. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsysroutines_exhandler" class="grid col-full">
<h4>Exception Handler</h4>
<p>When the machine encounters an exception it sets EFR (Exception Flag Register) with details corresponding to the exception and calls the exception handler routine (pages 7 and 8 in memory). (Refer <a href="xsm-spec.html#navexcep" target="blank"> Exceptions in XSM</a>) </p>
<p>The structure of EFR is given below </p>
<img src="doc/EFR-structure.png" style="width:40%" width="20%">
<p>XOS handles all exceptions other than Page Fault by killing the process
which caused the exception.
<h5> Page Fault Exceptions </h5>
<p>The Cause field of EFR for Page Fault Exceptions is 0. The logical page which caused the exception to occur (indicated by BadVAddr field in EFR ) will not have a corresponding valid entry in the page table of the process. If the page table entry contains a disk block number, the block is loaded from the disk to a free memory page, and this memory page number is stored in the page table entry (See <a href="#navmemmgmt_vm">Virtual Memory</a>). The Valid/Invalid bit is set to 1, and the exception handler returns back to the process. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsysroutines_timer" class="grid col-full">
<h4>Timer Interrupt Routine</h4>
<p>The Timer Interrupt Routine is responsible for context switch, i.e. storing the state (values of the registers) of the currently executing process to the PCB, and setting the registers with values from the PCB of the next ready process in the Ready List of PCBs. A scheduler is responsible for selecting a ready process from this list. The Scheduler code is also contained in the Timer Interrupt Routine. The Timer Interrupt routine resides in pages 9 and 10 of the memory.</p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
<article id="navsysroutines_interrupt" class="grid col-full">
<h4>Interrupt Routines</h4>
<p>The Interrupts from 1 to 7 are invoked by the user processes through system calls. Each interrupt routine has code corresponding to one or more system calls. Every interrupt routine occupies 2 pages in memory. Interrupt routines for interrupts 1 to 7 reside in memory pages 11 to 24. Refer <a href="#navsyscalls" >System Calls</a>. </p>
</article>
<div class="up grid col-one-third" style="float:right">
<a href="#navtop" title="Go back up"> top ↑</a>
</div>
</div> <!-- 100%articles-->
</section>
</div> <!--main-->
<div class="divide-top">
<footer class="grid-wrap">
<ul class="grid col-one-third social">
<li><a href="http://github.com/xosnitc">Github</a></li>
</ul>
<div class="up grid col-one-third ">
<a href="#navtop" title="Go back up">↑</a>
</div>
<nav class="grid col-one-third ">
<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">Roadmap</a></li></ul>
</ul>
</nav>
</footer>
</div>
</div>
<!-- Javascript - jQuery
<script src="http://code.jquery.com/jquery.min.js"></script> -->
<script>window.jQuery || document.write('<script src="js/jquery-1.7.2.min.js"><\/script>')</script>
<!--[if (gte IE 6)&(lte IE 8)]>
<script src="js/selectivizr.js"></script>
<![endif]-->
<script src="js/scripts.js"></script>
<!-- Asynchronous Google Analytics snippet. Change UA-XXXXX-X to be your site's ID. -->
<script>
var _gaq=[['_setAccount','UA-XXXXX-X'],['_trackPageview']];
(function(d,t){var g=d.createElement(t),s=d.getElementsByTagName(t)[0];
g.src=('https:'==location.protocol?'//ssl':'//www')+'.google-analytics.com/ga.js';
s.parentNode.insertBefore(g,s)}(document,'script'));
</script>
</body>
</html>