Bsys, Betriebssysteme, Vorlesung An Der Fh Frankfurt

  • Uploaded by: Ro
  • 0
  • 0
  • October 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Bsys, Betriebssysteme, Vorlesung An Der Fh Frankfurt as PDF for free.

More details

  • Words: 8,478
  • Pages: 43
version 1, may 1992 �����������������������������������������������Ŀ � UNIX-V � � � � � � short explanation of UNIX System V � � � � � ������������������������������������������� rw �� ���������������������������������������������������������������������������� General preface -----------Op-Modes(OS) -----------DP= DataProcessing a.) seq. DP = MonoProgramming - 1 Prog simult only - no simult use of Op_means - low administration expense, simple OS - bad use(Resources) - througput can't be optimized b.) simult DP = MultiProgramming - sev. Progs simult in CompuSys - Op_means work simult; Progs concurrate - OS is Arbiter, which has to assign access_rights 2 Progs c.) sev_user_op (dynamic timeSharing) - sev. user simult - cyclic slices assigned per user - key(distribution) has to be found - complexity(OS) inc's if Throuput shell be inc'd Use(CompuSys) a) BatchProcessing - all jobs in one batch - worked out sequentially by time b) interactive Op - user interacts with equipment c) RT_Op - pacekeeping and on-time reaction on technical Process - on-line couppling (technical Process & CompuSys) -------------Layer_Struct(OS) --------------

� User � User_Interface (GUI) � Cmd_Interpreter (Shell) � Scheduler � FileSys � OS_means administration (Dev Management & Mem Management) � Kernal � Driver � Process administration � Processor administration � Sys_HW Expansion thru additional OS_Layer - Compu_Couppling (LANing) - COM_Layer - DB_Layer - GUI_SW Layers ------------------Processing(Program) ------------------User_cmds have to be recognized and transformed. jobs to OS(User) is done be OS-Ctrl-Prg = cmd_interpreter OS_calls have to be exe'd by OS --> Prg.Ctrl'd Req (OS-Ctrl-Prg) Comparable with Sub_Calls (=Sys_Calls) OS must be able to recognize time dependencies(PartTasks) and to use resulting Parallelities for troughput maximizing. This is the Task(Scheduler) = OS-Ctrl-Prg Resources have to be optimally assigned to minimize delay on OS_means OS-Ctrl-Prg (to uP = Dispatcher) to administer Processors, Mem, I/O-dev's, Files ------FileSys = all logically linked Files ------View(User) logical FileSys crucial systemwide logicall context Basic FileSys administration details, dev_independent pyhsical FileSys dev_dependent, adapted 2 MassStorageOrg und -tech - fixed, how for e.g. Block is defined Storage Media

