I thought a segment table had 4 segments and looked something like

[RedX]

I thought a segment table had 4 segments and looked something like this:

[tex]
\begin{array}{ccc}
\mbox{Seg ID# } &\mbox{Base }& \mbox{Limit} \\
\mbox{0 (code) } &0\mbox{x}4000& 0\mbox{x}0800 \\
\mbox{1 (data) } &0\mbox{x}4800& 0\mbox{x}1400 \\
\mbox{2 (shared) } &0\mbox{x}\mbox{F}000 & 0\mbox{x}1000\\
\mbox{3 (stack) } &0\mbox{x}0000 &0\mbox{x}3000 \\
\end{array}
[/tex]

But on an actual CPU, there is a register for each of these segments, so it seems like the table above is useless. Is each segment register 32 bits, with the 1st 16 bits containing the base address, and the 2nd 16 bits containing the limit? So when the CPU swaps out your program for another one (called a context switch), it swaps out all the segment registers with new ones that contain the different base address and limits for the new program?

I guess another way to put is this: do the segment registers contain a pointer to the memory address containing the information about the base and limit, or contain the actual information about the base and limit inside it? I heard that the segmentation table is in the processor itself, and not the memory, so that when you switch programs, you have to switch out the entire table, instead of a single pointer to the memory address of a table. But I'm not sure this is right.

I tried understanding Intel's specification for the segment registers, but I don't quite understand them. Their segment register is 16 bits, not 32 bits. 13 of the bits are an index to a segment entry, and the rest are flag bits. Does this mean that, say for the code segment register, there are 2^13=8 K entries?

So really the table should look like this:

[tex]
\begin{array}{ccc}
\mbox{Code Seg ID# } &\mbox{Base }& \mbox{Limit} \\
\mbox{0} &0\mbox{x}4000& 0\mbox{x}0800 \\
\mbox{.} &0\mbox{x}4800& 0\mbox{x}1400 \\
\mbox{.} &0\mbox{x}6200& 0\mbox{x}1000\\
\mbox{.} &0\mbox{x}7200 &0\mbox{x}1000 \\
2^{13}-1 &... &... \\
\end{array}
[/tex]

and there is also a similar 2^13 entry table for the data segment, the stack segment, and the shared segment? Why would you need 2^13 segments for just the code, 2^13 segments for the data, 2^13 segments for any segment register that exists? I thought a single program only needed 1 segment for code, 1 segment for data, etc, like the 1st table I have?

For each of the 2^13 entries there seems to be two 32-bit numbers that describe each entry ( http://www.cs.cmu.edu/~410/doc/segments/segments.html ), and one of them has 16 bits for the base and 16 bits for the segment limit. The other one I have no idea what it is. But how does the processor, just from looking at the 2^13 bit number in the register, know to look at these two particular 32-bit numbers stored somewhere? Doesn't the processor need the address for those 32-bit numbers? But how does it get a 32-bit address from just the 2^13 bit number?

 

[rcgldr]

I'm not sure, but I think segments are mostly used for transferring data between tasks or between a dll's local memory and a calling task's memory, at least since Windows NT. I think Windows uses page mode (virtual memory) and sets up the segments for a flat address space, although the segment registers may still be setup to prevent execution of code from non-code space areas.

 

[lostinxlation]

I'm not an expert of x86, but in general, the address translation is performed in the similar ways on any processors, so here is my thought.

I tried understanding Intel's specification for the segment registers, but I don't quite understand them. Their segment register is 16 bits, not 32 bits. 13 of the bits are an index to a segment entry, and the rest are flag bits. Does this mean that, say for the code segment register, there are 2^13=8 K entries?

If you look at how the paging(or segmenting depending on how it is called) is performed, what an address translation table gives you is starting physical address for the given virtual address(VA). More specifically, they concatinate the starting physical address you get from DAT or TLB and the lower part(offset) of the virtual address. That's why segmentation register only has 16bits. If you search "two level paging"(which is most commonly used scheme in VM system) on google, you might be able to find a good diagram.

Again I'm not an expert of x86, but I think your assumption of 8k separate segments(max) is probably right, but that segment registers need 2^13 entries isn't correct to me. You might have as many as 2^13 entries in segmentation table, but segment registers are just a few registers that define the physical address of segment currently in use(for quick look-up).

and there is also a similar 2^13 entry table for the data segment, the stack segment, and the shared segment? Why would you need 2^13 segments for just the code, 2^13 segments for the data, 2^13 segments for any segment register that exists? I thought a single program only needed 1 segment for code, 1 segment for data, etc, like the 1st table I have?

A single process needs only one segments for code/data etc at a time, but there is no guarantee that the data size the single process processes is smaller than the size of segment. If the data size is huge, you have to deal with multiple pages/segments. And also you want to run multi-task programs which switch the segments. Without having many segments, you can't have multiple contexts.

For each of the 2^13 entries there seems to be two 32-bit numbers that describe each entry ( http://www.cs.cmu.edu/~410/doc/segments/segments.html ), and one of them has 16 bits for the base and 16 bits for the segment limit. The other one I have no idea what it is. But how does the processor, just from looking at the 2^13 bit number in the register, know to look at these two particular 32-bit numbers stored somewhere? Doesn't the processor need the address for those 32-bit numbers? But how does it get a 32-bit address from just the 2^13 bit number?

There should be a register that has a base address of the address translation table that OS can set. And how to reach the particular entry of the segmentation table is, usually, by using the upper field of VA as an offset from based address of DAT table to point to the entry.
How it gets 32bit address from those segment is, as I said above, through the concatination of a segment(or page) address and an offet you get from VA.
A quick example is suppose you have VA, 0xdeadbeef. The upper 16bits, 'dead', is used to look up the address translation table(how DAT is performed is hardware dependent), and gets, 000f, as a segment address(And I believe 000f is set to the segment register for this particular context). You concatinate 000f and lower 16bits of VA, 'beef', which makes physcal address, 0x000fbeef. This is how DAT works in most of CPUs.
Next time you access the memory within the same context, you don't have to run DAT again, because looking up the segment register gives you the base physical address of segment.

One thing you have to check is which processor you are focusing on. Virtual memory system is implement dependent, which implies every x86 variant could have different implementations.

 

[lostinxlation]

OK, I found an old x86 book at home and just quickly read it.
Here is what I got(I corrected some part I wrote in #3 response as well).

I thought a segment table had 4 segments and looked something like this:

[tex]
\begin{array}{ccc}
\mbox{Seg ID# } &\mbox{Base }& \mbox{Limit} \\
\mbox{0 (code) } &0\mbox{x}4000& 0\mbox{x}0800 \\
\mbox{1 (data) } &0\mbox{x}4800& 0\mbox{x}1400 \\
\mbox{2 (shared) } &0\mbox{x}\mbox{F}000 & 0\mbox{x}1000\\
\mbox{3 (stack) } &0\mbox{x}0000 &0\mbox{x}3000 \\
\end{array}
[/tex]

But on an actual CPU, there is a register for each of these segments, so it seems like the table above is useless.

Why are these useless ? Segment registers seem to point to the base address of segment current process is using. To me, it seems a simple form of TLB.

Is each segment register 32 bits, with the 1st 16 bits containing the base address, and the 2nd 16 bits containing the limit?

Yes and yes.

So when the CPU swaps out your program for another one (called a context switch), it swaps out all the segment registers with new ones that contain the different base address and limits for the new program?

I don't think it 'swaps out' the segment register. It just loads the segment register with new value. Next time you come back to the same context, you have to run DAT and recalculate the segment address, I guess.

I guess another way to put is this: do the segment registers contain a pointer to the memory address containing the information about the base and limit, or contain the actual information about the base and limit inside it?

A segment register contains a pointer to actual physical location where the given segment starts.

Segment registers are pointer to the base address of segment I heard that the segmentation table is in the processor itself, and not the memory, so that when you switch programs, you have to switch out the entire table, instead of a single pointer to the memory address of a table. But I'm not sure this is right.

I doubt you can have a segment table in the processor. It's too large and the size is unpredictable depending on the setup. However, you might be able to have a part of them in the processor, like TLB does. Usually address translation table is in the memory.

 

[rcgldr]

Again, I don't think that versions of Windows make much use of segment registers since winmem32 or win32s extensions on Window 3.1. Still some starting points:

http://en.wikipedia.org/wiki/Global_Descriptor_Table

http://en.wikipedia.org/wiki/Local_Descriptor_Table

I'm under the impression that Windows sets up the segement registers to create a flat 32 or 64 bit virtual address space, and that page mode is used to translate the virtual addresses into physical addresses. As mentioned before, the segment registers are are also used to transfer data between tasks or dlls. The only table in the cpu is the translation look aside buffer (cache).

http://en.wikipedia.org/wiki/Page_table

http://en.wikipedia.org/wiki/Translation_lookaside_buffer

 

[RedX]

Thanks. That was really helpful. I'm watching some free online videos on operating systems, and it's great because it's free and good, but you can't ask the instructor questions. For anyone interested:

http://academicearth.org/lectures/introduction-what-is-an-operating-system-anyway

(warning: if you click on the link it will immediately start playing a flash video [just like if you entered the URL of a youtube video], so turn the volume down)

More specifically, they concatinate the starting physical address you get from DAT or TLB and the lower part(offset) of the virtual address. That's why segmentation register only has 16bits.

I think I now understand a page table (your 0xdeadbeef example helped a lot). There is a page-table base register that contains the physical address of the first entry in the page table. So take the case of pages that are 6-bits in size, in an 8-bit processor. So a page table might look something like:

[tex]

\begin{array}{cc}
\mbox{Page# } &\mbox{Frame#}\\
\mbox{0} &\mbox{2} \\
\mbox{1} &\mbox{3}\\
\mbox{2} &\mbox{1}\\
\mbox{3} &\mbox{0}\\
\end{array}[/tex]

But this is really an abstraction. Say the the value of the page-table register is byte #32 (there are 64 bytes since an 8-bit processor can access 2^8 bytes of memory). At byte #32 is stored the first 2 bits of the physical address of page 0 (in this case 10), at byte #33 is stored the first 2 bits of the physical address of page 1 (in this case 11), etc. So when a program wants access to the 8-bit virtual address of the form 00offset, then the CPU sees the 00 so it searches byte 32 for the two bits and replaces them to get: 10offset. Similarly if the virtual address is of the form 01offset, the CPU looks at byte #33 to get: 11offset. There are six extra bits in each byte that are unused. I suppose these extra bits can be used for flags such as access rights. While retrieving the first 2 bits at byte 32 for example, it can scan the rest of the 6 bits and if there is no permission it can stop the whole process and complain.

So in a real example, say a 32-bit processor with pages of size 2^12=64K and a total of 2^20 pages, with the page-table register pointer at byte #32, then for a virtual address of 00000000000000000000twelveoffset (page 0) the CPU looks at all 8 bits of byte #32 and all 8 bits of byte #33 and the first 4 bits of byte #33 and replaces the twenty 0s with these bits:
00000000000000000010twelveoffset. The remaining 4 bits of byte #33 can be used for flags, or you can add byte #34 and have 12 bits for flags. Then the entry for page 1 would begin in byte #35, and each page entry would be spaced 4 bytes apart from the base physical address of byte #32.

So if this right, and a segment register holds the physical address of the first segment in a segment table, then the register would be 16 bits only if the CPU were 16-bit.

You might have as many as 2^13 entries in segmentation table, but segment registers are just a few registers that define the physical address of segment currently in use(for quick look-up).

That would make more sense, but unfortunately, looking at the x86 specification, it doesn't seem like the segment register holds a physical address. But then again I read that the x86 does segments in a weird way. I'm not interested in a particular processor, but just how computers work in general, so if most chips store the physical address of the 0th segment in a segment table in the segment register, then I can accept that.

A single process needs only one segments for code/data etc at a time, but there is no guarantee that the data size the single process processes is smaller than the size of segment. If the data size is huge, you have to deal with multiple pages/segments. And also you want to run multi-task programs which switch the segments. Without having many segments, you can't have multiple contexts.

Segments can be variable length unlike pages, and I think the length is set by the linker after compilation? So you shouldn't have to worry about segments not being large enough. So the code segment can be as large as the linker/compiler says it needs to be, the data segment can be as large as the linker/compiler says it needs to be, etc. But I guess if you use really large segments then memory can get fragmented easily, and if you just use one segment for the code, one for data, etc. then there is no way you can give memory back to the CPU until your entire program ends.

Again, I don't think that versions of Windows make much use of segment registers since winmem32 or win32s extensions on Window 3.1. Still some starting points:

http://en.wikipedia.org/wiki/Global_Descriptor_Table

http://en.wikipedia.org/wiki/Local_Descriptor_Table

I'm under the impression that Windows sets up the segement registers to create a flat 32 or 64 bit virtual address space, and that page mode is used to translate the virtual addresses into physical addresses. As mentioned before, the segment registers are are also used to transfer data between tasks or dlls. The only table in the cpu is the translation look aside buffer (cache).

http://en.wikipedia.org/wiki/Page_table

http://en.wikipedia.org/wiki/Transla...okaside_buffer

Thanks. Can't pages be used to share memory (isn't that what you do to transfer data between tasks, creating a shared memory area by having your segment or page table for two different processes correspond to the same physical memory location)?

 

[rcgldr]

a segment register holds the physical address of the first segment in a segment table

If paging (virtual memory) is enabled, than almost all addresses will be virtual until they go through the page table lookup process.

So you shouldn't have to worry about segments not being large enough. So the code segment can be as large as the linker/compiler says it needs to be, the data segment can be as large as the linker/compiler says it needs to be, etc.

In windows, all these segments end up mapped into the same virtual address space, with unique addresses for code, data, stack, ...

segments used to transfer data between tasks or dlls

Can't pages be used to share memory (isn't that what you do to transfer data between tasks, creating a shared memory area by having your segment or page table for two different processes correspond to the same physical memory location)?

Shared memory is a different issue. I'm talking about transferring data from one task's virtual address space to another task's virtual address space, the addresses in this case are not unique, and the transfer requires setting up segments to transfer data between two different physical addresses.

Shared memory between tasks is another issue, because setting up inter task communication is awkward in windows. One method is for one task to pass information via command line parameters when invoking a second task, where the command line parameters are the first task's process handle value and some of that first task's handle values to be used by the second task for DuplicateHandle() to be able to access stuff from the first task (named handles can also be used). Multi-threading is easier because all the threads share the same virtual address space. Dlls are a special case in windows because they use the calling task's context, yet also have the ability to access their own local address space.