StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
2908346
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
1
CommunityOwnedDate
CreationDate
2010-05-25T20:37:48.327
FavoriteCount
0
LastActivityDate
2010-05-25T20:37:48.327
LastEditDate
2017-05-23T12:01:15.033
LastEditorUserId
-1
OwnerUserId
206367
ParentId
2907004
PostTypeId
2
Score
3
ViewCount
0
LastEditorDisplayName
text
Body
Ok, to answer this question please refer to my <a href="https://stackoverflow.com/questions/2293581/does-linux-time-division-processes-or-threads/2293724#2293724">answer</a> to another question here on SO, in relation to 'Does Linux time division processes or threads?', let's follow on from that structure of an imaginary kernel here using x86 processor and C code...I have amended this structure to take into account of semaphores <pre> struct regs{ int eax, ebx, ecx, edx, es, ds, gs, fs, cs, ip, flags; struct tss *task_sel; } struct mem_loc{ int *phys_mem_begin; int *phys_mem_end; int *semaphores; } struct thread{ struct regs *regs; struct mem_loc *memlocTracker; int parent_id; struct thread *next; } struct task{ struct regs *regs; struct mem_loc *task_mem; int *filehandles; int priority; int *num_threads; int quantum; int duration; int start_time, end_time; int parent_id; struct thread *task_thread; /* ... */ struct task *next; } struct queue_ready{ struct task *task_id; struct queue_ready *next; } </pre> There, I think that looks better, right, in relation to following on from my previous answer linked above, let's see what happens when there's queues involved, now, look at this <code>queue_ready</code> structure, now, supposing there's a task in the that structure as set up by the kernel, a linked list of <code>queue_ready</code> to be more precise, this is based on the <code>priority</code> field of the <code>task</code> structure itself, and the priority is 1 for example, to be ready to executed. Let's look at an imaginary scheduler based on C, as shown below, ok, it may be crappy and vulnerable to nit-picky, but put that aside to concentrate on the aspect of the question... <pre> static void scheduler(void){ struct queue_ready *rdy_sched; while(1){ for (rdy_sched = head_queue_ready; rdy_sched != NULL; rdy_sched = rdy_sched->next){ if (time >= rdy_sched->task_id->start_time + rdy_sched->task_id->quantum){ save_cpu_task_state(&task_reg->regs); save_mem_task_state(&rdy_sched->task_id->task_mem); }else{ struct regs *task_reg = rdy_sched->task_id->regs; struct mem_loc *mem_task = rdy_sched->task_id->task_mem; load_cpu_task_state(task_reg); load_mem_task_state(mem_task); jmp_and_exec_cpu_task(task_reg->cs, task_reg->ip); save_cpu_task_state(&rdy_sched->task_id->regs); if (rdy_sched->task_id->num_threads > 0){ struct thread *threads = rdy_sched->task_id->task_thread; while (threads->next != NULL){ struct regs *thread_reg = threads->regs; load_cpu_thread_state(thread_reg); if (threads->memlocTracker->semaphores){ /* House keeping in relation to semaphores */ lock_memory(threads->memlocTracker); jmp_and_exec_cpu_thread(thread_reg->cs, thread_reg->ip); save_cpu_thread_state(&thread->regs); unlock_memory(threads->memlocTracker); }else{ jmp_and_exec_cpu_thread(thread_reg->cs, thread_reg->ip); save_cpu_thread_state(&thread->regs); } } } } } } } </pre> The kernel's scheduler looks overly complex, but it isn't really, the only omission I have left out in the code is the priorities...that can be ignored now for the discussion of the OP's question. Let's break this scheduler function <code>scheduler</code> down...but first a quick peek and explanation of what functions are used within the <code>scheduler</code> function: <ul> <li>'load_cpu_task_state' and 'load_cpu_thread_state' - this loads the state of the CPU registers, for brevity, they are for task and thread respectively.</li> <li>'load_mem_task_state' and 'save_mem_task_state' - this loads and save, respectively, the memory state, perhaps to/from a page on disk specified by the <code>phys_mem_begin</code> and <code>phys_mem_end</code> fields of the <code>mem_loc</code> structure for the said task. For brevity, this will load all memory owned by the said task, including threads.</li> <li>'jmp_and_exec_cpu_task' and 'jmp_and_exec_cpu_task' - this causes the kernel to issue the magic in jumping to the specified <code>cs</code> and <code>ip</code> registers of the said task's <code>reg</code> structure, again same for the thread respectively.</li> <li>'save_cpu_task_state' and 'save_cpu_thread_state' - this causes the kernel to save the state of CPU registers for both task and thread respectively.</li> <li>'lock_memory' and 'unlock_memory' - this is for the locking of the memory region using the semaphores which comes into play shortly...</li> </ul> Now, <code>scheduler</code> runs forever, and iterates over the linked list of tasks, the check is required to see if the task has run for a period and exceeded the <code>quantum</code> amount, for example, 20ms. Then it saves the cpu state, and state of memory, (perhaps saved to paging file on disk), ready to go on to the next task in the list. If there is still time left, it loads the task's CPU registers and loads up the memory (perhaps from a page), and jumps to where the last instruction pointer and code segment was (ip and cs respectively) and the task resumes. If the said task has threads, it will iterate over the linked-list of threads, loading the CPU registers, and jumping into the code to resume thread execution then save the CPU registers. Now, this is where things gets a bit hairy, especially in this toy OS, how to manage semaphores! uh huh, looking like a big headache looming over the OS developer's head.... I would imagine if the section of memory is locked, the <code>semaphores</code> would be non NULL, and would have been acquired by the runtime manager in user-land code that requested the semaphore, it would lock the memory to prevent a thread trampling the data, and jump into the code for the said thread and would unlock it when that thread's duration is completed and saves that state of thread's CPU registers... Conclusion: This is my conclusion based on this, as for facts to back me up, I cannot, as this theory has been exhaustively lectured at, examined under the microscope in countless books, ranging from a University in the US, all the way around to the University in New Zealand, this is from my observations and my understanding, as you can see from this code, the complexity and the burden placed on the developer in coding this, not alone that, the constraints imposed, design decisions - both hardware and software. Managing semaphores in this context is far more complicated, to answer, if there was more queues available, like I have strived to keep it to one queue <code>queue_ready</code>, the cost factor in terms of memory usage, disk usage and above all time usage, grows as the kernel would have to keep track of those mitigating factors that come into play, another equally important factor is how much priorities is there going to be, so having a ready queue for different semaphores in my opinion is not a viable and feasible option.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POPros and cons with a ready-queue for diffrent semaphores in a mini OS
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USt0mm13b
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POPros and cons with a ready-queue for diffrent semaphores in a mini OS
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. CONicely done! The OS we had at our lab session used an array which contained all thread info and stack pointers, having a linked list would be more efficient in moving/removing tasks and i guess most systems do but our toy OS was just for understanding the basics.
 singulars
 PostPostId
 PO
 UserUserId
 USJoelmob

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.