Targets(FileSys): - systemUnite FileOrg --> Universalness - different FileTypes --> FileClassifiing - Definition (allowed&disallowed Op's) --> AccessRights - dev_independent Op with Files, free(HW_specialities) --> logic Struct ------------

Logic FileSys ------------

Leaves are allways files or empty catalogues root is a catalogue in general catalogues are Files, which include refs 2 other Files Every Catalogue can have SUB_dirs Sev same Filenames are admitted, if differing thru AccessPaths

Files are DataCollections. Sev FileTypes can be marked thru ext.'s ---------------------loc'ing(File): Pathname ---------------------abs.AcessPath starts with root "/" cuts catalogue from File or following catalogues. rel.AcessPath is starting from preset catalogue, the WD = workingDir. rel.AcessPath beginns not wit "/" or "//". HomeDir: @login this catalogue is preset, in general dedicated 2 user lin TreeStruc has only one predecessor CatalogTree - starts with root - ends with regular File oder emty catalogue - is adressed from root 2 leaves sev. Filesys's can be put together to one FileSys, so called "mounting" ------FileSys ------Main task

- is to loc File thru one specific AccesPath - Order(catalogues) including Filenames in TreeDirection - seperation(Catalogues) thru seperator "/"

---------n.lin.Tree ---------common Use(File) over sev Catalogues, where File exists only one time --> n.lin.Tree Advantages: Problem:

Mem is saved, no copying is enquired save copytime no problems with FileConsitency, because only one File exists sev Users get Access, but not simult. (--> Record_locking)

Ref is only possible within the same FileSys (physically within same disk) - no ref on catalogue possible - polyfold access must be handeld - OS allows acces only to one User/Prog because(special Priorities) ���EXOR�Ŀ

- File can only be deleted, if no additional Ref(s) exist(s). Shortly before deletion, a lin. Tree exists. - No link on catalogue possible. Establish(Ref = link) under UNIX ������� Path(catalogue) where Ref. has to be started � File Path � ������������ pay attention to AccessPath, if abs. or rel. Path(reg.File)

cmd:

ln

ex.:

���source(path&filename � ln /usr/usr1/dat11 /usr/usr2 � ���dest Cmd now knows which is subject(link) so dat11 accessible in usr2 if you add a new name behind the dest_path a rename can be included.

--------------Basic UNIX-Cmds --------------makeDir removeDir

rmdir

mkdir [path] ;works only, if catalogue has no further entries

PrintWorkDir pwd ChangeDir cd [path] cd

list

go back to workDir

cd.. cd /

;climb to next higher level ;set root 2 workDir

ls

;read catalogue, if no path is passed ;workDir is shown ;long listing

ls -l catenate

cat > [path/file] ;entry chars2file over keyboard ;press Ctrl-Z to close File create File > [filename] ;open textfile copy

cp [source] [dest] ;copy source2dest cp [source1] [source2] [...] [path] ;if files are overwritten, orginal UID and ;access rights remain. Else UID and access ;rights of user are taken

remove

rm [file] ;enter rm [file] -i to be interorgated with ;warning message, the dependencies on UID and ;access rights has to be considered.

rm -r move

;recursive remove, a "kill tree" including ;subDirs, no savety message avail.

mv [source1] [source2] ;source2 can be overwritten, if source2 ;already has content or ist already ;existant.

show/change access rights

chmode [object] ;catalogue

;object can be a Filename and also a

;pos.Logic in contrary to umask !! octal value 2000 1000 400 200 100 40 20 4 2 1

4000 change user_num @exe change group_num @exe executable shared File remain in SysSwapArea after exe readAcces for user writeAcces for user catalogueAcces for user

exe_right

readAcces for group writeAcces for group 10 catalogueAcces for group readAcces for others writeAcces for others catalogueAcces for others

change user mask umask

;defines & alters rights ;negative logic

u octal number

g ��¿ ��¿ ���� ���� rwx rwx

u ��¿ ���� rwx

right is active, if a "0" is placed to appropriate position "1" means right is not given. if cmd is entered without spec(mask), sys displays current rights on std_out. ex.:

user has all rights; his group and all others shell be taken away the rights.

mask = 000 111 111 = 77 oct ==> cmd is : umask 77 after creation(File), File gets rights(creating user). Only owner can change rigths. Other users can't change rights(owner). "=" signifies abs. Def.(Rights). Only appended rights shell be existant. ex.:

u=r

;User may only read object.

"+" signifies rel. Def.(Rights). Rights can be increased. ex.:

u+r

;User may at least read object.

"-" signifies rel. Def.(Rights). Rights can be decreased. ex.:

u-r

;User may not read object. ;other rights untouched

Use octal num only @ abs. Mode Def. else at rel. Def's use "=,+,-" signs

disk free

df

;displays amount(free storage capacity) ;1 Block = 1024 Bytes

disk usage

du

;displays num(used blks(current catalogue)) ;1 Block = 512 Bytes ;see also ls -s ; "s" for size

--------------I/O-Redirection ---------------

"<","<", "<<",">>" ... Redirection cmds.

Input from other file than preset

cmd:

< [file]

Output 2 other file than preset

cmd:

> [file]

ErrorOutput 2 other file than preset

cmd:

2> [file]

;Used nums: 0 = std_in 1 = std_out 2 = error_out Output 2 already existing file

cmd:

>> [file]

Output with exception of the >> cmd overwrites existing file Std_out of Cmd is auto made Input of another cmd (= cmd_Pipe) cmd1 � cmd2 ������� PipeSymbol cat [file] � pg

; evokes paging with keypress ctrl

------------Access Rights ------------- Important is construction of this rights in MultiUserSys's - Therefore special DataStruct in FileHeader is necessary Rights, which are connected to file

Options are

r w x

read write (also erase) execute (also Catalogue may be included in AccessPath)

----------------Access Admittance ----------------login: password: Therfore cmp with entry in Password-File. (ASCII-File loc'ed in /etc/passwd) Struct is: name:password:uid:gid:special_Info:Homedir:Shell � � � � � � � � � � � � � � accessPath(Prog), being � � � � � � exe'd after login, � � � � � � most often cmd_� � � � � � Interpreter. No entry � � � � � � signifies /bin/sh � � � � � � � � � � � � assigned catalogue @login 2 user � � � � � � � � � � random optional additional Info � � � � � � � � group identifier (2 byte Integer) � � � � � � user identifier (2 byte Integer � 0), unique user_ID � � 0 for Superuser � � � � coded Password � � UserName 8 chars max (":" is seperator) Manipulation(File) is done thru Superuser(CompuSys). User can change Password. Groups:

several user can be taken together to one Group by Superuser.

----------BaseFileSys ----------struct(FileSys) blknum0 blknum1

bootBlock consists bootstrap(UNIX-Core) SuperBlock - description(FileSys), Ref2List(free Blks) - (see fragmentation) - Name(FileSys), Name(FileCarrier) - Date(last modification, last save (i_node)) - ptr 2 FileHeaderList (i_node) - magnitude(FileHeaderList [Blks]) - SuperBlk remains in MainMem

blknum2...n i_Node-List - description of single File - per File one FileHeader (i_node) - per Blk 8 FileHeader to 64 Bytes blknum n+1...m

DataBlocks - thru Superblk and FileHeaders administrated objects: - real FileContents (including catalogues) - free blks - RefLists (-> i_nodes)

Every FileHeader (i_node) consists @FileSys one unique i_node_num under which the linked file is administrated. 2 enquire i_node num enter: ls -i [path] @ links 2 a File the same i_node num visions @ every catalogue ----------AccesRights ----------Bits 6,7,8 Bits 5,4,3 Bits 2,1,0

describe Rights(Files(owner = first creater)) describe Rights(Group) describe Rights(others)

If Owner has created file: Rights(owner) cannot be altered (exeption Superuser) Problems encountered @ copying: There, the new user cannot alter Rights above the permitted Rights(owner) [this ist done by Owner_Id_check= cmp(UID,Passwrd)] Bits 8...0 Bit 9

Bit 11

Rights t-Flag

File mustn't stored on massStorage (can be set by Superuser only, @SysProgs) attrib

set UID owner permits x-right to all other SysMembers User thru setting(this Bit) (only @ (x) follows executeRight) Applic @ all SystemProgs being accessable by all users

to set this s-bit, x-right must be already avail. ex.:

owner has file Dat1 with rwx-rights open(x-Right) for all SysUsers chmod u+s dat1

;therafter u{rws} is being displ'd

this effect comes thru the fact, that UID(owner) ist valid for user. undo: chmod u=rwx dat1 Bit 10 --------

set GID

like @Bit 11, but restrainted on groupmembers

FileTypes --------

Bits 12...15

Bit 15

describe attribs...

reglular Files

Bit 14,13

if = 10[bin] => catalogue "d" is displayed @ ls cmd (dir) if = 01[bin] => charFile driver "c" is displayed @ ls cmd (char) if = 11[bin] => blk oriented driver File "b" is displayed @ ls cmd (blk) if = 00[bin] => not used (maybe error)

Bit 12

pipe "p" is displayed @ ls cmd there we have a file which has to do with piping, so a temp. File used for processCOM for ex. deleted shortly after use. Mostly non user transparent

RefCtr

Sw-Counter which counts the num(Links) inited by ln cmd on the appro file, if lnk-cntr = 0 then file can be erased

UID_field GID_field

consists UID(Owner) consists GID(Owner)

owner = user if match(UID@i_node, UID@Passwrd_File) = true User may alter userRights ex.:

erasing(File)

ex.:

copying(File)

Precond. !

without w-Right possible after safety_message cp [source] [dest] � � source must at least have r-Right

Owner = user

If dest is not existant @copyRuntime, the dest is created with ownerRights otherwise, if dest is exist, UNIX pays attention 2 rights(dest), although file contents is being overwritten. ---------if owner != user

(remember: if UID @ i_node != UID @ passwordfile)

for this case GroupRights or OthersRights are valid. Alteration(Rights) above this Rights thru current Propritaire (user) impossible. Otherwise RightsSys would be useless. ex.: Owner has following Rights towards file Dat: rwx r-x --u g o

User is no member(Group(owner)) and User != owner Current User has no rights on file dat. error mes if current user wants to copy because r-Right for others is missing cp

--> "permission denied"

cat

--> "cannot open"

;err mes cause insufficient ;rights

readout(rights) ls -l

u

g u ��¿ ��¿ ��¿ ���� ���� ���� rwx rwx

Bit pos Bit 9 : File_Len Timestamp

9 876 �

543

210

� "-" regular File

"c" charFile

"b" blkFile

"p" pipe

in Bytes is updated @ every write/erase-access is updated after every common read or write access

-----------------struct(fileheader) -----------------(i_node =information node @UNIX) (all following parts are three bytes long) -----------------------------------------Attribs + accessRights lnk_ctr uid gid file_len [bytes] time of creation last modification last fileAccess concerning file: prt to DataBlk 0 ... prt to DataBlk 9 references: ref. one_fold ref. two_fold ref. three_fold

(the deeper the ref, the more nested)

--------------------meaning (i_node nums) --------------------i_node_num only exists @ catalague entries

i_node_num i_node_num i_node_num i_node_num

"0" "1" "2" "3"

is reserved to mark not existent (erased) files often used for administration(bad blks) root "/" , def(abs begining(search path)) and following nums handle administrated files

--------catalogue --------i_node: d-attrib has to be set to mark file as catalogue_file begin(catalogue) i_node_num(catalogue) i_node_predecessor ex.:

how is path

. ..

/usr/dat1/dat11 described

root_dir i_node 2 2 2 4 7

. .. bin �not fixed node_nums dev � �6 user �������������� � �i_node 6 ��usr . � i_node 6 . � . � 6 . ref2itself data_blk �� 2 .. ref2predecessor . . . � 26 dat 1 � �������������� �i_node 26 �� dat1 . � i_node 26 . � 26 . . � 6 .. data_blk����������������� . . . 60 dat11

-------file_ops --------

=> file thru path /usr/dat1/dat11 over blk 60 accessable

Acces2file first by setting(i_node) therfore initially: - name(file_sys)........................gather from super_blk - ptr on beginning(file_header_list)....gather from super_blk - concrete num(i_node)..................gather from catalogue 1a) create(file) ------------ gen i_node(file which is to create) - entry (ref2i_node (i_node_num) @catalogue) if file = catalogue ��> write enabled only if file != catalogue ��> write enabled, set len=0 if file already exists & file=catalogue ��> exe enabled only - entry (preset rigths2catalogue) - entry (current sys_time for all sets(time)) - reset lnk_ctr 1b) open(file) ------------ assign file2file_descriptor and pass num2calling program (prog can receive 0..19 filedescriptors) - inc(lnk_ctr) ;find out with ls -l - if open unpossible, pass -1 to file_descriptor - gen help_ptr (pos_ptr) for r/w(file), pointing on 1st word. pos_ptr is passed2pgm opening file. 2) access on file: (r)ead, (w)rite --------------r :

