Transcript OS Overviewx

Project 1 – My Shell
Let’s get started…
1.1 Compile and Validate
A task is a unit of execution (also referred to as a process).

A shell (Command Language Interpreter) is a task that functions as an
interface between the user and an Operating System.

A shell interprets textual commands coming either from the user’s
keyboard or from a script file and executes the commands either
directly or creates a new child process to execute the command.
For Project 1:

Download all the project files from class website.







os345.c, os345interrupts.c, os345signals.c os345tasks.c, os345semaphores.c
os345.h, os345config.h, os345signals.h
os345p1.c, os345p2.c, os345p3.c, os345p4.c, os345p5.c, os345p6.c
os345park.c, os345park.h, os345lc3.c, os345lc3.h, os345mmu.c, os345fat.c,
os345fat.h
Edit os345config.h (if necessary) to select host OS/IDE/ISA. (Only
enable one of the following defines: DOS, GCC, MAC, or NET.)
Compile and execute your OS.
BYU CS 345
OS Overview (Chapter 1)
2
BYU CS 345
P1, P2
P1, P2, P5
OS Overview (Chapter 1)
P6: FAT File Manager
os345p6.c
os345FAT.c
P5: FSS Scheduling
os345p5.c
P4: Virtual Memory
os345p4.c
os345mmu.c
os345lc3.c
P3: Jurassic Park
os345p3.c
os345park.c
P2: Tasking
os345p2.c
P1: Shell
os345p1.c
OS345
os345tasks.c
os345semaphores.c
os345.c
os345interrupts.c
os345signals.c
3
OS345

OS Files






main: os345.c, os345.h, os345config.h
pollInterrupts: os345interrupts.c
semaphores: os345semaphores.c
signals: os345signals.c, os345signals.h
tasking: os345tasks.c
Project Files






Shell: os345p1.c
Tasking: os345p2.c
Jurassic Park: os345p3.c, os345park.c, os345park.h
Virtual Memory: os345p4.c, os345lc3.h, os345lc3.c, os345mmu.c
Scheduling: os345p5.c
FAT: os345p6.c, os345fat.h, os345fat.c
BYU CS 345
OS Overview (Chapter 1)
4
OS345

os345.c, os345.h, os345config.h







os345interrupts.c




int main(int argc, char* argv[]);
static int scheduler();
static int dispatcher();
void swapTask();
static int initOS();
void powerDown(int code);
// idle (scheduling) loop
while(1)
{
// check for character / timer interrupts
pollInterrupts();
// schedule highest priority ready task
if ((curTask = scheduler()) < 0) continue;
// dispatch curTask
if (dispatcher() < 0) break;
}
void pollInterrupts(void);
static void keyboard_isr(void);
static void timer_isr(void);
os345semaphores.c





void semSignal(Semaphore* s);
int semWait(Semaphore* s);
int semTryLock(Semaphore* s);
Semaphore* createSemaphore(char* name, int type, int state);
bool deleteSemaphore(Semaphore** semaphore);
BYU CS 345
OS Overview (Chapter 1)
5
OS345

os345signals.c, os345signals.h






int signals(void);
int sigAction(void (*sigHandler)(void), int sig);
int sigSignal(int taskId, int sig);
void defaultSigIntHandler(void);
void createTaskSigHandlers(int tid);
os345tasks.c




int createTask(char* name,
int (*task)(int, char**),
int priority,
int argc,
char* argv[]);
int killTask(int taskId);
static void exitTask(int taskId);
int sysKillTask(int taskId);
BYU CS 345
// task name
// task address
// task priority
// task argument count
// task argument pointers
OS Overview (Chapter 1)
6
OS345

Shell: os345p1.c





Tasking: os345p2.c







