COSC 4348, Systems Programming - Exam Review

iSearchNotes is a FREE service that allows College Students to
Search and Share Class Notes.

Vote Up
Vote Down
By: CoryMathews 123
May 4, 2009 | Computer Science - Ajay Katangur
Save Notes for Word

Many of these bullets are from

  • Outline the major the differences between threads and processes
    • We can think of a thread as basically a lightweight process. 
    • Processes have:
      • a virtual address space which holds the process image.
      • protected access to processors, other processes, files, and I/O resources.
    • Threads have:
      • An execution state (running, ready, etc.)
      • Saves thread context when not running
      • An execution stack and some per-thread static storage for local variables
      • Access to the memory address space and resources of its process
  • What are the advantages of threads compared to processes?
    • Threads take:
      • Less time to create a new thread than a process, because the newly created thread uses the current process address space.
      • Less time to terminate a thread than a process.
      • Less time to switch between two threads within the same process, partly because the newly created thread uses the current process address space.
      • Less communication overheads -- communicating between the threads of one process is simple because the threads share everything: address space, in particular. So, data produced by one thread is immediately available to all the other threads.
  • What are the benefits that can be achieved by multithreading your code?
    • Improve application responsiveness -- Any program in which many activities are not dependent upon each other can be redesigned so that each activity is defined as a thread. For example, the user of a multithreaded GUI does not have to wait for one activity to complete before starting another.
    • Use multiprocessors more efficiently -- Typically, applications that express concurrency requirements with threads need not take into account the number of available processors. The performance of the application improves transparently with additional processors. Numerical algorithms and applications with a high degree of parallelism, such as matrix multiplications, can run much faster when implemented with threads on a multiprocessor.
    • Improve program structure -- Many programs are more efficiently structured as multiple independent or semi-independent units of execution instead of as a single, monolithic thread. Multithreaded programs can be more adaptive to variations in user demands than single threaded programs.
    • Use fewer system resources -- Programs that use two or more processes that access common data through shared memory are applying more than one thread of control. However, each process has a full address space and operating systems state. The cost of creating and maintaining this large amount of state information makes each process much more expensive than a thread in both time and space. In addition, the inherent separation between processes can require a major effort by the programmer to communicate between the threads in different processes, or to synchronize their actions.
  • What are the advantages and disadvantages of User-level threads?
    • Advantages:
      • Thread switching does not involve the kernel -- no mode switching
      • Scheduling can be application specific -- choose the best algorithm.
      • ULTs can run on any OS -- Only needs a thread library
    • Disadvantages:
      • Most system calls are blocking and the kernel blocks processes -- So all threads within the process will be blocked
      • The kernel can only assign processes to processors -- Two threads within the same process cannot run simultaneously on two processors
  • What are the advantages and disadvantages of Kernel-level threads?
    • Advantages
      • the kernel can simultaneously schedule many threads of the same process on many processors blocking is done on a thread level
      • kernel routines can be multithreaded
    • Disadvantages:
      • thread switching within the same process involves the kernel, e.g if we have 2 mode switches per thread switch this results in a significant slow down.

  • How can you combine User-level threads and Kernel-level to achieve better performance?
    • Thread creation done in the user space
    • Bulk of scheduling and synchronization of threads done in the user space
    • The programmer may adjust the number of KLTs
    • Process includes the user's address space, stack, and process control block
    • User-level threads (threads library) invisible to the OS are the interface for application parallelism
    • Kernel threads the unit that can be dispatched on a processor
    • Lightweight processes (LWP) each LWP supports one or more ULTs and maps to exactly one KLT
    • Threads

  • You need to know about the various functions used in conjunction with threads. These are discussed in the class.
    • pthread_create() to add a new thread of control to the current process.
      • int pthread_create(pthread\_t *tid, const pthread\_attr\_t *tattr, void*(*start_routine)(void *), void *arg);
        • start_routine is the function with which the new thread begins execution. When start_routine returns, the thread exits with the exit status set to the value returned by start_routine.
        • When pthread_create is successful, the ID of the thread created is stored in the location referred to as tid.
        • Creating a thread using a NULL attribute argument has the same effect as using a default attribute; both create a default thread. When tattr is initialized, it acquires the default behavior.
    • pthread_join function to wait for a thread to terminate.
      • int pthread_join(thread_t tid, void **status);
        • The pthread_join() function blocks the calling thread until the specified thread terminates. The specified thread must be in the current process and must not be detached. When status is not NULL, it points to a location that is set to the exit status of the terminated thread when pthread_join() returns successfully. Multiple threads cannot wait for the same thread to terminate. If they try to, one thread returns successfully and the others fail with an error of ESRCH. After pthread_join() returns, any stack storage associated with the thread can be reclaimed by the application.
        • The pthread_join() routine takes two arguments, giving you some flexibility in its use. When you want the caller to wait until a specific thread terminates, supply that thread's ID as the first argument. If you are interested in the exit code of the defunct thread, supply the address of an area to receive it. Remember that pthread_join() works only for target threads that are nondetached. When there is no reason to synchronize with the termination of a particular thread, then that thread should be detached. Think of a detached thread as being the thread you use in most instances and reserve nondetached threads for only those situations that require them.
    • pthread_detach() is an alternative to pthread_join() to reclaim storage for a thread that is created with a detachstate attribute set to PTHREAD_CREATE_JOINABLE.
      • int pthread_detach(thread_t tid);
        • pthread_detach() returns a zero when it completes successfully. Any other returned value indicates that an error occurred. When any of the following conditions are detected, pthread_detach() fails and returns the an error value.
    • pthread_keycreate() is used to allocate a key that is used to identify thread-specific data in a process.
      • int pthread_key_create(pthread_key_t *key, void (*destructor) (void *));
      • When pthread_keycreate() returns successfully, the allocated key is stored in the location pointed to by key. The caller must ensure that the storage and access to this key are properly synchronized. An optional destructor function, destructor, can be used to free stale storage. When a key has a non-NULL destructor function and the thread has a non-NULL value associated with that key, the destructor function is called with the current associated value when the thread exits. The order in which the destructor functions are called is unspecified.
      • pthread_keycreate() returns zero after completing successfully. Any other returned value indicates that an error occurred. When any of the following conditions occur, pthread_keycreate() fails and returns an error value.
    • pthread_keydelete() is used to destroy an existing thread-specific data key.
      • int pthread_key_delete(pthread_key_t key);
        • pthread_keydelete() returns zero after completing successfully. Any other returned value indicates that an error occurred. When the following condition occurs, pthread_keycreate() fails and returns the corresponding value.
    • pthread_setspecific() is used to set the thread-specific binding to the specified thread-specific data key
      • int pthread_setspecific(pthread_key_t key, const void *value);
        • pthread_setspecific() returns zero after completing successfully. Any other returned value indicates that an error occurred. When any of the following conditions occur, pthread_setspecific() fails and returns an error value.
        • pthread_setspecific() does not free its storage. If a new binding is set, the existing binding must be freed; otherwise, a memory leak can occur.
    • pthread_getspecific() to get the calling thread's binding for key, and store it in the location pointed to by value
      • int pthread_getspecific(pthread_key_t key);
    • pthread_self() can be called to return the ID of the calling thread
      • pthread_t pthread_self(void);
    • ...
  • Look at the sample programs available on the course website (Chapter 6 – Threads)
  • What are Mutexes?
    • Mutexes are used to prevent data inconsistencies due to race conditions. A race condition often occurs when two or more threads need to perform operations on the same memory area, but the results of computations depends on the order in which these operations are performed. Mutexes are used for serializing shared resources. Anytime a global resource is accessed by more than one thread the resource should have a Mutex associated with it. One can apply a mutex to protect a segment of memory ("critical region") from other threads. Mutexes can be applied only to threads in a single process and do not work between processes as do semaphores. 
  • What are Condition Variables?
    • Condition variables provide yet another way for threads to synchronize. While mutexes implement synchronization by controlling thread access to data, condition variables allow threads to synchronize based upon the actual value of data. Without condition variables, the programmer would need to have threads continually polling (possibly in a critical section), to check if the condition is met. This can be very resource consuming since the thread would be continuously busy in this activity. A condition variable is a way to achieve the same goal without polling.
    • A condition variable is a variable of type pthread_cond_t and is used with the appropriate functions for waiting and later, process continuation. The condition variable mechanism allows threads to suspend execution and relinquish the processor until some condition is true. A condition variable must always be associated with a mutex to avoid a race condition created by one thread preparing to wait and another thread which may signal the condition before the first thread actually waits on it resulting in a deadlock. The thread will be perpetually waiting for a signal that is never sent. Any mutex can be used, there is no explicit link between the mutex and the condition variable.

  • You need to know about the various functions used in conjunction with Mutexes and Condition variables. These are discussed in the class.
    • pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
      int counter=0;

      void functionC()
        pthread_mutex_lock( &mutex1 );
        pthread_mutex_unlock( &mutex1 );
    • pthread_cond_init
    • pthread_cond_destroy
    • pthread_cond_wait
    • pthread_cond_timedwait
    • pthread_cond_signal
    • pthread_cond_broadcast
  • What is a race condition?
    • While the code may appear on the screen in the order you wish the code to execute, threads are scheduled by the operating system and are executed at random. It cannot be assumed that threads are executed in the order they are created. They may also execute at different speeds. When threads are executing (racing to complete) they may give unexpected results (race condition). Mutexes and joins must be utilized to achieve a predictable execution order and outcome.
  • What is a Mutex deadlock? How can it occur?
    • Mutex Deadlock: This condition occurs when a mutex is applied but then not "unlocked". This causes program execution to halt indefinitely. It can also be caused by poor application of mutexes or joins. Be careful when applying two or more mutexes to a section of code. If the first pthread_mutex_lock is applied and the second pthread_mutex_lock fails due to another thread applying a mutex, the first mutex may eventually lock all other threads from accessing data including the thread which holds the second mutex. The threads may wait indefinitely for the resource to become free causing a deadlock. It is best to test and if failure occurs, free the resources and stall before retrying.
  • What is a Condition Variable deadlock? How can it occur?
    • The logic conditions (the "if" and "while" statements) must be chosen to insure that the "signal" is executed if the "wait" is ever processed.
  • Look at the sample programs available on the course website (Chapter 7 – Threads: Mutexes, Condition Variables)
  • What are the differences between system calls and standard I/0 calls?
    • Standard I/O uses function libraries to help speed up the I/O by using buffers automatically
  • Look at the sample programs available on the course website (Chapter 8 – Cat and its variants, Buffering)
  • What is an atomic action?
    • An atomic action is a sequence of actions that gets executed as a whole, uninterrupted by the CPU. They are important in systems programming as they can make guarantees that would be impossible to make otherwise.
  • What is the function of the setuid bit?
    • to set the user id of the program being executed to that of the owner of the executable file.
  • You need to know about the functions used in Chapter 9 – Log Files.
  • Look at the sample programs available on the course website (Chapter 9 – Log Files)
  • You need to know about the important aspects such as process and memory management, file systems, device control, networking, network interfaces, character devices, block devices,printk, insmod, rmmod etc.
    • Process management: The kernel is in charge of creating and destroying processes and handling their connection to the outside world (input and output).
    • Memory management: The kernel builds up a virtual addressing space for any and all processes on top of the limited available resources. The different parts of the kernel interact with the memory management subsystem through a set of function calls, ranging from the simple malloc/free pair to much more exotic functionalities.
    • Filesystems: The kernel builds a structured filesystem on top of unstructured hardware, and the resulting file abstraction is heavily used throughout the whole system. In addition, Linux supports multiple filesystem types, that is, different ways of organizing data on the physical medium.
    • Device control: Almost every system operation eventually maps to a physical device. With the exception of the processor, memory, and a very few other entities, any and all device control operations are performed by code that is specific to the device being addressed. That code is called a device driver. The kernel must have embedded in it a device driver for every peripheral present on a system, from the hard drive to the keyboard and the tape streamer.
    • Networking: The system is in charge of delivering data packets across program and network interfaces, and it must control the execution of programs according to their network activity. Additionally, all the routing and address resolution issues are implemented within the kernel.
    • Character devices: A character (char) device is one that can be accessed as a stream of bytes (like a file); a char driver is in charge of implementing this behavior. Such a driver usually implements at least the open, close, read, and write system calls. The text console (/dev/console) and the serial ports (/dev/ttyS0 and friends) are examples of char devices. The only relevant difference between a char device and a regular file is that you can always move back and forth in the regular file, whereas most char devices are just data channels, which you can only access sequentially.
    • Block devices: Like char devices, block devices are accessed by filesystem nodes in the /dev directory. A block device is something that can host a filesystem, such as a disk. In most UNIX systems, a block device can be accessed only as multiples of a block, where a block is usually one kilobyte of data or another power of 2. Like a char device, each block device is accessed through a filesystem node and the difference between them is transparent to the user.
    • Network interfaces: Any network transaction is made through an interface, that is, a device that is able to exchange data with other hosts. Usually, an interface is a hardware device, but it might also be a pure software device, like the loopback interface. A network interface is in charge of sending and receiving data packets, driven by the network subsystem of the kernel.
    • printk function is defined in the Linux kernel and behaves similarly to the standard C library function printf.
    • insmod after loaded, the module is linked to the kernel, thus printk can be called
  • You need to understand the kernel module’s functionalities, concurrency in the kernel, hardware caching, memory barrier etc.
    • One way in which device driver programming differs greatly from (most) application programming is the issue of concurrency. An application typically runs sequentially, from the beginning to the end, without any need to worry about what else might be happening to change its environment. Kernel code does not run in such a simple world and must be written with the idea that many things can be happening at once. There are a few sources of concurrency in kernel programming. Naturally, Linux systems run multiple processes, more than one of which can be trying to use your driver at the same time. Most devices are capable of interrupting the processor; interrupt handlers run asynchronously and can be invoked at the same time that your driver is trying to do something else.
    • The problem with hardware caching is the easiest to face: the underlying hardware is already configured (either automatically or by Linux initialization code) to disable any hardware cache when accessing I/O regions (whether they are memory or port regions). The solution to compiler optimization and hardware reordering is to place a memory barrier between operations that must be visible to the hardware (or to another processor) in a particular order. Linux provides four macros to cover all possible ordering needs.
      • void barrier(void)
        • In #include <linux/kernel.h>
          This function tells the compiler to insert a memory barrier, but has no effect on the hardware.
          Compiled code will store to memory all values that are currently modified and resident in CPU
          registers, and will reread them later when they are needed.
      • void rmb(void);
        void wmb(void);
        void mb(void);

        • In #include <asm/system.h>
        • These functions insert hardware memory barriers in the compiled instruction flow; their actual instantiation is platform dependent. An rmb (read memory barrier) guarantees that any reads appearing before the barrier are completed prior to the execution of any subsequent read. wmb guarantees ordering in write operations, and the mbinstruction guarantees both. Each of these functions is a superset of barrier.
Enjoyed These Notes?
Your support will help spread the extreme awesomeness that is iSearchNotes!


You must login to comment. on Facebook

Login - Register