��������> buffer (main_mem)

��������> mass_storage

w :

��������> mass_storage ��������> buffer (for system shutdown, empty buffer first. sync cmd)

Problem: save(buffer) before shutdown UNIX V : buffer is transfered2mass_storage @ 30 secs cycle. 3) close file after acces ---------- dec(lnk_ctr) 4) erase file ---------- marked @dir as unused, i_node_num is "0" -----------------------------III user_env & cmd_interpreter

-----------------------------usr_cmds form a task_Ctrl_language (so called Job Ctrl language = JCL) This is comparable2higher prog_languages, but especially tailored for Data_processing. several cmds can be taken together for cmd_proc (makro_cmd) cmd_interpreter (UNIX-Shell) interprets cmd_proc cmd_interpreter can be set over certain sys_vars = shell_vars, being represended thru txt_$'s. (UNIX lims to 256 sys_vars) var_declaration: name = ... � ������txt_$ � assignment_operator -------------------------------III.1 global resevered sys_vars -------------------------------shell is preset over this vars the most important ones are: HOME = /...

;abs path spec

"Homedir" cd cmd refs2home_cmd path =

:/... :/... � � ������� delimiter or seperator sign. possible access_paths to catalogues:

ex.:

PATH = :/bin:/usr:/bin PS1 = $ "Prompt sign" � ��� entry request ��� spec(sign) to entry request PS2 = > � ��� Prompt 2 display entry of following line IFS =

(I)nternal (F)ile (S)eperator �� space is sign to seperate single fields(cmd_line) mostly <space> gens newline

user_profile file .profile setting(this vars) can happen auto., eg. thru interpretation(profile_file) .prolile is a invisible file being auto execued after login

----------------------III 2. cmds & pos_parms ----------------------cmd_struct: name sucess on exe'tion(cmd) is displayed thru exit_status. exit_status is eval'd after cmd_exe by cmd_interpreter. exit_status is represented by sys_vars. "0" != "0" -

cmd_exe is correct err @ cmd_exe, error_code ret'd

pos_parms consist the ingrediences(a cmd). this parms are loaded @ every cmd_exe Pos_parms

(...outline)

$0 - name(called cmd) $1 ... $9 - parms(cmd) or options (excluding redirections !) $? - exit_status : if 0 = okay, else error $# - num(parms) (name is not valid as parm) $$ - process_num(shell) (see below) ex.:

cmd ls -l file/sub $0 consists "ls" $1 " "-l" $2 " "file/sub" $# $?

$$

" "

"2" "0", false, so exe'tion is correct process_num(shell)

"

--------------III 3 cmd links --------------Pipeline (pipe)