void mySigIntHandler();
int P1_shellTask(int argc, char* argv[]);
int P1_quit(int argc, char* argv[]);
int P1_help(int argc, char* argv[]);
int P2_project2(int argc, char* argv[]);
int P2_listTasks(int argc, char* argv[]);
int P2_listSems(int argc, char* argv[]);
int P2_reset(int argc, char* argv[]);
int P2_killTask(int argc, char* argv[]);
int ImAliveTask(int argc, char* argv[]);
Jurassic Park: os345p3.c, os345park.c, os345park.h





int P3_project3(int argc, char* argv[]);
int P3_dc(int argc, char* argv[]);
int jurassicTask(int argc, char* argv[]);
int jurassicDisplayTask(int argc, char* argv[]);
int lostVisitorTask(int argc, char* argv[]);
BYU CS 345
OS Overview (Chapter 1)
7
OS345

Virtual Memory: os345p4.c, os345lc3.h, os345lc3.c, os345mmu.c










int P4_project4(int argc, char* argv[]);
int P4_dumpFrameTable(int argc, char* argv[]);
int P4_initMemory(int argc, char* argv[]);
int P4_vmaccess(int argc, char* argv[]);
int P4_virtualMemStats(int argc, char* argv[]);
int P4_crawler(int argc, char* argv[]);
int P4_memtest(int argc, char* argv[]);
unsigned short int *getMemAdr(int va, int rwFlg);
void initLC3Memory(int startFrame, int endFrame);
Scheduling: os345p5.c




int P5_project5(int argc, char* argv[]);
int parentTask(int argc, char* argv[])
int childTask(int argc, char* argv[])
int groupReportTask(int argc, char* argv[])
BYU CS 345
// group 1
// child Task
OS Overview (Chapter 1)
8

FAT: os345p6.c, os345fat.h, os345fat.c










int P6_project6(int, char**);
int P6_cd(int, char**);
int P6_dir(int, char**);
int P6_dfat(int, char**);
int P6_mount(int, char**);
int P6_run(int, char**);
int P6_space(int, char**);
int P6_type(int, char**);
int P6_dumpSector(int, char**);
int P6_fileSlots(int, char**);

















int P6_copy(int, char**);
int P6_define(int, char**);
int P6_del(int, char**);
int P6_mkdir(int, char**);
int P6_unmount(int, char**);
int P6_chkdsk(int, char**);
int P6_finalTest(int, char**);
BYU CS 345


int P6_open(int, char**);
int P6_read(int, char**);
int P6_write(int, char**);
int P6_seek(int, char**);
int P6_close(int, char**);
int fmsCloseFile(int);
int fmsDefineFile(char*, int);
int fmsDeleteFile(char*);
int fmsOpenFile(char*, int);
int fmsReadFile(int, char*, int);
int fmsSeekFile(int, int);
int fmsWriteFile(int, char*, int);
OS Overview (Chapter 1)
9

FAT: os345p6.c, os345fat.h, os345fat.c













int fmsGetDirEntry(char* fileName, DirEntry* dirEntry);
int fmsGetNextDirEntry(int *dirNum, char* mask, DirEntry* dirEntry, int dir);
int fmsMount(char* fileName, void* ramDisk);
int fmsUnMount(char* fileName, void* ramDisk);
void setFatEntry(int FATindex, unsigned short FAT12ClusEntryVal, unsigned char* FAT);
unsigned short getFatEntry(int FATindex, unsigned char* FATtable);
int fmsMask(char* mask, char* name, char* ext);
void setDirTimeDate(DirEntry* dir);
int isValidFileName(char* fileName);
void printDirectoryEntry(DirEntry*);
void fmsError(int);
int fmsReadSector(void* buffer, int sectorNumber);
int fmsWriteSector(void* buffer, int sectorNumber);
BYU CS 345
OS Overview (Chapter 1)
10
Chapter 1 – Computer Systems
CS 345
Stalling’s Chapter
#
Project
1: Computer System Overview
2: Operating System Overview
4
P1: Shell
3: Process Description and Control
4: Threads
4
P2: Tasking
5: Concurrency: ME and Synchronization
6: Concurrency: Deadlock and Starvation
6
P3: Jurassic Park
7: Memory Management
8: Virtual memory
6
P4: Virtual Memory
9: Uniprocessor Scheduling
10: Multiprocessor and Real-Time Scheduling
6
P5: Scheduling
11: I/O Management and Disk Scheduling
12: File Management
8
P6: FAT
Student Presentations
6
BYU CS 345
OS Overview (Chapter 1)
12
Learning Objectives

