Week 6 - Lecture notes 6 PDF

Preview

Summary

All of Week 6 notes for INFO 1211 operating systems....

Description

Week 6: Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash Concurrency • at this point we have discussed how operating systems are largely concerned with managing processes and threads - could be in a SISD, SIMD, MISD or MIMD system • issues arising from concurrent processing: - how do processes communicate with each other? - how can processes share resources? how can this be done fairly? - what methods exist for synchronizing processes? - how can processor time be allocated to processes? - (note that all of the above apply to threads as well as to processes)

Mutual Exclusion • one important concept to consider is mutual exclusion - mutual exclusion is defined as the action of preventing other processes from accessing a resource while it is being used by a process • example: suppose two applications both want to use the printer at the same time - cannot just interleave commands and data from both applications, since the result would be gibberish • the part of a program which accesses a shared resource like this is called a critical section - only one program at a time can be in its critical section - other examples include accessing a file, accessing the contents of a data structure, etc. • the need to enforce mutual exclusion would seem to indicate that it is necessary for a process to be able to “own” a resource and to give it up only when it has finished with it - this can lead to other problems • suppose a process needs two resources, A and B - suppose there is another process which needs those resources also, but in the opposite order - it might be possible for the first process to hold resource A and wait for resource B to become available, at the same time that the second process is holding resource B and waiting for A to become available - if neither process relinquishes its resource until the next resource is freed, the two processes will be at a standstill, or a deadlock • a similar problem is that of starvation - in this case, imagine the existence of three processes all dependent on one resource

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 2 of 11

- it might be possible, if no steps are taken, for two processes to end up swapping control of the resource back and forth between each other thereby starving out the third process - here there is no deadlock, but one process may be prevented indefinitely from continuing • in both cases, the OS will need to be involved - processes must have some mechanism for requesting mutual exclusion, and the OS must be able to grant control of a resource as needed to a process • ideally, there are six requirements that must be met to support mutual exclusion - it must be enforced; that is, when more than one process has a critical section for a resource, only one should be allowed into its critical section - deadlock and starvation should be prevented - a process requesting entry into its critical section must be allowed to do so without delay, when no other process is in its critical section for that resource - a process must be in its critical section for a finite time only - when a process halts in its noncritical section, it must not interfere with other processes - no assumptions are made about the speed of processes or the number of processors • there are three basic ways that mutual exclusion can be handled - allow the processes themselves to handle it by coordinating their actions - this incurs performance overhead and relies on the processes implementing this correctly - provide hardware support for mutual exclusion - in a uniprocessor system, simply allowing processes to disable interrupts could work - before a critical section is entered, the process disables interrupts, and enables them again after the critical section is finished - this would incur a significant performance penalty, and might not work in a multiprocessor system (unless you disabled interrupts for every processor in the system) - implement some multistep hardware instructions as atomic instructions, meaning they cannot be interrupted in the middle of completing - for example, when a memory address is examined to see if it should be changed, lock out other processes from altering its value in the meantime Process 1: if a == 0 then set a = 10 -

Process 2: set a = -1

if Process 2 executes after Process 1 has checked the value of a, perhaps it is not correct for Process 1 to reset the value of a to 10, since a is now negative - a special instruction could be implemented that would make sure Process 1 finished its task (above) before any other process could access that memory space - unfortunately this scheme doesn’t necessarily prevent deadlock or starvation - provide operating system support - there are a number of methods in common use; they include semaphores, monitors and message passing

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 3 of 11

• semaphores - a semaphore is like a variable whose value is maintained by the operating system; it will be initialized to zero or a positive value - a process can issue a signal or a wait instruction - when a wait is issued, the semaphore value is decremented - if the semaphore value becomes negative, the process that issued the wait blocks - if the value is zero or positive, the process can continue - when a signal is issued, the semaphore value is incremented - if the resulting value is 0 or less, a process that has been blocked can continue - the following example is from Stallings, 2009:

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 4 of 11

- notice how the value of the semaphore named lock varies as processes A, B and C “wait” on a resource and “signal” when they release the resource - notice that if n is the number of processes waiting for the resource, -n is the value of the semaphore - also, note that the starting value of the semaphore indicates how many processes at a time may use the resource; for example, if the starting value had been 2, B would not have been blocked when it called wait - one important aspect of semaphores is that only three operations are allowed on them: initialization, waiting, and signalling - the type of semaphore described above can be called a general semaphore or a counting semaphore; a binary semaphore is different, and can take on only the values 0 and 1 - a slightly different take on the binary semaphore is the mutex - a mutex works like a binary semaphore, but there is a constraint that the process that locks a resource must be the one to unlock it - when semaphores are used, the OS keeps a list of the processes that are blocked on that semaphore; processes may be unblocked in FIFO order or some other order • monitors - a monitor is an entity supported in some programming languages - the concept is that the monitor encapsulates data values that can only be accessed by passing messages to (calling) the monitor - in this way, it is like an object in an object-oriented program - a monitor has these characteristics: - its local data can only be accessed by the monitor’s functions, and not by external ones - a process can enter the monitor by invoking one of its functions - only one process may be executing in the monitor at any given time; other processes that wish to execute in the monitor are blocked - monitors (and semaphores) are supported in Java • message passing - one final approach to mutual exclusion is to allow processes to communicate directly with each other

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 5 of 11