: std_out(cmd) = std_in (next cmd) (temp_save(file) thru p-attr. (see@file_sys)

way of entry: cmd1 � cmd2 ex.:

"�" is pipe symbol

count files(catalogue_path), count contents(file) with wc = word_count cmd

output:

num(chars)

num(words)

num(lines)

options(wc_cmd) - c num( (c)hars) - w num( (w)ords) - l num( (l)ines) ls path � wc -l � � count lines

(1 line is one file)

����� wordcount output is one num on std_out only ex.:

path � pg

-----Filter -----scan one or several files for expr (mask, pattern). result is exit_status, which has to be eval'd further cmd:

grep

<expr>

<....>

grep = (g)(r)(ep) = (g)et (r)egular (e)x(p)ression ex.:

scan file/etc/passwd

cmd:

grep root

for file root

/etc/passwd

link with other cmds is done over pipline ex.:

scan Catalogue "path" for filename "new"

cmd:

ls path � grep new

gen(expr's) with Meta_chars for pattern_scanning (meta_chars are special Ctrl_chars; expr's have to be embraced with " " some meta_chars ^ $ . [S] * \ ex.:

start of line SOL end of line EOL wildcard every sign(string S) preceding char is iterated as long as it occurs following sign even valid, if being no meta_char (so called getaway symbol)

ls - l � grep " ^ [d-]"

outputs all catalogue_names of current catalogue ex.:

output(all files), being "d" or regular in current catalgue. ls -l � grep "^[d-]"

ex.:

num(files) in current catalogue ls � wc -l

ex.:

num(catalogues) in current catalogue

ls -l � grep "^d" � wc-l III. 4 Shellvars & shellscrips (shellprocs) -------------------------------------------shellvar ------(val_assignment)

ex.:

var_name = val � ��chars

access = //node_a10f/user_ebs/egroup20

sev. chars, being distiguished by <space> delimiter, are embraced with brackets ex.: Dir = "ls -l"

(brackets are necessary, because of <space>)

parm_subst: ---------implies, var is subst'ed by val @ occuring place - acces over var_name use "$" - sign

-

ex.:

$var_name � �� causes content to be eval'ed by shell, so var is subst'ed by val

ex.:

Dir

���>

non executable cmd (causes err_msg from interpreter)

$Dir

���>

Dir is subst'ed by ls -l, and ls -l thereafter is executed

output(content(shell_var) ------------------------echo $var_name � �� � ��� spec'd var_name � ��� content of �������� output on std_out ex.:

echo $Dir

���> ls -l on std_out

- immediate output(val) -------------------echo string ����> string is put out - output(string(val)) consisting(several words): obligate echo "string1 string2 .... "

���> brackets are

-

output(string) and content(var) ------------------------------echo "string $name" �� ...alternative for parm_subst name(var)

name = ${pos_parm - $name} � �� "alternative char" name = content(pos_parm)

as far as existant

or name = content(name1), if pos_parm non existant ex.: shell_proc "command" following cmd shell be within the shell_proc "command" var = ${2-$name} � � � �� var being def'd before �� looks, if pos_parm is there call: moved into $0 $1

command para1 � � ;def'd

;So, after entering ;cmd pos_parm 2 is not

var is granted content(name) command para1 alpha � � � $0 $1 $2

;now var gets val alpha ;see sh_proc "command"

cmd_xlations (cmd_subst) --------------------------If you want to subst a cmd as executable cmd, you have to mark it specially. If a cmd is executed, and its output is to be processed further, you need a special manner(embracing) to mark a string as cmd. ex.:

We want to achieve, that the var "Dir" gets access_path without explicitly entering it, but thru canvassing by the pwd - cmd. in short: move current access_path2var "Dir"

enter: Dir 'pwd'

" ' ", apostroph to mark string as cmd

1.) pwd is executed due to the apostroph by that time shellvar gathers abs access_path

2.) output(pwd) is assigned the var "Dir" (no display on std_out) So, the abs acces_path is avail every time via "Dir". ex.:

assign num(catalogues)2var num ='ls - l � grep "d" � wc -l' if shlashes were missing we would encouter a collision between var and file_type, because a file would be gen'ed (remember, even screen_dev is handled as file under UNIX) vars remain sys_vars until logout

- erasing(sys_vars = shell_vars) -----------------------------unset name �

ex.:

;undo declaration(vars)

�� name is for now on unkown to system

output(num(user)) in the system : echo "user : ��

"

'who � wc -l'

;who-cmd has to ;to be in "'"s that ;num is put behind ":"

remarks: -------To commence explanatory remarks as txt_lines inside shell_procs use the "#" (hash_sign) linewise A shell_script (shell_proc) is a sequence(cmds) being entered by editor, including rem's or a sequence(other proc_calls), especially ctrl_cmds. ctrl_cmds: ---------1. decisions a) if - condition ;condition @cmd is given by � then cmd1 ;exit_status, whereby the exitstruct �Ĵ ;status is stored in a certain � else cmd2 ;sys_var, a pos_parm. fi ;end ;if exit_status = 0, true ;��> condition satisfied, "then" branch used.. ;=! 0, false "else" branch used... (pos. logic) condition is gen'd thru execution(cmd). exit_status can be requested over Pos_parm $? short_form

if condition

then cmd fi - special Test_cmds to express conditions --------------------------------------test -f file

;tests if "file" is a regular file

(result be true, exit status = 0, so "file" exists as regular file) refers 2 that one who currently applies cmd test -r file test -w file test -d file

;tests if "file" is a readable file ;tests if "file" is a writable file ;tests if "file" is a catalogue file

- negation -------negation(shortly above used options) over negation_sign "!" ex.:

check, if file is no catalogue test ! -d file

ex.:

write a shell_script to erase file with one parm, if file is no catalogue, but a regular file if test - $1 then rm $1 else echo "excuse me, file is not regular" fi

- multiple brachning -------------------case $Var in �� two ";"s because cmd can be seperated pattern 1) cmds ;; and last ";" is terminator char pattern 2) cmds ;; for one branch . . . *) cmds ;; Var is a free var_name, a pos_parm or a reserved sys_var *) all not mentioned patterns - loops ------a) until condition do cmds (can be several lines long) done b) while condition

;cmd_exe'tion as long as ;condition satisfied

do

cmds

done

;cmd_exe'tion as long as ;condition satisfied

ex.: for a) display date in 3 sec cycle as long as file being named under pos_parm no. one exists. until test -f $1 do date sleep 3 done

;file on which loop waits ;for must be created in ;parallel (open own proc_window)

if called with unspec'd parm, default is used. name1 = $[2-$name] ;if parm 2 is not passed, then ;cmd subst's name by ;content(name). c) for-loop c1) for name in w1 w2 wn ;alludes on passed parms(shell) � ;& processes passed parms. � � don't use "$" before "name" shell_var "name" is sequentially loaded with vals w1...wn. for this vals, loop is exec'ed. (parms to be defined within shell) c2)

for name do cmds done

;loop is exec'ed once for every ;pos_parm, where pos_parm 0 ;representing shellscript is ;not included. ;"name" is free selectable ;var_name

� num(passed vars) � ex.:

for i do echo $1 done

;call with: ;stored as:

alpha beta $1 $2

;output: ;alpha ;beta ex.:

for i do for i do echo $i done echo$i done

;call with parms: A B C ;A ;B A (outer loop) ;C ;�� ;C ;����� ;A ;B B (outer loop) ;C ;�����

;C ;�� ;A ;B ;C ;�� ;C ex.: for file in * do cat $file done

c

(outer loop)

;"*" = wildcard symbolises ;all file_names(cur't catalogue) ;per cycle, content(file) being ;current set is put out

ex.: output(catlogue_subs) only when using ls. can be exec'd correctly. � Else output msg. "error" � list of cur't catalogue if ls. >/dev/null ;null_dev is trashcan then ls Sub echo echo Fehler ;if one expr only, no ;apostrophies necessary fi - cmd_exe'tion and Processes ---------------------------a) exe'tion(cmds/shell_scripts) by naming name

;shell interpretes name ;immediate

cond.: "name" must be readable & executable b) shell is called once again and reads name sh name cond.: "name" must only be readable diag.:

shell �Ŀ � ���>���� sh name �������� ;new shell interprets ;shell waiting � ;"name" � ���������<��������������� ;End of new shell � ;shell activates �

- process = program being in exe ----------see above pipe_flow :

(here cmd or shell_proc)

waiting shell �Ŀ � 2 processes(same shell_pgm)

new shell ��� - backgroundprocess = bck_gnd_process --------------------process exec'ed only if sys @idle. cmd name & ;"&" marks proc as bck_gnd_proc � ;name runs quasi � 2 procs(entered cmds) � � cmd, which is to be exec'd as bck_gnd_proc UNIX : 3 options for cmd_exe'tion ��������Ŀ ��������Ŀ �������������������Ŀ � - Seq. � � - Pipe � � - bck_gnd_process � ���������� ���������� ��������������������� cmd to display cur't proccesses in sys ---------------ps -el

;long list(cur't (p)rocess (s)tatus)

output_struct: ����������������������������������������������������������������������Ŀ � F S UID PID PPID C PRI NI ADDR SZ TTY � ������������������������������������������������������������������������ --> F = process_marking : 0 = process not in main_mem, away, swapped w.s.e. 1 = process in main_mem 2 = sys_process in main_mem, no applic_pgm --> S = Status

R = running = process active S = sleeping = process waits

--> PID = process ID = child ID

;every process is assigned with unique ID

--> PPID = parrent PID

;ID(cur't process), so PID gen'g process

--> C, NI, PRI --> ADDR

;special sys_parms for priority_ctrl, ;user alterable ;start(adr_blk_num(exe'table)) code

--> SZ = Size(exe'table) code - measurement(duration(exe'tion(pgm))) -------------------------------------time name output format:

;prec. is .1 sec

user � cmdexe'tion

sys realtime � � internal Gross_time sys_time for OS_calls including wait_time

IV. scheduler -----------OS_ctrl_prog. set over for long term strategies = high_level_scheduling @Job processing 1.) fast service(jobs) minimise response time @dialog_systems 2.) maximize thruput ���������������������������������Ŀ � thruput = num(jobs) / time_base � ����������������������������������� - exploite operation_means optimally -- achieve 100% processor_load(system) -- supervise resources(op_means) (canvass op_means_assessment & op_means_assignment) -- recognize and use parallelities -- recognize and heed timely seq(parts(tasks)) 3.) fair distribution(compute_time) (= processors) -- pay attention to priorities(job) -- avoid unnecessary wait_times -- avoid injuries