Describe the basic elements of a computer system
and their interrelationship.

Explain the steps taken by a processor to execute an instruction.
Understand the concept of interrupts and how and why a processor
uses interrupts
List and describe the levels of a typical computer memory
hierarchy.
Explain the basic characteristics of multiprocessor and multicore
organization.
Discuss the concept of locality and analyze the performance of a
multilevel memory hierarchy.
Understand the operation of a stack and its use to support
procedure call and return.





BYU CS 345
OS Overview (Chapter 1)
13
Quiz: Define the following terms
Kernel
Part of OS always in memory.
Systems program
Programs associated with OS.
Applications program
Programs not associated with OS.
Middleware
Additional frameworks for developers.
Firmware
Hardware initialization software.
Bootstrap program
Initial program executed on PU.
Daemon
Kernel associated services.
Device driver
Device controller software.
Asymmetric multiprocessing Each processor assigned specific task.
Symmetric multiprocessing
BYU CS 345
Each processor performs all tasks.
OS Overview (Chapter 1)
14
1.1 Compile and Validate
A task is a unit of execution (also referred to as a process).

A shell (Command Language Interpreter) is a task that functions as an
interface between the user and an Operating System.

A shell interprets textual commands coming either from the user’s
keyboard or from a script file and executes the commands either
directly or creates a new child process to execute the command.
For Project 1:

Download all the project files from class website.







os345.c, os345interrupts.c, os345signals.c os345tasks.c, os345semaphores.c
os345.h, os345config.h, os345signals.h
os345p1.c, os345p2.c, os345p3.c, os345p4.c, os345p5.c, os345p6.c
os345park.c, os345park.h, os345lc3.c, os345lc3.h, os345mmu.c, os345fat.c,
os345fat.h
Edit os345config.h (if necessary) to select host OS/IDE/ISA. (Only
enable one of the following defines: DOS, GCC, MAC, or NET.)
Compile and execute your OS.
BYU CS 345
OS Overview (Chapter 1)
15
The main Function
What is the output of the following echo C program?
>>echo Good Morning America
Good Morning America
>>
int main(int argc, char* argv[ ])
{
while (--argc > 0)
{
printf("%s%s", *++argv, (argc > 1) ? " " : "");
}
printf("\n");
return 0;
}
BYU CS 224
Pointers and Arrays
16
Command-line Arguments
1.2 Malloc/free argc/argv

All tasks functions (main’s) are passed two arguments:



The first (conventionally called argc, for argument count) is the number
of command-line arguments (including the program name).
The second (argv, for argument vector) is a pointer to an array of
character pointers (strings) that contain the arguments, one per string.
By convention, argv[0] points to the program name and argv[argc] is a
null pointer.
Modify the function P1_shellTask() (os345p1.c) to parse the
commands and parameters from the keyboard inbuffer string into
traditional argc and malloc'd argv C variables:



Your shell executes the command directly using a function pointer with
malloc’d arguments, waits for the function to return, and then recovers
memory (free) before prompting for the next command.
Commands and arguments are case insensitive.
Quoted strings are treated as one argument and case is preserved
within the string.
BYU CS 345
OS Overview (Chapter 1)
17
1.2 Malloc/free argc/argv
inbuffer
echo Good "Morning America"\0
argv
Malloc'd memory
echo\0
good\0
Morning America\0
\0
argv = (char**)malloc(argc*sizeof(char*));
for each argument i
argv[i] = (char*)malloc(strlen(arg)+1);
strcpy(argv[i], arg);
int retValue = (*commands[?]->func)(argc, argv);
for each argument i free(argv[i]);
free(argv);
BYU CS 345
OS Overview (Chapter 1)
18
1.3 Background Tasks
3. Implement background execution of programs:


