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;