� �� comprimise necessary �

4.) co-determinate attendance(new users) - drive users from system @overload. hi_lvl_scheduling





lo_lvl_scheduling

�����������Ŀ � ������������Ŀ �����������Ŀ � scheduler � �����> � � dispatcher � ������> � processor � ������������� � �������������� ������������� � (inside os-core) IV.1 scheduling strategies (algos) ---------------------------------for preemeptive jobs for non preemeptve jobs

(to preempt = to interupt)

one job gets priority before several jobs because of scheduling strategie (@ one resource)

jobs are waiting in a wait_queue. queue = dynamic data_struct, linking jobs over ptr's and fixing seq(jobs) ex.:

wait_queue job 1

Ŀ � ptr job 2 <�� ���Ŀ � ptr job 3 <������� seq.: 1-2-3

job 1 job 2

� job 3

Ŀ � <�Ŀ � ptr <��

� ���

seq.: 1-3-2 (altered queue_strategy by changing ptr's (= adresses))

jobs

������������¿ �����������Ŀ ���������Ŀ �����������Ŀ ���> �� ��� ���> � scheduler � ���> � os-core � ���> � processor � �������������� ������������� ����������� ������������� � � ������<����� (job_switching_time neglected) def's .: -------job_duration

= whole working_time without processing_time on serving

serving_time

= working_time + wait on service (eg.: waiting as long as predecessor is served)

mean serving_time

=

arithmetic mean_val(serve_times(single job))

working_time

=

time during which job is really computed

remain_time

@UNIX

=

time name output: user sys

A)

time, as long job has to remain computing in system

real � �� serving_time � �� working_time � �

SJF-Strategie

((s)hortest (j)ob (f)irst)

- non preemptive jobs - job_duration must be kown in advance by estimation - minimising(mean serving_time(jobs) (mean serving_time also includes wait_time due to serving_time(predecessor_jobs) ! )

order

� 1. 2. 3. 4. � job_name � A B C D � job_duration per � 8 4 4 4 � tb=time_base time_base � ��������������������������������������������� serving_time �8 12 16 20 t_m = 56/4 tb = 14 tb change order... order

� 1. 2. 3. 4. � job_name � B C D A � job_duration per � 4 4 4 8 � tb=time_base time_base � ��������������������������������������������� serving_time �4 8 12 20 t_m = 44/4 tb = 11 tb --> longsest job @end, or shortest job first general using n jobs(job_duration)

x1,x2,x3,...,xn

job � serving_time ��������������������������������� 1 � x1 2 � x1 + x2 3 � (x1 + x2) + x3 . � . � . � n � x1 + x2 + x3 + ... + xn ������������������������������������������������������� �(serving_time) � n�x1 + (n-1)x2 + (n-2)x3 + ... + 2�x(n-1) + xn for mean serving_time

= t_m

������������������������������������������������������������Ŀ � n�x1 + (n-1)x2 + (n-2)x3 + ... + 2�x(n-1) + xn � ==> � t_m = ������������������������������������������������ � � n � �������������������������������������������������������������� t_m =

x1 + (n-1)�x2 + (n-2)�x3 + ... + 2�x(n-1) + 1 xn ����� ����� � � � n n n n � � � �� strongest weigh weakest weigh ����

... so use shortest job first, because strongest weigh. B) SRT-Strategy ((s)hortest (r)emaining (t)ime) ----------------------------------------------- preemptive Jobs - interactive operation possible, still necessary compute_time of each job must be common. still necessary (remain_time) - queue has to be scanned and rearranged on every incoming job. - job of shortest remain_time is computed. - minimising of mean serving_time: job is broken by job with shorter remain_time. - earlier job first, on equal remain_time - switch_time t_sw is point(interruption) ex.:

Job � duration / tb � arrival_time ��������������������������������������� � A � 4 � 1 � t B � 3 � 2 � C � 1 � 3

when is which job served ? ex.:

��� further jobs don't entry

[SRT]

t_sw � job_A � job_B � job_C � ��������������������������������� 1 � 4.�. � � � 2 � 3.�. � 3 � � 3 � 2 � 3 � 1.�. � 4 � 2.�. � 3 � 0 � 5 � 1.�. � 3 � 0 � 6 � 0 � 3.�. � 0 � . � � � � . � � � � 9 � 0 � 0 � 0 �

.�. =

job is being computed Job_C leaves Sys @t=4 Job_A leaves Sys @t=6 Job_B leaves Sys @t=9

jobs �� C �� A �� B � � � �� offset ! (4-1) + (6-1) + (9-1) mean serving_time = t_m = ��������������������������� = 3 t_m = (3+5+8)/3

= 5.333

time_diag: job � � �������������Ŀ All jobs finished � � A �B� A � B � @t=9, so ready after ���������������������������� t 8 tb's. 1 2 3 4 5 6 9 C) FIFO = FCBS strategy

((f)irst (c)ome (f)irst (s)erved)

----------------------------------------------------------------- devised for non-preemptive jobs - serving_order due to arrival_time jobs ��������������Ŀ �����������Ŀ �����������Ŀ ���> �n�... �2�1� ���> � scheduler � ���> � processor � ���������������� ������������� �������������

n... 2 1

advantages: - procedure easy to implement - behavior(strategie) can well be forecasted disadvant'es: - sometimes longe wait, because early long jobs block late short jobs. FIFI often used in combination with other strategies. criterion is also mean serving_time t_m. t_m has to take into account wait_time in queue. (cmp. with SJF & SRT) D) Round Robin = RR (cyclic assessment_procedure) ------------------------------------------------application:

- typically used in Dialog_sys's (time sharing) (implemented in Process_administration(UNIX))

preconditions: - preemptive_jobs - per job computation is done within a specific preset time_interval = q (quantum, time_slice) - fair assessment_procedure, cause compute_time evenly distributed on all users. jobs

������������¿ �����������Ŀ �����������Ŀ ���> �� ��� ���> � scheduler � ���> � processor � � �������������� ������������� ������������� � � � ;End of time slice � � � ;new ordering � �����������Ŀ � � �� �� �� <�� �� �� �� �� ͵ scheduler � � variable ordering after ������������� � new considerations. � � � ����� <� ��������������������������������

���> results

1. Fill(wait_queue) after FCFS-Strategy, first job come in is first served. If only one job arrives, then it is processed at once without preemption. Time_canvass runs naturally. 2. Several jobs in wait_queue. After time_quantum q expires, job is interrupted and ordered in wait_queue again. This is done dependent from strategy(wait_queue) either at the end(wait_queue)

