CST334 - Week 6

CST334 – Operating Systems - Week 6

This week, we are learning about semaphores to solve problems in concurrency. The semaphores are an alternative technique to the locks and condition variables using the two routines, sem_wait() and sem_post(). A semaphore initial value determines the routines' behavior (i.e., sem_init(&s, 0, 1;) indicates that the initial value of the semaphore is 1, and 0 indicates it is shared among other threads. sem_wait() decrement the value of semaphore when the value is above 0, and return. When the value is 0 or negative, sem_wait() simply waits till the value is above 0 again. sem_post() increment the value of semaphore and return. The negative value of semaphore is the count of the waiting threads.

The use scenarios for semaphore: -

1- Used as a lock (binary semaphore)
In this case, the semaphore is initialized as value 1, and the critical section is surrounded by sem_wait() and sem_post().

2- Ordering events (similar to condition variables)
In this case, a thread is waiting for a condition to come true. While another thread is working on the condition, a signal will wake it once the condition is satisfied. To accomplish this, the semaphore is initialized to the value of zero, the ordering thread calls sem_wait(), and the delivery thread calls sem_post().

3- The Producer/Consumer (Bounded Buffer) – one p and one c
The idea is that the producer waits for an empty buffer to fill it, and the consumer waits for a full buffer to use it. Again, the initial value of the semaphore determines the outcome. In this case, there are two semaphores initialized for full and empty to 0,1, respectively. If a consumer runs first calling a sem_wait(&full), the value becomes -1 and waits for a sem_post() to be called. On the other hand, the producer is calling sem wait(&empty) on an initial value of 1, which is decremented to zero and makes an entry to the buffer. Then sem_post(&full) is changed to 0. Now, the consumer is awake. The producer will continue to run, or the consumer will run to realize a full buffer and finish the program.

4- The Producer/Consumer (Bounded Buffer) – multi producers and consumers                                    For multiple producers and consumers, a mutual exclusion must be implemented to avoid race condition and protect critical section. The use of binary semaphore surrounding the producer and consumer with sem_wait(&mutex), sem_post (&mutex), will result in a deadlock. Instead of calling sem_wait(&mutex) and sem_post(&mutex) before sem_wait() is called on full and empty, the lock is lowered as follow.

sem_wait(&empty);

sem_wait(&mutex);         //lock

put(i);

sem_post(&mutex);         //unlock

sem_post(&full);

 

Concurrency Problems

1- Atomicity-Violation Bugs: the absence of proper synchronization leads to this problem. When resources are shared between threads, the use of mutexes lock/unlock ensures that access to critical sections is done without a chance of interruption.

2- Order-Violation Bugs: This is a non-deadlock bug caused by disordered memory access, which could result in unpredictable behavior. The solution to these types of bugs is to use conditional variables or semaphores to enforce ordering.

3- Deadlock Bugs: The problem occurs when threads hold locks and depend on each other for lock release. Circular dependencies may occur in large code if locking is not designed carefully. Four conditions require prevention to avoid deadlocks: mutual exclusion, hold-and-wait, no preemption, and circular wait.

CST334 - Week 5

 

CST334 – Operating Systems - Week 5

This week in Operating Systems, we are focusing on an introduction to concurrency. The use of threads improves the processing speed when used with a multi-processor system. Program blocking progress is also avoided using threads by utilizing the CPU for other activities while waiting on I/O request to complete. Threads share the same address space but will have multiple program counters and separate calls to the stack. To create threads, the function pthread create() Is used in conjunction with pthread join() or procedure call.

Locks ensure the atomic execution of instructions by protecting critical sections. The basic routines for locks using mutex(mutual exclusion) in pthreads library are:

int pthread_mutex_lock(pthread_mutex_t *mutex);

   int pthread_mutex_unlock(pthread_mutex_t *mutex);

   int pthread_mutex_trylock(pthread_mutex_t *mutex);

      int pthread_mutex_timedlock(pthread_mutex_t *mutex,

struct timespec *abs_timeout);

 

** Example of wait call with condition, singling is done from the calling thread.

Pthread_mutex_lock(&lock);

while (ready == 0)

Pthread_cond_wait(&cond, &lock);

Pthread_mutex_unlock(&lock);

The purpose of the wait call is to put the thread to sleep and release the lock once the condition is lifted and the global variable ready values are set to a non-zero value. Locks are evaluated for protecting the critical sections, fairness while voiding thread starvation, and reasonable time overheads for better performance.

A condition variable is used to allow parent thread to wait on the child to finish execution or meet a condition. The advantageous of using condition variable over spin is efficiency. The condition variable does not waste the CPU time and signaling  - signal() – the waiting thread to wake up once a condition is satisfied.

CST334 - Week 4

 

CST334 – Operating Systems - Week 4

What an exciting week to learn about paging. This is a great topic to dive into space management for memory virtualization by paging. The concept divides memory into equal, fixed spaces called pages and translates the virtual address through a stored mechanism for translation. A page table is the data structure where address translation data is stored for mapping virtual page numbers to physical frame numbers (PFN). The page table comes in a simple form of a linear page table as an array. The different types of bits are the valid bits to validate the address translation and protection bits for read, write, and execution permissions. There's also a presence bit that determines the location of the page (physical memory or disk), a dirty bit that indicates if a page has been modified, and a reference bit to track access to pages.