- in this scheme a send instruction and a receive instruction are provided - sending and receiving a message must specify a recipient or a sender, respectively - this allows messages to be sent to a specific process, and for processes to wait on messages from a specific process - in terms of blocking when sending or receiving, message passing can usually be done in one of several ways: - blocking send, blocking receive: also known as a rendezvous, both the sending and receiving processes block until the message is delivered - allows for tight synchronization between processes - nonblocking send, blocking receive: this is a useful scheme, as the sending process can send many messages without having to wait - processes that must wait to receive a message before proceeding are simply blocked until that message arrives - a client/server relationship is an example of where this could be used - nonblocking send, nonblocking receive - processes that are waiting to receive may be dealt with in a FIFO manner, or using a priority system - message passing lends itself well to distributed systems

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 6 of 11

The Tale Thus Far... • so far we have looked at the following commands in Linux: - working with directories: cd, pwd, ls, mkdir, rmdir - Linux supports wildcard usage with file names (DOS and Windows do as well) - * stands for any number of characters (0 or more) - ? stands for exactly one character - e.g. ls a* means show files with names starting with a ls a??? means show files with four-character names that start with a - working with files: cat, chmod, cp, less, more, mv, rm, sort, wc - general commands: clear, finger, passwd, w, who • we have also spent some time looking at the vi editor

Setting Up Your Terminal: stty • the stty command allows you to set certain terminal characteristics, including the special characters needed to interact with Linux • use stty –a to see the current settings (^c stands for Ctrl+c, etc.) - intr = ^c stop the currently running process - erase = ^? backspace character - kill = ^u erase line that you are currently typing - start = ^q, stop = ^s to pause/unpause text that is scrolling by - susp = ^z suspend the current job - eof = ^d character that indicates end of file • you can change the character for a specific code using the stty command - e.g. stty erase ^? (press your Backspace key after the word erase) • if you have a number of reassignments to do with stty, instead of typing them all in each time you log on, if you are using the bash shell you can put them in the .bash_profile file in your home directory - the .bash_profile file is a hidden file, like all files which start with a dot, and doesn’t show up when using ls unless you use ls –a or ls –A - (speaking of hidden files, you can create a .plan file and/or a .project file. When someone uses finger to see your details, your plan and project will be displayed for them.) - note: it’s also common practice to put these commands into the .bashrc file instead; we’ll make some more comments about this in the next class

Environment Variables and Shell Variables

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 7 of 11

• environment variables are variables that have a special meaning to the shell - programs can use them to find out information about the current Linux environment • you can use the env and printenv commands to see all of the environment variables and their current values; here are some: - USER=astu1234 - LOGNAME=astu1234 - HOME=/home/astu1234 - PATH=/usr/local/bin:/usr/bin:/usr/local/sbin:/usr/sbin:.: /home/astu1234/.local/bin:/home/astu1234/bin - MAIL=/var/spool/mail/astu1234 - SHELL=/bin/bash - TZ=Canada/Pacific - PWD=/home/astu1234 - you can also use the echo command to see the value of an environment variable: $ echo $LOGNAME astu1234 - the echo command is used to display information on the screen - if you just use echo LOGNAME, the actual text LOGNAME appears - you must put a $ in front of a variable’s name to actually access the variable’s value • one very important environment variable is PATH - this variable contains a list of directories, separated by : symbols - the shell looks in the directories to find the programs that you want to run - for example, the ls command is actually a program - when you type ls to see your files, Linux has to actually run the program - question: where is the program file actually stored? - use the which command to see where a command is actually located $ which ls /usr/bin/ls - /usr/bin contains the majority of the Linux utilities - however, you may need to look in other directories as well, to find the programs you need; for example, if you have a number of programs that are in a subdirectory of yours, you would need to include that subdirectory in PATH - even if your program is in your present directory, you still either need to have your pwd in PATH, or use the absolute pathname of your program when you invoke it - as an example, the /usr/sbin directory contains some utilities that could be useful, but /usr/sbin is not listed in the PATH variable - to fix this, you have a couple of options: - reset the entire PATH variable as follows

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 8 of 11