or in the middle. 3. If job is prematurely terminated before end(time_quantum), next job is processed right after. No wait on end(interval) to avoid unnecessary waits. 4. If a new job entries, it is sorted before the interrupted job. (So the new job has higher Priority.) This is valid only, if both jobs are processed simultaneously from scheduler. ex.: �� queue 3 ���Ŀ ����> �3�2� ��> � �����

�� processor ���Ŀ � 1 � � ����� �

��������������� <�� ���

�� queue �� processor �����Ŀ ���Ŀ ����> �1�4�3���> � 2 � � � ������� �����



��������������� <�� �����

5. after a job is processed, and no new job has arrived, wait_queue is emptied by one element. ex.: assesment(queue) for 2 jobs. q = 1 job_duration per Job is 2�q assuption: wait_queue is filled before first time_intervall, no further jobs entry. a)

b)

�� queue �� processor ���Ŀ ���Ŀ �2�1� ��> � - � t < 0 ����� ����� �Ŀ ���Ŀ �2� ��> � 1 � ��� �����

0 � t � 0 � ��� switching_point � q � t � 2q

c)

�Ŀ ���Ŀ �1� ��> � 2 � ��� �����

d)

�Ŀ ���Ŀ �2� ��> � 1 � ��� �����

2q � t � 3q job 1 leaves system @t=3q

e)

���Ŀ � 2 � �����

3q � t � 4q job 2 leaves system @t=4q

f)

���Ŀ � - � �����

... "processor empty"

choice(q) : q as little as possible ��>

hi load (sys) thru



switching_time

� �� compromise � ��> rel. long wait_times for � following jobs & user

q very large

cycle_time c @RR (R)ound (R)obin = time(one serve(whole wait_queue)) -----------�����������Ŀ � c = n � q � �������������

where

��> n = c / q

practical value for q � 100 ms

q = time_quantum n = num(jobs) in wait_queue including(the one), cur'tly processed c = often preset.

os_switching_time � 5 ms q can be dynamically altered at some systems E) Priority Scheduling ---------------------Priority - @preemptive and non_premtive jobs - arriving jobs get external priority, a pri_num as greater the num, the less claim, the less the pri(job) - one queue per pri static Priority, fixed assement(Pri) - comparably easy --------------to realize - under certain circumstances long wait(jobs(lo_Pri)) dyn. Priority, adaptation(pri) to job_resting_times(sys). ------------��> fair Pri_assesment jobs(lo pri) get timewise higher Pri, to be faster terminated Pri Pri_num FIFO-Queues �������������������������������������������������������������� Pr[0]

0

Pr[0]

1

Pr[0]

2

Pr[0] > Pr[1] > Pr[2]

��������������Ŀ � ���������������� � ��������������Ŀ � jobs sorted ���������������� � due2 pri ��������������Ŀ � ���������������� �

Queue with higher Pri is processed 1st. Inside the queue, internal rules are valid. (mostly FIFO) F) multiple feedback_queues ---------------------------

Designed for which jobs ?

- job's have to be preemptive - short jobs favoured - with inc'ing compu_time(job) its pri is lowered (in short: inc(compu_time)��>dec(pri)) - multiple wait_queues with different time_quantas - After end(time_quanta) job is ordered 2 wait_queue of next lower pri - always, wait_queue with higher pri is emptied 1st. Pri_num time_quanta /q 1 Processor FIFO-Queues ������������������������������������������������������������������� 1

1

2

2

3

4

"ready" ��Ŀ ��������������Ŀ jobs <��� � � <�� � � � � � <���� ���� ���������������� ���������������������������Ŀ � � "ready" ��Ŀ ��������������Ŀ � <��� � � <�� � � � � � <��� ���� ���������������� ���������������������������Ŀ � � "ready" ��Ŀ ��������������Ŀ � <��� � � <�� � � � � � <��� ���� ���������������� ���������������������������Ŀ �

. . .

. . .

n

2^(n-1)

here: -

"ready" ��Ŀ ��������������Ŀ <��� � � <�� � � � � � <�Ĵ ���� ���������������� � ����������������������������� (except last queue, FIFO strategy everywhere )

- time_quanta doubles from queue i to queue i+1. And pri is reduced, pri_num is inc'd queue no. n (lowest pri) enables long remain_time in sys. additional supervision(compu_time(of each job) possible as break criterion. the job, being @begin(queue) is processed 1st and as long as time_quanta(assigned) queue allows. every new arriving job is ordered in queue(highest pri) time_quata is not waited @premature end(job) serving(job) is terminated @the end(time_quanta). Job is ordered in next lower wait_queue.



- empty queues ignored max. job_len @ n queues (without Round Robin) ������������

q =1 tb

t_max/[tb] = 1 + 2+ 2^2 + ... + 2^i + ... + 2^n-1 =

n-1 � 2^i = (1-2)^n /(1-2) i=0

t_max/[tb] = 2^n -1 ������ ex.:

job_len = 10 � q

How many wait_queues are necessary without Round Robin ?

10 = 2^n-1 � � ��> n = �ld 11 � = 4

(take next greater whole num)

So, 4 wait_queues are necessary. t_max = 2^4 - 1 = 15 ex.:

t = 0 in queue 1

jobs �, �, �, len 1, 2, 3, when finished ?

t � time_quantum � queue_num � queue �������������������������������������������� 0 � 1 � 1 � 3 � 2 � 2 �

other queues �, �, �, @t=0 shell be �, �, empty

t=1 �> � is ready, is not ordered in queue 2 t=2 �> � reordered t=3 �> � reordered

t=4 �> � is ready t=4 �> � wll be ready

--------Homework: --------1.) FCFS-Strategy with external Priorities. In queue(scheduler) there are the jobs J[i] with i = [0,1,2]. Priorities Pr[i] are assigned to this jobs, that Pr[2] < Pr[1] < Pr[0]. And D for Job_duration is D[i] = q�(i+1) with time_quantum q. Please state assessment(wait_queue and processor) in dependency to quantised time t=j�q when using FCFS-Strategy. jobs � Num_i � duration D[i]/q � ���������������������������������Ĵ

� � �

0 1 2

� � �

1 2 3

� � Pr[2] < Pr[1] < Pr[0] �

Queue Processor ��������������Ŀ____�Ŀ ���������������� ��� time/q � Queue � Processor � ������������������������������Ĵ 0 � 2 1 0 � x � 1 � 2 1 � 0 � 2 � 2 � 1 � 3 � 2 � 1 � 4 � � 2 � 5 � � 2 � 6 � � 2 � 7 � � x � 2.)

@t=2q job 0 ready @t=4q job 1 ready @t=7q job 2 ready

Scheduler with RR-Strategy

there are 3 jobs in RR-queue. Every job needs two time_slices of duration in t_s. Further jobs don't entry. a) tell assessment(wait_queue) in dependency(time) when does which job get the processor. b) After which time is the queue emptied ? After which time are all jobs terminated ? Queue Processor _____> ��������������Ŀ____�Ŀ � ���/���������������� ��� � ����������������������������� time/t_s � Queue � Processor � ��������������������������������Ĵ <1 � 3 2 1 � x � 1 � 3 2 � 1 � 2 � 1 3 � 2 � 3 � 2 1 � 3 � 4 � 3 2 � 1 � 5 � � 2 � 6 � � 3 � 7 � � x � b)

