Transcript 9. Linking and Sharing

9. Linking and Sharing
9.1 Single-Copy Sharing
– Why Share
– Requirements for Sharing
– Linking and Sharing
9.2 Sharing in Systems without Virtual Memory
9.3 Sharing in Paging Systems
– Sharing of Data
– Sharing of Code
9.3 Sharing in Segmented Systems
Operating Systems
1
Single-Copy Sharing
• Focus: sharing a single copy of code or data in
memory
• Why share?
– Processes need to access common data
• producer/consumer, task pools, file directories
– Better utilization of memory
• code, system tables, data bases
Operating Systems
2
Linking and Sharing
• Linking resolves external
references
• Sharing links the same copy
of a module into two or more
address spaces
• Static linking/sharing:
– Resolve references before
execution starts
• Dynamic linking/sharing:
– While executing
Operating Systems
3
Sharing without Virtual Memory
• With one or no Relocation Register (RR)
– All memory of a process is contiguous
– Sharing user programs:
• Possible only with 2 user programs by partial
overlap
• Too restrictive and difficult; generally not used
– Sharing system components:
• Components are assigned specific, agreed-upon
starting positions
• Linker resolves references to those locations
Operating Systems
4
Sharing without Virtual Memory
• With multiple RRs
– CBR: Code Base
Points to shared
copy of code
– SBR: Stack Base
Points to private
copy of stack
– DBR: Data Base
Points to private
copy of data
– Multiple processes
can share code or data
Operating Systems
5
Sharing in Paging Systems
• Sharing of data pages:
– PT entries of different
processes point to same pages
– If shared pages contain no
addresses, linker can:
• assign arbitrary page
numbers to shared pages
• record in PT
– So shared data page can
have a different page # in
different processes
– But address in shared page
does not work
Operating Systems
6
Sharing in Paging Systems
• Sharing of code pages
• Solution 1: assign the same page numbers to all shared
pages
– Restrictive
• Solution 2: no page numbers in shared code
– Compile self-references relative to CBR
– Compile data/stack references relative to DBR/SBR
– Limitation: shared code cannot contain any external
references
Operating Systems
7
Sharing of Code Pages in Paging Systems
When to resolve external
references (to shared pages)?
• loader could check which
shared pages are resident,
adjust PT (e.g. n2)
– too much overhead
– many shared libs are
never accessed
• solution: defer linking until
first access:
– dynamic linking
– using transfer vector
Operating Systems
8
Dynamic Linking via Transfer Vector
• One tv entry per shared
module
• Initially each entry contains
only a stub
• Stub does the following:
– checks if referenced code
is loaded
– if not, it loads it
– it then replaces itself by
a branch to shared code
• Next reference to the same
code bypasses stub (simple
indirect branch)
Operating Systems
9
Sharing in Segmented Systems
• Similar to paging
• Data pages: assign any segment numbers
• Code pages:
– Assign same segment numbers in all STs, or
– Use base registers for self/data/stack references
• Limitation: no addresses in shared segments
• But segments are logical entities—permit general solution:
– Keep private linkage section (LS) for each segment
– External references are in LS, not in code
– Every process has its own copy of LS:
• Can use different segment numbers
– Introduced in Multics (1968)
Operating Systems
10
Unrestricted Dynamic Linking/Sharing
• Self-references resolved using CBR
• Other references via addresses but kept in private LS
– sharing is unrestricted (can use different page #s,
shared segments can contain external references)
• Linking/sharing is dynamic
– External reference kept symbolic: (S,W), where S is a
program name and W is a label, e.g. (HelloWorld, start)
– At runtime, on first use:
• (S,W) is resolved to (s,w), using trap mechanism
• (s,w) is entered in linkage section of process
– code is unchanged
– Subsequent references use (s,w) without involving OS
Operating Systems
11
Dynamic Linking/Sharing
Before and After External Reference is Executed
Operating Systems
12