For faster paging, a hardware cache is used first to look up the value for address translation. The translation-lookaside buffer, or TLB, is used in the MMU to reference virtual memory without needing access to the page table. A TLB hit occurs when a relevant translation is held in the TLB, resulting in a successful translation. A TLB miss means that the CPU could not find the translation in the TLB, so the hardware accesses the page table on a valid bit. TLB misses are handled by CISC (hardware-managed TLBs) or RISC (software-managed TLB). RISC utilizes a trap handler with a return different from a trap caused by a system call. The return from a TLB miss-handling trap resumes with the same instructions that caused the trap.

The replacement policy of the OS is designed to evict pages to allow fresh and most-used ones to have room. Since any cache misses cost access to the slower disk, choosing a smart policy is crucial to lower slow performance. Three types of cache misses are compulsory (when the cache is empty), capacity (when the cache does not have space), and conflict (due to restrictions on item placement in hardware cache). Optimal, FIFO, LRU, LFU algorithms, and Random are examples of replacement policies.

CST334 - Week 3

 

CST334 – Operating Systems - Week 3

In this week, we are learning about memory in Unix. The two types of memory are stack memory and heap memory. Each type of memory has its own properties. For example, the stack memory is deallocated after the return statement; however, the heap is controlled by the programmer.

Example int *ptr = (int *) malloc(sizeof(int)).

Note: Passing the desired size depends on the declared variable’s data type. This is because sizeof() operator calculation corresponds to the type of data. For example, a terminated null character ‘’\0’ in a string requires adding 1 when strlen() function is used.

The call of free() frees the memory allocated to the heap.

Common issues

• Not allocating memory – some functions allocate memory automatically
• Allocate the wrong size or coming short of the size
• Not initializing memory or initializing memory incorrectly
• Memory leak when memory freed correctly.
• Freeing memory too soon or more than once
• Calling free() incorrectly by passing the wrong pointer

Happy 4^th of July!

The hardware-based address translation provides memory access by translating the virtual address to a physical address with the help of the OS. In dynamic relocation or base and bounds, two registers are defining the boundaries of the physical memory. Each process will hold two values, one for the base and another for the bounds while the program is compiled to start at address zero. The OS places the program at a physical address by setting the value of the base then adding it to the virtual address.

The disadvantage of the base and bounds method is the generated wasted physical space after address translation. The segmentation technique helps reduce the unused free memory between the stack and the heap. The OS places different segments of the address space in the physical memory. Also, sharing segments is available to allocate memory efficiently with fewer wasted holes among processes. In the case of context switching, registers are saved and restored to run the switched-to process, preserving the virtual address.

CST334 - Week 2

 

CST334 – Operating Systems - Week 2

In this module, the discussion focused on processes and how OS manages them. The process is the program's state at an instance during execution, identified by PID. A processor contains the memory status for static and dynamic allocations, CPU registers, and file descriptors (standard input, output, and error). The first step to running a program is loading its code by invoking its main method. The process abstraction provides an illusion of endless resources, achieved by the process control block CPU virtualization and the scheduler. For instance, multiple processes will run and stop using CPU Time Sharing supported by mostly all OSes. The OS manages the running processes via the CPU scheduler. Policies determine which process to run at a point in time, and the mechanism allows the switching of processes status.

In Unix systems, processes are created using fork() and exec() system calls. A fork() function will create a copy of the parent process with a different address space called a child. I also learned that a Unix shell means that a code could be run between the call of fork() and exec(), allowing an additional layer of manipulation to run a program. The use of wait() results in a deterministic outcome since the parent must wait for the termination of the child. Additionally, exec() frees the child to execute a new program.

The concept of CPU scheduling is not only interesting but also familiar.

• FIFO: First In, First Out. Works great if all jobs have almost equal run time. Otherwise, the convoy effect greatly impacts the average turnaround time.

• Shortest Job First (SJF): designed to allow the shortest run time job first, improving the convoy effect issue if shortest jobs arrive before the longer ones.

• Shortest Time-to-Completion First (STCF): Longer jobs are preempted once a short job arrives to resume after the completion of the short run time. STCF adds preemption to SJF, therefore, improving the overall average turnaround time.

• Round Robin: great for response time. The time-slicing or RR will interrupt by the period value of time slice while considering the cost of context-switch.

Multi-Level Feedback Queue (MLFQ)

Jobs will run based on the priority set by the schedules in different queues. If more than one job is set to the same priority, the scheduling uses Round Robin between these jobs.  A new job enters the system with high priority until the allotment period is over, in which case the priority is reduced. In the case the job alerts the CPU for activities like I/O waiting on a user’s input, the job remains a high priority. The idea is to get a sense of the job length so that the OS can position the job in the appropriate queue. If the job is short, a queue with high priority allows the job to finish; however, if the job takes longer, the job is lowered to the next lower-priority queue.

Some Problems with MLFQ

• Starvation: When long-running jobs don’t receive CPU time due to many high-priority jobs, a priority boost solves this issue, which allows all jobs to be moved into a topmost priority after a period of time.
• Game the scheduler: This problem, which involves triggering the CPU with conditions to continue preserving a higher share of the CPU, can significantly disrupt the scheduling process.