If the command line ends with an ampersand (&), your shell creates a
new task to execute the command line. (Otherwise, your shell calls the
command function (and waits for the function to return.)
Use the createTask function to create a background process.
int createTask(char* name,
// task name
int (*task)(int, char**), // task address
int priority,
// task priority
int argc,
// task arg count
char** argv)
// task arg list


The command arguments are passed to the new task in malloc'd argv
strings. Modify the function createTask (os345tasks.c) to malloc new
argc and argv variables.
Modify the function sysKillTask (also in os345tasks.c) to recover malloc'd
createTask memory.
BYU CS 345
Chapter 2: OS Overview
19
1.3 Background Tasks
inbuffer
echo Good "Morning America“&\0
argv = (char**)malloc(argc*sizeof(char*));
for each argument i
argv[i] = (char*)malloc(strlen(arg)+1);
strcpy(argv[i], arg);
createTask(argv[0],
*commands[c]->func,
tcb[curTask].priority,
argc,
argv);
//
//
//
//
//
name
address
priority
arg count
arg list
for each argument i free(argv[i]);
free(argv);
BYU CS 345
int createTask(char* name, int (*task)(int, char**),
int priority, int argc, char** argv)
{
// populate new TCB tid
tcb[tid].argc = argc;
tcb[tid].argv = (char**)malloc(argc*sizeof(char*));
for each argument i
tcb[tid].argv[i] = (char*)malloc(strlen(argv[i])+1);
strcpy(tcb[tid].argv[i], argv[i]);
// put task in ready queue
} // end createTask
int sysKillTask(int taskId)
{
// delete task from ready queue
for each argument i free(tcb[taskID].argv[i]);
free(tcb[taskID].argv);
// release TCB
} // end sysKillTask
OS Overview (Chapter 1)
20
1.3 Background Tasks
int P1_shellTask(int argc, char* argv[])
{
while (1)
{
SEM_WAIT(inBufferReady);
// parse command line into
// malloc’d argv variables
int createTask(char* name,
int (*task)(int, char**),
int priority,
int argc, char** argv)
{
// populate new TCB
// malloc new argv variables
// put task in ready queue
} // end createTask
// execute command
if (background)
// call createTask
else // call function directly
// free malloc’d memory
while (argc) free(argv[argc--]);
free(argv);
}
} // end P1_shellTask
BYU CS 345
int sysKillTask(int taskId)
{
// delete task from ready queue
// free task malloc’d variables
// release TCB
} // end sysKillTask
Chapter 2: OS Overview
21
Learning Objectives

Describe the basic elements of a computer system and their
interrelationship.

Explain the steps taken by a processor to execute
an instruction.

Understand the concept of interrupts and how and why a processor
uses interrupts
List and describe the levels of a typical computer memory
hierarchy.
Explain the basic characteristics of multiprocessor and multicore
organization.
Discuss the concept of locality and analyze the performance of a
multilevel memory hierarchy.
Understand the operation of a stack and its use to support
procedure call and return.




BYU CS 345
OS Overview (Chapter 1)
22
Registers
Processor Registers

User-visible registers


May be referenced by machine language
Available to all programs - application programs and system
programs





Data Registers – can be changed by user
Address Registers – could be separate from data register
Stack Registers – user / supervisor stacks
Condition Codes – results of operations
Control and status registers

May or may not be visible




BYU CS 345
Program Counter (PC) – address of next instruction
Instruction Register (IR) – most recently fetched instruction
MAR/MBR – memory reference registers
Program Status Word (PSW) – condition codes, interrupts, mode
OS Overview (Chapter 1)
23
Registers
Instruction Execution
BYU CS 345
OS Overview (Chapter 1)
24
Registers
Instruction Execution
BYU CS 345
OS Overview (Chapter 1)
25
Learning Objectives


Describe the basic elements of a computer system and their
interrelationship.
Explain the steps taken by a processor to execute an instruction.

Understand the concept of interrupts and how and
why a processor uses interrupts

List and describe the levels of a typical computer memory
hierarchy.
Explain the basic characteristics of multiprocessor and multicore
organization.
Discuss the concept of locality and analyze the performance of a
multilevel memory hierarchy.
Understand the operation of a stack and its use to support
procedure call and return.



BYU CS 345
OS Overview (Chapter 1)
26
Interrupt Service Routine
Interrupt Service Routines
Interrupt
Main Routine
Interrupt Service
Routine
(synchronous)
(asynchronous)
BYU CS 345
OS Overview (Chapter 1)
27
Interrupts


The interrupt was the principle tool available to system
programmers in developing multi-tasking systems!
Classes of Interrupts






Program: arithmetic overflow, division by zero
Execute illegal instruction
Reference outside user’s memory space
I/O: Timer, DMA
Hardware failure
Interrupt control



Disable during ISR
Allow Interrupts?
Allow higher priorities?
BYU CS 345
OS Overview (Chapter 1)
28
Learning Objectives



Describe the basic elements of a computer system and their
interrelationship.
Explain the steps taken by a processor to execute an instruction.
Understand the concept of interrupts and how and why a processor
uses interrupts

List and describe the levels of a typical computer
memory hierarchy.

Explain the basic characteristics of multiprocessor and multicore
organization.
Discuss the concept of locality and analyze the performance of a
multilevel memory hierarchy.
Understand the operation of a stack and its use to support
procedure call and return.


BYU CS 345
OS Overview (Chapter 1)
29
Storage Performance
Level
1
Name
Registers
Typical Size
Implementation
Technology
< 1KB
Custom
memory
w/multiple
ports CMOS
Access time (ns)
0.25-0.5
Bandwidth (MB/sec)
20,000100,000
Managed by
Backed by
BYU CS 345
Compiler
Cache
OS Overview (Chapter 1)
30
Storage Performance
Level
1
2
Name
Registers
Cache
< 1KB
< 16MB
Custom
memory
w/multiple
ports CMOS
On-chip
CMOS RAM
Access time (ns)
0.25-0.5
0.5-25
Bandwidth (MB/sec)
20,000100,000
5,00010,000
Compiler
Hardware
Cache
Main
Typical Size
Implementation
Technology
Managed by
Backed by
BYU CS 345
OS Overview (Chapter 1)
31
Storage Performance
Level
1
2
3
Name
Registers
Cache
Main
memory
< 1KB
< 16MB
<64GB
Custom
memory
w/multiple
ports CMOS
On-chip
CMOS RAM
CMOS
SRAM
Access time (ns)
0.25-0.5
0.5-25
80-250
Bandwidth (MB/sec)
20,000100,000
5,00010,000
1,0005,000
Compiler
Hardware
OS
Cache
Main
Disk
Typical Size
Implementation
Technology
Managed by
Backed by
BYU CS 345
OS Overview (Chapter 1)
32
Storage Performance
Level
1
2
3
4
Name
Registers
Cache
Main
memory
Solid state
disk
< 1KB
< 16MB
<64GB
<1TB
Custom
memory
w/multiple
ports CMOS
On-chip
CMOS RAM
CMOS
SRAM
Flash
Access time (ns)
0.25-0.5
0.5-25
80-250
25,00050,000
Bandwidth (MB/sec)
20,000100,000
5,00010,000
1,0005,000
500
Compiler
Hardware
OS
OS
Cache
Main
Disk
Disk
Typical Size
Implementation
Technology
Managed by
Backed by
BYU CS 345
OS Overview (Chapter 1)
33
Storage Performance
Level
1
2
3
4
5
Name
Registers
Cache
Main
memory
Solid state
disk
Hard disk
< 1KB
< 16MB
<64GB
<1TB
<10TB
Custom
memory
w/multiple
ports CMOS
On-chip
CMOS RAM
CMOS
SRAM
Flash
Hard disk
Access time (ns)
0.25-0.5
0.5-25
80-250
25,00050,000
5,000,000
Bandwidth (MB/sec)
20,000100,000
5,00010,000
1,0005,000
500
20-50
Compiler
Hardware
OS
OS
OS
Cache
Main
Disk
Disk
Disk or
tape
Typical Size
Implementation
Technology
Managed by
Backed by
BYU CS 345
OS Overview (Chapter 1)
34
Learning Objectives




Describe the basic elements of a computer system and their
interrelationship.
Explain the steps taken by a processor to execute an instruction.
Understand the concept of interrupts and how and why a processor
uses interrupts
List and describe the levels of a typical computer memory
hierarchy.

Explain the basic characteristics of multiprocessor
and multicore organization.

Discuss the concept of locality and analyze the performance of a
multilevel memory hierarchy.
Understand the operation of a stack and its use to support
procedure call and return.

BYU CS 345
OS Overview (Chapter 1)
35
Multi (processor/core)

Traditionally, the computer has been viewed as a sequential
machine.



Multiple control signals
Pipelining
Parallelism

Symmetric Multiprocessors (SMP)




Multicore Computers





2 or more identical processors that share resources
Integrated OS to control jobs, tasks, files, data elements…
High degree of interaction/cooperation between processes
Single piece of silicon (die)
Independent processors + levels of cache
Intel Core i7
Prefetching
Cluster computing




BYU CS 345
Loosely coupled - network
Client / server environment
Middleware
DME, RPC
OS Overview (Chapter 1)
36
Learning Objectives





Describe the basic elements of a computer system and their
interrelationship.
Explain the steps taken by a processor to execute an instruction.
Understand the concept of interrupts and how and why a processor
uses interrupts
List and describe the levels of a typical computer memory
hierarchy.
Explain the basic characteristics of multiprocessor and multicore
organization.

Discuss the concept of locality and analyze the
performance of a multilevel memory hierarchy.

Understand the operation of a stack and its use to support
procedure call and return.
BYU CS 345
OS Overview (Chapter 1)
37
Multi-level Memory

Given:



Processor Cache:






Processor speed is faster than memory speed
Execution/data localizes
Contains a portion of main memory
Invisible to operating system
Used similar to virtual memory
Increases the speed of memory
Processor first checks cache - If not found in cache, the
block of memory containing the needed information is
moved to the cache
Disk cache, I/O cache, VM cache,…
BYU CS 345
OS Overview (Chapter 1)
38
Locality

Locality

Spatial locality – clustered access



Large cache
Pre-fetch
Temporal locality – recent/repeated access


BYU CS 345
Cache Least Recently Used (LRU)
Cache hierarchy
OS Overview (Chapter 1)
39
Learning Objectives







Describe the basic elements of a computer system and their
interrelationship.
Explain the steps taken by a processor to execute an instruction.
Understand the concept of interrupts and how and why a processor
uses interrupts
List and describe the levels of a typical computer memory
hierarchy.
Explain the basic characteristics of multiprocessor and multicore
organization.
Discuss the concept of locality and analyze the performance of a
multilevel memory hierarchy.
Understand the operation of a stack and its use to
support procedure call and return.
BYU CS 345
OS Overview (Chapter 1)
40
Subroutines
The Call / Return Mechanism
Faster programs.
Less overhead.
BYU CS 345
Smaller programs.
Easier to maintain.
Reduces development costs.
Increased reliability.
Fewer bugs do to copying code.
More library friendly.
OS Overview (Chapter 1)
41
BYU CS 345
OS Overview (Chapter 1)
42