t_s = time_slices

@t=5�t_s ��> Job 1 ready @t=6�t_s ��> Job 2 ready @t=7�t_S ��> Job 3 ready

Queue empty: @t=6 so, after 5�t_s All jobs finished @t=7 so, after 6�t_s

IV.2 execution(Tasks, processes) -------------------------------A job consists of tasks They are

- sequential

or

- parallel

executable

Parallelity : parallel existing Resources(Compu_sys) usable. inc(thruput) In general ther a several posibilities, to depict a job as Sequence of sequential or parallel Tasks . Every posible sequence is a schedule. - thru Algo underlying the job - thru num and kind(op_means) ��task � ex.: � Prog1 � � �� job1 � output1 � seq. Ĵ schedule � Progs � � �� job2 � output2 � �

compute � compute

� Prog1 � output �

Prog2 Out1

� Out2 � output � ����������������� schedule with one parallelity

1 main processor 1 printer (including I/O Processor) Next: Task be non preemptive

Problem : how to recognize parallellites ��> Depict job by using succesor- and predecessor-relations ��> precedence_graph, a directed graph, it is cycle_free Prog1 * / \

ex.:

still no restrain on num(printers)

\/ \ Prog2 * \/ ------�----------- * out1 ----------- knots on same level � // depict parallelities \ // (posible parallelities) \/ \// printer is ready Out2 * after printout(result(prog1)) - Knots = Task, Task_durance - edges are directed, point to successor - knots @ same level ��> parallel tasks posible here

-a precedence graph is a data_struct (see lists), being interpreteted from scheduler und partly automatically gen'd. Conventions: knots symbolise tasks

identifieres T_i, Task_i, durance : 1 Time_base / / / reserved symbol for task ex.:

T3

T1 * � � T2 * / \/ * � � \

T1,1

\ \/

\

T3,2 * T4 /

\/

/ \/

* T5 ��Ŀ �T4� �����������Ŀ �T1�T2�T3�T5� ������������� Problem :

* � � T2,1 * / \ \/ \ * \/ � * T4,3 � / \ / \/ \/ * T5,2

����������Ŀ � T4,3 � ��������������������������Ŀ �T1,1�T2,1�T3,2 � // �T5,2 � ���������������������������� Time_dependencys can restrain posible paralellities

- precedence_graph doesn't display timely dependence - for display(assignment(resources) in dependency(discrete System_time) see Gantt-Diag (describing schedule) time 1 2 ������������������������������Ĵ Resource1 � � � ������������������������������Ĵ Resource2 � . � ///// � ///// not assigned, can ��������������� � ������������Ĵ still be used, but . � � � � not from this algo . � � (lowers thruput) . � � . � �� display(respective task) os_switching_times are neglected time 1 2 3 ����������������������������������Ĵ process 1 � Prog1 � Prog2 � //// � gantt-diag ����������������������������������Ĵ from precedence_graph ouput � /// � Out1 � Out2 � ����������������������������������Ĵ len (schedule) = T(s) = 3

optimal schedule : shortest schedule possible ---------------ex.:

t_opt(s) = t(s) = 3

Def.(schedule) S: the schedule S is a description(work) for m Resources and a predefined amount(dependencies), which every resource can do a every point in time. eval(schedule) -------------- schedul_len t(s) - comp with pure seq. schedule �����������������������Ŀ --> speed_up_faktor � S_p = t(s)_seq / t(s) � ������������������������� if efficency is inc'd is S_p > 1 -->

Utilisation (Resource) = U_i ��������������������������Ŀ � U_i = t_C / t(s) � 100% � ���������������������������� where t_C = Compute_time within schedule t(s)

-->

Mean Utilization U_p

� � � � �

����������������������Ŀ p � where p = num(resources) � (t_Cj) � = main processors j = 1 � U_p = ���������� � p � t(s) � ������������������������

--> System Thruput �����������������������Ŀ � num(jobs) � � Thru = ���������� � � time � ������������������������� ex.:

job

Thru is strongly dependent from kind(jobs) & division(tasks) and splitting with the jobs

y := a � b + c � d two main processors, every arith. op is of equal len = 1 Tb

def(task)

T1 => a * b T2 => c * d T3 =>

precedence graph

y := T1 + T2 T1 ���>Ŀ ��� T3

T2 ���>�� Gantt Diag: time

1 2 �������������������Ĵ �P1 � T1 � T2 � �������������������Ĵ �P2 � T1 � /// � t(s) = 2 = t_opt (s) s_p = t(s)_seq / t(s) = 3 / 2 = 1.5

( > 1)

U_p1 = 2 / 2 � 100 % = 100 %

processor1 utilisation

U_p2 = 1 / 2 � 100 % = 50 %

processor2 utilisation

U_p = ( t_C1 + t_C2 ) / 2 � t(s) = ( 2 + 1) / 2 � 2 D =

ex.:

1 job / 2 tb's

=

=

3 / 4

= 75 %

0.5 Jobs /tb

Thruput

T 1,1 �����>����������Ŀ � � � T 4,1 � � � T 2,1 �����>���� � ������������>���T 5,1 �������>����������������� � T 3,1 �����>������������

Gantt Diag for 3 main Processors 1 2 3 4 �����������������������������������Ĵ �P1 � T1,1 � T4,1 � � � �����������������������������������Ĵ �P2 � T1 � /// � T5,1 � �����������������������������������Ĵ �P3 � T3,2 � T3,2 � T5,1 �

t(s) = 3 � �

Gantt Diag for 2 main Processors 1 2 3 4 �����������������������������������Ĵ �P1 � T1,1 � T2,1 � T4,1 � � �����������������������������������Ĵ �P2 � T3,2 � T3,2 � T5,1 �

t(s) = 3 �

t_seq

= 6

evals � 2 �P's � 3�P's ��������������������������������������Ĵ t(s) � 3 � 3 S_p � 6/3 = 2 � 2 � � � U_p1 � 100 % � 2/3 = 66,7 % � U_p2 � 100 % � 66,7 % � U_p3 � --� 66,7 % � � � � D � 1/3 � 1/3 � � � Up � 100 % �6/3�3=6/9=2/3 �

� � �



V parallel run and processes ---------------------------------problem :

Pgm_exe is to be enabled thru assignment(op_means), especially main_processors

precond.:

pgm's are exe'able and base on maschine-pgm's in standby but still not exe'ed.

machine pgm

processor ������������������> assignment

process

������������������Ŀ �� � Hi_lvl_scheduler ����Ŀ � �������������������� � jobs, tasks � � feedbck strategies � ���������Ŀ � ����>�� � Core � ����>���� ����������� Process = Run(pgm) being in exe that means HardwareProcessor is occupied to exe machine code(pgm) There are to big classes @OS's : - user_processes - sys_processes Hardware_Processor = real processor : last instance(exe) in the ---------------------------------compu_sys in General more simultaneously existing processes as real processors therefore: alternate assignment(real processors) to the processes --> process_switching by time_mux Virtual_Processor ( = process-ctrl-blk = PCB) : a Data_struct, to ----------------enable process_switch-