$ PATH=/usr/local/bin:/usr/bin:/usr/local/sbin:/usr/sbin:.: /home/astu1234/.local/bin:/home/astu1234/bin:/usr/sbin - that’s a lot of typing, if the PATH variable already contains a large number of directories - instead, you can add your new path directory to the existing path variable: $ PATH=${PATH}:/usr/sbin - what this does is to set the path to whatever is currently in PATH (remember to put the $ symbol in front of ‘PATH’) plus /usr/sbin as well • shell variables can be seen using the set command - some of the variables show up as both environment variables and shell variables; for example, PATH, PWD, and USER show up in both lists - variables unique to the shell list include: - BASH_VERSION - HISTFILE - PROMPT_COMMAND

current version of the shell name of the file holding a list of your previous commands command that gets executed each time the prompt is shown

• there are also a number of shell options which can be turned off or on as you desire - to see the settings, use the command set –o - there are a lot of options, but three that are good to know are: - ignoreeof - noclobber - noglob

when on, it keeps typing a ^d on the command line from logging you out immediately; this can prevent accidentally logging out when on, it prevents you from overwriting existing files; you will see the message “cannot overwrite existing file” if you try when on, it prevents “file globbing”, which is using the ? and * wildcard characters for file names

- to turn on the options, use: - set –o ignoreeof, or set –o noclobber, or set –o noclobber - you can turn each one off by using set +o instead of –o, in each case • example: setting the prompt - the prompt string in bash is contained in the PS1 shell variable - for example: $ PS1='bash: ' bash:

this sets the prompt to the text bash: … …as you can see from the result

- you can set the prompt to whatever text you want, but bash allows you to customize the prompt greatly - you can run a command and use its result as part of the prompt - for example, you can use the whoami command to put the user’s name in the prompt: $ PS1='`whoami`> ' note the ` ` (backquote) characters around the command username> prompt now shows the user’s username, followed by >

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 9 of 11

- you can also do this to include the time in the prompt string: $ PS1='`date +%T`> ' 13:25:11>

date +%T is the command to show the current time now the prompt shows the time

- if you do this, however, the prompt will be “stuck” on whatever time it was when you issued the command to change the prompt; it won’t update as time passes - if you want to see the actual time in your prompt, you can do that by using special codes in the string you use for PS1 - there are lots of codes, but some that you might find useful are: Code \d

Result current date

Code \w

\h, \H

the hostname

\!

\n

a new line

\###

\t, \T, \@, \A

current time, in different formats

\\

\u

current user’s username

\v

Bash version

\[

\]

Result current directory history number of this command the ASCII character with octal code ### a backslash to surround a sequence of special non-printing characters*

…and more!

*

non-printing characters allow you to do things like change the prompt text’s colour, move the cursor around, change the content of the title bar of the terminal window, and so on - for a huge “tl;dr” explanation of how to set the prompt, you can go to https://www.tldp.org/HOWTO/text/Bash-Prompt-HOWTO - here are some example prompt settings for you to try; see if you can figure out what they do before you actually try them PS1='\u(\!): ' PS1='\h:\T $ ' PS1='\n\u@\h(\!)% ' • if you have particular shell variable values that you like to use, you don’t have to type them in each time you log in - the .bashrc file is traditionally where any setting of shell variables takes place - this file is also used for setting up any aliases you might have

Aliases • eventually you’ll discover that you like to commands in particular ways, and that you don’t want to type them in all the time; for example:

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 10 of 11

- ls - ls is very useful, but has two drawbacks; in its raw form it doesn’t show a lot of information, and if there are a lot of files in the directory, they will rapidly scroll off the screen - you could fix this by typing ls –l | more all the time to see the detailed file information and pipe it to more, but that is a lot of typing - instead, you can create an alias in this way alias dir='ls –l | more' - now, whenever you type the DOS-like command dir, csh will substitute the improved version of the ls command - if you don’t like using a different code, you can use ls just as well alias ls='ls –l | more' - rm - a reason to use an alias for rm is because by default, rm does not prompt you when you indicate you want to delete a file - this makes it easy to accidentally delete files - rm –i prompts you so you have to confirm file deletion alias

rm='rm –i'

• you may also choose to use alias to abbreviate commands that you use often - e.g. m for more, md for mkdir, rd for rmdir, and so on • the best place to put your list of aliases is in your .bashrc file • following is an example .bashrc file: #

-----

Aliases

-----

#

alias h=history alias rm='rm -i' alias dir='ls -al | more' alias md=mkdir alias rd=rmdir #

-----

Environment Control

-----

mesg y # let other users write messages to my screen HISTSIZE=50 # remember the last 50 commands PATH=/usr/local/bin:/usr/bin:/usr/local/sbin:/usr/sbin:.

INFO 1211

Week 6 Concurrency: Mutual Exclusion, Synchronization; More Useful Linux Commands and an Introduction to bash

Page 11 of 11

Using Your History • when you set your HISTSIZE variable to anything greater than 0 (e.g. HISTSIZE=50), the shell will remember that number of previous commands • to step back through your previous commands, you ...