ing to this belong - processor_context (content(regs)) - refs (ptr's) on diverse mem_areas every process is represented by its own virtual_processor kernal (nucleus) : main task is process_switching and administration(virtual and real processors) ���������������Ŀ � real virtual � �������ij processor � � ����������������� � ���������������Ŀ ���������������Ŀ ���������������Ŀ � virtual � � virtual � � virtual � � processor 1 � � processor 1 � ... � processor n � � � � � � ����������������� ����������������� ����������������� � � � � � � � � � ���������������Ŀ ���������������Ŀ ���������������Ŀ � process � � process � � process � � � � � � � � 1 � � 1 � ... � n � ����������������� ����������������� �����������������

- Tasks(Kernal) - establish virtual_processor on first exe(pgm) = create process - assign processor = process_switching done by a lo_lvl_scheduler, a os_kernal_pgm, the dispatcher - swiching_events - end(time_slice), time_intervall, external Interrupt end(Process) - processor_administration @ several real processors - process_administration has to care for special states(process) In general we don't have true parallelity in a Compu_sys, but it is tried to approach parallelity. Pseudo_parallelity is tried to achieve by time_wise exe(process's) V.1 Process_state_diag -------------------------a) Process has to be preemptive ��> concrete resume(process) on new assignment(processor) b) Process has to be able to wait on resources, even interminately long



(ex.: Input_dev's ready-handshake) ���> several states(process) have to be possible Process_state_diag ------------------

(with five states)

�����������Ŀ �������Ŀ � � � � �terminated � ���> �active � ������������> � � activate � � � ������������� � ��������� � process � � � is no �������Ŀ �������Ŀ � deactivate � longer � � create � � � � recogn'd �inits � ���> ��� � ready � <�� � from sys � � � � � ��������� ��������� � � Process waits � � on processor �������Ŀ � Task comes in � � � (short wait) �blocked� �� <�� ���� � � ��������� Process is driven from processor (long wait) Process_state & transitions init_state :

- virtual processor (PCB) is gen'd and put in process_table (wait_queue, process_list) by scheduler

ready_state: - wait on processor_assesment thru entry in ready_list - first entry means create (task(scheduler)) active_state:

- process has processor, and is computed

- when process is activated it is erased from ready_list by dispatcher deactivate_state: - processor is taken from process and process is entried in ready_list or re_entried by dispatcher. no wait on external events blocked:

- Process waits on external event, a keyboard_entry for example. How long it waits cannot be forecasted. entry in blocked_list, processor_withdrawel task(scheduler) : scheduler makes book_keeping on devs(sys) ��> dev_management posibly swaping(blocked process) to mass_storage

awaking :

- Event has taken place: process is erased from blocked

list and re_entried in ready_list terminate:

- Process is finished, all results have been computed Processor_withdrawl, Process is erased from process_list

V 2 PCB's and list ---------------------Model(PCB) = virtual processor �������������������Ŀ � PID � (P)rocess (Id)entification unique �������������������Ĵ process_num � state � {state = active, ready, blocked,..} �������������������Ĵ � priorities � regulates processor_assignment �������������������Ĵ additionally � P_prog � start_adr(pgm) where process is evolved �������������������Ĵ � P_dat � start_adr(data_area) �������������������Ĵ � swapped (y/n) � if lack(main_mem), underlying pgm � � responsible for swapping on mass_storage � � (in blocked_state) � mass_storage � �������������������Ĵ � hw_context � save(pgm_regs) for switching �������������������Ĵ � next � ptr2next element(list) ��������������������� PCB consists(Data(several Types)), therfore a PCB is a record PCB's are elements(dyn. expand'ble) data_struck a so called branched list Marks: - ref = adr on succesor (single branched list) - additional ref on predecessor (double ptr'd list) list, single branched follows �����������Ŀ �������Ŀ � begining � �����> � � ������������� � � � � �������Ĵ � � ����Ŀ ��������� � �������Ŀ <����� � � � � � � �������Ĵ � � ��������� �����Ŀ . � . . . .

�������Ŀ � � � � � � �������Ĵ � NIL ���������



last element

{Pascal definition follows} TYPE

VAR

List_element = Record; ptr: pointer END;

{ptr on succesor}

list, list_end, element :Pointer

{global data_struct}

procedure append; BEGIN Listend -> List_element.ptr := element; {Step 1} Listend := element;

{Step 2 : cur't ptr on last element}

Listend -> List_element.ptr := Nil {Step3 : neu end(list) } Obj1.ptr := Addr(objs) Obj2.ptr := Nil

{ptr on sucessor)

some important list_op's -----------------------chain in list = entry obj in a list append = chain @end(list) = list is expanded for one element �����������Ŀ �������Ŀ � List � �����> � � ������������� � � �������Ĵ � � �����Ŀ Step (2) ��������� � �����������Ŀ . � Listend � . ������������� . appended element �����������Ŀ �������Ŀ <������ element �> �������Ŀ � List � �����> � � � � � ������������� � � � � � �������Ĵ � �������Ĵ � NIL � Step (1) � � NIL � ��������� -------------------� ��������� (old) (new) Step (3) A List_element is(TYPE) Record; TYPE L_element := Record . . . Date : D_Type; ptr : Pointer;

(ptr points to successor)

End; ex.:

�������Ŀ chaining(obj1) and obj2 � obj1 � �������Ĵ Assume: obj1 & obj2 are vars(TYPE) L_Element � � �����Ŀ ��������� � �������Ŀ <������ begining(pgm) � obj2 � var obj1,obj2:L_elment; �������Ĵ � � ��������� Access on Record_element is done via selector. It is gen'd by a var(Typ(Record)) and the name(appropriate) rec_element ex.:

var_name. record_element

ex.:

Type_declaration (records) as above: VAR

union:name; {Var(Rec_type)} access:integer;

. . . Begin {Rec_element "num" after VAR "access"} . . . access := union.num End; - New std_func

Addr(name) ������� name(struct) which adr has to be determined.

ptr := Addr(obj)

{ptr is(TYPE) pointer;}

Adr_assignment:

ptr_var ��> Type_identifier

selection(element(several elmenents(same Type))) num_bases : hex, Q, bin List_end : NIL Data_Type "Record"(Pascal) ex(record).: TYPE

name = Record num: Integer; Date: Boolean;

Element(cmd_list)

(type_agreement)

�������Ŀ � ����������> �������Ĵ � ����������> ���������

ptr on PCB ptr on next ready process

element(blocked_list) �������Ŀ � ����������> ptr on PCB �������Ĵ � � � ����������> � � � � ���� ptr on dev_routines, on which ready_sig is � � � � waited for � ����������> � �������Ĵ � ����������> ptr on next blocked process ��������� pseudo_language, basing on std_pascal with some new structs. new data_type POINTER (= ptr on adr = start_adr(data_struct) e.g. list) declaration:

VAR name : POINTER;

Related Documents


More Documents from "Manasvi Mehta"